一种新的二分路由查找方法  

New Binary Search Algorithm for IP Address Lookup

作　　者：朱国胜[1,2] 余少华[2] 

机构地区：[1]华中科技大学计算机科学和技术学院,湖北武汉430074 [2]新一代光纤通信技术和网络国家重点实验室,湖北武汉430074

出　　处：《小型微型计算机系统》2010年第9期1717-1720,共4页Journal of Chinese Computer Systems

基　　金：国家"八六三"高技术研究发展计划项目(2005AA121410)资助;CNGI项目(CNGI-04-3-1D)资助

摘　　要：分析路由表前缀间的覆盖关系特征,证明了前缀覆盖级别集合符合二分查找特性,提出一种基于前缀覆盖级别的二分路由查找算法,和传统基于前缀长度或者前缀值的线性或者二分查找算法相比,在查找性能、路由更新和存储空间方面具有优势,本方法可以在O(log2m ax_level+1)个TCAM时钟周期内完成1次路由查找,其中m ax_level为最大的前缀覆盖级别,目前m ax_level不超过7;本方法无需前缀扩展和排序,支持路由增量更新;另外,传统TCAM路由查找相比,可以节省功耗约50%.We analysized the statistics features of routing preifx covered levels and proved that the sets of prefix covered levels fulfil the requirement of binary search algorithm.A novel binary search algorithm based on prefix covered levels called BSPCL（Binary Search on Prefix Covered Levels） is proposed in this paper.Traditional schemes implement IP address lookup using linear or binary search on prefix lengths or prefix values at the cost of slow lookup speed,complex pre-computation or high power consumption.Our scheme has better performance over others in search performance,incremental updates,memory space and power consumption.We can finish one IP address lookup in O（log2max_level＋1） TCAM clock cycles where max_level is the max prefix covered levels,the current max_level is no more than 7.Incremental updates are supported without the need of prefix expansion and prefix ordering.The power consumption can be reduced about 50% when compared to traditional TCAM scheme.

关 键 词：IP路由查找 二分查找 前缀覆盖级别 

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