多拓扑生成算法及在流量工程中的应用研究

论文摘要

多拓扑路由技术通过为IP路由器预配置备用路由表,可以实现IP网络的快速恢复。随着IP网络中承载的业务种类越来越多,业务流量越来越大,对IP网络的可靠性,QoS支持能力,业务量工程能力的要求越来越迫切。在这种情况下,发展以IGP为基础的解决方案,使之既能满足上述要求,又对现有基础实施的改动最小,成为业内追求的目标。正是在这样的背景下,MTR的出现受到了极大的关注。针对多拓扑路由在多层IP网络中研究不足的现状,本文首先探讨了多拓扑路由在多层IP网络快速恢复中的应用,提出了两种生成备份拓扑的启发式算法以及一种可以减少IP层备份拓扑数目的重路由算法。展示了这两种启发式算法的性能及其与求解ILP模型得出的最优解的差距。对于重路由算法,研究了IP层链路的物理路由的均衡程度对于备份拓扑数目的影响。通过仿真结果的对比分析,展示了重路由算法的性能及其与IP层物理路由“均衡引导”的可结合性。其次,探究了多拓扑在流量工程中的应用:通过合理设计各个路由拓扑的权重,来达到流量叠加后最大链路利用率最小的优化目标。提出了一种将业务量均摊到多拓扑的联合权重优化方法,在初始路由拓扑权重的基础上,重新规划部分链路权重,以降低网络的拥塞程度。同时也探讨了更改路由拓扑数量对流量均衡的影响,通过仿真可以看出,在路由器上备份少量路由拓扑即可获得较大的性能改善。最后,讨论了如何在链路失效时,既保证路由器能够本地无时延的切换到相应备份拓扑,又能使业务量在全网尽可能的流量均衡。提出了一种基于单链路失效的多拓扑流量均衡算法,通过改变备份拓扑中的链路权重,使得在单链路失效的情况下,全网业务量依旧比较均衡的目的。对比了基于多拓扑与单拓扑在单链路失效情况下的最大链路利用率,并展示了通过备份少量拓扑即可获取较好的网络抗毁性能的可行性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 IP 网络的多拓扑路由概述
• 1.1.1 IP 网络的快速恢复
• 1.1.2 多拓扑路由在 IP 网络快速恢复中的应用
• 1.2 多层 IP 网络构架概述
• 1.3 多拓扑路由中的流量均衡概述
• 1.4 多拓扑路由中的流量均衡研究现状及不足
• 1.5 全文的主要贡献与内容安排
• 第二章 多层网络构架下的多拓扑生成算法研究
• 2.1 问题描述
• 2.1.1 背景介绍
• 2.1.2 ILP 模型
• 2.2 多拓扑生成算法
• 2.2.1 基于孤立链路的多拓扑生成算法
• 2.2.2 基于构造最小生成树的多拓扑生成算法
• 2.3 一种减少 IP 层备份拓扑数目的重路由算法
• 2.3.1 初始备份拓扑的产生
• 2.3.2 初始备份拓扑的内部疏导
• 2.3.3 重路由算法的主要步骤
• 2.4 IP 层链路物理路由的均衡程度对备份拓扑数目的影响
• 2.4.1 最优的物理路由
• 2.4.2 一种简单的均衡引导算法
• 2.5 仿真结果与分析
• 2.5.1 随机拓扑生成算法
• 2.5.2 备份拓扑的平均路由长度
• 2.5.3 IP 层备份拓扑生成算法的仿真结果
• 2.5.4 重路由算法仿真结果
• 2.5.5 IP 层链路物理路由的均衡程度对备份拓扑数目影响的仿真结果
• 2.6 算法的仿真实现
• 2.6.1 仿真平台的总体框架
• 2.6.2 仿真软件源代码中的主要类
• 2.7 本章小结
• 第三章 多拓扑路由中的流量均衡研究
• 3.1 问题描述
• 3.2 业务量矩阵分割问题的 ILP 模型
• 3.3 一种业务量分割和多拓扑权重设计的联合优化算法
• 3.3.1 初始权重的产生以及归一化流量分布的计算
• 3.3.2 ECMP（Equal Cost Multipath Routing）等价多路径分流算法简介
• 3.3.3 多拓扑权重优化的主要步骤
• 3.3.4 归一化流量分布的更新
• 3.3.5 业务量分割和多拓扑权重设计的联合优化算法综述
• 3.4 路由拓扑的数目对流量均衡的影响
• 3.5 仿真结果与分析:通过更改路由拓扑数量对流量均衡的影响
• 3.5.1 测试网络如下图所示
• 3.5.2 不同路由拓扑数量下的最大链路利用率
• 3.5.3 不同路由拓扑数量下的最大链路利用率的仿真结果
• 3.5.4 仿真结果分析
• 3.6 本章小结
• 第四章 多拓扑路由中基于单链路失效的流量均衡研究
• 4.1 问题描述
• 4.2 一种业务量转移和多拓扑权重设计的联合优化算法
• 4.2.1 初始参考拓扑的权重优化迭代
• 4.2.2 剩余业务量矩阵的提取方法
• 4.2.3 多拓扑权重联合优化算法
• 4.3 仿真结果与分析一:单失效情况下的最大链路利用率对比
• 4.3.1 测试网络如下图所示
• 4.3.2 单失效时多拓扑下最大链路利用率与单拓扑下最大链路利用率对比
• 4.3.3 单失效情况下的最大链路利用率对比的仿真结果
• 4.3.4 仿真结果分析
• 4.4 仿真结果与分析二:通过更改备份拓扑数量对流量均衡的影响
• 4.4.1 测试网络如下图所示
• 4.4.2 备份拓扑数量对最大链路利用率的影响的仿真结果
• 4.4.3 仿真结果分析
• 4.5 本章小结
• 第五章 全文总结
• 5.1 研究工作总结
• 致谢
• 参考文献
• 攻硕期间取得的研究成果
• 个人简介