MPLS流量工程中相关约束路由算法的研究

摘要

基于约束的路由选择算法可以根据一个或多个满足服务质量（QoS：Quality of Service）的约束条件，来计算出所有的可行路径，并根据一定的法则从中选出一条最佳的路径。与传统的最短路径优先路由算法相比，基于约束的路由选择算法不仅可以为业务流找出满足其QoS要求的可行路径，而且还可以根据其它的度量方式使业务流均匀合理地分布，从而可以在很大程度上克服最短路径的瓶颈效应、减少拥塞的发生概率、提高网络资源的利用效率、达到网络性能优化的目标。所以研究并提出有效的基于多协议标签交换（MPLS：Multipul Protocol Label Switch）流量工程的约束路由算法，通过实施合理的选路控制，满足业务需求的服务质量，最大限度的优化网络的运行性能，对实际的网络应用具有重要意义。
　　 约束路由算法决定路由如何选择，是流量工程中的核心问题之一，是本课题讨论研究的重点。本文分析了约束路由机制，重点比较了传统的最短路径优先（SPF：Shortest Path First）算法和一般的约束最短路径优先（CSPF: Constrained Shortest Path First）算法。从现有的扩展CSPF路由算法入手，详细介绍最小干扰路由算法（MIRA：Minimum Interference Route Arithmetic），并总结了诸多算法中的优缺点。本文在现有CSPF算法的基础上，提出了一种基于多QoS约束的改进算法，详细论述算法的设计思路和算法流程，分析了算法计算的时间复杂度。改进的算法主要是加入了时延约束机制，从选择最小时延路径集入手，考虑了关键链路的重定位问题，选择时延最小路径集中的瓶颈链路作为关键链路，希望在消耗较少网络资源的同时，使流量负载尽量分布在资源空闲的链路上，以达到网络性能优化的目标。课题利用NS-2搭建了MPLS网络环境，模拟了MPLS流量工程的负载均衡要求。重点借助NS-2仿真平台，分别在树形、环形等不同的复杂网络拓扑环境下，分析比较本课题改进的算法和现有算法的性能差异。文章最后指出了算法研究中存在的不足和下一步的研究方向。
　　 由仿真分析结果可以看到，本文提出的S-CSPF算法在LSP建路请求的接入率、带宽资源利用率、非均衡负载网络环境下的呼叫拒绝率以及计算的时间复杂度等方面都不同程度地优于现有的一些扩展的CSPF算法。S-CSPF算法的提出有利于实际网络的扩展应用，对动态实现基于MPLS的流量工程、均衡网络负载、避免拥塞的发生和优化网络利用率都具有特别重要的意义。

目录

文摘

英文文摘

声明

第一章 绪论

第二章 基于MPLS的流量工程

第三章 约束路由机制的研究

第四章 扩展的CSPF算法研究

第五章 基于多QoS约束的改进算法S-CSPF

第六章 S-CSPF算法的性能评估

第七章 总结与展望

致 谢

参考文献