一種ＭＰＬＳ的故障恢復方案
2007-01-01 00:00:00李彬陳向東
計算機應用研究 2007年2期
摘 要：在備份路徑預建立的前提下，提出了一種MPLS的故障恢復方案——EB，該方案在現有的Bridge模型基礎上引入了Backpressure信令以解決分組失序問題。理論性能評估及仿真實驗均表明，EB較好地繼承了Bridge方案原有的優勢，并且解決了分組失序問題。經綜合評估，EB有著良好的恢復性能。
關鍵詞：MPLS； 快速重路由； 故障恢復； 路徑恢復
中圖法分類號：TP393文獻標識碼：A
文章編號：1001—3695(2007)02—0098—03
1 引言
IETF提出的MPLS(Multi-Protocol Label Switching)已成為IP骨干網的核心技術之一。它是一種通過定長標簽進行數據轉發的新技術，能夠在無連接網絡中引入面向連接網絡的特性，并可以較好地支持QoS保障、流量工程、VPN等增值業務。作為骨干網技術，MPLS需要對網絡故障作出快速響應，避免在路由器緩存中留下大量數據，導致網絡性能下降及QoS降低。因此，關于MPLS的故障恢復方案引起了廣大學者的廣泛關注，并且取得了一系列研究成果。
國外方面，文獻[1]提出了Haskin方案，在建立備份路徑時構成回路，故障后實現快速重路由；文獻[2]提出了Makam方案，故障后向上游節點發送故障指示信號（FIS）將流量切換至備份路徑；文獻[3，4]建議了一種新的Backpressure信令，以解決重路由時的分組失序問題；IETF針對故障恢復問題，提出了故障恢復的框架[5]。國內方面，文獻[6]結合Simple-dynamic和Makam方案提出了一種MD方案，有效地結合了兩者的優點；文獻[7]擴展了LDP信令，提出一種新的Bridge模型，利用工作路徑和備份路徑的橋接路徑實現了流量的切換。本文在備份路徑預建立的前提下，綜合了Bridge方案和Backpressure信令，提出了一種改進的恢復方案EB（Enhanced Bridge）方案，該方案的主要貢獻在于，在繼承Bridge方案優勢的同時，解決了分組失序問題。本文給定的網絡拓撲描述了現有的Haskin，Makam及Bridge方案，并給出了其不足之處。
2 相關方案簡介
2.1 Haskin，Makam和Bridge方案[1，2，7]
給定實例拓撲如圖1所示。其中0，10為普通路由器；1—9為LSR（Label Switched Router），共同構建了MPLS域。圖1中的工作路徑為1—3—5—7—9。LSR1為MPLS域的PSL（Protection Switching LSR），負責在工作路徑與備份路徑間切換流量；LSP9為PML（Protection Merging LSR），負責從工作路徑和備份路徑接收流量。假定業務流F由節點0發送至節點10。
對于Haskin方案，當鏈路發生故障后流量將沿工作路徑的反向傳送至PSL，再由PSL切換至備份路徑（與工作路徑不交）；當故障恢復后將流量切換回工作路徑。假定某時刻LSR5檢測到LSR7故障，則LSR5將流量切換至備份路徑5—3-1—2—4—6—8—9，故障恢復后，LSR負責將流量重新切換回原工作路徑。Haskin方案為一種局部方案，優點是故障后可快速切換，因而丟包較少；缺點是恢復路徑較長、時延較高，并且在流量切換時將導致分組失序。
Makam方案是一種全局方案。它的恢復路徑建立在PSL與PML之間。如圖1所示，Makam方案是建立備份路徑1—2—4—6—8—9，LSR5檢測到故障后會向上游傳送故障指示信號(FIS)至PSL；由PSL負責將流量切換至備份路徑，故障恢復后同樣向上游發送故障恢復信號（FRS），以告之PSL將流量切換回原工作路徑。Makam方案的主要優點是失序分組較少，且恢復路徑較短。但必須在FIS傳送至PSL后才會實施切換，因而會造成較大的丟包。
Bridge方案擴展了LDP消息，得到了Bridge信令，并利用該信令構建了工作路徑與備份路徑之間的橋接路徑。故障發生后，流量將通過橋接路徑切換至預建立的備份路徑；故障恢復后，流量重新切換回工作路徑。例如LSR5檢測到LSR7故障，流量將沿1—3—5—6—8—9傳輸。Bridge方案的優點在于恢復較快、恢復路徑較短，但依然會導致分組失序。
2.2 Backpressure信令[3，4，8]
Backpressure信令的基本目標是在路由器緩存未溢出的情況下，通過對數據包在路由器中實施緩存來控制包傳送至PML的先后順序。該信令主要包括如下三種信息：
（1）NR(b)。它通知上游路由器，某LSP流量正在緩存，它包含了對剩余緩存空間的估計值。當上游Router收到NR(b)時，它將不會向NR(b)的源路由器發送超過b Bytes的數據，之后將進入緩存狀態。當其緩存空間的占用率達到了某預定的門限之后，它將估計自己的剩余可用空間b，并以NR(b)的形式發送至上游Router。
（2）SE。它由PSL或故障的下游節點開始發送，并向下游Router發送至PML，用來標志工作路徑的流量已經完成傳送至PML。
（3）RD。PML接收到RD后會通知備份路徑的上游節點可以發送更多數據了。RD將沿上游節點方向到達NR(b)曾經到達過的Router。
該信令要求路由器估計出自NR(b)發出后到上游節點接收NR(b)這段時間中鏈路傳送的流量大小。文獻[3]簡單分析并描述了估計值b的數學表達式，關于該信令的具體配置及相應協議屬于已有成果，本文在此不作贅述，詳盡內容請參見文獻[3，4]。
3 EB方案簡述
初始化：利用Bridge消息構建工作路徑與備份路徑之間的橋接路徑。
故障發生算法流程如下：
Begin
故障下游節點繼續轉發流量至PML，并在流量轉發完畢后向PML發送SE信息；
故障上游節點將流量切換至Bridge恢復路徑；
if(SE先于恢復路徑流量到達PML)
PML正常轉發流量；
else if(恢復路徑流量先于SE到達)
PML正常轉發流量，緩存恢復路徑流量；
if(E到達PMLPML緩存達到門限)
取消緩存，轉發恢復路徑流量；
else if(SE未達到PMLPML緩存門限)
{PML估計出b，向恢復路徑上游節點發送NR(b)；
do{上游節點繼續緩存流量，向下游節點發送不超過b的流量；}
while（收到SE信息||節點緩存容量低于門限）
取消緩存，正常轉發流量；}End
4 理論性能評估及仿真分析
圖2為假定的MPLS域，直線表示兩節點直連，虛線表示邏輯連接（中間經過其他節點）。假設工作路徑為I-S-D-E-M，備份路徑為I-J-K-N-M。其中工作路徑跳數為m，備份路徑跳數為n(跳數包括兩端點)，由于故障前工作路徑通常是根據當時網絡信息而計算得到的最優路徑，因此可假設備份路徑的總跳數大于等于工作路徑跳數，即n≥m。假定業務流自I傳送到M，節點I為PSL，節點M為PML。故障點為D，D≠I且D≠M，定義H1為故障點到PSL的跳數（I-S-D），H1=s+1；H2為故障點到PML的跳數（D-E-M），H2=m-s；H3為Bridge路徑跳數（S-K），H3=b(b≥2)；H4為備份路徑橋接點K到PSL的跳數(I-J-K)，H4=k；H5為橋接節點K到PML的跳數(K-N-M)，H5=n-k+1。
以下將結合圖2來對比分析Haskin，Makam和EB方案的恢復時間、恢復路徑時延、丟包和失序數目。重點將討論Haskin，Makam，Bridge和EB的失序情況。為簡化分析，假定每秒恒定發送R個分組，每個路由器的時延（隊列和處理時延）均相同，記為d。
4.1 恢復時間
此處定義恢復時間為故障發生至流量經備份路徑轉發到達下一跳節點的時間間隔。故障發生后，Haskin和EB都啟動快速重路由轉發數據。由于故障后Haskin的重路由反向路徑和EB重路由的Bridge路徑都是預先建立的，因此兩者的恢復時間相當。
Makam方案由S經反向路徑傳遞FIS至I，此后切換流量至備份路徑，實施重路由，此間時間間隔d=dsi。當s=1時，Haskin，Makam，EB有著相同的恢復時間；當s＞1時，Haskin和EB的恢復時間優于Makam，并且s-1之值越大，EB和Haskin恢復時間優勢越明顯。
4.2 恢復路徑的端到端時延及丟包
在每個路由器時延恒定為d的前提下，端到端時延與流量傳輸所經過的路由器跳數成正比。三種方案在恢復的不同階段其路徑各不相同，因而端到端時延也不等同。故障發生后，在Haskin方案中，數據將沿反向路徑回傳，路徑為S-I-J-K-N-M，總跳數為2s+n-2；在Makam方案中，數據將沿備份路徑傳輸，此路徑為I-J-K-N-M，跳數為n；在EB方案中，數據將先后沿Bridge路徑和備份路徑傳輸，整個路徑為I-S-K-N-M，跳數為s+b+n-k-1。考慮到Bridge消息構建的橋接路徑通常是在工作路徑節點與備份路徑節點未經其他節點的直連，因此為簡化分析，可以設H3的跳數b=2。
在三種方案中，發生在故障節點的數據包將丟失，這部分丟包是固定的。故障后，Haskin和EB會采用快速重路由將數據轉發，不會再有新的丟包；而Makam方案在故障發生時要等故障指示信號反向傳遞到PSL后再執行切換操作，這段時間內，由PSL轉發至故障的工作路徑的數據包將再次丟失。
4.3 失序分組數量
由同一PSL轉發的分組先后經兩條不同的路徑傳輸并匯聚在同一PML時，可能將導致分組失序。
（1）Haskin方案中共有兩次流量切換。第一次為故障發生時，LSR(S)將流量由工作路徑I-S-D-E-M切換至恢復路徑I-S-I-J-K-N-M；節點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方案的失序分組數目。顯然，其伴隨H1的增長而增長，即故障點離PSL越遠，失序分組越多。
（2）Makam方案同樣也有兩次流量切換，第一次為故障發生后，S的流量自工作路徑切換至備份路徑。由于備份路徑跳數多于工作路徑，則必定不會導致失序。按上述分析方法易得到第二次切換后失序分組數目為(n-m)dR。因此，失序分組數目伴隨備份路徑與工作路徑跳數差的增大而增大。
（3）Bridge方案也不例外，它也有兩次流量切換。第一次在故障發生后，S將流量切換至備份路徑S-K-N-M，工作路徑中的殘余分組將在(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將流量切換至S-D-E-M，S至M的跳數為m-s+1=H2+1，而原備份路徑中S至M的跳數為n-k+2=H5+1。如果H5＞H2則必然導致失序，失序分組數為(H5-H2)dR。②當H5+1＜H2-1時，則在工作路徑的殘余分組完全到達M之前，備份路徑中的分組已到達M，將導致失序。失序分組數目為(m-s-1-n+k-2)dR=(H2-H5-2)dR。故障恢復后，由于H5+1＜H2-1＜H2+1，故S-D-E-M的跳數大于S-K-N-M的跳數，此時不再有失序分組。
（4）EB方案在Bridge方案的基礎上引入了Backpressure信令。第一次切換流量時，故障下游節點將殘余分組完全轉發至下游節點后，將向下游發送SE信息，以告之工作路徑已無殘余流量。當SE先于備份路徑S-K-N-M的流量到達M，此時不會導致失序，M等待備份路徑的流量到來并將其轉發；當備份路徑流量先于SE信息到達M時，此時將導致失序，M將備份路徑的流量實施緩存。當緩存容量達到預定的門限值時，M對緩存容量作出估計，向備份路徑的上游節點發送NR(b)信息，備份路徑流量將被緩存，直到M收到工作路徑的SE信息。此時，M向上游節點發送RD信息以告之取消緩存并返回正常轉發狀態。因此，EB可以解決Bridge未解決的失序分組問題。第二次切換時，類似上述操作，同樣無失序分組。
4.4 仿真分析[9，10]
本文的仿真環境為NS2.26，并添加了MNS-2.1-ns-2.26，Trace分析工具為Tracegraph。仿真拓撲如圖1所示，由節點0向節點10發送UDP流，數據包大小為200Bytes。為簡化仿真，利用MNS中的API——Setup-crlsp來設定恒定的緩沖大小。在0.8s時，工作路徑的LSR發生故障，1.3s故障恢復。表1為統計數據。由于LSR3故障時，Haskin，Makam，EB有著相同的恢復路徑，故表1只分析了LSR5和LSR7的故障情形。
仿真表明，EB繼承了Bridge的良好性能，在恢復時間及丟包數目上與Haskin相當，而在端到端時延上明顯優于Haskin，與Makam相當。重要的是，EB解決了Bridge方案的失序問題，消除了失序，優于上述三種方案。綜上所述，從分析的四個參數上評估最終結果，EB具有較為全面的優良性能。
5 結束語
本文提出了MPLS的故障恢復方案——EB。通過形式化的理論分析及仿真數據，與經典的Haskin， Makam及現有的Bridge方案在恢復時間、恢復路徑時延、丟包、失序等幾個參數上進行了對比分析。EB在兼顧Bridge優勢的同時，消除了分組失序，總體評估優于現有的這幾種方案。
下一步工作將針對多故障的故障恢復模型進行研究。針對多故障情形，同樣以恢復方案的上述四個性能參數作為評價標準優化多故障的恢復方案。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
