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的流量工程、均衡网络负载、避免拥塞的发生和优化网络利用率都具有特别重要的意义。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 课题的提出
• 1.2 课题的研究现状
• 1.3 本文主要工作和内容安排
• 第二章 基于MPLS的流量工程
• 2.1 MPLS技术的基本原理
• 2.2 MPLS网络节点结构
• 2.2.1 MPLS网络结构
• 2.2.2 MPLS节点结构
• 2.3 MPLS标签分发机制
• 2.3.1 标签分发协议
• 2.3.2 资源预留协议
• 2.3.3 扩展的RSVP
• 2.3.4 扩展的LDP
• 2.3.5 RSVP-TE和CR-LDP的比较分析
• 2.4 MPLS工作流程
• 2.5 从流量工程的角度分析IP网络的不足
• 2.5.1 IP路由问题
• 2.5.2 流量划分问题分析
• 2.6 MPLS流量工程的体系结构
• 2.6.1 分组转发单元
• 2.6.2 信息发布单元
• 2.6.3 路径选择单元
• 2.6.4 信令单元
• 2.7 MPLS流量工程的基本原理
• 2.7.1 实现MPLS流量工程需要解决的基本问题
• 2.7.2 流量中继属性和特征
• 2.7.3 资源特性
• 2.7.4 约束路由
• 第三章 约束路由机制的研究
• 3.1 约束路由算法概述
• 3.1.1 约束路由算法的稳定性
• 3.1.2 约束路由算法的特点
• 3.2 约束路由算法的度量参数
• 3.2.1 约束路由算法的度量参数分类
• 3.2.2 常用的度量参数选择方法
• 3.3 约束路由算法的分类
• 3.3.1 QoS路由算法与TE路由算法
• 3.3.2 离线路由算法与在线路由算法
• 3.3.3 单约束路由算法与多约束路由算法
• 3.3.4 精确信息路由算法与非精确信息路由算法
• 3.3.5 单路径路由算法与多路径路由算法
• 第四章 扩展的CSPF算法研究
• 4.1 SPF算法和CSPF算法的比较分析
• 4.1.1 传统的SPF算法描述
• 4.1.2 CSPF算法描述
• 4.2 计算约束路由的数学描述
• 4.3 现有的扩展CSPF算法研究
• 4.3.1 SDP算法
• 4.3.2 WSP算法和SWP算法
• 4.3.3 MIRA算法
• 4.4 MIRA算法分析
• 4.4.1 网络最大流的数学模型
• 4.4.2 MIRA算法的问题定义
• 4.4.3 MIRA算法的数学模型
• 4.4.4 MIRA算法流程描述
• 第五章 基于多QoS约束的改进算法S-CSPF
• 5.1 S-CSPF算法的提出
• 5.2 问题定义
• 5.3 算法核心思想
• 5.3.1 接受建路请求能力
• 5.3.2 关键链路
• 5.4 算法流程
• 5.5 算法复杂度分析
• 第六章 S-CSPF算法的性能评估
• 6.1 仿真平台介绍
• 6.1.1 NS-2 仿真原理
• 6.1.2 NS-2 网络仿真的一般方法
• 6.2 基于NS-2 模拟MPLS网络环境
• 6.3 扩展的CSPF算法性能评估
• 6.3.1 网络资源利用效率
• 6.3.2 带宽利用率
• 6.3.3 非均衡负载网络的资源利用
• 6.3.4 算法的计算复杂度
• 第七章 总结与展望
• 7.1 本文工作总结
• 7.2 未来工作展望
• 致谢
• 参考文献