A fast and scalable IP lookup scheme for high-speed networks
作者： W.-S.E. Chen , C.-T.J. Tsai
关键词:
摘要: One of the key design issues for next-generation IP routers is lookup mechanism. For each incoming packet, routing needs to perform a longest prefix matching on address in order determine packet's next hop. Currently, process done software and has become major bottleneck router performance. In this paper, we propose high-speed scheme best (BMP) by using forwarding tables consisting information (PIT) (LT) that provide guidelines efficient search. The scales very well as sizes table increase. IPv4, 1 memory access case, 2 accesses plus one hash worst case locate BMP, if exists. It requires only 560 KBytes 670 space when about 45000 entries backbone are logged simulation. When 50 ns DRAM used tables, offers speed 10 millions packets per second. can be improved linearly with speedup type used.
sci-hub.se 参考文章(9)
Stefan Nilsson, Gunnar Karlsson, Fast address look-up for internet routers BC '98 Proceedings of the IFIP TC6/WG6.2 Fourth International Conference on Broadband Communications: The future of telecommunications. ,vol. 121, pp. 11- 22 ,(1998) , 10.1007/978-0-387-35378-4_2
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
C. Labovitz, G.R. Malan, F. Jahanian, Origins of Internet routing instability international conference on computer communications. ,vol. 1, pp. 218- 226 ,(1999) , 10.1109/INFCOM.1999.749286
S. Nilsson, G. Karlsson, IP-address lookup using LC-tries IEEE Journal on Selected Areas in Communications. ,vol. 17, pp. 1083- 1092 ,(1999) , 10.1109/49.772439
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
S. Keshav, R. Sharma, Issues and trends in router design IEEE Communications Magazine. ,vol. 36, pp. 144- 151 ,(1998) , 10.1109/35.668285
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
Marcel Waldvogel, George Varghese, Jon Turner, Bernhard Plattner, Scalable high speed IP routing lookups acm special interest group on data communication. ,vol. 27, pp. 25- 36 ,(1997) , 10.1145/263105.263136