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

摘要：

分析路由表前缀间的覆盖关系特征,证明了前缀覆盖级别集合符合二分查找特性,提出一种基于前缀覆盖级别的二分路由查找算法,和传统基于前缀长度或者前缀值的线性或者二分查找算法相比,在查找性能、路由更新和存储空间方面具有优势,本方法可以在O(log2max_level+1)个TCAM时钟周期内完成1次路由查找,其中max_level为最大的前缀覆盖级别,目前max_level不超过7;本方法无需前缀扩展和排序,支持路由增量更新;另外,传统TCAM路由查找相比,可以节省功耗约50%.

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

所属期刊栏目：31

分类号：TP393(计算技术、计算机技术)

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

在线出版日期：2011-01-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：1717-1720