论文部分内容阅读
分析路由表前缀间的覆盖关系特征,证明了前缀覆盖级别集合符合二分查找特性,提出一种基于前缀覆盖级别的二分路由查找算法,和传统基于前缀长度或者前缀值的线性或者二分查找算法相比,在查找性能、路由更新和存储空间方面具有优势,本方法可以在O(log2m ax_level+1)个TCAM时钟周期内完成1次路由查找,其中m ax_level为最大的前缀覆盖级别,目前m ax_level不超过7;本方法无需前缀扩展和排序,支持路由增量更新;另外,传统TCAM路由查找相比,可以节省功耗约50%.
It is proved that the set of prefix coverage conforms to the dichotomous search feature. A binary search algorithm based on prefix coverage level is proposed. Compared with the traditional linear or binary search algorithm based on prefix length or prefix value, , Which has advantages in finding performance, routing updates and storage space. The method can perform a route lookup within O (log2m ax_level + 1) TCAM clock cycles, where m ax_level is the maximum prefix coverage level, and the current m ax_level is not More than 7; This method does not need prefix expansion and sorting, support incremental routing updates; In addition, the traditional TCAM routing lookup, you can save about 50% power consumption.