A Scalable Exact matching in Balance Tree Scheme for IPv6 Lookup
作者： Xiaoyu Zhao , Wenjian Jiang , Yan Ma , Xiaohong Huang , Qiong Sun
DOI:
关键词:
摘要: Recently, the significantly increased IPv6 address length has posed a greater challenge on wire-speed router for IP lookup. As result, even most efficient IPv4 lookup scheme can not meet demand in IPv6. In this paper, we make thorough study of real world IPv4/IPv6 routing tables and find out useful characteristic leaf nodes first time. The be arranged single balance tree thus change LPM (longest prefix matching) model to exact matching one This only reduce number searching keys, but also memory cost support fast update. What's more, procedure stop immediately when meeting match. our is general concept. Here, implement with three typical trees: B-tree, red black avl detailed comparison from every aspect. experimental results show that its average speed less than third newly proposed rangebased algorithm PIBT[1]. And among these schemes, best consumption while B-tree least update
sigcomm.org 参考文章(10)
Priyank Warkhede, Subhash Suri, George Varghese, Multiway range trees: scalable IP lookup with fast updates Computer Networks. ,vol. 44, pp. 289- 303 ,(2004) , 10.1016/J.COMNET.2003.09.004
Lih-Chyau Wuu, Kuo-Ming Chen, Tzong-Jye Liu, A longest prefix first search tree for IP lookup international conference on communications. ,vol. 51, pp. 989- 993 ,(2005) , 10.1109/ICC.2005.1494497
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
A. Broder, M. Mitzenmacher, Using multiple hash functions to improve IP lookups international conference on computer communications. ,vol. 3, pp. 1454- 1463 ,(2001) , 10.1109/INFCOM.2001.916641
B. Lampson, V. Srinivasan, G. Varghese, IP lookups using multiway and multicolumn search international conference on computer communications. ,vol. 3, pp. 1248- 1256 ,(1998) , 10.1109/INFCOM.1998.662939
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
Donald R. Morrison, PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric Journal of the ACM. ,vol. 15, pp. 514- 534 ,(1968) , 10.1145/321479.321481
Haibin Lu, S. Sahni, A B-tree dynamic router-table design IEEE Transactions on Computers. ,vol. 54, pp. 813- 824 ,(2005) , 10.1109/TC.2005.104
Craig Labovitz, G. Robert Malan, Farnam Jahanian, Internet routing instability acm special interest group on data communication. ,vol. 27, pp. 115- 126 ,(1997) , 10.1145/263105.263151