（计算机应用技术专业论文）mpls流量工程与约束路由算法的研究.pdf

摘要 进入2 1 世纪，随着i n t e m e t 的发展不断加快，每天都有新的内容加入，网 络中的流量也越来越大，不同类型的业务流层出不穷。在传统砰网络的基础上。 这些业务流要求各式各样的服务质量( q o s ) 保证，比如更高更可靠的传输效 率、动态的路由调整、灵活的网络控制能力等。但是目前的传统l p 网络采取的 是尽力而为的传送方式，主要采用最短路径算法选择路径，忽略了网络可用链 路容量和业务本身的要求，因此会导致整个网络的利用率没有达到最佳。 基于多协议标签交换( m u l t i p r o t o c o ll a b e ls w i t c h i n g ，简称m p l s ) 网络 的流量工程可以很好地适应新的业务流要求，流量工程可以对网络中的业务流 进行精确控制，在满足业务流o o s 前提下使网络资源尽可能的合理利用，同时 能够接入更多的业务，提高全网利用率。本文对基于m p l s 的流量工程 ( m p l s - t e ) 进行了深入的研究与分析，着重研究其关键技术：基于约束的路 由算法。基于约束的路由算法对收集到的网络信息进行分析，并在一定条件的 限制下计算路由，通过对网络中多种因素的考虑来找到一条负载较轻的路径， 进而达到提高网络效率的目的。 本文首先介绍m p l s 技术的基本原理，给出了流量工程的基本概念和处理 模型，在此基础上分析了如何基于m p l s 技术实现流鼍工程，并总结了 m p l s t e 的优越性。 其次，分析了当i i 的约束路由算法，针对单路径算法的路径建立成功率较 低的局限性，提出了一种基于约束的最小带宽多路径路由算法，该算法通过寻 找最适合的可用带宽路径来满足较大带宽约束请求的一部分，并循环这样的过 程直到将所有的带宽请求分配到多条路径中，达到以最少的路径数目，增加带 宽约束路径建立成功率的目的。 最后，通过仿真实验与传统路由算法做出比较，并验证这种基于带宽约束 的多路径路由算法对于满足较大带宽约束请求具有更高的成功率，并且能够更 好的均衡网络负载。 关键词：服务质量；多协议标签交换；流量工程；约束路由算法；多路径路由 算法：n s 仿真 l i a b s t r a c t w i t ht h ef a s td e v e l o p m e n to ft h ei n t e r n e ti nt h e2 1 “c e n t u r y , n e wc o n t e n ti s a d d e de v e r y d a y ，f l o w si nt h en e t w o r ka r ea l s og r o w i n g , a n dd i f f e r e n tt y p e so f b u s i n e s sf l o w sa r ev a r i o u s t h e s ef l o w sr e q u i r eaw i d er a n g eo fq u a l i t yo fs e r v i c e ( o o s ) g u a r a n t e e so n t h eb a s i so ft r a d i t i o n a li pn e t w o r k f o re x a m p l e ，h i g h t r a n s m i s s i o ne f f i c i e n c y , d y n a m i c - r o u t i n ga d j u s t m e n t ，f l e x i b l en e t w o r kc o n t r o l c a p a b i l i t y , e t c b u tt h et r a d i t i o n a li pn e t w o r k , u s i n gt h es h o r t e s tp a t ha l g o r i t h mt o c h o o s ep a t h ，i st h eb e s t - e f f o r td e l i v e r ym o d e t h i sm e t h o do v e r l o o k st h ea v a i l a b l e n e t w o r kl i n kc a p a c i t ya n dt h eb u s i n e s s sr e q u e s t i tw i l lc a u s et h ee n t i r en e t w o r k w o r kw i t h o u tt h eu t i l i z a t i o no ft h eb e s t t h et r a f f i c e n g i n e e r i n gb a s e d o n m u l t i p r o t o c o ll a b e ls w i t c h i n g ( m p i s ) i sa d a p t e dt ot h e s er e q u e s t s i tc a l lp r e c i s e l y c o n t r o lt h eb u s i n e s sf l o wi nt h en e t w o r k ，r a t i o n a l l yu s en e t w o r kr e s o u r c e s ，a c c e s s m o r eb u s i n e s s ，a n di m p r o v en e t w o r ke f f i c i e n c y i nt h i sp a p e r w es t u d ya n da n a l y z e m p l s - b a s e dt r a f f i ce n g i n e e r i n g ( m p l s - t e ) w i t haf o c u so ni t sk e yt e c h n o l o g y ： c o n s t r a i n t - b a s e dr o u t i n ga l g o r i t h m t h ec o n s t r a i n t b a s e dr o u t i n ga l g o r i t h ma n a l y z e s t h ec o l l e c t e dn e t w o r ki n f o r m a t i o na n dc a l c u l a t e sr o u t i n gu n d e rc e r t a i nc o n s t r a i n t s g i v i n gc o m p r e h e n s i v ec o n s i d e r a t i o nt ot h ev a r i o u sf a c t o r so nt h en e t w o r k ，w et r yt o f i n dal i g h tl o a dp a t ht oi m p r o v en e t w o r ke f f i c i e n c y t h i sp a p e rf i r s ti n t r o d u c e st h eb a s i cp r i n c i p l eo fm p l sa n di m p o r t st h eb a s i c c o n c e p ta n dw o r km o d e lo ft e o nt h i sb a s i s ，w ea n a l y z eh o w t oa p p l ym p l st ot e a n ds u m m a r i z et h ea d v a n t a g eo fm p l s t e s e c o n d l y t h ee x i s t i n gc o n s t r a i n t b a s e dr o u t i n ga l g o r i t h ma r ec l a s s i f i e da n d a n a l y z e d w ep u tm i n i m u mb a n d w i d t hm u l t i p a t hc o n s t r a i n t - b a s e dr o u t i n ga l g o r i t h m t ob r e a kt h el i m i t a t i o n so fs i n g l e p a t ha l g o r i t h m sl o ws u c c e s sr a t e t h ea l g o r i t h m f i n d st h em o s ts u i t a b l ep a t ho ft h ea v a i l a b l eb a n d w i d t ht om e e tp a r to fal a r g e b a n d w i d t hc o n s t r a i n ta n dk e e pt h i sp r o c e s su n t i la l lb a n d w i d t hi sa l l o c a t e dt om o r e p a t h s ，t or e a c ht h ep u r p o s et h a ti n c r e a s e st h es u c c e s sr a t e o ff i n d i n gb a n d w i d t h c o n s t r a i n tp a t hw i t hf e w e s tp a t h s f i n a l l y , w ec o m p a r et h es i m u l a t i o nr e s u l t sw i t ht r a d i t i o n a lr o u t i n ga l g o r i t h m ， 1 1 1 v e r i f yt h a tm u l t i - p a t hc o n s t r a i n t - b a s e dr o u t i n ga l g o r i t h mw i t hm i n i m u mb a n d w i d t h h a sh i g h e rs u c c e s sr a t et h a nt r a d i t i o n a l s i n g l e p a t h c o n s t r a i n t - b a s e d r o u t i n g a l g o r i t h md o e si nm e e t i n gl a r g eb a n d w i d t hr e q u e s t , a n dt h e r e f o r ep r o v et h e yh a v e g r e a te f f e c to nb a l a n c i n gn e t w o r kl o a d k e y w o r d s ：q o s ；m p l s ；t e ；c o n s t r a i n t - b a s e dr o u t i n ga l g o r i t h m ；m u l t i - p a t h r o u t i n g a l g o r i t h m ；n ss i m u l a t i o n i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包括其他人已经发表或撰写过的研究成 果，也不包含为获得西北师范大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示了谢意。 签名：三蚴同期：垄堕三：i 关于论文使用授权的说明 本人完全了解西4 lr ) 巾范人学有关保留、使用学位论文的规 定，即：学校有权保留送交论文的复印件，允许论文被查阅和借 阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印 或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：兰蚴导师签名：生垦邀日期：2 苎0 ：皇三f 1 1 研究背景 第一章绪论 近年来，随着i n t e r a c t 的迅速发展，其网络规模和所承载的业务流量不断增 长，平均每个月网络规模增长1 0 左右，每6 9 个月网络流量翻一番。同时由 于网络技术的发展与融合，网络上业务流量发生了两极分化，一方面是传统的 电子邮件、f t p 、w w w 浏览等服务决定了计算机网络的灵活传送机制的必要 性，另一方面是m 电话、视频会议、可视电话和在线影视等流式多媒体的广泛 应用又要求计算机网络支持许多电信网的特征【1 1 ，而且这些业务的传递不再仅 仅需要具有可达性，而更多需要保证业务的服务质量( o u a l i t yo fs e r v i c e ， 0 0 s ) 1 2 。这些多媒体业务对于时延、抖动、丢包率等服务质量具有严格的要求。 但是在目前，m 网络是面向传统数据业务设计的，并没有部署服务质量的 概念，采取的是尽力而为( b e s t e f f o r t ) 1 3 , 4 j 的传送方式，这种方式并不能保证足 够的带宽和符合要求的传输时延，并且由于i p 路由协议本质上是无连接的，只 是基于目的l p 地址，利用最短路径算法选择路径，忽略了网络可用链路容量和 业务本身的要求，因此会导致整个网络的利用率没有达到最佳。如图1 - 1 所示 网络，r 1 到r 8 和r 2 到r 8 的业务流在最短路径算法的情况下部选择 r 3 r 5 r 7 路径，导致r 3 r 5 一 r 7 过载，同时r 3 一 r 4 r 6 r 7 却闲置不用， 浪费了网络资源，同时又造成网络拥塞，影响业务性能。 图1 ，- 1 传统l p 网络问题 为了最大限度的利用现有资源来为用户提供可靠的服务，就需要实施流量 工程( t r a f f i ce n g i n e e d n g ，t e ) 。流量工程1 5 l 的目的是实现对网络中业务流的精 确控制，在满足业务流o o s 要求的i j 提下使网络资源尽可能合理使用，避免出 现网络拥塞：同时能够接入更多的业务，提高全网利用率，降低网络运营成本。 可以说，网络流量的不断增长和对资源的渴求是实施流最工程的内在因素，资 西北师范大学硕l ：学位论文 第一章绪论 源的优化利用和i s p ( i n t e m e ts e r v i c ep r o v i d e r ) 投资回报率的提高是实施流量工 程的外在因素。 1 2 相关技术的研究现状 1 2 1m p l s - t e 的提出背景及研究现状 早期的流量工程只是通过简单的改变路由度量值( m e t r i c ) 来实现的，即给 每条链路规定一个度量值，两点之间的路由是按照一定的策略计算度量值后来 确定的。因为那时无论从路由器数量、链路数还是业务流量来讲，i n t e r n e t 骨干 网都是非常小的，所以基于度量的控制是足以胜任的。同时，在w w w 普遍流 行之前，i n t e m e t 的拓扑层次也强制业务流通过网络中较为确定的路径，不会产 生临时“热点”。但随着网络规模的不断扩大，由于网络中路由的交互作用，部 分链路度量的改变常常会影响到网络中的其他路径，导致全网范围的、无法意 料的流量抖动。而且这种方式并不能克服l p 路由协议只基于拓扑驱动而不考虑 业务负载要求的固有局限，无法真正达到全网的优化配置。 为了克服以上问题，人们引入了a t m ( a s y n c h r o n o u s t r a n s f e r m o d e ) 技术 l “，利用a t m 面向连接的特性，在骨于网上实旌流量工程。基于a t m 核心的 网络采用了一种i p o v e r - a t m 的覆盖模趔，即i p 运行在a t m 网络上，路山器 在a t m 网络边缘环绕，每个路由器通过一系列经由a t m 物理拓扑配置的永久 虚电路( p v c ) 与其他路由器通信。路由器并不能直接访问a t m 结构中p v c 的具体物理拓扑信息，仅了解特定的p v c ，就像出现在两个路由器之间的简单 的点到点电路。 基于a t m 的核心网完全支持流量工程，因为它可以对p v c 进行明确路由。 p v c 的路由是通过在网络底层的物理拓扑上提供随机的虚拟拓扑实现的，而在 网络底层的物理拓扑上，通过对p v c 进行路由以使业务分配到所有链路上，以 致链路被平均使用。这种实现避免了业务全部汇集到低花费路由上去，从而不 会造成链路的过分使用或未充分使用。但是i p - o v e r - a t m 方式的一个最根本的 局限性是它需要对两个不同的网络进行管理：a t m 基础结构和逻辑的i p 覆盖。 不仅增加了网络的复杂性，而且需要进行信元转换，加倍了开销，造成资源浪 费：而且随着核心路由器技术的发展，a t m 骨干网将逐渐被路由器所取代。因 此，如何在未来的i p 网络实现流量工程就成为i s p 面临的一大问题。 2 西北师范人学硕十学位论文第一章绪论 为了解决上述问题，1 9 9 7 年，以c i s c o 公司为主的几家公司提出了多协议 标签交换( m p l s ) 技术。m p l s 是i n t e r n e t 核心网中的路由转发技术的最新发 展，它可以将网络层i p 路由的控制能力和第二层交换1 7 i 的简单性无缝地集成起 来。而且，因为m p l s 解决了许多复杂的问题，它为支持先进路由服务的配置 提供了基础，这些复杂问题包括： 1 ) m p l s 解决了普遍使用的i p - o v e r - a t m 覆盖模型【8 l 的可扩展性问题。 m p l s 明显减少了网络运行的复杂程度。 3 ) m p l s 简化了用于增强传统腰路由技术的新型路由能力的推出过程。 钔m p l s 提供了一个基于标准的解决方案【们，从而保证了多个厂商之间的 互操作性。 m p l s 引入了a t m 提出的流量工程的概念，与a t m 相比，m p l s 协议的 可扩展性强。它不仅支持不同的路由协议以及各种网络层协议，而且支持不同 的链路层协议，尤其适合广域网互联。m p l s 的功能划分更为合理，增强了边 缘节点的智能性，它将负载的拥塞控制1 1 0 l 、流量控制【1 1 l 等功能推到网络边缘节 点去完成，核心网络只负责完成传送功能，简化了网络管理。与a t m 覆盖型路 由器网络比较，需要建立互联的路由器实体被缩减为标签交换路由器【1 2 1 ( l a b e l s w i t c hr o u t e r ，l s r ) 和直接与l s r 相连的路由器。边缘标签交换路由器( l a b e l e d g e r o u t e r ，l e r ) 不需要与m p l s 域中每个l e r 相连，减少了虚电路数鞋， 扩展性好，易于管理配置。确定的路由选路策略，使数掘在网络中的流动变得 可以人为控制。利用这种技术数掘流可以更为高效的利用网络资源，使网络性 能得到优化和提高。 对于m p l s - t e ，目的己提出了一些相关的r f c 和大量的i n t e m e t 草案，如 r f c 2 7 0 2 描述了在m p l s 网络中实施流量工程的要求，r f c 3 3 4 6 总结了 m p l s t e 的适应性。然而，虽然m p l s - t e 的标准已初步完善，但一些相关技 术仍在发展中，如约束路由等，而且国内的研究多停留在理论阶段，对于 m p l s - t e 的实现涉及较少，这些都有待于进一步研究。 1 2 2 约束路由算法的提出背景及研究现状 基于m p l s 流量工程的约束路由算法是实现m p l s 流量工程的重要组成部 分，也是实现q o s 业务的关键。传统的路由协议尽管采用了不同的思想和机制， 但考虑的都是拓扑结构中链路的可连通性，没有涉及到网络的资源使用情况。 3 西北师范大学碗十学位论文 第一章绪论 传统路由协议中所采用的路径选择算法也通常是只考虑单一的度量参数，如跳 数或时延等。现有的i n t e r n e t 路由基于目的i p 地址逐跳寻路1 1 3 l ，没有考虑网络 资源有关参数如带宽等。由于网络规模的不断发展，使得网络资源使用情况变 得紧张，链路误码率高、传输速率小，并将会在很大程度上影响业务的可靠传 输，使用具有约束条件的路由已经显得十分重要。 基于约束的路由选择技术是从o o s 路由选择技术【1 4 l 发展而来的，它可以根 据一个或多个o o s 的约束条件来计算出所有的可行路径，并根据一定的法则从 中选出一条路径。与传统的最短路径优先路由算法相比，基于约束的路由选择 算法不仅可以为业务流找出最可能满足其o o s 要求的可行路径，而且还可以根 据其他的度量方式使业务流均匀合理的分布，从而可以在很大程度上克服最短 路径的瓶颈效应、减少拥塞的发生概率、提高网络资源的利用效率。 基于约束的路由算法是国内外研究的一个热点。文献【l5 1 的算法由z w a n g 和j c r o w c r o f t 提出，其中包括了两种算法，一种主要要求带宽，延时约束单播 路由问题，另一种主要研究最短最宽路由问题。文献1 1 6 l 提出了最小干涉路由算 法( m i r a ) ，选择的路径为使节点对的最大流减少最小( 即对未来的业务请求 影响最小) 的路径，称为最小干涉路径。基于特征路由算法( p b r ) 1 7 1 在m i r a 算法的基础上把对以往业务的测量得出的特征作为对未来业务分布的粗略预 测，得到每种业务类在网络中每条链路上的预期带宽需求，用束限制对每个业 务类的带宽分配。 i s r a e lc i d o n 和r a p h a e lr o m 等在文献1 1 8 l 中论证了要在一个网络资源可用性 变化极快的网络中快速建立路由时，多路径路由是一个非常有吸引力的解决方 法。y a n x i aj i a 等在文献1 1 9 l 中提出了基于带宽和基于跳数的两种k 最短路径o o s 路由机制，通过在不同网络拓扑和流量情况下的仿真试验验证了这两种多路径 算法比其它算法能更有效处理链路状态信息的陈旧和不精确。i s r a e lc i d o n 和 r a p h a e lr o m 等还在文献【驯中分析了多路径路由算法的性能，指出与单一路径 预留相比多路径预留能显著减少连接建立时问，而且采用2 到3 条并行的多路 径就可以获得几乎最好的性能。 在文献中，为了补偿网络节点链路状态信息的不精确性，提出了一个计 算从源节点到目的节点若干条传输路径的q o s 路由算法。依据d i j k s t r a 算法， 设计了一个收集第k 最短路径的路由策略，并研究了在不同网络拓扑结构和不 同流模式下的算法性能。结果证明算法比传统的单个最短路径算法具有低的阻 4 两北师范大学硕t 学位论文 第一章绪论 塞概率和较好的网络链路利用率。因此该算法可以降低链路状态更新频率且不 降低网络整体性能。 国内有关非精确网络状态信息下的o o s 路由算法的研究不多见，目前北京 邮电大学、清华大学、中南大学、华中科技大学等单位己经丌始了这方面的研 究，但都只是处在起步和探讨阶段。文献1 2 2 , 2 3 i 论述了非精确网络状态信息下o o s 路由算法研究的意义及重要性，认为它是网络路由算法研究的重要方向之一， 具有深入研究的价值。文献【2 4 l 指出研究链路状态不精确情况下的多路径o o s 路 由是未来的重要工作之一。 1 3 本文的研究内容与结构 本文通过对m p l s 从操作、结构、组件等方面进行的研究，掌握m p l s 技 术的实质，然后将m p l s 应用到流量工程中，详细研究了m p l s 流量工程的处 理模型，并主要研究了m p l s 流量工程中的约束路由算法。通过对已有的约束 路由算法的研究，提出了一种新的对现有约束路由算法的改进算法，最后通过 仿真比较验证该改进算法的有效性。 第一章，主要介绍了本文的研究背景、研究现状和本文的主要工作。 第二章，首先介绍了m p l s 技术的发展背景、基本概念和基本原理，之后 通过对流量工程的概念和处理模型，流量工程技术的发展过手口的介绍，重点阐 述了m p l s 流量上程技术的具体实现。 第三章，从约束路由原理、约束路由与m p l s 的结合、约束路由的约束种 类、约束路由的主要组成部分多个方面对约束路由技术进行了介绍，并总结了 现有路由算法在特定q o s 请求下的局限性。 第四章，主要针对现有约束路由算法在特定o o s 请求下路径建立成功率不 高的局限性，提出了一种基于带宽约束的多路径约束路由算法。从理论的角度 对这种算法的实现原理，实现流程进行了详细的介绍和论述。 第五章，对改进的多路径路由算法进行具体的仿真实验，验证算法的有效 性，并同现有的算法进行比较，最终从仿真实验的角度对改进的算法进一步的 加以验证。 第六章，对全文的工作进行了总结，同时提出了下一步的研究内容。 5 第二章m p l s 流量工程技术 2 1m p l s 的基本原理 2 1 1m p l s 技术的基本概念 m p l s 技术是一种使用i p 路由信息基于标签交换的技术，它包含两个基本 组件：控制组件和转发组件。以下是m p l s 技术的一些基本概念： 标签( l a b e l ) 用于识别流的标志符，标志符是简短而定长的( 2 0 位) ， 在物理上连续且只有本地意义。 标签和标签堆栈标签的格式如图2 - 1 所示； o1 92 0 2 22 32 43 l 图2 - 1 标签的格式 标签格式中各个域的含义： l a b e l ( 2 0 位) 标签域，仅具有本地意义，用于数据转发； e x p ( 3 位) 试验字段，可被用于传递区分服务的服务类型信息； s 栈底标记，表示该标记是否标记堆栈的栈底( s = 0 表示栈底) ； t r l ( 8 位) 存活时间，指示m p l s 分组的存活时l 、日j 。在m p l s 网络 边界设置，每经过一个m p l s 网络中继段，1 r r l 值便减去1 。 转发等价类( f o r w a r d i n ge q u i v a l e n c ec l a s s e s ，f e c ) 指以同样方式( 如 相同的转发处理策略、遵循相同的路径等) 转发的一组i p 包。虽然它 们的业务类别相同、处理策略相同，或者遵循相同的路径，但它们并不 一定同源： 标签分配协议( l a b e ld i s t r i b u t i o np r o t o c o l ，l d p ) ：在m p l s 节点之f b j 分配、发布、维护和回收标签资源的协议； n h l f e 下一跳标签转发条目 转发标签分组时使用下一跳标签转发条目，它包含下列信息： 1 分组的下一跳； 2 在分组的标签堆栈上完成的下列操作之一： 1 1 用特定的新标签替换标签栈顶的标签； 6 西北师范人学硕i ：学位论文 第二章m p l s 流量t 程技术 2 1 标签堆栈执行出栈操作： 用特定的新标签替换标签栈顶的标签，然后将一个或多个特定的新 标签压入堆栈； n h l f e 还可以包含如下信息：传送分组使用的数据链路封装；传送分 组时标签堆栈的编码方式；对分组进行适当的处理所需的其他信息。 f e c 到n h l f e 映射( k i n ) f t n 将每个f e c 映射到一组n h l f e 。对 于收到的未打标签但要在转发之前打上标签的分组，要将其转发时，需 要使用f i n 。当f t n 将某一特定标签映射到包含多个元素的一组 n h l f e 上时，在对该分组进行转发之前必须从该组中明确地选出一个 元素。 输入标签映射( i l m ) 将每个输入标签映射到一组n h l f e 。对收到的 标签分组进行转发时将使用i l m 。当i l m 将某一特定标签映射到包含 多个元素的一组n h l f e 时，转发该分组之前必须从该组中明确地选出 一个元素。 标签交换( l a b e ls w i t c h i n g ) 通过使用标签来识别要转发的数据流，允 许数据的流水式转发，通过标签交换，分组可以从一个m p l s 节点转发 至另一个m p l s 节点。 标签交换路径( l s p ) 标签交换路径是山一个或多个标签交换跳连接而 成的路径，通过标签交换路径，分组可以穿越一个m p l s 网络。 标签转换( l a b e ls w a p ) 指m p l s 技术中基本的转发操作，包括检查输 入标签以确定其输出标签、封装形式、输出端口和其它数据处理信息。 具体的在对一个分组进行转发时下列过程称为标签转换： 1 为了转发一个标签分组，l s r ( 标记交换路由器) 对标签栈顶的标 签进行检查，使用i l m 将该标签映射到一个n h l f e ，使用n h l f e 中 的信息决定向哪罩转发该分组并完成分组的标签栈操作。随后，将新标 签栈编码后放入该分组，对该分组进行转发。 2 为了转发一个无标签分组，l s r 分析分组的网络层分组头确定分组 的f e c ，随后使用f t n 将该f e c 映射到一个n h l f e ，l s r 使用n h l f e 中的信息决定向哪罩转发该分组，并完成分组的标签栈操作。随后，将 新标签栈编码后放入分组中，对该分组进行转发。使用标签替换时下一 跳要从n h l f e 获得。 7 西北帅范人学硕e 学位论文第二二章m p l s 流量- 程技术 标签交换路由器( l s r ) ：支持m p l s 的路由器称为标签交换路由器， 亦即可以进行第三层包转发的m p l s 节点； 标签交换边缘路由器( l e r ) ；m p l s 网络同其他网络的边缘设备，它 提供流量分类和标签的映射( 作为入口) 、标签的移除( 作为出口) 功 能： 2 1 2m p l 5 技术的基本原理 m p l s 网络由l e r 和l s r 组成。l e r 位于a t m 骨干网的边缘并作为m p l s 的入口出口路由器。l e r 执行全部的第三层功能和由运行l d p 2 6 1 或r s v p l 2 7 1 而产生的基于l i b ( l a b e li n f o r m a t i o nb a s e ) 的标签绑定功能。l e r 连到网络内 部的l s r 。l s r 执行基于l i b 的标签交换，具有第三层转发分组和第二层交换 分组的功能。同时也能运行传统口选路协议，还可以执行一个特殊控制协议与 相邻的l s r 协调f e c 标签绑定信息。l e r 与l s r 之间的l s p 是通过l d p 协 议建立起来的。提供o o s 保证的口业务( 如i n t s e r v 和d i f f s e r v ) 和i pv p n 的 i p 业务能够按照这个网络模型灵活地通过不同的接入网( 例如，纯a t m 网、 帧中继、x d s l 、1 p 网等) 提供给i p 用户。 在一个m p l s 网络中，入口l e r 为流量数据包分配标签。每个数据包沿着 标签交换路径转发，每个l s r 独立地根据标签的内容做出如何转发数据包的决 定。在每一跳上，l s r 去掉数据包中已有的标签并为之绑定一个新的标签，这 个新的标签指明数据包被转发的下一跳。在出口l e r 上，数掘包中的标签被去 掉，并被按一般的方式转发到它的目的地。 m p l s 不同于常规i p 网络基于最长的地址匹配路由查找的h o p b y h o p 的数 据包转发方式。在传统i p 转发机制中，每个路由器分析包含在每个分组头中的 信息，然后解析分组头，提取目的地址，查询路由表、决定下一转接点的地址、 计算帧头的校验、递减t r l 、完成合适的出口链路层封装、最后发送分组。而 在m p l s 中，只是在分组进入网络的边缘节点处对i p 包头进行分析，后续节点 不再分析包头，路由决策的做出也不仅仅是根掘l p 地址，它可以依据多种参数， 如o o s 参数、流量工程服务参数等。它的工作原理如下： 1 ) 为数据流加上标签( 1 a b e l ) ； 2 ) 用简短定长的标签来识别流，简化转发处理： 3 ) 在某些情况下，m p l s 直接利用第二层交换，如链路层是a t m 网络时； 4 1 采用标签分配协议，使m p l s 节点为每个流加上标签； 8 西北师范大学硕i 二学位论文第二章m p l s 流量t 程技术 5 1 支持传统的路由协议。 m p l s 旨在简化路由器入口处对网络层帧头的分析过程和f e c 分配功能的 过程【删，改善选路的性能和成本。尽管m p l s 面向多协议，但它主要还是支持 i p 协议。在传统的i p 转发处理中，一个路由器会把符合最长匹配的具有相同网 络前缀的目的地址的分组看成是属于同一个转发类，而到了另一个节点，那里 的路由器又要重新选择分组所属的转发类。而m p l s 在分组进入网络时就将分 组划入某一个转发等价类f e c ，并赋予一个简短定长的标签，这个标签随同分 组一起转发到下一个中继点。在随后的中继点上，不再需要分析分组的头标， 取而代之的是用标签作为索引在路由表中寻找下一个中继点，并用新的标签取 代老的标签。在m p l s 转发处理中，一旦分组被划入某一个转发类，在随后的 转发节点上不需要分析分组的头标，所有的转发由标签决定。 2 2 流量工程介绍 随着i n t e m e t 的不断发展，多种业务需求的不断增加，m 网络拥塞的问题 变得越来越严重。如何高效、合理的利用有限的网络资源实现多种业务的需求， 成为i s p 面临的主要问题。而流量工程就是用来解决此问题的一种网络技术。 2 2 1 流量工程的概念 流量 程【2 9 1 用来解决实际运行的i p 网络中的性能评估和性能优化问题。它 的一个主要目标是在优化网络资源利用和流量性能的同时，提供高效可靠的网 络运行。流量工程的性能目标有两个方面的含义：通信量和资源。从网络运营 商的角度来看，流量工程的目标就是用最小的代价高效地传输尽可能多的分组； 具体的就是提高当前网络的资源利用率，增强网络的健壮性，向用户提供高效 率、高可靠性的通信服务。 流量工程、网络工程、网络规划是三个内容相近的概念。它们的区别可以 简单地概括为：网络规划或者网络工程致力于为当前或者未来的流量需求提供 网络容量( 即通信资源) ；流量工程致力于将网络流量高效地放置到当前可供使 用的网络容量上，提高网络资源利用率和业务的服务质量。 2 2 2 流量工程的处理模型 流量工程可用于i p 骨干网中的拥塞避免和拥塞恢复，尤其是由低效的资源 分配引起的拥塞问题：例如网络中某些资源处于超载状态，另一些资源却处于 9 两北师范大学硕l 学位论文第一二章m p l s 流量工程技术 未充分利用状态，流量工程主要处理这类问题。流量工程在测量、建模、特征 化和互联网流量控制等方面运用各种技术和科学原理到达上述目标。流量工程 的具体过程可以用图2 2 所示的处理模型表示： 修改控制策略? 制定控制策略 确定流蕈和 网络状态特征 苎i 优化网络性能 性能监测 错误监测 分析模型 容最规划 网络设计 网络运行管理 容鼍增加 配置控制 图2 - 2 流龟：r 程处理模璎 流量工程处理模型【3 0 1 描述了流量工程的生命周期中四个阶段：制定策略阶 段、观测网络状态阶段、确定流量特征和分析网络状态阶段、优化网络性能阶 段。 制定策略阶段：可实施的流量工程首先要求尘成合适的控制策略：就是网 络运营商根据商业模型、网络运营成本结构、当i i 主流的策略和性能优化的标 准来制定控制策略。网络运营商可能建立一个概念化的商业模型( 运营收入) 、 性能模型( 资源利用率模型) ，借助于这些模型来生成合适的策略。这些策略就 是运营商希望通过流量工程要达到的目标。 观测网络状态阶段：在这个阶段，对所运营的网络进行网络观测，通过性 能监测、错误监测和分析模型，获取网络流量特征，从中得出对流量工程具备 可操作意义的特征。 确定流量特征和分析网络状态阶段：通过网络的流量模式( 对流量工程域 来说有四种流量模式：内部流量，传输流量，输入流量，输出流量) 、链路利用 率、流量变化趋势和网络分组丢弃率统计等特征，将其结果用于对网络进行具 体的容量规划与网络设计，并制定相应的网络管理策略。 优化网络性能阶段：应用合适的决策过程来选择一系列的行动来增强网络 1 0 西北师范人学硕七学位论文 第一苹m p l s 流量工程技术 性能。优化不是一个一次性的过程，可能是网络性能提高的一个连续迭代过程。 优化涉及对进入网络的流量进行调节，利用路由控制能力束控制流量和可供使 用的网络资源之间的映射，通过添加额外的链路来扩展网络拓扑，增加某些链 路承载的流量或者控制局部分组处理策略( 排队，调度，丢弃策略等) 。当发现 性能优化无法达到网络流量的需求时，可能引发修改控制策略或者网络规划的 过程。 2 3m p l s 流量工程技术的具体实现 m p l s 流量工程将面向连接的特性引入砰网络。通过特定的策略把流量转 移到预先指定的路径l s p 上，避开网络中拥塞的节点，提高对网络资源的利用 效率 。 m p l s 实现在线流量工程的基本思想是通过扩展s p f 算法的路由协议 o s p f 或者l s i s ，将网络中的链路信息局部扩散，每个l s r 收集拓扑和资源信 息形成流量工程数据库( t e d ) 。为基于约束需求的流量建立l s p 隧道时，可 采用约束路由算法依据当前流量工程数据库中的内容，计算l s p 途经的路径。 l s p 的具体建立工作由i e t fm p l s 工作组所定义的信令协议完成。 m p l s 流量工程的基本框架如图2 3 所示，主要分成下面几个部分【3 1 1 ： 建l s p 信息发布 入分组 i g p 路d j 汁算模块 i 路径计算模块 匿h 匿 信息发布模块：o s p f i s i s 扩展 信令模块 分组转发模块 建征l s p 信息发布 出分组 图2 - 3 流量工程的实现框架图 1 1 信息发布模块： 因为流量工程需要有关网络拓扑和网络负荷的动态信息细节，新的流量工 程模型的主要需求是用于信息发布的框架。这部分可简单地通过定义相关的 i g p 扩展来实现，这样，链路特性可包含在每个路由器的链路状态广播中。每 两北师范大学硕 学位论文 第一二章m p l s 流量t 程技术 个l s r 通过个特殊的流量工程数据库对网络链路特性和拓扑信息进行管理。 t e d 专门用于计算l s p 通过物理拓扑时的外在路径。同时，i g p 继续运行，通 过路由器状态数据库所包含的信息进行传统的最短路径计算。由于o s p f 和 i s i s 在信息扩散时的范围特性限制，这种流量工程的应用只能局限在a r e a 或 者l e v e l 内部。 与传统的路由算法相比，流量工程在进行路由计算时要考虑c r - l s p 的资 源需求和链路基于约束的特性。l s r 根据l s p 的需求与约束特性，为l s p 计算、 选择满足约束条件的路径。l s r 除了需要收集网络的拓扑信息以外，还需要收 集链路的资源与约束特性。支持流量工程，可以对o s p f ，i s i s 进行扩展。 i e t f 发布了两个草案，分别定义了如何扩展o s p f 3 2 1 ，i s i s t 3 3 l 协议发布约 束信息。内容基本一致，具体实现的角度上看，目前的扩展局限于点到点链路， 点到多点、多点到多点的链路目前难以进行资源分配。具体的扩展内容如下： 1 流量工程路由器i d ：标识路由器的唯一性； 2 链路通告信息扩展：传统的s p f 路由算法只通告网络拓扑相关的链路可 达性信息。为了获得网络的具体约束信息，需要增加如下内容： 3 流量工程度量，一般它由网络管理人员分配，为流量工程执行选路算法 时使用，原先的链路度量仍然保留； 4 邻接点的路由器i d ； 5 链路上邻接点的接口地址： 6 路由器该链路自己的接口地址； 7 链路的管理标识，又称着色或者资源类别，3 2 位标识，每位可以被解释 为某个群组可以使用该链路。基于管理策略需求，能被灵活应用与解释； 8 链路的最大带宽，单向，物理链路带宽； 9 链路的最大可预留带宽，单向，能支持超量的资源预留，其值可以大于 实际的链路最大带宽； 1 0 链路的未预留带宽，单向，为了能支持优先级与抢占( 当资源不足时， 高优先级的l s p 优先占据资源) ，将其分为旷- 7 共八个优先级别，通告每个 优先级上未预留的带宽值。网络中具备流量工程能力的l s r 在收到这些信息后， 形成流量工程数据库。与传统的链路状态数据库( l s d ) 信息相比，增加了对 链路的资源和约束特性的描述。 2 1 路径计算模块： 1 2 两北师范大学硕l ：学位论文 第一二幸m p l s 流量t 程技术 流量工程的最终目标是将网络流量合理映射到实际的物理拓扑中，即为每 个l s p 确定物理路径，这通过路径选择模块来完成。路径选择模块利用t e 数 据库中的信息，加上必要的附加信息( 如某种管理策略、链路权值等) ，使用约 束路由算法，为特定l s p 请求计算条显式路由。 显式路由( e x p l i c i tr o u t e d ，e r ) 【蚓是m p l s 路由技术的核心，它是在传送 数据包之前首先利用标记分发协议建立标记交换路径，当l s p 建立以后，数据 包到达l s r ，l s r 根据标记来决定下一跳转发路由。e r 与m 协议中定义的