基于CIDR表的哈希地址二分查找算法的改进  

Improvement of binary lookup algorithm of Hash addresses based on CIDR list

作　　者：杜慧军[1] 杨宁[1] 

机构地区：[1]广东技术师范学院电信学院,广东广州510665

出　　处：《系统工程与电子技术》2009年第3期697-701,共5页Systems Engineering and Electronics

基　　金：广东省自然科学基金资助课题(5006102)

摘　　要：为了解决核心交换机中路由表的爆炸式容量问题,业界引入了一种无类域间路由CIDR结构,它有效地减少了路由表容量,但是IP地址查找算法却不能令人满意。通过对基于哈希地址前缀长度的二分查找匹配算法的分析,得出由于CIDR表的存储容量有限,因而二分查找算法的优点没有体现出来。针对此问题,利用几个定点地址前缀长度扩展方法,对该算法进行改进,得到了一种满足CIDR表要求的快速查找匹配算法。经过仿真实验,改进后算法更好地满足了快速转发IP分组的需求。To resolve the problem that the route list in core switches needs explosive capacity, a CIDR （classless inter domain routing） structure is introduced. The CIDR list efficiently reduces route list capacity, but is not satisfied with the IP address lookup algorithm. With an analysis of binary lookup algorithm based on the prefix length of Hash address, it can be seen that the advantage of this algorithm is not embodied since the limitation of store capacity on CIDR list. With the improvement of this algorithm by the method of prefixes length expansion for a few fixed point addresses, a faster lookup matching algorithm is brought forward which satisfies the requirements of the CIDR list. From the simulated experiment, the improved algorithm meets the demand for fast forwarding IP blocks better.

关 键 词：计算机系统结构 CIDR表 哈希匹配算法 二分查找算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]