自相似活跃子网前缀空间的路由查找

Route Lookup in Fractal Active Subnet Prefix Space

IP地址查询是路由器的基本工作,活跃IP和子网前缀地址空间是重尾分布且自相似的,而针对这种重尾分布的IP地址和前缀可以用于对路由查找进行统计优化.文章分析并验证了活跃IP地址空间的特点和子网前缀空间分形自相似特性,活跃IP的子网前缀在不同的聚类规模上的次序统计量服从Pareto分布,主干路由表项的次序统计量也近似服从Pareto分布.该文提出了一种基于活跃度排序的路由逐次查找算法———SOSL,对IP地址查询进行了优化,在该文的模拟实验中,活跃路由表的规模、刷新周期和活跃度判定下限间存在一些对数线性关系,使得作者可以以很小的活跃路由表来实现全部路由查找需求的99%;为SOSL实现中最关键的活跃路由表排序问题提出了一个基于计数器溢出的方案,复杂度为O(1).对比发现该文的算法与TCAM结合能够提高TCAM的效率,高效地控制活跃路由表的规模,易于硬件实现.

Route lookup is a basic work for the routers. The active subnet prefix is self-similar at different prefix length, and this fractal distribution can be used to statistical optimizing the route lookup. After validating self-similar characteristic of the active subnet prefix space, it was found that the order statistic of the active subnet prefix at different aggregation class obeys to Pareto Distribution, and the active subnet distribution of different subnet prefix scale is selfsimilar.Further investigation disclosed that the active degree of route items in backbone router is close to Pareto distribution. Based on these results, this paper proposes a new route lookup method——Statistical Optimized Successive Lookup algorithms （SOSL）, which optimizes the route lookup by the active route sorting. The simulating experiment suggests that there are some logarithmic linear relationships among the scale of active route table, refreshing period of active route table and counter＇s overflowing value, and which enable router to classify the packet in a very small active route table. A fast sort scheme is presented to solve the key bottleneck, route active degree sorting, in SOSL with O（1） time complexity metrics. The comparison among SOSL, Longest Prefix Matching algorithm（LPM） and TCAM implied that SOSL is easy to implement by hardware. It is the greatest advantage that SOSL can work along with TCAM to improve the efficiency of TCAM with efficient active route table scale management.