（计算机应用技术专业论文）基于mpls技术的路由容错研究.pdf

武汉科技大学硕士学位论文第l 页 摘要 随着网络规模的迅猛发展和新业务的大量涌现，如何提高网络的服务质量成为当前迫 切需要解决的问题之一。现有l p 协议的拓扑驱动和无连接等特性对网络对资源和流缺乏整 体控制能力，易造成网络资源使用不均衡，整体利用率不高等问题。优化网络资源的使用、 合理地分配负载、提升网络的错误恢复能力成为流量工程的主要目的。 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 下降。 文章通过对现有m p l s 故障恢复模型及其存在问题进行分析和研究，提出了一种基于 m p l s 的生成树快速重路由模型及其路由容错算法( f r s t ) 。在网络设备或链路发生故障或 失效造成网络拓扑发生变化时，利用m p l s 技术，利用拓扑的生成树之间的路径显式指定 l s p 完成快速重路由，避免了单个链路故障引起的整个网络正常工作的停顿，使网络可用 性提高，保证了网络运行的可靠性，改善了网络整体的运行性能。通过n s 2 对算法进行仿 真实验，结果和分析表明与h a s k i n 和m a k a m 两种m p l s 路由容错模型相比，本模型和算 法具有较好的性能，能够达到与h a s k i n 模型相当的重路由时间性能，避免了h a s k i n 模型 的较长时延和m a k a m 模型较大的丢包率等问题，另外，本模型的性能基本不受故障链路 的位置影响，具备较为稳定的性能。 关键词：流量工程；m p l s ；故障恢复机制；快速重路由；n s 2 第1 i 页武汉科技大学硕士学位论文 a b s t r a c t w i t ht h ee x p l o s i v eg r o w t ho ft h en e t w o r ks c a l ea n dt h ee m e r g e n c eo fal o to fn e ws e r v i c e s ， h o wt oi m p r o v et h eq o so ft h en e t w o r kb e c o m e st h eo b j e c t t h et r a d i t i o n a li n t e r n e tp r o t o c o l s f a i lt oa d d r e s st h ep r o b l e mo fn e t w o r kc o n g e s t i o na n dp e r f o r m a n c ed e g r a d a t i o nr e s u l t i n gf r o m t h ei n e f f i c i e n tr e s o u r c ea l l o c a t i o nu n d e rh e a v yt r a f f i cl o a d t h e r e f o r e ，h o wt oo p t i m i z et h e n e t w o r kr e s o u r c eu t i l i z a t i o n ，b a l a n c et h el o a do nt h el i n ka n di m p r o v et h ep e r f o r m a n c eo ff a u l t r e c o v e r yh a v eb e c o m et h em a j o rt a s ko fi n t e r n e tt r a f f i ce n g i n e e r i n g m p l sc a nh e l pt o o p t i m i z i n gt h eu t i l i z a t i o n o fn e t w o r kr e s o u r c ea n di m p r o v i n gt h e p e r f o r m a n c eo fn e t w o r k t a k i n gu s eo fm u l t i p r o t o c o ll a b e ls w i t c h i n g w i t hi t se f f i c i e n ts u p p o r t o fr e c o v e r ym e c h a n i s mp r o v i d e sb a s i cm e t h o d sf o rf a c i l i t a t i n gt r a f f i ce n g i n e e r i n g t h e r e f o r e ， f a u l tr e c o v e r yh a sb e c o m ea ni m p o r t a n tr e s e a r c ha r e ai nm p l st r a f f i ce n g i n e e r i n g t h eb a c k u p p a t hs h o u l db ep r e - c o n f i g u r e df o rt h ep r o t e c t e dl s pb ym p l s f a u l tr e c o v e r ym e c h a n i s mi no r d e r t oe n s u r et h a tt h er e l i a b l ea p p l i c a t i o nc a ng e tf a s tr e c o v e r yt r e a t m e n t t h ef a s tr e r o u t em o d e lb a s e do nm p l ss p a n n i n gt r e e ( f r s t ) a n di t sf a u l tt o l e r a n tr o u t i n g a l g o r i t h ma r ep r o p o s e d w h i l et h en e t w o r kt o p o l o g ya r ec h a n g e da n d t h a tc a u s e db yf a u l t si nt h e n e t w o r kd e v i c eo rl i n k s ，t h ef a s tr e r o u t ei sc o m p l e t e dw i t ht h ee x p l i c i tp a t hl s pa s s i g n m e n t t e c h n o l o g ya n dt h es p a nt r e eo fm p l st o p o l o g ya n dt h a ta v o i dt h eb r e a k d o w no ft h ee n t i r e n e t w o r k ，i n c r e a s et h en e t w o r ku s a b i l i t y , e n s u r et h en e t w o r kr e l i a b i l i t ya n di m p r o v et h ee n t i r e n e t w o r kp e r f o r m a n c e ，t h r o u g ht h es i m u l a t i o no ff r s tb yn s 2 ，i t sp e r f o r m a n c ei sb e t t e rt h a n h a s k i nm o d e la n dm a k a mm o d e l ；i th a st h ee q u i v a l e n tr e r o u t et i m ea st h eh a s k i nm o d e l ，b u t a v o i dt h el o n gd e l a yo fh a s k i nm o d e la n dh i 【g hp a c k e tl o s sr a t eo fm a k a mm o d e l i na d d i t i o n ，i t s p e r f o r m a n c ed o s en o tb e e na f f e c t e db yt h el o c a t i o no ft h ef a i l u r el i n k k e yw o r d s ：t r a f f i ce n g i n e e r i n g ；m p l s ；r e c o v e r ym e c h a n i s m ；f a s tr e r o u t e , n s 2 武汉科技大学 研究生学位论文创新性声明 本人郑重声明：所呈交的学位论文是本人在导师指导下，独立进行研 究所取得的成果。除了文中已经注明引用的内容或属合作研究共同完成的 工作外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名：多善型 日期： 研究生学位论文版权使用授权声明 本论文的研究成果归武汉科技大学所有，其研究内容不得以其它单位 的名义发表。本人完全了解武汉科技大学有关保留、使用学位论文的规定， 同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查 阅和借阅，同意学校将本论文的全部或部分内容编入有关数据库进行检索。 论文作者签名： 指导教师签名： 日期： 马展芝 1 2 撞逢2 丝星垒兰旦! 塑 武汉科技大学硕士学位论文第1 页 1 1 研究背景 第一章绪论 随着网络数据业务量和用户量的猛增，对信息和网络的依赖程度日益增大。网络的可 靠性问题逐渐凸显，网络生存性技术因此应运而生。网络的生存性主要是指网络在节点、 链路失效以后，在不需要人为的干预情况下，自动恢复受故障影响的业务的能力【。而未 来i p 网业务的多样性使得网络生存性尤为重要。大多数网络都有两种机制来实现网络的 生存性：一种是恢复机制，另一种是保护机制。恢复机制是在网络失效后动态地寻找可用 资源从而选择另一条路由；而保护机制则是预先配置保护路径来防止可能出现的故障。保 护机制与恢复机制各有优缺点：保护机制比恢复机制的恢复时间短但灵活性不足，而且资 源利用率不如恢复机制。 尽管目前的路由算法已经相对成熟，但依然无法保护网络故障后恢复时间与性能。因 此，尽管i p 路由提供重路由功能，但其恢复时间较长( 几秒到几分钟) 。对于要求高可靠 性高实时性的业务，这样的恢复时间是不可接受的。此外，对于某些需要o o s 保护的业务， 不仅需要在故障后建立新路径传输流量，而且需要有对原传传输路径等同的网络带宽。而 i p 路由在实施故障恢复的同时，却难于确保网络带宽。一些常用媒体对传输网络的要求见 表1 1 所示。典型的网络业务如v o l p ( v o i c eo v e ri p ) 、语音传输、视频传输，而对于这 类业务，i p 重路由常常显得力不从心。 表1 1 媒体对传输网络的要求 。 最大最大时延平均吞吐量可接受的误可接受的误 时延( m s )抖动( m s )( m b i t s ) 码率分组率 语音 2 5 01 00 0 6 4 1 0 1 1 0 。l 活动图像2 5 01 0 1 0 0 1 0 。2 1 0 2 压缩活动图像 2 3 012 1 0 0 1 0 6 1 0 。9 数据文件传输 1 0 0 02 1 0 0o0 实时数据 1 - 1 0 0 0 1 0 000 静止图像1 0 0 02 1 0 0 1 0 4 l m i n 慢 2 0 0 m s l m i n 中等 5 0 m s 2 0 0 m s 古 2 0 m s 5 0 m s 同 很高 2 0 m s 链路故障恢复级别与恢复时问如表3 2 所示。链路的故障恢复与保护技术主要有基于 物理层、数据链路层和网络层的研究。本节主要在网络层研究重路由算法和技术来处理链 路的故障和失效问题。 3 1 1 基于i p 的网络重路由容错 基于l p 的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 网络也由 以前单一的数据网变成了由多种业务相融合的综合数字网，这就对i n t e r n e t 的服务质量 ( q o s ) 提出了很高的要求。这些实时通信业务不仅要求网络能够满足信息传输的可达性， 而且要求网络可以对信息传输的过程具有可预见性，在任何情况下都能提供稳定的q o s 保 证。 重路由( r e r o u t i n g ) 模型定义为，在网络故障发生后，按需在线建立一条新的完整的传 输路径或建立其中路径的某一段。新路径的建立必须基于当时的网络扶况，如网络故障信 息、网络路径策略、预定的配置、网络拓扑信息。在该模型中，新路径或路径段( s e g m e n t ) 在故障发生后动态建立【3 5 j 。重路由恢复方案事先无须建立备份路径。在故障发生后，再建 立新路径恢复流量传输。对新路径的选择取决于故障位置，路由策略、网络拓扑。故障发 生后，参照当前已更新的网络状态，按需建立保护路径，动态实施恢复并优化资源利用。 与此同时，由于相应重路由算法收敛需要一定时间，重路由的恢复速度较慢，但对于对实 时要求不高的业务，重路由也是一种较好的选择。 基于i p 的网络在网络节点或链路发生故障时，最先检测到这一变化的路由器通过路 由协议将拓扑变化的信息通过邻接节点广播出去，网络中的其它路由器收到更新消息后， 更新路由表，然后继续向外发布路由更新消息，直到全网路由信息达到收敛。各个路由器 节点在新的拓扑结构下分别计算通信节点之问的最短路径，形成新的一轮通信过程。这一 过程往往会需要几秒钟甚至几分钟，这对于很多敏感的实时业务( 如i p 电话、视频传输等) 来说是不可接受的。显然这种方式下的容错能力主要是在一定时间周期内通过邻接节点问 互相通知和拓扑发现对路由的重计算和重配置来实现，这种方式存在着一定问题： ( 1 ) 路由的重新计算和配置是在所有网络路由器节点中分布式独立完成的，需要保持 网络拓扑结构在每个网络路由器市点中的一致性。网络拓扑发现是一个通过网络节点间两 第1 8 页武汉科技大学硕士学位论文 两告知而逐渐收敛的过程，在网络节点众多的情况下往往需要较长时间来完成，同时还需 要每个节点之间的通信是无障碍即时进行的，在网络流量负荷过重时难以达到要求； ( 2 ) 由于某一个网络元素发生故障时，其它没有受到直接影响的其它网络元素乃至整 个网络都要停下正在进行的正常工作，重新进行网络拓扑的配置计算工作，因此影响通信 时间的延迟，各个通信的路由路径都可能发生改变造成丢包从而引起网络的振荡、抖动、 延时和网络通信路径的不可预见性，造成网络性能难以控制和管理，网络行为和状态的不 可预测以及网络的可用性大大降低。 ( 3 ) 网络根据传统路由协议o s p f ( 开放最短路径优先) 进行路由的重新计算和配置 后，也会造成网络的拥塞，造成丢包、引起网络的振荡、抖动和延时，使网络性能大大降 低。 3 1 2 基于m p l s 技术的故障恢复与保护 m p l s 故障恢复技术是指在m p l s 网络环境中，当传输数据的工作路径l s p 出现故障后， 流量被快速切换或分配到未被损坏的路径( 保护路径) 上继续传输的技术。在m p l s 网络中 数据流的转发实际上是( 端口，标签) 的交换映射，链路发生故障后，只要使用信令协议 建立起新的l s p ，数据就可以沿着新的路径传输，而无论全网的路由信息是否已经收敛。 所以，m p l s 技术使i p 层的恢复能够在网络拓扑发现计算收敛前完成，故障恢复速度更快。 m p l s 重路由技术是m p l s 技术的重要优点之一，由于它的快速、高服务质量和易扩展性， 已经成为m p l s 领域的研究热点。 m p l s 技术的出现，通过显式的标记交换路径l s p 指定，可以通过相关信令协议来指 定端对端通信的路由及其相关策略，解决了传统i p 网络任意网络元素的故障将对整个网 络的可用性和可靠性产生影响的问题，可以把故障的修复局部化在部分网络元素中进行， 网络的端对端通信路径的管理也变得更加方便和有预见性。 网络中任何资源都有可能发生故障，因此，提供一个足够高的可用性的网络，必须预 计并且计划好解决这些可能的故障的方法。由人为造成的链路中断；电缆磨损造成连线断 裂，光缆由于收发器故障而丢失光信号等等这些故障都可能造成网络数据传输业务的中 断。还有像路由器的故障，整个标记交换路由器可能瘫痪。这种情况下，路由器的硬件故 障很容易解决，可以通过增加冗余链路板卡来降低硬件故障的影响。单个设备故障可以通 过一定的技术手段如采取硬件设备冗余的办法来实现。 链路发生故障时在条件允许的情况下采用链路冗余的办法来实现，由此发展出m p l s 网络中对于通信链路故障失效的路由容错技术。但是链路冗余的方法在实际网络部署中具 有一定的局限性，本文对此问题进行研究。 3 1 3m p l s 恢复机制 传统的【p 恢复机制速率较慢，而m p l s 可以加速i p 层的失效恢复时间。目前，i e t f 武汉科技大学硕士学位论文第1 9 页 已经出台了利用m p l s 技术提供网络层的快速失效恢复的草案。m p l s 可以在有效路径的两 端或失效节点间建立替换l s p 。虽然这种方式也是在路径失效后才由m p l s 的信令计算出可 替换的路径或链路，但由于m p l s 利用固定长度的标签交换技术减少了路由器解析i p 包头 的延时，从而可以加速i p 层的实效恢复1 3 6 j 。根据恢复对象可分为两种方法：基于链路的 恢复和基于路径的恢复。在基于路径的情况下，整条l s p 都被替换。而基于链路则只替换 失效的l s p 跳数。 基于链路的方法是基于路径方法的简化，它适用于在一对节点间有多条光路径的情况。 恢复机制可以采用集中式控制，由控制管理中心根据网络失效后的资源状况进行重路由， 同时也可以采用分布式的控制，与失效相关的节点通过使用广播消息的方法来寻找一条恢 复路由。 其次与恢复机制相同，m p l s 通过预先配置保护l s p 也要分为两种方法：基于链路的1 3 7 】 和基于路径的，原理与恢复机制一样，只是保护路径和链路是预先配置的。这时执行l s p 保护切换1 3 8 j 不需要信令的参与。这种方法的恢复时间可和s d h 相媲美。虽然这对数据业务 并不是必要的，但是对实时业务却是必须的。即预先计算好一条备用的l s p 来保护主用的 l s p ，一旦主用l s p 出现问题则立即切换到备用l s p 。可在备用l s p 上传输一些低优先级的 尽力而为的业务。一旦主用l s p 出现故障，立即将主用l s p 上的流量全部切换到备用l s p 。 3 1 4m p l s 修复机制的工作流程 m p l s 修复机制的工作流程如下1 3 9 】： ( 1 ) 工作路由和备份路由的计算。 ( 2 ) 资源预留。在m p l s 中使用r s v p ( r e s o u r c er e s e r v a t i o ns e t u pp r o t o c 0 1 ) 协议 【冽在工作路由和保护路e h _ k 进行资源预留。 ( 3 ) 建立工作路由和备份路由。在网络中以动态重路由或者保护交换的方式建立工作 路由和保护路由。 ( 4 ) 网络损坏。主要是指链路和节点的物理损坏或性能减退。 ( 5 ) 故障发现。 ( 6 ) 故障通告。故障指示信息f i s ( f a u l ti n d i c a t e ds i g n a l ) 向上游l s r 层层传送。 ( 7 ) 切换到备份路径。 ( 8 ) 流量在新的路径即备份路径上传输( 完成流量切换工作) 。 故障修复后，流量从备份路径恢复到原工作路径的步骤如下： ( 1 ) 网络故障的修复。 ( 2 ) 原工作路径可以重新使用。 ( 3 ) 启动恢复操作。 ( 4 ) 恢复操作完成以后，流量蘑新切换到原工作路径上。 第2 0 页武汉科技大学硕士学位论文 3 2m p l s 故障恢复名词简介 ( 1 ) w o r k i n gp a t h ：工作路径，如图3 1 所示。入口路由器为数据包所建立到出口路 由器的路径，又称为p r i m a r yp a t h 或是a c t i v ep a t h 。 ( 2 ) b a c k u pp a t h ：备份路径，如图3 1 所示。当工作路径发生断线或是故障时，用 来替代工作路径的l s p 。又称为恢复路径r e c o v e r yp a t h ，在全局修复时又称为a l t e r n a t i v e p a t h ，在局部修复时又称为b a c k u pt u n n e l 。 ( 3 ) p s l ( p a t hs w i t c hl s r ) ：路径切换路由器，当工作路径发生断线或是故障时， 负责将数据流切换到备份路径上。图3 1 中的i n g r e s s 即为p s l ，但p s l 不一定是i n g r e s s l s r 。 ( 4 ) p m l ( p a t hm e r g el s p ) ：备份路径与工作路径的合并的l s r ，负责将备份路径上 的数据转向往工作路径上传送，如图3 1 的e g r e s sl s r 即为p m l ，但p m l 不一定为e g r e s s l s r 。 ( 5 ) p o r ( p o i n to fr e p a i r ) ：故障修复路由器。负责执行m p l s 故障恢复的l s r ，通 常为p m l 或是p s l ，根据具体的故障恢复机制而定。 ( 6 ) nh o p ( n e x t - h o pr o u t e r ) ：下一跳路由。与目前路由器距离一跳远的路由器。 ( 7 ) n nh o p ( n e x t n e x t _ h o pr o u t e r ) ：下下一跳路由。与目前路由器距离两跳远的路由 器。 ( 8 ) f i s ( f a u l ti n d i c a t i o ns i g n a l ) ：故障指示信号。用来通知w o r k i n gp a t h 发生 故障的信息，由发生故障的两端的l s r 发现，该信息依照不同机制，往l s p 上游传送或是 下游传送给p o r ，通知p o r 立即做出故障恢复程序。 l s r 3l s r 4 - - w o r k i n gp a t h 一一一一一一 b a c k u pp a t h 图3 1 肝l s 网络示意图 m l l s r 6 e g r e s s 武汉科技大学硕士学位沦文第2 1 页 3 3 基于m p l s 技术的路由容错技术 m p l s 技术因具有面向连接和融合多种网络层次上的协议而得到广泛关注和深入研究， 对于m p l s 网络中，在重路由、链路故障恢复处理和容错技术等方面也独具特刨矧。在链 路发生故障时可以在条件允许的情况下采用链路冗余的办法来实现，主要的链路保护方法 有重新路由和保护切换两种方案。 3 3 1 重新路由 在m p l s 网络中发生故障时，重新路由的基本思路是：一般来说故障链路承载了数量众 多、源目点各异、路径不一的业务流量，对这些业务流量的传输路径重新调整是必然要进 行的，但希望尽量减少这些业务流的调整对全网业务流正常传输的影响，必要时在故障链 路或节点所在路径的上游标记交换路由器l s r ( 不一定是路径的起点边缘路由器) 就可以 尝试重新通过信令建立新的l s p ，然后将故障链路上的业务流数据转移到新的l s p 上进行 传输。 e l ，e 2 一边缘路由器 n o m m u n i c a t i o nn o d e r - i ，a b e ls w i t c hr o u t e r 图3 2 重新路由 然而要重新建立一条l s p 不仅依赖于路由表中的路由信息的重构，还必须使用信令协 议进行标签的分配和映射，这两个过程都要耗费较多时间，而且重新选路也并不一定总能 够成功：现有网络的基本架构是边缘复杂而核心简单，即网络核心是无状态的，不具有负 载均衡能力和针对业务流等小颗粒度的信息，故障点上游每个路由器同步寻求l s p 的努力 可能由于网络链路流量负载的不可预知性而均告失败，同时也势必增加核心路由器的负 担。新路径的选择要在路由收敛后进行，并基于故障位置、路由策略和网络拓扑等信息， 所以这种方式建立的路径是最佳的，但恢复时间较长。i e t f ( i n t e r n e te n g i n e e r i n gt a s k f o r c e ，i e t f ) 建议采取以下两个方式来解决： ( 1 ) 如果一条在两个标记交换路由器之间的连接中断，通过c r - l d p ( 基于路由约束 的标记分配协议) 来拆除受到影响的l s p ，并且发出一个故障通告消息给入口端标记交换 路由器。入口端标记交换路由器再重新发起信令建立一条新的l s p 。 ( 2 ) 根据网络拓扑和路由表的变化，通过r s v p t e 协议来对i p 流重新分配资源。也 就是说允许l s p 根据网络拓扑结构的变化进行重路由，但是要求只能在入口路由器和故障 检测点处进行莺路由。 第2 2 页武汉科技大学硕士学位论文 无论以上那种情况，标记交换路由器在建立新的l s p 过程中，由于发送了大量的信令， 并且要耗费大量的c p u 资源用于路由计算，因而会花费很长时间，超出时限，有可能导致 重路由不会成功。 3 3 2 保护交换 保护交换是一种可以在最短时间内恢复链路或者节点故障的方法，在保护交换里，数 据在修复点从故障l s p 到备份路径l s p 上，备份的l s p 通常都是预先配置好的。 如图4 2 所示，数据沿工作l s p 被转发，备份l s p 作为备选的路径。在l s p 工作时， 备份l s p 不承载任何数据。当l s p 上发生故障，业务流被迅速切换到备份l s p 上来。 备份l s p 的配置包括物理链路及其标记交换的映射事先完成，可以同时作为两条或多 条l s p 的备份，它不需要在l s p 发生故障时通过信令建立，上游路由器检测到故障发生以 后，逐级将信号传递到源点，在源点负责切换到备份路径上，无需作太多的路由计算和处 理，所以保护交换速度通常修复速度要快得多1 4 。 虽然保护交换使得链路恢复速度很快，但是由于必须对路径进行备份，因而链路投入 成本很高，这是其存在的一个主要问题。同时网络中很难估计出那条链路是易损的或故障 率高的，要对所有链路或路径都进行备份几乎是不可能的事情，所以保护链路存在一定局 限性。 按备份路径的作用分类，主要有一下几种工作模式： ( 1 ) 1 + 1 保护：每条工作l s p 都有一条专用的备份l s p ，一旦工作l s p 故障失效，则将 业务流切换转移到备份l s p 上，问题是网络资源利用率太低，成本代价过高。而且备份l s p 的确定也是困难的问题。 图3 3 保护交换 ( 2 ) 1 ：1 保护：与1 + 1 保护模式相同，每条工作l s p 都有一条专用的备份l s p ，只不 过在工作l s p 正常时该条备份路径可以用来进行低优先级业务流的传输。一旦工作l s p 故 障失效，则丢弃在备份路径上传输的低优先级业务流，全部保证工作l s p 上的业务流传输。 相对于1 + 1 模式保护只是改进了网络资源利用率的问题。但是将备份路径上的低优先级业 武汉科技大学硕士学位论文第2 3 页 务流的负载在工作l s p 故障时加载到网络其它链路上势必对网络性能会造成不利影响。 ( 3 ) 1 ( m ) ：n 保护：可以考虑将1 3 条 ：作路径共用1 条或m 条备份路径的方法。这种 方式通常用于多个工作l s p 同时发生故障可能性不大的情况，它的优点是节省备用资源的 使用费用。 在链路保护技术中，重路由方式占用资源较少，灵活性强，而保护交换备份方式修复 速度快，信令的复杂度也较低，两种方法各有其有缺点。重新路由的方式在故障发生后建 立恢复路径，故障恢复速度相对较慢，但是在网络资源利用方面具有优势。保护交换在故 障前已经建立了备份路径，故障恢复速度快，但是资源利用率不高。基于m p l s 网络研究 能够使链路保护既有效而且代价较低的技术十分必要。考虑到网络的分布性和复杂性，重 路由技术已成为基于m p l s 流量工程( m p l s t e ) 中实现路由容错和调整流量分布的主要手 段。 3 3 3 链路保护方案 目前基于m p l s 技术的链路保护和重路由模型主要有d i m t r yh a s k i n 提出的h a s k i n 模 型和s r i n i v a sm a k a m 提出的m a k a m 模型。 主路径 备份路径 图3 4h a s k i n 模型 1 ) h a s k i n 模型中，当链路失效时业务流反向沿主路径传递到入口标记交换路由器， 然后沿和主路径平行的备份路径传递。 在图3 4 中，业务流沿主路径，e 1 一r 2 - r 4 - r 6 - e 2 传递，并建立备份标记交换路径 e 卜r 3 一r 5 一r 7 一e 2 。当节点r 6 与e 2 之间的链路发生故障时，业务流沿l s p 的反方向， 一r 6 一r 4 一r 2 传递到入口节点e 1 ，然后再沿备份标记交换路径e 1 - r 3 - r 5 - r 7 - e 2 传递到目的 节点e 2 。显然，故障发生后的传递路径是e 1 - r 2 - r 4 - r 6 - r 4 - r 2 - e 1 - r 3 - r 5 - r 7 - e 2 ，传输路 径有重叠导致传输延时加大和资源利用率低的情况。 这种模型的优点是备份路径投入时间较少，丢包率较低。 当链路恢复后l s p 切换到主路径传递。 2 ) m a k a m 模型： m a k a m 模型的工作原理如图3 5 所示：业务流沿主路径e 1 - r 2 - r 4 - r 6 - e 2 传递，并建立 备份标记交换路径e 卜r 3 一r 5 - r 7 一e 2 。与i l a s k i n 模型不同的是，当r 6 与e 2 之间链路故障 时，业务流从源节点e 1 开始沿备份路径传递。显然比h a s k i n 模型传输效率和资源利用率 要高，网络传输延时较小。但是需要有一个故障消息通告的过程，会有少量丢包情形发牛。 第2 4 页武汉科技大学硕士学位论文 主路径 备份路径 图3 5m a k a m 模型 3 ) 动态最短路方法 事先配置一条备份路径不光是代价过高，而且在何处进行备份配置也是一个十分困难 的问题。动态最短路方法的基本思想是不用事先配置备份路径，利用现存网络的资源，在 链路故障时从故障测出点处起找到一条绕过故障链路的最短路径，实现故障的恢复【2 9 1 。就 图3 5 来说，就是在r 4 - r 6 之间链路有故障时，r 4 最先检测到故障信号后，立即通过路由 计算，建立一条绕过r 4 - r 6 的最短的l s p ，也就是l s p ( r 4 一r 5 一r 7 一e 2 ) ，在路由器节点r 6 将流量转发到接续的l s p ( r 4 - r 5 一r 7 一e 2 ) 上，形成新的标记交换路径( e 1 一r 2 一r 4 一r 5 一r 7 一e 2 ) 。 主路径 备份路径 图3 5 动态最短路 该方法无需额外建立新的备份路径，可以充分利用现有网络资源，减少了对全局网络通信 路径的干扰和影响；存在问题是重路由计算的时间较长，可能会造成最初一段时间的丢包 率上升，同时如果所选备份路径负载较重可能会引起拥塞现象而导致网络性能急剧下降， 也就是说存在传统的最短路径路由所造成的种种缺吲3 0 1 。 3 4 小结 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 技术的故障与恢复模型如h a s k i n 模型、m a k a m 模型等均存 在一些性能j ：的问题，文章在第四章提出_ 种基于生成树的快速重路由算法。 武汉科技大学硕士学位论文第2 5 页 第四章一种基于生成树的快速重路由算法 链路保护中的保护切换要求对于工作l s p 事先配置好专用备份路径引起成本过高的问 题，事实上对哪些工作l s p 配置备份链路及或备份路径也是一个难以确定的问题。由于其 地理范围的广泛性和分布性，网络链路处于不确定的状态，很难确定那条或哪些通信链路 失效率高，保护切换技术难以适应高并发性的大流量工作条件，具有先天的不足，从本质 上讲是一种理想条件下的技术。研究快速重路由的链路保护技术，具有十分重要的意义。 本章提出了一种基于生成树的快速重路由模型( f a s tr e r o u t em o d e l b a s e do nm p l s s p a n n i n gt r e e ，f r s t ) ，以期实现保证网络服务质量、对于全局网络通信路径影响尽量局 部化、重路由算法简洁快速的快速重路由模型。 4 1 快速重路由 快速重路由是m p l s 流量工程的一个重要功能，是对r s v pt e 子系统的功能增强。对 于复杂的网络，经常会出现链路或者节点的失效。传统的处理方法是由i g p 处理，对网络 拓扑进行重新汇聚，快速产生路由。对于大型网络来说，拓扑的汇聚需要相当长的时间， 一般为秒级，用户数据丢失比较严重。m p l st e 具有使流量脱离i g p 驱动的最短路径的能 力，m p l st e 和它的这种能力可以帮助减轻网络中和链路失效或节点失效有关的分组丢失。 m p l st e 提供的这种能力的机制被称为快速重路由( f a s tr e r o u t e ，f r r ) 或简单的称为 m p l st e 保护，所以，f r r 可以理解为就是对网络中链路或节点失效时起的一种保护。f r r 功能可以在几十毫秒时间内，将分组从失效链路切换到备份链路，大大减少分组的丢失。 同时满足一定的资源要求。 虽然对于数据流量来说几秒钟的分组丢失是可以忍受的，但是对于像为了满足诸如视 频会议电视这一类业务的实时应用，必须对这些流量有毫秒级的l s p 保护能力。f r r ，即 快速恢复机制或者简单称为保护，虽然不可能建立一种完全没有丢失的失效恢复机制，但 是可以建立尽可能减小丢失的机制。m p l s 快速重路由技术可以实现在没有信令介入情况 下，由故障检测点直接对故障链路流量根据预先设定的保护路径进行重定向，恢复点即为 故障点。多数的快速重路由方案依赖预先建立的备份通道，当网络恢复点检测到网络故障 时，它要做的工作就是简单地更新l s p 交换表，使流量从故障端口的l s p 切换到预先在正 常端口建立的l s p 内。快速重路由的优势除了可以提高保护恢复的速度外，通过有选择的 在网络薄弱环节配置保护能力，避免了在可靠网络重复保护、无谓消耗核心网络资源。m p l s 快速重路由技术能提供5 0 m s 内的保护切换。 4 2 快速重路由性能因素分析 每个路由算法获得合适路径选择方法的所需要的最基本的信息就是网络的状态信息。 第2 6 页武汉科技大学硕士学位论文 网络状态的信息包括网络拓扑结构和与有关资源利用率。网络状态的每一个变化都应该被 检测到并且传播到同一个自治域的所有的路由器，然后在再通过边界传播到所有收到此变 化通知的自治域中去。因为这个拓扑变化的频率很低，状态变化的最主要的原因就是网络 中资源利用率的变化与因种种原因引起的拓扑的变化。 在3 2 节中提到，在m p l s 网络中，错误指示信号( f i s ) 用来通知工作路径发生故障 的信息，由发生故障的两端的l s r 发现，该信息依照不同机制，往l s p 上游传送或是下游 传送给p o r ，通知p o r 立即做出故障恢复程序。在m p l s 网络中，控制和数据平面共享同一 个传输媒介，这意味着一个故障发生就会同时影响这两个平面。由图4 1 所示，网络丢包 发生在故障发生至p o r 做出故障恢复措施之间的时间段。 完成链路恢复切换链路故障 ill ii i lii 时间 一 图4 1 链路恢复过程 在m a k a m 模型中，当f i s 到达的时候入口节点负责故障恢复。这个算法需要为每一条 工作路径都确立一条不相交的备份路径。不管故障发生在工作路径的哪个地方，保护总是 在入口节点就被激活。这就意味着在保护开关被触发之前必须把故障信息传送回源节点。 在f i s 向入口结点传递过程中，p o r 不能发现链路故障，因而i n g r e s sl s r 继续向该l s r 发送业务数据，造成大量的丢包，在恢复时间方面的代价比较高。 在h a s k i n 模型中，当工作路径上一旦发现故障，在故障处的重新路由进来的流量。 使这些流量与刚才被传送的方向相反被传送回工作路径的入口节点，并且f i s 也被送到了 入口节点。当到达入口节点时，入口节点就停止向工作路径传送流量了，而是把流量转移 到全局备份路径上去。故障指示机制是非常简化的，重路由时间比较短。因为逆向备份提 供了向入口节点传送故障指示信号的路径并且同时通过逆向备份，流量也被恢复。 重路由方法中的动态最短路方法的问题是： ( 1 ) 在复杂网络系统中路径计算收敛的时间过长，导致丢包率上升； ( 2 ) 由于重新回到最短路径算法寻径，又会导致网络资源利用率下降和负载不均衡， 与流量工程的目标不一致； 武汉科技大学硕士学位论文第2 7 页 ( 3 ) 如果动态最短路方法所确定的后续备份传输路径本身负载较高，可能导致原来在 通过后续备份传输路径的业务流的服务质量受到严重影响，引起网络性能的严重下降。 图4 2h a l 【i n 与m a k 锄模型中f i s 传输距离 在使用f i s 提供故障指示机制的恢复模型中，如图4 2 所示，在f i s 由故障链路的上 游或者下游l s r 向p m l 或p s l 传送的距离直接影响到这些模型的重路由性能，对于m a k a m 模型来说，当故障链路距离i n g r e s sl s r 越远时，其f i s 传输至p s l 所需时间就越长，其 重路由时间也就越长，同时会造成更高的丢包率；而h a s k i n 模型由于故障链路的上游l s r 迅速对业务流量进行重路由，并把f i s 和业务流一起传向p s l ，在f i s 到达p s l 的时间窗 口中，数据包的丢失大大降低，但是同时带来的是资源的消耗的增大与时延的大幅增长， 故障链路距离i n g r e s sl s r 越远，其时延增长越大。也就是说，h a s k i n 和m a k a m 模型对于 网络的故障恢复性能是随故障链路距离i n g r e s sl s r 距离变大而降低的的保护模型。 因此，在快速重路由模型中，f i s 传播距离、重路由后路径的跳数、l s r 在重路由过程 中计算量等因素在重路由算法中具备举足轻重的作用。 在本章以后的部分提出了一种基于生成树的快速重路由模型，以实现较好的、稳定的 快速重路由性能。 4 3 网络生成树模型 我们使用集合g = ( v ，e ，c ) 来表示的一个简单有向图来表示一个m p l s 网络拓扑，v 表示拓扑中节点的集合，e 表示拓扑中链路的集合，c 为各链路的带宽的集合。我们使用 e ( i ，j ) 表示节点v ；和v ，之间的链路。我们使用图4 3 所示m p l s 网络拓扑来说明本模型。 定义等距线：我们称网络拓扑中对于特定业务流，与目标节点有相等距离的节点集 合所在的线称之为等距线，如图4 4 所示。显然，在图4 4 中对于源节点和目标节点分别 为v 。和v ，的业务流，v 、v 。、v 。相对于目标节点v ，处于同一等距线上。 第2 8 页武汉科技大学硕士学位论文 图4 3m p l s 网络 图4 4 等距线 我们以图4 5 所示的m p l s 网络为例，来简单说明本模型的工作过程。从节点v o 到节 点v 1 3 传送一业务流，m p l s 网络建立标签交换路径( l s p ) ，假定建立的l s p 为v o v 6 一v 9 一v 1 3 。 v v13 图4 5 网络正常状态 对网络拓扑从目标节点开始进行广度遍历，产生生成树，如图4 6 所示。与目标节点 武汉科技大学硕士学位论文第2 9 页 具有相同距离的点在相同的等距线上，可以从产生生成树中过程中得到等距线，图4 6 中， 节点上所标值相等的点在同一等距线上。 1 3