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

Size: px

Start display at page:

Download "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"

こうたちとく
5 years ago
Views:

1 (ICN) Compact / (ICN) (CCN) Abstract A Proposal and Evaluation of Cache Replacement Policy for the Implementation of ICN Router Atsushi OOKA, Shingo ATA, and Masayuki MURATA Graduate School of Information Science and Technology, Osaka University -5 Yamadaoka, Suita, Osaka, , Japan Graduate School of Engineering, Osaka City University Sugimoto, Sumiyoshi-ku, Osaka-shi, Osaka , Japan {a-ooka,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 and computational and memory overheads that are low enough to run on ICN router s hardware. We focus on as the suitable policy for an access pattern of workload on the router and propose the cache replacement policy (called Compact ) that satisfies the requirements. We also evaluate our proposed approach and show that the size of cache memory required to achieve a certain performance can be reduced to /th of that of the simple policy. Key words Policy Future Networks, Information-Centric Networking, Content-Centric Networking, Caching, Cache Replacement. Information-Centric Networking (ICN) ICN ICN IP name NDN/CCN [] [3], PSIRP/PURSUIT [4], SAIL/NetInf [5] ICN ICN clean-slate IP name

2 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 Data Data name Data 2. 2 ICN CE 2 (Cache Everything Everywhere) [], [2], [4], [5] CE 2 [8] d [9] [] [] Leave Copy Down (LCD) CE 2 [2] [3] 2. 3 Random First-In, First Out () Not Recently Used (NRU) Random First-In, First Out () IP Not Recently Used (NRU) ( R ) R LRU LRU [] Least Recently Used (LRU) Adaptive Replacement Cache (ARC) [4] Low Inter-reference Re- 2

3 cency Set (LIRS) [5] Least Frequently Used (LFU) LRU ICN Random LRU [], [6] ARC LRU LFU LRU ARC 2 LRU L L 2 2 L n (n =, 2) (T n ) (B n ) recent T n B n B n ghost cache T T 2 < = c L L 2 = T B T 2 B 2 < = 2c LRU LRU LIRS LRU loop(3. ) LFU LRU LRU R = R = R LRU ARC Clock with Adaptive Replacement () [7] T T 2 ARC B B 2 LRU T T 2 MRU operation LIRS -Pro [8] LRU loop LIRS ICN [3], [9] LRU LFU [2] scan, loop, correlated-reference, frequentlyshifts scan LRU n S > c loop scan (LRU, LFU, ARC ) scan correlated-reference LFU frequently-shifts LIRS / LRU MRU operation NRU LFU LRU tail NRU R set LRU-stack NRU bit ARC 3

4 LIRS ghost cache LFU 3. 2 ICN ICN 3 scan loop scan frequently-shifts 2 Web VoIP scan loop MTU.5KB scan loop MB 7k 3 scan loop scan frequently-shifts loop ARC -Pro correlated-reference LFU loop frequtently-shifts LFU ARC LIRS LRU LRU [7], [8] NRU -Pro -Pro loop frequently-shifts 3 loop scan frequently-shifts LRU 4. Compact 4. ARC LRU-stack ( ) LRU-stack 2 Compact ARC/ T, T 2, B, B 2 L = T B, L 2 = T 2 B 2 T T 2, B B 2 c c T = T T 2, B = B B 2 c T B 4

5 T ( T = n) a a 2 a i a n b c n b j a n a a 2 a 3 T 2 ( T 2 = c n) B ( B = m) B 2 ( B 2 = c m) b c n b b 2 b x x k x m y c m y l y b 3 x m x x 2 x 3 y c m y y 2 y 3 Algorithm 3 ReplaceBtm() for Compact : procedure REPLACEBTM(i) 2: Swap(B i [Hand Bi ], B i.edgechunk) 3: Discard B i.edgechunk 4: Rotate Hand Bi 5: an address next to the edge of B i is ensured to be free. 6: end procedure a i a i reference-bit (R-bit) b j b j Compact ( ARC ) T ( T = n) a a 2 a i a n b c n b j 2 a n a a 2 a i a i a 3 T 2 ( T 2 = c n) b c n b b 2 b j b j b b 3 x k x k T ( T = n ) a n a a 2 a n a i a 3 y l y l T 2 ( T 2 = c n + ) a a n a n a i b c n b j a i b (T T 2 a k ) + b j b j b 2 b b 3 Algorithm 4 ReplaceTop() for Compact : function REPLACETOP(i) 2: while T i [Hand Ti ].R-bit= do 3: T i [Hand Ti ].R-bit 4: if i= then 5: Swap(T i [Hand Ti ], T i.edgechunk) 6: Shift the boundary between T and T 2. 7: end if 8: Rotate Hand Ti 9: end while : s e an address next to the edge of B i : B i [s e] T i [Hand Ti ] 2: Swap(T i [Hand Ti ], T i.edgechunk) 3: Discard T i.edgechunk 4: Rotate Hand Ti 5: return T i.edgeaddr 6: end function Algorithm Dual-bit/Compact Replacement Algorithm : procedure CACHEREPLACEMENT(x) x is an accessed chunk. 2: if x T then cache hit 3: x.r-bit 4: return 5: else if x B then ghost hit 6: i 2 to cache x in T 2 7: if x B then 8: δ max(, B 2 ); p min(c, p + δ) B 9: DiscardBtm(,x) : else x B 2 : δ max(, B ); p max(, p δ) B 2 2: DiscardBtm(2,x) 3: end if 4: else cache miss 5: i to cache x in T 6: if Full(L ) & B > then ReplaceBtm() 7: else if Full(L) & B 2 > then ReplaceBtm(2) 8: end if 9: end if 2: if Full(T ) then 2: if T > = max(p, ) then s t ReplaceTop() 22: else s t ReplaceTop(2) 23: end if 24: else T is not full. 25: s t a free address in T i 26: end if 27: T i [s t ] x x is cached as a chunk in T i. 28: end procedure Algorithm 2 DiscardBtm() for Compact : procedure DISDBTM(i, x) 2: Swap(x, B i.edgechunk) 3: Discard x (at the edge of B i ) 4: an address next to the edge of B i is ensured to be free. 5: end procedure Compact 4. 2 Compact Compact T T 2 B B 2 T T 2 B B 2 R LRU-stack 2 T = (a, a 2,, a n ) T 2 = (b, b 2,, b c n ) a k LRU-stack a k T 2 (b j+,, b c n ) Compact a k a n T = (a, a k, a n, a k+, a n ), T 2 = (b, b 2,, b c n, a k ) T T 2 LRU 4. 3 Compact Compact R (2 4 ) 5 9 B ghost hit (5 3 ) p ghost hit p ARC T 5

6 p (4 9 ) B B B 2 p 2 26 B T s t 27 s t Hand Ti T i T i [Hand Ti ] (B i ) ( EdgeChunk) T Ghost hit B B 2 B i B B 2 DiscardBtm ( 2) B i x Ghost hit ReplaceBtm ( 3) B i B ReplaceTop ( 4) T i T T R 2 T 2 B B DiscardBtm ReplaceBtm B B Compact Zipf Zipf 2 A Zipf(α) A Zipf A Zipf(α) α A Zipf r f(r) = c α /r α (c, α ) [2] α.5.2 α =.6,.8,.,.2 4 A 7 YouTube, nicovideo, dailymotion ,428, ,545 3,4,868 3 Zipf 49,82 L 5B.5KB 6KB 6

7 [pck/sec].5kb 5KB 6KB SD(4.5[MB/min]) HD(9.[MB/min]) 2.5 A Zipf(α) 7 A KB 2: 2: ( 9 ) 5KB 3:2 4:8 ( 66 ) 6KB 9:57 4:45 ( 9 ) A C Zipf(α) AC A P =LKB Zipf(α) A P =LKB,,, CE 2 () 7 C 6 [Chunks] A Zipf(α) Zipf α A C Zipf(.6) 4 A C Zipf(.8) 5 AC Zipf(.) 6 AC Zipf(.2) 7 α =. 8 9 Compact LRU.5% / % α A A C, A P =.5KB 4 A P =LKB A P =.5KB A P =5KB A P =.5KB A P =6KB , A C Zipf(α) 5, A P =LKB Zipf(α),A P =5KB 7, 8 2,, 96,, 2, 2 7

8 Compact Compact Compact Compact A C Zipf(.6) 5 A C Zipf(.8) 6 A C Zipf(.) 7 A C Zipf(.2) Compact.3 Compact.4 Compact A P =.5KB Zipf(.) 9 A P =5KB Zipf(.) A P =6KB Zipf(.) Compact.5 Compact.5 Compact.4 Compact A C 2 A P =.5KB 3 A P =5KB 4 A P =6KB Repel Repel Repel Repel st th st th st th st th 5 A C Zipf(.8) (c = 5 [Chunks]) 6 A P =6KB Zipf(.2) (c = 3 [Chunks]) 7 A P =6KB Zipf(.) (c = 3 [Chunks]) 8 A P =6KB Zipf(.) (c = 4 [Chunks]) Repel Repel LRU Compact st 9 A C (C = 3 [Chunks]) th st 2 A P =5KB (C = 3 [Chunks]) th % A Zipf(α) α 8

9 loop loop loop 6. 2 Data Gbps.25GB Data 64B 2MSPS Interest % bit 2MSPS 2 24bit 63MB SRAM 2.3Gbit(8 288Mbit) 4 SRAM.45ns [22] 4 DRAM SSD FPGA [6] ICN 7. ICN ICN CS Web ICN [7] Compact Compact LRU / ICN SCOPE [] 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. 2, Dec. 29. [2] 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. 2. http: //named-data.net/techreport/trndn-proj.pdf [3], CCNx, [4] N. Fotiou, P. Nikander, D. Trossen, and G.C. Polyzos, Developing information networking further: From PSIRP to PURSUIT, Proceedings of the International ICST Conference on Broadband Communications,Networks, and Systems, pp. 3, Oct. 2. [5] T. Levä, J. Gonçalves, R.J. Ferreira, et al., Description of project wide scenarios and use cases, Feb eu/wp-content/uploads/2/2/sail D2 Project wide Scenarios and Use cases Public Final.pdf [6] K.I. Atsushi Ooka, Shingo Ata and M. Murata, High-speed design of conflict-less name lookup and efficient selective cache on CCN router, IEICE Transactions on Communications, vol.e98-b, no.4, pp.67 62, April 25. [7] F. Guillemin, B. Kauffmann, S. Moteau, and A. Simonian, Experimental analysis of caching efficiency for YouTube traffic in an ISP network, Proceedings of the 2 International Teletraffic Congress, pp. 9, Sept

10 [8] S.K. Fayazbakhsh, Y. Lin, A. Tootoonchian, A. Ghodsi, T. Koponen, B. Maggs, K.C. Ng, V. Sekar, and S. Shenker, Less pain, most of the gain: Incrementally deployable ICN, ACM SIGCOMM Computer Communication Review, vol.43, no.4, pp.47 58, Aug. 23. [9] S. Arianfar, P. Nikander, and J. Ott, On content-centric router design and implications, Proceedings of the ACM Re-Architecting the Internet Workshop, pp. 6, Nov. 2. [] W.K. Chai D. He I. Psaras, and G. Pavlou, Cache less for more in information-centric networks, Computer Communications vol.36 no.7 pp [] D. Rossi and G. Rossini, Caching performance of content centric networks under multi-path routing (and more), Technical report, Telecom ParisTech, July 2. [2] 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. 25. [3] L. Wang, S. Bayhan, and J. Kangasharju, Optimal chunking and partial caching in information-centric networks, Computer Communications, vol.6, no., pp.48 57, May 25. [4] 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.5 3, March 23. [5] 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. [6] S. Arianfar, P. Nikander, and J. Ott, Packet-level caching for information-centric networking, Technical report, Finnish ICT SHOK, June 2. [7] S. Bansal and D.S. Modha, : Clock with adaptive replacement, Proceedings of the USENIX Conference on File and Storage Technologies, pp.87 2, March 24. [8] S. Jiang, F. Chen, and X. Zhang, -Pro: An effective improvement of the replacement, Proceedings of the USENIX 25, pp , April 25. [9] J. Ran, N. Lv, D. Zhang, Y. Ma, and Z. Xie, On performance of cache policies in named data networking, Proceedings of the International Conference on Advanced Computer Science and Electronics Information 23, pp , July 23. [2] A. Jaleel, K.B. Theobald, S.C. Steely, Jr., and J. Emer, High performance cache replacement using re-reference interval prediction (RRIP), ACM SIGARCH Computer Architecture News, vol.38, no.3, pp.6 7, June 2. [2] 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 22, pp.3 35, March 22. [22] D. Perino and M. Varvello, A reality check for Content Centric Networking, Proceedings of the ACM SIGCOMM workshop on Information-centric networking, pp.44 49, Aug. 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

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-Pro 565-871 1-5 558-8585 3-3-138 E-mail: {a-ooka,suyong,murata}@ist.osaka-u.ac.jp, ata@info.eng.osaka-cu.ac.jp (ICN) CLOCK-Pro ICN CLOCK-Pro Using Switching Hash-table (CUSH) (ICN) (CCN) A Proposal