哈希表和多比特Trie相结合的IPv6分阶段路由查找算法  

Multi-stage IPv6 Routing Lookup Algorithm Based on Hash Table and Multibit Trie

作　　者：秦怡[1] 杨云[1] 闵玉涓 姚明[1] 赵晶晶[1] QINYi;YANG Yun;MING Yu-juan;YAO Ming;ZHAO Jing-jing(College of Information Engineering, Yangzhou University, Yangzhou 225127, China)

机构地区：[1]扬州大学信息工程学院计算机系,江苏扬州225127

出　　处：《小型微型计算机系统》2018年第5期893-898,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(F020509)资助;江苏省产学研前瞻性研究项目(BY2016069-16)资助

摘　　要：IPv6具有128位的地址长度、无分类编址,这使得IPv6网络中的核心路由器路由查找处理负担更重、要求更高,已有的基于IPv4的路由查找算法扩展到IPv6后无法适应新的需求,需要建立新的基于IPv6的路由查找算法.在分析了IPv6地址前缀长度和分布特点的基础上,提出一种哈希表和多比特Trie(retrieval)相结合的IPv6路由查找算法.算法首先根据地址前缀值来进行分类,然后针对常用的地址前缀值,以48比特为路由查找起点,分阶段、高效的进行路由查找,对于非常用的地址前缀值采用直接哈希查找.算法仿真表明,在大多数情况下,只需要一次存储器访问,就能查找到下一跳路由信息,算法查找效率高.算法结构简单,易于硬件实现.The address length of IPv6 is 128,in the IPv6 network,the processing burden of the core router is heavier and the requirements are higher,many of the existing algorithms can not adapt to the new requirements after expanding to IPv6,so it is necessary to propose a new routing lookup algorithm based on IPv6. Although most of the traffic on the Internet or by the IPv4 network,but the IPv4 address space has been depleted facts cannot be changed,IPv6 as the successor of IPv4,solves the shortcomings of IPv4,can further the Internet development. After thorough analysis of the IPv6 address prefix distribution regularity,this paper proposes a new scheme based on simple data structure： Hash Table and Multibit Trie（ retrieval）. This algorithm first classifies the prefix value and then starts its first lookup by using the first 48 bits prefix of the IPv6 Address,simulation results show that in most cases,the algorithm needs only one memory access to find the next hop routing information. This algorithm has high lookup speed and can be easily implemented with hardware.

关 键 词：哈希表 多比特Trie 路由查找 最长匹配 IPV6 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]