Efficiency analyses on routing cache replacement algorithms
作者： Woei-Luen Shyu , Cheng-Shong Wu , Ting-Chao Hou
关键词: Parallel computing 、 Computer network 、 Routing table 、 Cache-oblivious algorithm 、 Static routing 、 Page cache 、 Cache invalidation 、 Locality of reference 、 Cache 、 Cache pollution 、 Quality of service 、 Algorithm 、 Policy-based routing 、 Cache algorithms 、 Router 、 Enhanced Interior Gateway Routing Protocol 、 Routing protocol 、 Computer science 、 Adaptive replacement cache
摘要: Recent research on router architectures focuses speeding up the time-consuming routing-lookup procedure by elaborate algorithms and data structures to match ever-increasing wire-speed of fiber links. However, we observed strong temporal locality in traffic traces collected from two TANet backbone routers. Thus, a routing cache, which is used reuse previous results, can significantly offload module. In this paper, first introduce our analysis. Then investigate efficiency several cache replacement algorithms, includes FIFO, LRU, random proposed LFU implementation alternative. The simulation results show that exponentially decayed scheme provides better performance than other especially under small-size caches.
sci-hub.se 参考文章(13)
E. Rosen, B. Davie, D. Katz, G. Swallow, Y. Rekhter, Cisco Systems' Tag Switching Architecture Overview RFC. ,vol. 2105, pp. 1- 13 ,(1997)
K. Thompson, G.J. Miller, R. Wilder, Wide-area Internet traffic patterns and characteristics IEEE Network. ,vol. 11, pp. 10- 23 ,(1997) , 10.1109/65.642356
Nen-Fu Huang, Shi-Ming Zhao, Jen-Yi Pan, Chi-An Su, A fast IP routing lookup scheme for gigabit switching routers IEEE INFOCOM '99. Conference on Computer Communications. Proceedings. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. The Future is Now (Cat. No.99CH36320). ,vol. 3, pp. 1429- 1436 ,(1999) , 10.1109/INFCOM.1999.752163
P. Newman, G. Minshall, T. Lyon, L. Huston, IP switching and gigabit routers IEEE Communications Magazine. ,vol. 35, pp. 64- 69 ,(1997) , 10.1109/35.568212
C. Partridge, P.P. Carvey, E. Burgess, I. Castineyra, T. Clarke, L. Graham, M. Hathaway, P. Herman, A. King, S. Kohalmi, T. Ma, J. Mcallen, T. Mendez, W.C. Milliken, R. Pettyjohn, J. Rokosz, J. Seeger, M. Sollins, S. Storch, B. Tober, G.D. Troxel, D. Waitzman, S. Winterble, A 50-Gb/s IP router IEEE ACM Transactions on Networking. ,vol. 6, pp. 237- 248 ,(1998) , 10.1109/90.700888
D.C. Feldmeier, Improving gateway performance with a routing-table cache IEEE INFOCOM '88,Seventh Annual Joint Conference of the IEEE Computer and Communcations Societies. Networks: Evolution or Revolution?. pp. 298- 307 ,(1988) , 10.1109/INFCOM.1988.12930
M.A. Ruiz-Sanchez, E.W. Biersack, W. Dabbous, Survey and taxonomy of IP address lookup algorithms IEEE Network. ,vol. 15, pp. 8- 23 ,(2001) , 10.1109/65.912716
Mikael Degermark, Andrej Brodnik, Svante Carlsson, Stephen Pink, Small forwarding tables for fast routing lookups acm special interest group on data communication. ,vol. 27, pp. 3- 14 ,(1997) , 10.1145/263105.263133
W. Doeringer, G. Karjoth, M. Nassehi, Routing on longest-matching prefixes IEEE ACM Transactions on Networking. ,vol. 4, pp. 86- 97 ,(1996) , 10.1109/90.503764
P. Gupta, S. Lin, N. McKeown, Routing lookups in hardware at memory access speeds international conference on computer communications. ,vol. 3, pp. 1240- 1247 ,(1998) , 10.1109/INFCOM.1998.662938