Zipf [5] 2 5 [6] [7][11] ICN [12] LIRS/CLOCK-Pro [13], [14] CLOCK-Pro Using Switching Hash-table (CUSH) (3. )4. CUSH ICN 2. CPU [15] [17] LRU [1], [18

Size: px

Start display at page:

Download "Zipf [5] 2 5 [6] [7][11] ICN [12] LIRS/CLOCK-Pro [13], [14] CLOCK-Pro Using Switching Hash-table (CUSH) (3. )4. CUSH ICN 2. CPU [15] [17] LRU [1], [18"

しげじろうあいきょう
5 years ago
Views:

1 CLOCK-Pro (ICN) CLOCK-Pro ICN CLOCK-Pro Using Switching Hash-table (CUSH) (ICN) (CCN) A Proposal and Evaluation of Feasible Cache Replacement Policy for ICN Abstract based on CLOCK-Pro Atsushi OOKA, Eum SUYONG, Shingo ATA, and Masayuki MURATA Graduate School of Information Science and Technology, Osaka University 1-5 Yamadaoka, Suita, Osaka, , Japan Graduate School of Engineering, Osaka City University Sugimoto, Sumiyoshi-ku, Osaka-shi, Osaka , Japan {a-ooka,suyong,murata}@ist.osaka-u.ac.jp, ata@info.eng.osaka-cu.ac.jp Information-centric networking (ICN) requires an innovative cache replacement algorithm with performance far superior to simple policies such as FIFO and computational and memory overheads that are low enough to run on ICN router s hardware. We propose CLOCK-Pro Using Switching Hash-tables (CUSH) to satisfies the requirements and evaluated it, which reveals that CUSH can achieve cache hits against the traces that simple conventional algorithms cannot cause any hits. Key words Information-Centric Networking, Content-Centric Networking, Caching, Cache Replacement Policy 1. Information-Centric Networking (ICN) ICN (where) ICN IP name (what) NDN [1]CCNx [2]PURSUIT [3]SAIL [4]Green ICN ICN clean-slate NDN CCNx [1], [2] NDN MTU name YouTube ccn://youtube/video/a.mp4/s2 name 1

2 Zipf [5] 2 5 [6] [7][11] ICN [12] LIRS/CLOCK-Pro [13], [14] CLOCK-Pro Using Switching Hash-table (CUSH) (3. )4. CUSH ICN 2. CPU [15] [17] LRU [1], [18] CLOCK 2 n CLOCK R R Random Random LRU LRU [1]First-In, First Out (FIFO) 1 (FIFO tail) LRU LRU friendly LRU LRU stack Least Frequently Used (LFU) (frequency) Adaptive Replacement Cache (ARC) [19] LRU LFU ARC 2 LRU L 1 L (ghost cache) Low Inter-reference Recency Set (LIRS) [13] (Inter-Reference Recency; IRR) LRU (recency) LIRS IRR 2 IRR hot cold cold LRU cold LRU ARC 2

3 loop ( ) LFU hot ( 4n [13]) LRU LRU ARC 2. 3 CLOCK LRU CLOCK R R = 1 R = CLOCK CLOCK LRU Clock with Adaptive Replacement (CAR) [2] ARC CLOCK LRU CLOCK MRU operation ARC CLOCK LRU [12] CLOCK-Pro [14] LIRS CLOCK R 2 1 hot cold 1 test flag LIRS stack pruning cold () CLOCK 3 cold hot LIRS hot cold LRU-friendly ( n ) loop LIRS 3. CUSH ICN CLOCK-Pro (3. 1 ) CUSH CUSH (3. 2 ) 3. 3 CUSH CLOCK-Pro 3. 1 ( ) scan loop CLOCK-Pro ICN ( ) scanloopcorrelated-referencefickle-interest 4 1 scan: 1 LRU recency loop: scan recency frequency (LRULFUARC ) correlated-reference: 1 LFU frequency fickle-interest: correlated-reference frequency LFU LIRS hot 1 ARC 2 priority limited-frequency correlated-reference LFU loop LRU LFU 3

4 1: policies LRU, CLOCK LFU ARC, CAR LIRS CLOCK-Pro priority recency frequency limited-frequency IRR limited-irr scan loop loop correlated-reference fickle-interest CLOCK-Pro priority limited-irr loop LIRS CLOCK-Pro LIRS hot correlated-reference fickle-interest scan loop CLOCK-Pro scan scan 1 6 [6] CCNx NDN ICN scan scan loop Web OS 1 loop loop 1MB.7M loop correlated-reference fickleinterest SNS correlated-reference VoIP fickle-interest LIRS/CLOCK-Pro scan loop correlated-reference fickle-interest CLOCK-Pro scan loop Compact CAR scanfickle-interest [12] scan loop CLOCK-Pro loop fickle-interest 3. 2 CUSH CLOCK-Pro CLOCK-Pro CLOCK-Pro ICN CUSH CUSH CLOCK-Pro LIRS/CLOCK-Pro CLOCK-Pro LIRS IRR loop loop LRU CLOCK recency( ) 2 LIRS loop 4

5 interest: /A.mpg/s1 Lookup table KEY (name) (address) /A.mpg/s1 1 /A.mpg/s2 4 /A.mpg/s3 9 /X.jpg /B.mpg/s1 6 /B.mpg/s2 8 /B.mpg/s3 1 Cache Meta Circular buffer /Z.txt -1 [bit] log 2[bit] 1: CLOCK-Pro IRR( 2 ) loop IRR hot cold LIRS loop scan IRR cold scan CLOCK-Pro LIRS CLOCK LIRS IRR LRU stack pruning CLOCK-Pro LRU CLOCK loop CLOCK-Pro CLOCK 3 HAND cold HAND hot HAND test R hot/cold HAND test test 1 cold Chot H M R = 1 CLOCK-Pro HAND cold cold hot CLOCK R = 1 cold hot hot HAND hot hot cold cold test test hot cold test HAND test cold HAND test LIRS CLOCK CLOCK-Pro CLOCK-Pro ICN 3 loop loop CLOCK- Pro 2 loop loop CLOCK-Pro 1 CLOCK-Pro 5

Ideal (error-free ghost cache) Lookup table KEY (name) (address) Real (ghost cache without collision resolution) Lookup table KEY (name) (address) Circular buffer Cache [bit] Cache log 2 [bit] Hash

6 Ideal (error-free ghost cache) Lookup table KEY (name) (address) Real (ghost cache without collision resolution) Lookup table KEY (name) (address) Circular buffer Cache [bit] Cache log 2 [bit] Hash table Meta Address ((name)) (address) Meta [bit] log 2 [bit] cut down log 2 [bit] 2: CLOCK-Pro HAND cold HAND cold loop 1 Key-Value CLOCK-Pro n 2n (lookup table) (circular buffer) name L max[bit](name ) log 2n[bit] 2n(L max + log 2n)[bit] n(l max + log 2n)[bit] L max[bit] name ICN 1 ICN name 2 name 1 name L max [bit] name ICN CUSH CUSH CLOCK-Pro CUSH CLOCK-Pro CLOCK-Pro 2 ( 3 ) 1bit k loop 1 CUSH LIRS loop LIRS hot cold loop hot hot hot loop LIRS 6

7 CLOCK Pro Proposal Lookup table KEY (name) [bit] Cache (address) log 2 [bit] Cache Lookup table KEY (name) (address) Circular buffer 2 hands Circular buffer Cache [bit] log [bit] 3 hands Meta separate Meta fill alternately Hash table 1 Hash table 2 Hash table Address ((name)) (address) Address ((name)) (flag) Address ((name)) (flag) Meta [bit] [bit] log 2 [bit] 3: CLOCK-Pro LRU hot CUSH hot n h loop 2 correlated-reference hot CUSH 2 2 B 1B 2 B 1 n h /2 B 2 n h /2 B 1 B 1 loop B 1 B 2 CUSH HAND test 2 2bit HAND cold HAND hot 3 1bit 2bit 3. 3 CUSH 1,2,3,4 CUSH CLOCK A p A[p] c ()n, n h, n c cold hot m h, m c cold hot 2 B 1, B 2 B c B n B1, n B2 B 1 B 2 n hit x chunk chunk.r bit reference bit 1 chunk.h bit hot 1 hot 1 7

8 Algorithm 1 CUSH Replacement Algorithm 1: procedure CACHEREPLACEMENT(x) x is an accessed chunk. 2: if x A then cache hit 3: x.r-bit 1 4: UpdateHistory() 5: AdaptSmallIRR() 6: return 7: else if x B then ghost hit 8: UpdateHistory() 9: AdaptSmallIRR() 1: h true 11: if n = m then A is full. 12: Run HAND cold 13: if n h > m h then 14: Run HAND hot 15: end if 16: end if 17: else cache miss 18: if n < m then A is not full. 19: h (n h < m h ) 2: else A is full. 21: Run HAND cold 22: h (n h < m h & 2n c > m h ) 23: end if 24: end if 25: p an available address in A 26: A[p] x 27: if h then A[p].H-bit 1 28: end if 29: end procedure Algorithm 2 Algorithm for Adapting Parameters 1: procedure ADAPTLARGEIRR 2: m c max(m c max(m h /m c, 1), 1) 3: m h m m c 4: end procedure 5: 6: procedure ADAPTSMALLIRR 7: m h max(m h max(m c/(m h + 1), 1), ) 8: m c m m h 9: end procedure x R 1 ( 3 6) ( 7 15) ( 8 9)x hot h 1 ( 1) HAND cold hot n h m h HAND hot hot ( 11 16) ( 17 23) ( 18 19)hot n h m h hot hot loop ( 2 22)HAND cold hot Algorithm 3 Algorithms of Hand Movement 1: procedure RUN HAND cold 2: while (A[HAND cold ].H-bit= or A[HAND cold ].R-bit= 1) do 3: while n c = do 4: Run HAND hot 5: end while 6: if A[HAND cold ].R-bit= 1 then 7: A[HAND cold ].R-bit 8: A[HAND cold ].H-bit 1 9: end if 1: Move HAND cold forward 11: end while 12: Discard A[HAND cold ] and add it to B 13: if n b1 = c B then 14: SwitchHashTable() 15: end if 16: Move HAND cold forward 17: end procedure 18: 19: procedure RUN HAND hot 2: while (A[HAND hot ].H-bit= or A[HAND hot ].R-bit= 1) do 21: if A[HAND hot ].R-bit= 1 then 22: A[HAND hot ].R-bit 23: end if 24: if A[HAND hot ].H-bit= then 25: AdaptLargeIRR() 26: end if 27: Move HAND hot forward 28: end while 29: A[HAND hot ].H-bit 3: Move HAND hot forward 31: end procedure Algorithm 4 Algorithm for Updating Hash Tables 1: procedure UPDATEHISTORY 2: Increment n hit 3: if (n hit > Threshold() or n B = c B ) then 4: SwitchHashTable() 5: end if 6: end procedure 7: 8: procedure SWITCHHASHTABLE 9: AdaptLargeIRR() 1: Switch B If B = B 1 then B B 2 ; else B B 1. 11: Clear B Reset all bits in B. 12: n hit 13: end procedure 14: 15: function THRESHOLD 16: return max(n h /2, 1) 17: end function n h < m h cold n c ( hot m h cold ) hot ( ) ( 25 28) hot h 2 IRR hot/cold IRR LRU-friendly correlated-reference fickle-interest LRU/CLOCK 8

9 cold IRR scan loop scan loop loop hot IRR hot hot/cold m c m h 2 2 CLOCK-Pro CLOCK-Pro test m c CUSH test test CUSH CLOCK-Pro IRR IRR HAND hot cold CLOCK-Pro 1 test CLOCK-Pro CUSH ARC 3 2 (HAND cold HAND hot ) HAND cold R = cold ( 2 11) ( 12) hot R = 1 cold hot ( 6 8) cold HAND hot ( 3 5)cold ( 12 15) HAND hot 3 HAND hot R = hot ( 2 28) cold ( 29) R = 1 hot R = cold IRR CLOCK-Pro HAND hot test OFF m c 4 UpdateHistory n hit ( 2) ( 3 5) n hit n h /2(Threshold ( 15 17) ) SwitchHadhTable AdaptLargeIRR ( 9) CLOCK-Pro test m c ( 1) ( 11) ( 12) loop 4. CUSH CLOCK-Pro CUSH ( ) YouTube CUSH ( ) CUSH CUSH CLOCK CUSH CLOCK-Pro CUSH CLOCK-Pro CUSH scan loop Zipf ( ) CUSH CLOCK-Pro OPTFIFOCLOCK Compact CAR OPT ICN Random CLOCK LRU scan loop Compact CAR scan ARC CUSH scan CLOCK-Pro Compact CAR 2 9

10 OPT FIFO CLOCK Compact CAR CLCOK-Pro (real) CLOCK-Pro (ideal) (a) α =.8 (b) α = 1. (c) α = 1.2 4: OPT FIFO CLOCK OPT Compact CAR OPT CLCOK-Pro (real) CLOCK-Pro (ideal) CUSH-log (a) (b) Compact CAR (c) CLOCK-Pro 5: (α = 1.) loop Zipf α.8, 1., 1.2, 1.4 [21] 15B1.5KB6KB CUSH 4 () CLOCK-Pro n log 2n[bit] (CUSH-log) 2 CUSH-log CLOCK-Pro 4,5,6, ,7 5 loop scan 5(a) CUSH CLOCK 1 bit CUSH scan 5(b) scan Compact CAR loop Compact CAR CUSH 5(c) CLOCK-Pro 7 loop loop 7(a) CUSH loop 7(b) scan loop Compact CAR loop 7(a) 7(c) CLOCK-Pro CUSH 1

11 FIFO CLOCK Compact CAR CLCOK-Pro (real) CLOCK-Pro (ideal) (a) α = 1., L = 1.5K (b) α = 1.2, L = 1.5K (c) α = 1.4, L = 1.5K 6: FIFO CLOCK Compact CAR CLCOK-Pro (real) CLOCK-Pro (ideal) CUSH-log (a) (b) Compact CAR (c) CLOCK-Pro 7: (α = 1.4, L = 1.5K) 2: [pck/sec] 1.5KB 15KB 6KB SD(4.5[MB/min]) HD(9.[MB/min]) : loop CUSH-log CLOCK-Pro CUSH CLOCK-Pro loop CLOCK-Pro loop loop YouTube CUSH YouTube, nicovideo, dailymotion ,451, , ,378,925 8 Zipf 3,949 L 15B15KB6KB 11

12 OPT FIFO CLOCK Compact CAR CLCOK-Pro (real) CLOCK-Pro (ideal) (ht4x4) (a) (b) (L = 15K) 9: (c) (L = 6K) 1 2 A Zipf(α) 9 CUSH 4 correlated-reference fickle-interest loop ( 9(a)) CUSH Compact CAR scan loop ( 9(b),9(c)) CLOCK-Pro(real) CUSH CLOCK-Pro(ideal) loop CUSH scan loop CUSH 3 n n k FIFO CLOCK O(n) LRU LRU DLL LFU LFU H O(n log n) LRU LIRS CLOCK CAR CLOCK-Pro Compact CAR CLOCK O(n) n k O(kn log n) CUSH CLOCK kn k = 1 CLOCK-Pro k = log n CLOCK-Pro loop CUSH CUSH 4 CLOCK 1 1 α = 1. 1 O(n) CUSH CLOCK 4 CLOCK 1 2 CLOCK-Pro CLOCK CLOCK 12

13 3: [bit] [bit] [bit] FIFO O(log n) - - LRU DLL O(n log n) - - LFU H O(n log n) - - LIRS (with LRU DLL ) O(n log n) O(kn log kn) O(kn log kn) CLOCK O(n) - - CAR (with LRU DLL ) O(n log n) O(n log n) - CLOCK-Pro O(n) O(n) O(kn log n) Compact CAR O(n) O(n) O(kn log n) CUSH O(n) O(kn) - 4: n CLOCK CLOCK-Pro CUSH Compact CAR CLOCK CLOCK-Pro CUSH Compact CAR hot Compact CAR CUSH CLOCK-Pro CLOCK CUSH CLOCK-Pro CUSH CLOCK CLOCK-Pro (.8 ) Compact CAR 5. ICN loop ICN Compact CAR CLOCK-Pro CUSH CUSH loop CUSH CLOCK-Pro CLOCK ICN ICN ICN (SCOPE)

14 Technologies, pp.187 2, March 24. [1] L. Zhang, D. Estrin, J. Burke, V. Jacobson, J.D. Thornton, D.K. Smetters, B. Zhang, G. Tsudik, K. Claffy, D. Krioukov, D. Massey, C. Papadopoulos, T. Abdelzaher, L. Wang, P. Crowley, and E. Yeh, Named data networking (NDN) project, Oct. 21. http: //named-data.net/techreport/tr1ndn-proj.pdf [21] C. Fricker, P. Robert, J. Roberts, and N. Sbihi, Impact of traffic mix on caching performance in a content-centric network, Proceedings of the IEEE Conference on Computer Communications 212, pp , March 212. [2] V. Jacobson, D.K. Smetters, J.D. Thornton, M.F. Plass, N.H. Briggs, and R.L. Braynard, Networking named content, Proceedings of the ACM CoNEXT 29, pp.1 12, Dec. 29. [3] N. Fotiou, P. Nikander, D. Trossen, and G.C. Polyzos, Developing information networking further: From PSIRP to PURSUIT, Proceedings of the 7th International ICST Conference on Broadband Communications,Networks, and Systems, pp.1 13, Oct. 21. [4] T. Levä, J. Gonçalves, R.J. Ferreira, et al., Description of project wide scenarios and use cases, Feb eu/wp-content/uploads/211/2/sail D21 Project wide Scenarios and Use cases Public Final.pdf [5] L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker, Web caching and Zipf-like distributions: evidence and implications, Proceedings of IEEE INFOCOM 99, vol.1, pp , March [6] F. Guillemin, B. Kauffmann, S. Moteau, and A. Simonian, Experimental analysis of caching efficiency for YouTube traffic in an ISP network, Proceedings of the 25th International Teletraffic Congress, pp.1 9, Sept [7] S. Arianfar, P. Nikander, and J. Ott, On content-centric router design and implications, Proceedings of the ACM Re-Architecting the Internet Workshop, pp.1 6, Nov. 21. [8] A. Ioannou and S. Weber, A taxonomy of caching approaches in information-centric network architectures, Technical report, School of Computer Science and Statistics, Trinity College Dublin, Jan [9] L. Wang, S. Bayhan, and J. Kangasharju, Optimal chunking and partial caching in information-centric networks, Computer Communications, vol.61, no.1, pp.48 57, May 215. [1] D. Rossi and G. Rossini, Caching performance of content centric networks under multi-path routing (and more), Technical report, Telecom ParisTech, July 211. [11] W.K. ChaiD. HeI. Psaras, and G. Pavlou, Cache less for more in information-centric networks, Computer Communicationsvol.36no.7pp May 212 [12] A. Ooka, S. Ata, and M. Murata, A proposal and evaluation of cache replacement policy for the implementation of ICN router, Technical Committee on Information-Centric Networking (ICN), pp.1 1, July 215. [13] S. Jiang and X. Zhang, Making LRU friendly to weak locality workloads: a novel replacement algorithm to improve buffer cache performance, IEEE Transactions on Computers, vol.54, no.8, pp , Aug. 25. [14] S. Jiang, F. Chen, and X. Zhang, CLOCK-Pro: An effective improvement of the CLOCK replacement, Proceedings of the USENIX 25, pp , April 25. [15] J. Wang, A survey of web caching schemes for the Internet, ACM SIGCOMM Computer Communication Review, vol.29, no.5, pp.36 46, Oct [16] K.-Y. Wong, Web cache replacement policies: a pragmatic approach, IEEE Network, vol.2, no.1, pp.28 34, Jan. 26. [17] A.-M.K. Pathan and R. Buyya, A taxonomy and survey of content delivery networks, Technical report, University of Melbourne Grid Computing and Distributed Systems Laboratory, Feb. 27. [18] S. Arianfar, P. Nikander, and J. Ott, Packet-level caching for information-centric networking, Technical report, Finnish ICT SHOK, June 21. [19] N. Megiddo and D.S. Modha, ARC: a self-tuning, low overhead replacement cache, Proceedings of the 2Nd USENIX Conference on File and Storage Technologies, pp , March 23. [2] S. Bansal and D.S. Modha, CAR: Clock with adaptive replacement, Proceedings of the 3rd USENIX Conference on File and Storage 14

name name IP [6] ICN Zipf 2 5 [7] 2 name 2 CCN 3 ICN Compact CCN 2. ICN ICN name NDN/CCN [], [2] CCN MTU name Interest Data CCN FIB PIT CS 3 CS

name name IP [6] ICN Zipf 2 5 [7] 2 name 2 CCN 3 ICN Compact CCN 2. ICN ICN name NDN/CCN [], [2] CCN MTU name Interest Data CCN FIB PIT CS 3 CS 565-87 -5 558-8585 3-3-38 E-mail: {a-ooka,murata}@ist.osaka-u.ac.jp, ata@info.eng.osaka-cu.ac.jp (ICN) Compact / (ICN) (CCN) Abstract A Proposal and Evaluation of Cache Replacement Policy for the Implementation