骨干网路由表压缩、查找及增量更新技术研究
发布时间：2023-11-04 10:49
近年来，随着互联网规模的不断扩大，骨干网路由表条目数快速增长，给路由表的存储带来了很大的压力，一种有效的解决方案是采用路由表压缩技术。同时，骨干网的链路速率也在不断提高，对路由表查找速度提出了更高的要求。此外，各种新应用使得互联网的动态特性增强，导致路由表更新越来越频繁，而且呈现出突发性，这就要求路由表在实施压缩和提高查找速度的同时，必须具有快速增量更新的能力。本文围绕这三个问题展开研究，取得了如下成果： (1)针对一些路由器无法容纳飞速增长的路由表的问题，采用社会学中种子选举的思想，提出了两种压缩率高、压缩速度快、增量更新快、重压缩周期长的路由表压缩算法；针对前缀重叠给查找和更新带来诸多困难的问题，提出了一种构建最优的无重叠路由表的压缩算法；针对已有路由表压缩算法缺乏理论支持的问题，提出了一套通用的数学分析证明方法。 已有的文献大都在追求高压缩率或快速查找的过程中牺牲了系统增量更新的性能，尚未看到可以很好兼顾这三个问题的解决方案。不同级别的路由器对路由表查找的需求不同，本文针对下面三个典型的场景给出对应的解决方案： (2)场景一：未来互联网需要极高性能的路由器，可以容忍高硬件成本和高...
【文章页数】：126 页
【学位级别】：博士
【文章目录】：
摘要
Abstract
第1章 引言
1.1 研究背景
1.1.1 路由表关键技术和研究意义
1.1.2 工业界和学术界的现状和发展趋势
1.2 主要研究内容和难点
1.2.1 研究内容
1.2.2 研究难点
1.3 主要研究成果和创新点
1.4 论文组织结构
第2章 相关工作综述
2.1 路由表背景知识
2.1.1 RIB 与 FIB
2.1.2 Trie 树和最长前缀匹配规则介绍
2.1.3 TCAM 介绍
2.2 路由表压缩技术综述
2.2.1 路由表压缩算法的前提和衡量指标
2.2.2 现有的路由表压缩算法
2.3 路由表查找技术综述
2.3.1 基于 Trie 树的查找算法
2.3.2 基于 TCAM 的查找技术
2.3.3 基于 Bloom filter 的查找算法
2.3.4 其他查找算法
2.4 路由表更新算法综述
2.5 本章小结
第3章 路由表压缩技术研究
3.1 路由表压缩技术的难点
3.2 EAR 压缩算法
3.2.1 示意图的符号意义
3.2.2 选举算法的社会学思想
3.2.3 EAR 算法的一个简单例子
3.2.4 EAR 算法的原子模型
3.3 两种次优压缩算法
3.3.1 次优压缩算法的社会学思想
3.3.2 EAR-slow 算法模型
3.3.3 EAR-Fast 算法模型
3.4 增量更新算法
3.4.1 多原象问题
3.4.2 更新算法的几个定理
3.4.3 根节点更新问题
3.4.4 增量更新算法描述
3.5 ONRTC 算法
3.5.1 ONRTC 算法描述
3.5.2 ONRTC 算法的快速更新算法
3.6 四种算法的复杂度分析
3.7 压缩算法的理论依据
3.7.1 符号约定与定义
3.7.2 最长前缀匹配群
3.7.3 选举和代表模型
3.7.4 数学证明的应用
3.8 压缩算法的性能评价
3.8.1 实验数据来源与系统配置
3.8.2 六种压缩算法的压缩实验结果
3.8.3 六种压缩算法的更新实验结果
3.8.4 ONRTC 算法的压缩实验结果
3.8.5 ONRTC 算法的更新实验结果
3.9 本章小结
第4章 路由表查找技术研究
4.1 引言
4.2 CLUE：一种并行 TCAM 查找算法
4.2.1 CLUE 的设计思想
4.2.2 CLUE 的分区算法
4.2.3 并行查找机制
4.2.4 新动态冗余机制
4.2.5 系统性能下限
4.2.6 新的增量更新机制
4.3 TDDBF：一种基于 Bloom filter 的查找算法
4.3.1 Bloom filter 简介
4.3.2 TDDBF 算法的由来
4.3.3 TDDBF 算法描述
4.3.4 TDDBF 算法的几种改进方案
4.3.5 Bloom filter 的增量更新机制
4.4 查找算法的性能评价
4.4.1 CLUE 实验结果
4.4.2 TDDBF 实验结果
4.5 本章小结
第5章 路由表更新技术研究
5.1 引言
5.2 盲点算法
5.2.1 盲点算法的由来
5.2.2 盲点算法描述
5.3 盲点算法的应用
5.3.1 应用范围
5.3.2 应用到 Lulea 算法
5.3.3 应用到 LC-trie 算法
5.4 数学分析
5.4.1 盲点算法对查找速度的影响
5.4.2 盲点算法更新复杂度分析
5.5 盲点算法性能评价
5.5.1 实验数据来源与系统配置
5.5.2 盲点特性实验结果
5.5.3 应用到 Lulea 算法的实验结果
5.5.4 应用到 LC-Trie 算法的实验结果
5.6 本章小结
第6章 总结和展望
6.1 工作总结
6.2 工作展望
参考文献
致谢
个人简历、在学期间发表的学术论文与研究成果
本文编号：3860156
【文章页数】：126 页
【学位级别】：博士
【文章目录】：
摘要
Abstract
第1章 引言
1.1 研究背景
1.1.1 路由表关键技术和研究意义
1.1.2 工业界和学术界的现状和发展趋势
1.2 主要研究内容和难点
1.2.1 研究内容
1.2.2 研究难点
1.3 主要研究成果和创新点
1.4 论文组织结构
第2章 相关工作综述
2.1 路由表背景知识
2.1.1 RIB 与 FIB
2.1.2 Trie 树和最长前缀匹配规则介绍
2.1.3 TCAM 介绍
2.2 路由表压缩技术综述
2.2.1 路由表压缩算法的前提和衡量指标
2.2.2 现有的路由表压缩算法
2.3 路由表查找技术综述
2.3.1 基于 Trie 树的查找算法
2.3.2 基于 TCAM 的查找技术
2.3.3 基于 Bloom filter 的查找算法
2.3.4 其他查找算法
2.4 路由表更新算法综述
2.5 本章小结
第3章 路由表压缩技术研究
3.1 路由表压缩技术的难点
3.2 EAR 压缩算法
3.2.1 示意图的符号意义
3.2.2 选举算法的社会学思想
3.2.3 EAR 算法的一个简单例子
3.2.4 EAR 算法的原子模型
3.3 两种次优压缩算法
3.3.1 次优压缩算法的社会学思想
3.3.2 EAR-slow 算法模型
3.3.3 EAR-Fast 算法模型
3.4 增量更新算法
3.4.1 多原象问题
3.4.2 更新算法的几个定理
3.4.3 根节点更新问题
3.4.4 增量更新算法描述
3.5 ONRTC 算法
3.5.1 ONRTC 算法描述
3.5.2 ONRTC 算法的快速更新算法
3.6 四种算法的复杂度分析
3.7 压缩算法的理论依据
3.7.1 符号约定与定义
3.7.2 最长前缀匹配群
3.7.3 选举和代表模型
3.7.4 数学证明的应用
3.8 压缩算法的性能评价
3.8.1 实验数据来源与系统配置
3.8.2 六种压缩算法的压缩实验结果
3.8.3 六种压缩算法的更新实验结果
3.8.4 ONRTC 算法的压缩实验结果
3.8.5 ONRTC 算法的更新实验结果
3.9 本章小结
第4章 路由表查找技术研究
4.1 引言
4.2 CLUE：一种并行 TCAM 查找算法
4.2.1 CLUE 的设计思想
4.2.2 CLUE 的分区算法
4.2.3 并行查找机制
4.2.4 新动态冗余机制
4.2.5 系统性能下限
4.2.6 新的增量更新机制
4.3 TDDBF：一种基于 Bloom filter 的查找算法
4.3.1 Bloom filter 简介
4.3.2 TDDBF 算法的由来
4.3.3 TDDBF 算法描述
4.3.4 TDDBF 算法的几种改进方案
4.3.5 Bloom filter 的增量更新机制
4.4 查找算法的性能评价
4.4.1 CLUE 实验结果
4.4.2 TDDBF 实验结果
4.5 本章小结
第5章 路由表更新技术研究
5.1 引言
5.2 盲点算法
5.2.1 盲点算法的由来
5.2.2 盲点算法描述
5.3 盲点算法的应用
5.3.1 应用范围
5.3.2 应用到 Lulea 算法
5.3.3 应用到 LC-trie 算法
5.4 数学分析
5.4.1 盲点算法对查找速度的影响
5.4.2 盲点算法更新复杂度分析
5.5 盲点算法性能评价
5.5.1 实验数据来源与系统配置
5.5.2 盲点特性实验结果
5.5.3 应用到 Lulea 算法的实验结果
5.5.4 应用到 LC-Trie 算法的实验结果
5.6 本章小结
第6章 总结和展望
6.1 工作总结
6.2 工作展望
参考文献
致谢
个人简历、在学期间发表的学术论文与研究成果
本文编号：3860156
本文链接：https://www.wllwen.com/guanlilunwen/ydhl/3860156.html
