Journal of Systems Engineering and Electronics ›› 2009, Vol. 31 ›› Issue (3): 697-701.

• 软件、算法与仿真 • 上一篇    下一篇

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

杜慧军, 杨宁   

  1. 广东技术师范学院电信学院, 广东, 广州, 510665
  • 收稿日期:2007-10-26 修回日期:2008-04-23 出版日期:2009-03-20 发布日期:2010-01-03
  • 作者简介:杜慧军(1953- ),男,教授,主要研究方向为下一代高性能互联网技术,广域网通信协议.E-mail:hdu287@163.com
  • 基金资助:
    广东省自然科学基金资助课题(5006102)

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

DU Hui-jun, YANG Ning   

  1. Coll. of Electronics Engineering and Information, Guangdong Polytechnic Normal Univ., Guangzhou 510665, China
  • Received:2007-10-26 Revised:2008-04-23 Online:2009-03-20 Published:2010-01-03

摘要: 为了解决核心交换机中路由表的爆炸式容量问题,业界引入了一种无类域间路由CIDR结构,它有效地减少了路由表容量,但是IP地址查找算法却不能令人满意。通过对基于哈希地址前缀长度的二分查找匹配算法的分析,得出由于CIDR表的存储容量有限,因而二分查找算法的优点没有体现出来。针对此问题,利用几个定点地址前缀长度扩展方法,对该算法进行改进,得到了一种满足CIDR表要求的快速查找匹配算法。经过仿真实验,改进后算法更好地满足了快速转发IP分组的需求。

Abstract: 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.

中图分类号: