一种MPLS的故障恢复方案

一种MPLS的故障恢复方案

李　彬,陈向东

(西南交通大学信息科学与技术学院,四川成都610031)

3

摘　要:在备份路径预建立的前提下,提出了一种MPLS的故障恢复方案———EB,该方案在现有的Bridge模型基础上引入了Backpressure信令以解决分组失序问题。理论性能评估及仿真实验均表明,EB较好地继承了Bridge方案原有的优势,并且解决了分组失序问题。经综合评估,EB有着良好的恢复性能。关键词:MPLS;快速重路由;故障恢复;路径恢复

中图法分类号:TP393　　　文献标识码:A　　　文章编号:100123695(2007)0220098203SchemeofMPLS2basedRecoveryLIBin,CHENXiang2dong

(SchoolofInformationScience&Technology,SouthwestJiaotongUniversity,ChengduSichuan610031,China)

Abstract:Onconditionthatthebackuppathhasbeenpre2established,aschemenamedEBforMPLS2basedrecoveryispres2

ent,whichintroducedBackpressuresignalingmechanismtoBridgeschemeinordertoeliminatethepacketreordering.BoththeoreticalanalysesandsimulationresultsindicatethatEBschemenotonlypreserveadvantagesofBridgebutalsosolvethepacketreordering.GenerallyevaluatingshowsEBhasgoodperformance.

Keywords:MPLS(Multi2ProtocolLabelSwitching);FastReroute;Recovery;PathRestoration

1　引言

IETF提出的MPLS(Multi2ProtocolLabelSwitching)已成为IP骨干网的核心技术之一。它是一种通过定长标签进行数据

2　相关方案简介

211　Haskin,Makam和Bridge方案

[1,2,7]

给定实例拓扑如图1所示。其中0,10为普通路由器;1～

9为LSR(LabelSwitchedRouter),共同构建了MPLS域。图1

转发的新技术,能够在无连接网络中引入面向连接网络的特性,并可以较好地支持QoS保障、流量工程、VPN等增值业务。作为骨干网技术,MPLS需要对网络故障作出快速响应,避免在路由器缓存中留下大量数据,导致网络性能下降及QoS降低。因此,关于MPLS的故障恢复方案引起了广大学者的广泛关注,并且取得了一系列研究成果。

国外方面,文献[1]提出了Haskin方案,在建立备份路径时构成回路,故障后实现快速重路由;文献[2]提出了Makam方案,故障后向上游节点发送故障指示信号(FIS)将流量切换至备份路径;文献[3,4]建议了一种新的Backpressure信令,以解决重路由时的分组失序问题;IETF针对故障恢复问题,提出了故障恢复的框架[5]。国内方面,文献[6]结合Simple2

dynamic和Makam方案提出了一种MD方案,有效地结合了两

中的工作路径为123252729。LSR1为MPLS域的PSL(Protec2

tionSwitchingLSR),负责在工作路径与备份路径间切换流量;LSP9为PML(ProtectionMergingLSR),负责从工作路径和备份

路径接收流量。假定业务流F由节点0发送至节点10。

对于Haskin方案,当链路发生故障后流量将沿工作路径的反向传送至PSL,再由PSL切换至备份路径(与工作路径不交);当故障恢复后将流量切换回工作路径。假定某时刻LSR5检测到LSR7故障,则LSR5将流量切换至备份路径5232122242

62829,故障恢复后,LSR负责将流量重新切换回原工作路径。Haskin方案为一种局部方案,优点是故障后可快速切换,因而

丢包较少;缺点是恢复路径较长、时延较高,并且在流量切换时将导致分组失序。

Makam方案是一种全局方案。它的恢复路径建立在PSL

者的优点;文献[7]扩展了LDP信令,提出一种新的Bridge模型,利用工作路径和备份路径的桥接路径实现了流量的切换。本文在备份路径预建立的前提下,综合了Bridge方案和Back2pressure信令,提出了一种改进的恢复方案EB(Enhanced

Bridge)方案,该方案的主要贡献在于,在继承Bridge方案优势

与PML之间。如图1所示,Makam方案是建立备份路径1222

4262829,LSR5检测到故障后会向上游传送故障指示信号(FIS)至PSL;由PSL负责将流量切换至备份路径,故障恢复后

的同时,解决了分组失序问题。本文给定的网络拓扑描述了现有的Haskin,Makam及Bridge方案,并给出了其不足之处。

同样向上游发送故障恢复信号(FRS),以告之PSL将流量切换回原工作路径。Makam方案的主要优点是失序分组较少,且恢复路径较短。但必须在FIS传送至PSL后才会实施切换,因而会造成较大的丢包。

Bridge方案扩展了LDP消息,得到了Bridge信令,并利用

收稿日期:2005211218;修返日期:2005212223基金项目:国家自然科学基金资助项目(60572026)

该信令构建了工作路径与备份路径之间的桥接路径。故障发

第2期李　彬等:一种MPLS的故障恢复方案　　　・99・

生后,流量将通过桥接路径切换至预建立的备份路径;故障恢复后,流量重新切换回工作路径。例如LSR5检测到LSR7故障,流量将沿12325262829传输。Bridge方案的优点在于恢复较快、恢复路径较短,但依然会导致分组失序。

212　Backpressure信令

[3,4,8]

时网络信息而计算得到的最优路径,因此可假设备份路径的总跳数大于等于工作路径跳数,即n≥m。假定业务流自I传送到M,节点I为PSL,节点M为PML。故障点为D,D≠I且D≠

M,定义H1为故障点到PSL的跳数(I2S2D),H1=s+1;H2为故障点到PML的跳数(D2E2M),H2=m-s;H3为Bridge路径跳数(S2K),H3=b(b≥2);H4为备份路径桥接点K到PSL的跳数(I2J2K),H4=k;H5为桥接节点K到PML的跳数(K2N2M),

H5=n-k+1。

Backpressure信令的基本目标是在路由器缓存未溢出的情

况下,通过对数据包在路由器中实施缓存来控制包传送至

PML的先后顺序。该信令主要包括如下三种信息:

(1)NR(b)。它通知上游路由器,某LSP流量正在缓存,

它包含了对剩余缓存空间的估计值。当上游Router收到

NR(b)时,它将不会向NR(b)的源路由器发送超过bBytes的数据,之后将进入缓存状态。当其缓存空间的占用率达到了某预定的门限之后,它将估计自己的剩余可用空间b,并以NR(b)的形式发送至上游Router。

(2)SE。它由PSL或故障的下游节点开始发送,并向下游Router发送至PML,用来标志工作路径的流量已经完成传送至PML。

(3)RD。PML接收到RD后会通知备份路径的上游节点

以下将结合图2来对比分析Haskin,Makam和EB方案的恢复时间、恢复路径时延、丢包和失序数目。重点将讨论

Haskin,Makam,Bridge和EB的失序情况。为简化分析,假定

每秒恒定发送R个分组,每个路由器的时延(队列和处理时延)均相同,记为d。

411　恢复时间

此处定义恢复时间为故障发生至流量经备份路径转发到达下一跳节点的时间间隔。故障发生后,Haskin和EB都启动快速重路由转发数据。由于故障后Haskin的重路由反向路径和EB重路由的Bridge路径都是预先建立的,因此两者的恢复时间相当。

Makam方案由S经反向路径传递FIS至I,此后切换流量

可以发送更多数据了。RD将沿上游节点方向到达NR(b)曾经到达过的Router。

该信令要求路由器估计出自NR(b)发出后到上游节点接

收NR(b)这段时间中链路传送的流量大小。文献[3]简单分析并描述了估计值b的数学表达式,关于该信令的具体配置及相应协议属于已有成果,本文在此不作赘述,详尽内容请参见文献[3,4]。

至备份路径,实施重路由,此间时间间隔d=dsi。当s=1时,

Haskin,Makam,EB有着相同的恢复时间;当s>1时,Haskin和EB的恢复时间优于Makam,并且s-1之值越大,EB和Haskin

3　EB方案简述

初始化:利用Bridge消息构建工作路径与备份路径之间的桥接路径。

故障发生算法流程如下:

Begin

恢复时间优势越明显。

412　恢复路径的端到端时延及丢包

在每个路由器时延恒定为d的前提下,端到端时延与流量传输所经过的路由器跳数成正比。三种方案在恢复的不同阶段其路径各不相同,因而端到端时延也不等同。故障发生后,在Haskin方案中,数据将沿反向路径回传,路径为S2I2J2K2N2

M,总跳数为2s+n-2;在Makam方案中,数据将沿备份路径

故障下游节点继续转发流量至PML,并在流量转发完毕后向PML

发送SE信息;

　故障上游节点将流量切换至Bridge恢复路径;　if(SE先于恢复路径流量到达PML)　　PML正常转发流量;

　　elseif(恢复路径流量先于SE到达)

　　　PML正常转发流量,缓存恢复路径流量;　　　　if(E到达PML&&PML缓存达到门限)　　　　取消缓存,转发恢复路径流量;

　　　　elseif(SE未达到PML&&PML缓存门限)

　　　　　{PML估计出b,向恢复路径上游节点发送NR(b);　　　　　do{上游节点继续缓存流量,向下游节点发送不超过b

的流量;}

　　　　　while(收到SE信息||节点缓存容量低于门限)　　　　　取消缓存,正常转发流量;　　　　}End

传输,此路径为I2J2K2N2M,跳数为n;在EB方案中,数据将先后沿Bridge路径和备份路径传输,整个路径为I2S2K2N2M,跳数为s+b+n-k-1。考虑到Bridge消息构建的桥接路径通常是在工作路径节点与备份路径节点未经其他节点的直连,因此为简化分析,可以设H3的跳数b=2。

对于Haskin方案,时延t1=(2s+n-2)d=(n-4-2H1)

d;Makam方案,t2=nd;EB方案,t3=(s+b+n-k-1)d=(s+n-k+1)d=(H1+H5-1)d。由t3-t2=(s-k+1)d=(H1-H4)d,则EB和Makam的时延差与节点K位置相关。当H1≤H4,t3≤t2;当H1>H4,t3>t2。因此,在H1≤H4时,EB有着最

小的端到端时延。假定故障的路由器到PSL与桥接路由器到

PSL有着相同的跳数,即H1=H4,代入得t2=t3,t24　理论性能评估及仿真分析

图2为假定的MPLS域,直线表示两节点直连,虚线表示

逻辑连接(中间经过其他节点)。假设工作路径为I2S2D2E2M,备份路径为I2J2K2N2M。其中工作路径跳数为m,备份路径跳数为n(跳数包括两端点),由于故障前工作路径通常是根据当

对t1的优势也变得愈加明显。

在三种方案中,发生在故障节点的数据包将丢失,这部分丢包是固定的。故障后,Haskin和EB会采用快速重路由将数据转发,不会再有新的丢包;而Makam方案在故障发生时要等故障指示信号反向传递到PSL后再执行切换操作,这段时间

・100・计算机应用研究2007年

内,由PSL转发至故障的工作路径的数据包将再次丢失。

413　失序分组数量

Trace分析工具为Tracegraph。仿真拓扑如图1所示,由节点0

向节点10发送UDP流,数据包大小为200Bytes。为简化仿真,利用MNS中的API———Setup2crlsp来设定恒定的缓冲大小。在0.8s时,工作路径的LSR发生故障,1.3s故障恢复。表1为统计数据。由于LSR3故障时,Haskin,Makam,EB有着相同的恢复路径,故表1只分析了LSR5和LSR7的故障情形。

仿真表明,EB继承了Bridge的良好性能,在恢复时间及丢包数目上与Haskin相当,而在端到端时延上明显优于Haskin,与Makam相当。重要的是,EB解决了Bridge方案的失序问题,消除了失序,优于上述三种方案。综上所述,从分析的四个参数上评估最终结果,EB具有较为全面的优良性能。

表1　仿真数据故障点LSR5由同一PSL转发的分组先后经两条不同的路径传输并汇聚在同一PML时,可能将导致分组失序。

(1)Haskin方案中共有两次流量切换。第一次为故障发生时,LSR(S)将流量由工作路径I2S2D2E2M切换至恢复路径I2

S2I2J2K2N2M;节点D发生故障后,E中和残余分组将继续转发

至M;E到M的跳数为m-s-1,而节点S经备份路径至M的跳数为n+s-1,由于n≥m,故n+s-1>m-s-1。因而当备份路径的分组到达M时,工作路径已无残余分组,不会导致失序。Haskin的第二次切换为故障恢复后,S将流量自备份路径重新切换回工作路径。切换前,备份路径上从LSR(S)到M有

(n+s-1)dR个分组;切换后,工作路径上分组经过(m-s+1)d时间到达M,在此期间,备份路径中的分组被M接收(m-s+1)dR个分组。原备份路径中的剩余分组数即为失序分组数,[(n+s-1)-(m-s+1)]dR=(n-m+2s-2)dR=(n-m+2H1-4)dR,这即是Haskin方案的失序分组数目。显然,其

LSR7

伴随H1的增长而增长,即故障点离PSL越远,失序分组越多。

(2)Makam方案同样也有两次流量切换,第一次为故障发生后,S的流量自工作路径切换至备份路径。由于备份路径跳数多于工作路径,则必定不会导致失序。按上述分析方法易得到第二次切换后失序分组数目为(n-m)dR。因此,失序分组数目伴随备份路径与工作路径跳数差的增大而增大。

(3)Bridge方案也不例外,它也有两次流量切换。第一次在故障发生后,S将流量切换至备份路径S2K2N2M,工作路径中的残余分组将在(m-s-1)d,即(H2-1)d后被M接收,而经备份路径传输后到达M的时间间隔为(n-k+b)d。前面已经假定b=2,故上式为(n-k+2)=(H5+1)d。①当H5+1≥H2-1时,工作路径残余分组已先于备份路径分组被M接收,因此不会导致失序。然而当故障恢复后,在实施第二次切换时,S将流量切换至S2D2E2M,S至M的跳数为m-s+1=H2+1,而原备份路径中S至M的跳数为n-k+2=H5+1。如果H5>H2则必然导致失序,失序分组数为(H5-H2)dR。②当H5+1(4)EB方案在Bridge方案的基础上引入了Backpressure信令。第一次切换流量时,故障下游节点将残余分组完全转发至下游节点后,将向下游发送SE信息,以告之工作路径已无残余流量。当SE先于备份路径S2K2N2M的流量到达M,此时不会导致失序,M等待备份路径的流量到来并将其转发;当备份路径流量先于SE信息到达M时,此时将导致失序,M将备份路径的流量实施缓存。当缓存容量达到预定的门限值时,M对缓存容量作出估计,向备份路径的上游节点发送NR(b)信息,备份路径流量将被缓存,直到M收到工作路径的SE信息。此时,M向上游节点发送RD信息以告之取消缓存并返回正常转发状态。因此,EB可以解决Bridge未解决的失序分组问题。第二次切换时,类似上述操作,同样无失序分组。

414　仿真分析

[9,10]

方案恢复时间(ms)端到端时延(恢复路径)丢包数失序分组

Haskin10.6105.1410Makam18.081.3133Bridge10.681.443EB10.681.440Haskin10.6128.0417Makam26.281.3183Bridge10.681.443EB10.681.4405　结束语

本文提出了MPLS的故障恢复方案———EB。通过形式化的理论分析及仿真数据,与经典的Haskin,Makam及现有的

Bridge方案在恢复时间、恢复路径时延、丢包、失序等几个参数

上进行了对比分析。EB在兼顾Bridge优势的同时,消除了分组失序,总体评估优于现有的这几种方案。

下一步工作将针对多故障的故障恢复模型进行研究。针对多故障情形,同样以恢复方案的上述四个性能参数作为评价标准优化多故障的恢复方案。参考文献:

[1]DHaskin,RKrishnan.AMethodforSettinganAlternativeLabel

SwitchedPathstoHandleFastReroute[R].IETFDraft,2001.[2]ChangchengHuang,VSharma,SriniasMakam.APathProtection/

RestorationMechanismforMPLSNetworks[R].IETFDraft,2000.[3]RBarto󰂭,MRaman.DynamicIssuesinMPLSServiceRestoration

[C].Proc.ofthe14thIASTEDInternationalConferenceonParallelandDistributedComputingandSystem(PDCS),2002.

[4]RBarto󰂭,AGandhi.AControlProtocoltoMinimizetheTransient

EffectsorMPLSServiceRestoration[R].Dept.ofComputerScience,Univ.ofNewHampshire,2002.[5]

IETFRFC346922003,FrameworkforMPLS2basedRecovery[S].[6]康剑,曹阳,葛非,等.一种新的MPLS网络故障恢复算法[J].计

算机应用研究,2005,22(8):2072209.[7]杨新宇,王鹏,等.一种新的基于MPLS的快速重路由模型[J].微

电子学与计算机,2004,21(4):31234.[8]AGandhi,RBarto󰂭.DynamicIssuesinMPLSServiceRestoration

[R].Dept.ofComputerScience,Univ.ofNewHampshire,2001.[9]GAhn,WChun.SimulatorforMPLSPathRestorationandPerfor2

manceEvaluation[C].ATMandHighSpeedIntelligentInternetSymposium,2001.

[10]徐雷鸣,庞博.NS与网络模拟[M].北京:人民邮电出版社,2003.

作者简介:

李彬(19822),男,四川成都人,硕士研究生,主要研究方向为计算机网络和宽带通信;陈向东(19672),男,重庆人,博导,主要研究方向为信息获取与处理、无线传感器网络。

本文的仿真环境为NS2126,并添加了MNS22112ns22126,