学位论文 > 优秀研究生学位论文题录展示

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

作 者: 吴卫东
导 师: 石冰心
学 校: 华中科技大学
专 业: 通信与信息系统
关键词: 边际网关协议、路由查找算法 地址前缀 无类域间路由 数据转发引擎 二进制Trie树 三元内容寻址存储器
分类号: TN915.05
类 型: 博士论文
年 份: 2005年
下 载: 400次
引 用: 0次
阅 读: 论文下载
 

内容摘要


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

全文目录


摘要  3-5
Abstract  5-9
1 绪论  9-31
  1.1 课题的提出、目的、意义  9
  1.2 路由器基本体系结构  9-10
  1.3 数据转发引擎的发展  10-13
  1.4 交换结构  13-16
  1.5 调度技术  16-22
  1.6 路由查找技术  22-30
  1.7 本文研究的主要内容  30-31
2 BGP 路由表分析  31-45
  2.1 BGP 协议  31-33
  2.2 路由表的增长趋势  33-35
  2.3 路由稳定性  35
  2.4 地址分配策略与路由表  35-39
  2.5 地址前缀的结构  39-41
  2.6 影响路由表结构的因素分析  41-44
  2.7 本章小结  44-45
3 基于划分技术的路由查找算法  45-60
  3.1 路由查找的难点  45-46
  3.2 当前路由表划分技术  46-52
  3.3 基于地址前缀层次划分的算法  52-55
  3.4 算法比较  55-58
  3.5 本章小结  58-60
4 基于TCAM 的路由更新算法  60-74
  4.1 问题的提出  60-61
  4.2 基于TCAM 的路由查找原理  61-63
  4.3 TCAM 更新问题的研究状况  63-64
  4.4 基于路由表结构的路由更新算法  64-72
  4.5 本章小节  72-74
5 基于访问模式优化TCAM 的能耗  74-91
  5.1 路由器能耗问题  74-75
  5.2 TCAM 能耗问题的研究状况  75-77
  5.3 地址前缀的访问频率及相关的路由查找算法  77-79
  5.4 TCAM 能耗的优化结构  79-86
  5.5 性能分析  86-89
  5.6 本章小结  89-91
6 结论与展望  91-93
致谢  93-94
参考文献  94-101
附录1 攻读博士学位期间发表的论文目录  101

相似论文

  1. 低功耗三元内容寻址存储器设计,TP333
  2. 基于TCAM和多核处理器的高速路由查找转发引擎设计,TN915.05
  3. 混沌振子多进制调制解调技术研究,TN915.05
  4. HART无线适配器的研究与设计,TN915.05
  5. 高端分布式交换机端口镜像系统的配置管理,TN915.05
  6. 8PSK+TCM编码调制解调技术,TN915.05
  7. 基于蓝牙技术的数据网关关键技术的研究与实现,TN915.05
  8. 基于软交换的SIP网关的设计与实现,TN915.05
  9. 全数字MSK调制解调器的设计与实现,TN915.05
  10. 带交换功能远程用户接入技术,TN915.05
  11. 智能基础网络资源管理平台中的流程设计与应用,TN915.05
  12. 河北电信固网软交换扁平化方案与实现,TN915.05
  13. 三次群QPSK调制解调器设计与实现,TN915.05
  14. 大容量ATM交换机控制策略及其性能仿真研究,TN915.05
  15. ForCES路由器控制件的可用性模型研究,TN915.05
  16. 输入缓存多播交换技术研究,TN915.05
  17. 以太网交换机集群网管的研究与开发,TN915.05
  18. 三层交换机VLAN模块的设计与实现,TN915.05
  19. 基于CMX909B的GMSK调制解调的研究,TN915.05
  20. 全数字调制解调器研究与设计,TN915.05
  21. 基于物联网网关的研究及实现,TN915.05

中图分类: > 工业技术 > 无线电电子学、电信技术 > 通信 > 通信网 > 一般性问题 > 通信网设备
© 2012 www.xueweilunwen.com