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

• 作者: 丁伟 彭艳兵 徐加羚 龚俭
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 活跃IP 子网前缀 重尾分布 路由查询 统计优化 溢出排序
• 年，卷（期）: 2005,（8）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 1351-1359
• 页数: 9页
• 分类号: TP393
• 字数: 8244字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2005.08.014

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	龚俭	东南大学计算机科学与技术系华东北网络中心	107	2154	26.0	43.0
2	彭艳兵	东南大学计算机科学与技术系华东北网络中心	4	77	3.0	4.0
3	丁伟	东南大学计算机科学与技术系华东北网络中心	56	958	15.0	30.0
4	徐加羚	东南大学计算机科学与技术系华东北网络中心	4	158	3.0	4.0