A Dynamic Binary Hash Scheme for IPv6 Lookup
作者： Qiong Sun , Xiaohong Huang , Xiaoju Zhou , Yan Ma
DOI: 10.1109/GLOCOM.2008.ECP.447
关键词: Algorithm 、 Key-based routing 、 Computer science 、 Hash function 、 Cryptographic protocol 、 Routing protocol 、 Lookup table 、 Routing table 、 Longest prefix match 、 Computer network 、 IPv6 address 、 Routing (electronic design automation) 、 Memory management
摘要: 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 observation characteristic of IPv4/IPv6 routing table and propose novel division technique table, with which traditional LPM (longest prefix matching) problem be changed to an exact matching one majority prefixes. Based technique, DBH (dynamic binary hash) dynamic lookup, achieves O(log W) (W stands length) performance. Key feature new is its ability have performance guarantee 7 hash probes worst cast meanwhile it support incremental update. This makes more attractive reality. The evaluation shown that newly proposed achieve average memory access number 2.7 current It below 35% best existing algorithm. Besides, cost by data structure itself extremely small update very few.
sci-hub.se 参考文章(15)
Xiaoyu Zhao, Wenjian Jiang, Yan Ma, Xiaohong Huang, Qiong Sun, A Scalable Exact matching in Balance Tree Scheme for IPv6 Lookup ,(2007)
Subhash Suri, G. Varghese, P.R. Warkhede, Multiway range trees: scalable IP lookup with fast updates global communications conference. ,vol. 3, pp. 1610- 1614 ,(2001) , 10.1109/GLOCOM.2001.965852
Haibin Lu, Sartaj Sahni, $O(\log W)$ Multidimensional Packet Classification IEEE ACM Transactions on Networking. ,vol. 15, pp. 462- 472 ,(2007) , 10.1109/TNET.2007.892845
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
Pi-Chung Wang, Chun-Liang Lee, Chia-Tai Chan, Hung-Yi Chang, Performance improvement of two-dimensional packet classification by filter rephrasing IEEE ACM Transactions on Networking. ,vol. 15, pp. 906- 917 ,(2007) , 10.1109/TNET.2007.893872
Kai Zheng, Zhen Liu, Bin Liu, A scalable IPv6 route lookup scheme via dynamic variable-stride bitmap compression and path compression Computer Communications. ,vol. 29, pp. 3037- 3050 ,(2006) , 10.1016/J.COMCOM.2005.11.003
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
Zhenqiang Li, Xiaohong Deng, Hongxiao Ma, Yan Ma, Divide-and-conquer: a scheme for IPv6 address longest prefix matching high performance switching and routing. ,(2006) , 10.1109/HPSR.2006.1709678
Jonathan S. Turner, Haoyu Song, Fast Filter Updates for Packet Classification using TCAM global communications conference. ,(2006)