高速路由器的数据转发技术研究

论文题目: 高速路由器的数据转发技术研究

论文类型: 博士论文

论文专业: 通信与信息系统

作者: 吴卫东

导师: 石冰心

关键词: 边际网关协议,路由查找算法,地址前缀,无类域间路由,数据转发引擎,二进制树,三元内容寻址存储器

文献来源: 华中科技大学

发表年度: 2005

论文摘要: 随着光纤通信技术的飞速发展,链路的传输能力迅速提升,而路由器转发数据的能力相对落后,其主要原因之一是路由查找的困难。路由查找是为到达路由器的数据包找到转发端口,其依据是路由表。一方面,随着因特网规模扩大,路由表急剧膨胀,需要更大的存储空间,导致路由查找速度降低。另一方面,由于路由表结构的复杂,必须采用最长地址前缀匹配算法,既要比较目的IP 地址和地址前缀的值,又要比较地址前缀的长度—二维查找。这些特点说明了路由查找技术研究的意义和难度。面对不断膨胀的路由表和高速数据转发的需要,路由查找技术的研究受到广泛的重视。传统的二维查找算法不能满足高速数据转发的要求,许多研究者提出了新的解决方法,路由器的数据转发能力有明显提高。仍然,有许多问题需要研究,如:(1)在提高路由查找效率的同时,如何保证高效的路由更新操作?(2)基于硬件的算法能够提高路由查找的速率,但需要克服高能耗、路由更新的困难; (3)设计适应IPv6 地址结构的算法等。针对这些问题,本文选择了“高速数据转发引擎的关键技术研究”这一课题,对数据转发引擎的主要技术,如交换结构、调度算法、路由查找等进行了系统的分析。然后,基于路由表结构的分析,提出了一种研究路由查找技术的新思路。本文从分析路由表中地址前缀之间的关系出发,提出了一种分类方法,将地址前缀分为:独立前缀、根前缀、子前缀。然后,采用数据结构Trie 描述地址前缀,定义了地址前缀的级别,提出了路由表结构的概念。通过分析实际路由表,发现:各级别地址前缀数的比例相对固定; 级别的最大值远小于理论值; 与同一IP 地址匹配的地址前缀数较小,即只需要在较少的地址前缀中搜索最长匹配前缀等。通过研究路由发布行为对路由表的增长、结构变化的影响,发现:地址分配策略对路由表中独立前缀、根前缀的长度分布会产生显著的影响,但对子前缀的长度分布没有明显的影响; 用户发布分段的地址前缀是导致独立前缀增长的主要原因之一; 发布子前缀是导致路由查找困难的根本原因等。利用地址前缀级别的定义,提出了一种基于层次划分技术的路由查找算法。路由表中每项地址前缀有唯一的级别,由此,提出了一种按层次划分路由表的方法,将路由表按级别划分为几个部分。各部分路由表中地址前缀互不相交,对于任何IP地址最多有一个匹配的地址前缀,因而在各部分路由表中可采用精确匹配算法查找

论文目录:

摘要

Abstract

1 绪论

1.1 课题的提出、目的、意义

1.2 路由器基本体系结构

1.3 数据转发引擎的发展

1.4 交换结构

1.5 调度技术

1.6 路由查找技术

1.7 本文研究的主要内容

2 BGP 路由表分析

2.1 BGP 协议

2.2 路由表的增长趋势

2.3 路由稳定性

2.4 地址分配策略与路由表

2.5 地址前缀的结构

2.6 影响路由表结构的因素分析

2.7 本章小结

3 基于划分技术的路由查找算法

3.1 路由查找的难点

3.2 当前路由表划分技术

3.3 基于地址前缀层次划分的算法

3.4 算法比较

3.5 本章小结

4 基于TCAM 的路由更新算法

4.1 问题的提出

4.2 基于TCAM 的路由查找原理

4.3 TCAM 更新问题的研究状况

4.4 基于路由表结构的路由更新算法

4.5 本章小节

5 基于访问模式优化TCAM 的能耗

5.1 路由器能耗问题

5.2 TCAM 能耗问题的研究状况

5.3 地址前缀的访问频率及相关的路由查找算法

5.4 TCAM 能耗的优化结构

5.5 性能分析

5.6 本章小结

6 结论与展望

致谢

参考文献

附录1 攻读博士学位期间发表的论文目录

发布时间: 2006-04-05

参考文献

• [1].移动机会网络数据转发与拥塞控制技术研究[D]. 杨轶博.哈尔滨工业大学2018
• [2].社会感知网络路由及激励机制研究[D]. 刘丽.大连理工大学2015
• [3].机会网络数据转发与缓存调度研究[D]. 唐丽均.重庆大学2013
• [4].认知无线网络中协作资源分配研究[D]. 刘志慧.北京邮电大学2016
• [5].基于社会网络的移动容迟网络转发策略研究[D]. 胡桐.中国海洋大学2013
• [6].移动机会网络中路由选择与性能评估研究[D]. 袁培燕.北京邮电大学2013
• [7].基于博弈激励的移动自组织网络关键技术研究[D]. 徐占洋.南京邮电大学2013

相关论文

• [1].路由器高速交换开关调度算法的研究与实现[D]. 孙志刚.中国人民解放军国防科学技术大学2000
• [2].NGI高性能路由器转发处理算法与实现[D]. 王振兴.南京理工大学2004
• [3].多端口路由器并发测试技术研究[D]. 宋波.西南交通大学2005
• [4].T比特高性能路由器QoS实现机制研究[D]. 刘勤让.中国人民解放军信息工程大学2004
• [5].高速路由器中信元与分组调度若干问题的研究[D]. 刘晓冬.中国人民解放军信息工程大学2004
• [6].高性能路由器的服务质量关键技术研究[D]. 庞斌.中国科学院研究生院（计算技术研究所）2003
• [7].高性能IP路由查找和分组分类技术的研究[D]. 郑凯.清华大学2006
• [8].高性能业务路由器系统软件研究[D]. 吉萌.华中科技大学2006

标签：边际网关协议论文;  路由查找算法论文;  地址前缀论文;  无类域间路由论文;  数据转发引擎论文;  二进制树论文;  三元内容寻址存储器论文;