Two-stage IPv6 route search algorithm based on perfect-Hash table and multibit-trie
Du Fei1,4,DONG Zhiguo2,MIAO Lin3,TUO YupengYupeng1,4
1. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
2. China Nuclear Power Engineering Corporation Limited, China National Nuclear Corporation, Beijing 100840, China
3. National Computer Network Emergency Response Technical Team Coordination Center of China, Beijing 100027, China
4. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
Du Fei DONG Zhiguo MIAO Lin TUO YupengYupeng. Two-stage IPv6 route search algorithm based on perfect-Hash table and multibit-trie[J]. Journal of Computer Applications, 2013, 33(05): 1194-1202.
[1]陈蹊,赵跃龙.多分枝Trie树路由查找算法研究[J].电子设计工程,2010,18(3):4-5,8.[2]高莹,王贺明,陈强.采用分段哈希方法的IPv6路由查找算法研究[J].计算机工程与设计,2010,31(22):4790-4793.[3]王亚刚,杜慧敏,杨康平.使用Hash表和树位图的两级IPv6地址查找算法[J].计算机科学,2010,37(9):36-39,80.[4]孙庆南,鲁士文.一种改进的二分法IPv6路由查找算法[J].计算机工程,2006,32(18):35-38.[5]崔尚森,张白一.一种基于哈希表和Trie树的快速IP路由查找算法[J].计算机工程与应用,2005,41(9):156-158.[6]WALDVOGEL M,VARGHESE G,TURNER J,et al.Scalable high speed IP routing lookups[J]。ACM SIGCOMM Computer Communication Review, 1997,27(4):25-36.[7]EATHERTON W. Hardware based Internet protocol prefix lookups[D].St.Louis:Washington University,1999.[8]EATHERTON W,VARGHESE G,DITTIA Z.Tree bitmap: Hardware/software IP lookups with incremental updates[J]. ACM SIGCOMM Computer Communication Review,2004,34(2):97-122.[9]LI Y K,PAO D. Address lookup algorithms for IPv6[J].IEEE Proceedings of Communications,2006,153(6):909-918.[10]HUSTON G.Analyzing the Internet's BGP routing table[J].The Internet Protocol Journal,2001,4(1):2-15.[11]AS2IPv6 BGP Table Statistics [EB/OL].[2012-09-12]. http://bgp.potaroo.net/v6/as2.0/index.html.