名空间路由研究和源管理路由算法的分析与建模

论文摘要

网络路由一直是网络的关键问题。今天的计算机网络非常庞大、高速,传载着各种多媒体信息,因此,网络路由面临新的挑战。路由算法层出不穷,目的都是为了寻找满足要求的路径来传递信息。而目前因特网使用的路由算法,主要是基于1959年提出的Dijkstra算法和1962年提出的基于Bellman-Ford算法等理论研究成果。这些经典路由算法都是假设在网络拓扑的基础上定义一个度量,在这个度量的基础上计算每个节点到达其他节点的最短路由,并且为每个子网保持一个路由表项。它们的特点是全局维护,精确路由指向,最短路径路由。随着网络规模不断扩大,子网数量急剧增多,目前全局最优的传统路由算法将面临严重挑战。网络发展趋势引发在理论上重新审视现有路由算法和开拓新路由方案的迫切需求。本文在研究了VRR（Virtual Ring Routing）和ROFL（Routing on Flat Labels）路由算法的基础上,总结出的名空间路由思想：它是基于拓扑独立的路由法则；具有非精确路由指向,每个节点只指向有限个其他可达节点,按照路由法则将信息转发到记录中“最近”指向节点去；非全局路由维护,每个节点只需独立维护各自指定节点的可达性。本文研究了把VRR（Virtual Ring Routing）和ROFL（Routing on Flat Labels）应用到BGP路由协议的可行性,并把这种方法称为源管理路由方案。有如下发现：节点命名对路由性能有明显的影响,而在VRR（Virtual Ring Routing）和ROFL（Routing on Flat Labels）中命名是随机的；拓扑相关的命名策略并不能提高路由性能；核心AS在源管理路由算法中起到重要作用。探讨了源管理路由方案在基于AS商业关系的实际网络拓扑中的可行性,发现：直接把源管理路由方案应用实际AS商业关系的网络拓扑中,源管理路由方案得到的路径并不是都符合BGP路由策略；提出基于分层源管理路由方案建立和维护多条虚拟邻居路径的方法以提供基于AS商业关系的完备路由信息,确保完整路径的有效性。提出了源管理路由算法的理论模型,该路由算法思想虽然简单,却没有理论模型来描述它的路由选择问题以及计算任意节点间的路径长度,尤其是从理论上来评估源管理路由算法的性能。模型中通过利用虚拟环路径这一独特想法来描述路径选择问题,根据源节点和目的节点名字在标识符数值上的距离,分析在虚拟环上出现的所有可能路径的概率,计算在虚拟环上路径的平均跳数,最终估算出实际物理路径的长度。分析影响路由性能的因素,网络中的节点数量,虚拟邻居路径的长度,源节点目的节点名字在标识符数值上的距离以及网络拓扑都影响着源管理路由算法路径长度的分布。通过全面深入的分析源管理路由算法,对其路由效率及可扩展性有了完整的认识,为适应于未来核心网络路由打下坚实的理论基础。针对源管理路由方案中核心节点路由表可能会过于庞大的问题,研究了通过命名来压缩路由表的可能性。提出了一种基于概率的启发性命名算法,通过节点到达连续地址节点的下一跳尽可能相同（并将这些地址是连续的节点用间隔来表示）达到压缩路由表的目的。仿真表明该算法能够很大程度压缩路由表。

论文目录

• 致谢
• 中文摘要
• ABSTRACT
• 缩略语
• 图表清单
• 1 绪论
• 1.1 论文的研究背景及意义
• 1.2 网络路由的研究现状
• 1.3 本文的主要贡献
• 1.4 本文的组织结构
• 2 路由算法和协议
• 2.1 路由算法概述
• 2.2 经典路由算法及协议
• 2.3 Overlay网络路由算法
• 2.3.1 Chord
• 2.3.2 Pastry
• 2.4 名空间路由算法
• 2.4.1 VRR（Virtual Ring Routing）
• 2.4.2 ROFL（Routing on Flat Labels）
• 2.5 本章小结
• 3 名空间路由思想
• 3.1 引言
• 3.2 名空间路由理念
• 3.3 名空间路由与传统路由对比
• 3.4 名空间路由与overlay网络路由对比
• 3.5 本章小结
• 4 源管理路由方案
• 4.1 引言
• 4.1.1 BGP研究热点
• 4.1.2 BGP相关工作
• 4.2 源管理路由方案整体构架
• 4.3 源管理路由方案特点
• 4.3.1 名字特性
• 4.3.2 命名策略
• 4.4 启发性命名算法
• 4.5 仿真分析
• 4.5.1 性能参数
• 4.5.2 仿真结果
• 4.5.3 核心AS
• 4.6 本章小结
• 5 基于AS关系的源管理路由方案
• 5.1 引言
• 5.1.1 AS分类
• 5.1.2 AS的关系
• 5.1.3 AS的路由输出策略
• 5.1.4 Valley free特性
• 5.2 AS关系拓扑图
• 5.3 仿真分析
• 5.3.1 性能参数
• 5.3.2 仿真结果
• 5.4 路由策略的兼容性
• 5.5 分层源管理路由方案
• 5.6 本章小结
• 6 源管理路由算法模型
• 6.1 路由模型
• 6.1.1 虚拟环路径
• 6.1.2 模型假设
• 6.1.3 定义变量
• 6.2 路由模型描述
• 6.2.1 举例简单情况分析
• 6.2.2 无抄近路路径概率分析
• 6.2.3 虚拟环上可能路径概率
• 6.2.4 路径长度分析
• 6.3 仿真分析
• 6.3.1 模型验证
• 6.3.2 影响因素
• 6.3.3 拓扑影响
• 6.3.4 网络统计特征
• 6.3.5 下一步工作
• 6.4 本章小结
• 7 命名与路由表压缩
• 7.1 引言
• 7.2 相关工作
• 7.2.1 完整路由表
• 7.2.2 间隔路由表
• 7.3 基于概率的启发性地址分配算法
• 7.4 仿真分析
• 7.5 本章小结
• 8 结论
• 参考文献
• 作者简历
• 学位论文数据集