《MPLS流量工程中动态路由算法研究》由会员分享，可在线阅读，更多相关《MPLS流量工程中动态路由算法研究（65页珍藏版）》请在金锄头文库上搜索。
1、辽宁工程技术大学硕士学位论文MPLS流量工程中动态路由算法研究姓名：王红申请学位级别：硕士专业：计算机应用技术指导教师：刘建辉20051201辽宁工程技术大学硕士学位论文摘要流麓工程的阉题已经研究多年，人们提出了多种解决方法，但较传绕酶解决方案辛妥篦，M P L s 实藏滚量工程曩有更多豹魏势。M P L S 流量工程的问题最终可以归结为数据流传输的路径确定问题，即鼹式路径的确立问题，所以研究流量工程动态路由簿法的终哀条侮器嚣瑟瑟鼗，拭瑟建立算法瓣数学模麓释舞法栽赠对手动态实观基于M P L S 的流量工程具有特别重要的意义。本文通过对路由算法的分析与研究，在x u 飘算法的魁础上提出了一糖耨
2、的动态路鑫算法一L P R 并绘出了路径均餐度数概念，本文不德介绍了L P R 算法的具体实现，同时还通过仿真实验验证了该算法较x u E 及S P F 算法的优越陛。关键强：流量工程M P L S 缀式路出路径均衡缓X U EL P R堑主三堡垫查查兰婴主兰焦笙奎生A b s t r a c tT h ep r o b l e mo ff r a f f i ce n g i n e e r i n gh a s r e s e a r c h e df o ry e a r s ，a n dt h ep e o p l eh a v ep r o p os e dm a n yr e s
3、o l v e n t s ，b u tw i t hM P L St oi m p l e m e n tt r a f f i ce n g i n e e r i n gh a st h ea d v a n t a g eo ft h et r a d i t i o n a ls c h e m eT h ep r o b l e mo fM P L St r a f f i ce n g i n e e r i n gc a nc o m ed o w nt ot h ep a t hc o n f i r m e dw h i c ht h ed a t as t r e a m
4、t r a ns f e r s ，n a m e l ye x p l i c i tr o u t ee s t a b l i s h e d ，S Ow er e s e a r c ht h ec o n s t r a i n tc o n d i t i o na n d a i mf u n c t i o no ft h et r a f f i ce n g i n e e r i n gd y n a m i cr o u t i n ga l g o r i t h m ，b u i l dt h em a t hm o d e lo ft h ea l g o r i
5、 t h m ，a n dg i v et h er o u t i n gr u l e s ，t h a th a ss p e c i a li m p o r t a n tm e a n i n g sf o rd y n a m i cr e a l i z a t i o no ft r a f f i ce n g i n e e r i n gb a s e do nM P L SI n t h i sp a p e r ，w ep r o p o s ean e wd y n a m i cr o u t i n ga l g o r i t h mn a m e dL P
6、 Rb a s e do nX U Eb ya n a l y z i n ga n dr e s e a r c h i n gr o u t i n ga l g o r i t h ma n dg i v ea ni d e ao fp a t hl o a d i n ge q u i l i b r i u mW en o to n l yp r e s e n tt h ed e t a i lr e a l i z a t i o no fL P R ，b u tv a l i d a t et h ea d v a n t a g eo ft h i sa l g o r i
7、t h mc o m p a r i n gw i t hX U Ea n dS P Fa l g o r i t h mb yS i m u l a t i o nK e y w or dS ：T E ；M P L S ；e x p l i c i tr o u t i n g ；p a t hl o a d i n ge q u i l i b r i u m ；X U EL P R创新点声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果：针对，M P L S 一咧缀，首先对= ! E 算法进行分析研窥_ 指出工一X 娥一算揍走加丛耄鏖网终烫短忿配均衡簧局限i
8、然后钍怼蝼局限性提出工= 弛荔的秘蠢路由箬挂= L P 黔同尉在蘧算法史给出工照径均衡麋的概盒_ 一差通过仿篡塞殓验证工壕集迭较S P F及X U E 算法的有效性。尽我所知，到目前国内外文献未见报道。作者：三丝日期：墨! ! 兰! 辽宁工程技术大学硕十学位论文11 绪论1 1 研究背景随着I n t e r n e t 的迅猛发展，I n t e r n e t 上的业务种类也与日俱增，除了传统的数据传输，语音、图像等应用也越来越多，目前已经在I n t e r n e t 网上开通了I P 电话、电视会议等业务，这些实时业务对网络的延迟、带宽、抖动有严格的要求。随着网络应用和用户不断增加，
9、网络的规模和复杂性不断提高，带宽等网路资源的增长速度却远远落后，这使得目前以I P 协议为主的计算机网络在满足业务的各种Q o S 要求时越来越显得力不从心。传统的路由算法( 如O S P F 、I S I S ) ，通常从节省网络资源消耗出发，采用的是基于目的地址的最短路径路由，即选择到目的地址度量( 如距离、跳数、代价等) 最短的一条路径。其优点是实现起来非常简单，但其固有弱点在于不能根据网络资源的利用情况来选择不同的路径，从而导致某些网络节点的拥塞，而有些链路没有得到充分利用，造成网络资源没有得到有效利用。为了对最短路径造成的负载不均衡进行改善，后来在O S P F 中提出I ：r等价多
10、路径( E C M P ，E q u a lC o s tM u l t i - - P a t h ) 的方法。它将负载分摊到多条代价相等的最短路径上。但它要求每条代价相等的最短路径承担相同份额的负载，而不能根据每条路径的拥塞情况动态修改这些路径问负载分担的比例，所以当来自多个源的业务流都经过某条路径时，这条路径的负载就会比其他路径高，造成拥塞，并且要求负载只能在相同代价的路径间分担，不同代价的路径不能分担，可见其调节作用也是非常有限的。针对用户和I S P 对I n t e r n e t 的需求，目前I n t e r n e t 网路迫切需要解决的问题是如何保证服务质量( Q o S
11、) ，如何有效管理和利用网络资源，在这种形势下，提出了流量工程( T r a f f i cE n g i n e e r i n gT E ) 问题。将业务流有策略地映射到现有物理链路E 的任务称为流量工程，流量工程是一个强有力的工具，是一个控制业务流如何经过网络，以达到优化网络资源利用、提高网络性能目的的过程。通过它可以平衡网络中不同的链路、路由器和交换辽宁工程技术大学硕士学位论文2机之间业务负荷，使所有这些网络设备既不会过度使用，也不会未被充分使用，这样I S P 就可以有效利用整个网络的资源，同时终端用户所感受到的网络服务质是将得到显著的增强。在未来的主干网络中，流量工程将成为路由结构
12、中个重要的辅助部分，它能够在沿网络中备选路径转发业务时提供辅助信息。流量工程在选择通路时往往并不选择两个设备之间的最短路径，即便是源结点和目的结点完全相同的两个数据流，在流量工程中也可能走完全不同的两条路径。通过这种方式，网络中那些负荷较轻的网段和链路能够得到充分利用，同时也减轻了繁忙网段及链路的负荷。整个网络的流量就可以被均匀分摊给全网各结点。在早期基于路由器的核心网中，流量工程技术是通过简单地使用路由量度值( M e t r i c ) 来实现的。即给每条链路规定一个量度值，两点之间的路由是按照一定的策略计算量度值后来确定的。因为那时无论从路由器数量、链路数还是业务流量来讲，I n t e
13、 r n e t 骨干网都是非常小的，所以基于量度的控制是足以胜任的。同时，在w w w 普遍流行之前，I n t e r n e t 的拓扑层次也强制业务流通过网络中较为确定的路径，不会产生临时“热点”。随着I P 网络规模越来越大，基丁二量度的流量控制就越来越显出它的局限性。目前，解决I G P 协议簇的上= 述缺陷的较流行的方式是使用重叠模型技术，例如I P o v e r A T M 、I P o v e r F R 等。重叠模型在网络的物理拓扑结构上提供了一个自由的虚拟拓扑结构，从而扩展了网络设计的空间。这种虚拟拓扑结构由虚电路构成，在1 G P 路由协议看来，这些虚电路就相当于过去
14、的物理链路。重叠模型还提供了许多其他重要的业务来支持流量与资源控制，依靠这些功能可以实现许多流量工程策略。然而基于A T M 的核心网的个最根本的局限性是它需要对两个不同的网络进行管理：A T M 基础结构和逻辑的I P 覆盖。在A T M 网上运幸亍I P 网络，不仅增加了网络的复杂性，而且加倍了开销，因为I S P 必须管理和协调两个分离网络的运行。同时，路南和流量工程分别在不同的系统上来完成一路由在路由器上执行，流量工程则在A T M 交换机上完成。因此，将流量工程完全与路由集成在一起将是非常困难的。辽宁工程技术大学硕上学位论文3M P L S 技术的出现解决了覆盖模型的复杂性和难以扩展
15、的问题。M P L S技术是I E T F 正在秘极研究并大力推广的一种新的数据转发机制。它处在数据链路层和网络层之间，在克服I P 对于流量工程的局限性方面具有显著的优势。流量工程是通过将大量的用户业务转移到经过服务提供商网络中特定节点的预先设定的路径来实现的。这些预先设定的路径被称作标记交换路径( L S P ) 。M P L S 被认为是下一代I n t e r n e t 骨干网络技术，已经得到业内人士的普遍认可。将M P L S 用于实施流量工程，是M P L S 最具吸引力的应用。M P L S 流量工程的赢接用户将是大型I S P ，为了在现有网络上提供尽量好的服务和获得最大利润
16、，最大程度利用现有网络资源，优化网络的运行性能，I S P 必然借助于流量工程。因此，M P L S 流量工程本身的应用前景十分广泛。目前，M P L S 被认为是流量工程的最有力工具，基于M P L S 的流量上程受到业界的普遍关注，也是M P L S 研究领域的一个热点。M P L S技术在解决流量工程问题方面具有的独特优势使它成为新的流量工程解决方案的有力武器和必须之选。流量工程研究的主要目标是如何根据网路流量与资源的状态，通过实施合理的控制，使流量均衡地分布在现有的网络中，同时保证业务数据的服务质量( Q o S ) ，最大限度地优化网络的运行性能。对于利用M P L S 实施流量工程，从世界范围来看，还仅处在实验和研究阶段。J U N I P E R 等各大网络公司虽然推出了各自的M P L S 产品，但仅仅是停留在实现标记交换的层次上，无法很好的支持流量工程。因此，建立有效实施M P L S 流量工程的系统模型是很有必要的。因为M P L S 流量工程的问题最终可以归结为数据流传输的路径确定问题，即显式路径的确立
