ＭＰＬＳ ＶＰＮ動態路徑管理算法

摘 要：針對標簽交換路徑的設計與維護問題，提出基于故障恢復模型的MPLS VPN動態路徑管理算法。該算法在備份路徑設計準則的基礎上，測試全連通MPLS VPN中備份路徑可用性的條件，利用快速備份路徑構造算法，在多故障發生時，自動地構造滿足客戶故障恢復需求的VPN路徑，從而使VPN業務受干擾程度最小。

關鍵詞：邊界網關協議;多協議標簽交換;虛擬專用網;故障恢復

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2009)06-2224-05

doi:10.3969/j.issn.1001-3695.2009.06.068

Algorithm of dynamically managing MPLS VPN path

LIANG Hai-ying， LI Shu-mei， LI Duo

( School of Computer， Jilin Normal University， Siping Jilin 136000， China)Abstract:This paper put forward the algorithm to dynamically manage MPLS VPN path based on failure recover model.This method could dynamically configure the service paths of MPLS VPN satisfying the resilience requirement from the customers.Specifically，described backup path design rules and derived the conditions for testing the availability of feasible backup paths satisfying the resilience constraints in a full mesh MPLS VPN.And presented fast backup path construction algorithms which could make the MPLS VPN service to be available with minimal disruption， satisfying the resilience requirement from the customers.

Key words:BGP; MPLS; VPN; failure resilience

0 引言

在MPLS VPN中，VPN路由信息是由MP-BGP在服務提供商的骨干網上分發，由MPLS在參與的VPN站點之間轉發VPN流量。VPN客戶站點的無連接IP流量是通過提供商MPLS骨干的面向連接的路徑LSP（標簽交換路徑）透明地傳輸的。MPLS VPN這些路徑的有效設計是一個活躍的研究領域。

目前，在許多情況下，LSP是由網絡管理人員手工設計的。然而，必須能夠自動設計并維護這些路徑，才能在預料不到的多個故障發生時，給客戶提供最小或沒有干擾的服務。

故障恢復表示從網絡組件故障中恢復的能力。目前已經有許多關于網絡、系統、業務錯誤管理以及各種不同恢復機制的研究^[1，2]，包括MPLS^[3，4]、GMPLS^[5，6]和光纖網絡^[7，8]的最新研究。Lee等人^[9]提出了一個分層方案解決MPLS網絡的多個故障，此方案將發生故障中有高優先權的主要路徑分配給預先保留的路徑，而將其他故障路徑分配給共享的備份路徑，但沒有考慮段的故障恢復。Clouquer等人^[10]分析了在雙重故障發生情況下的分段可恢復全連通網絡的有效性，但這個方法僅適用雙重故障發生的情況。然而，對形式化定義的故障恢復工作的研究很少，對此，本文提出基于故障恢復模型的MPLS VPN動態路徑管理方法，利用簡單的故障恢復模型，有效地從故障中恢復出來，以便提高業務的可用性。

IETF標準為LSP路徑管理提出兩種恢復機制，即保護機制和恢復機制^[3]。a）保護機制通常叫做快速重路由。該機制通過事先裝配好備用LSP路徑，使網絡發生故障時服務的干擾減到最少。b）恢復機制也叫做重路由機制。通常采用Make-Before-Break原則，在新備份路徑裝備期間，舊路徑仍然在使用。通常情況下，在故障發生后建立備份路徑，當備份路徑被建立并分配必需的資源，完成裝備過程之后，發生故障的主要路徑的數據流量將被轉到備份路徑，并且關掉舊路徑。

在本文中，主要研究當多個故障發生時，可以快速構建LSP路徑，以此進行MPLS VPN業務管理的一種混合方法。這一方法之所以叫做混合方法，是因為在某種意義上，該方法能夠預先建立滿足k-保護故障恢復約束的備份路徑，這與IETF中提出的保護機制相似；當備份路徑也受故障影響時，構造其他可用的備份路徑，這與IETF中提出的恢復機制相似。在混合方法中，首先提出故障恢復模型及備份路徑設計準則；然后獲取在全連通MPLS VPN中，滿足故障恢復約束可用的備份路徑存在的條件；接著提出時間復雜度為O（n）的簡單快速備份路徑構造算法，該算法能動態地配置滿足來自客戶的TE故障恢復需求的MPLS VPN路徑，從而使VPN業務受故障干擾的程度降為最低；最后，通過仿真評價全連通結構MPLS骨干網絡的性能和業務可用性。

本文提出的故障恢復混合管理方法不同于其他方法的特點如下：

a）在設計故障恢復MPLS VPN路徑時，不僅考慮了主要路徑上的故障，而且考慮了備份路徑發生故障的情況。

b）考慮多個故障發生的情況，既考慮鏈路發生故障，也考慮節點發生故障時，如何構建可用備份路徑。

c）提出故障恢復的形式化定義，并將其用于動態路徑的重建和維護過程中。

1 MPLS VPN業務故障恢復模型

MPLS VPN管理的故障恢復路徑設計問題可以表述如下：對于MPLS VPN由節點、鏈路和故障恢復約束構成的網絡，建立并維持主要路徑和備份路徑，以便在多個組件發生故障時，使滿足故障恢復約束的服務干擾減到最少。

主要路徑是正在工作的路徑，VPN數據流量沿著它傳輸；備份路徑是由于節點或鏈路發生故障，導致主要路徑不可用時，用來傳輸VPN數據流量的路徑。路徑域表示在主要路徑中的節點集；而非路徑域表示不在主要路徑中的節點集，用于備份路徑的構建。一個優質的VPN服務為每個服務保留主要路徑和備份路徑兩條路徑，以便保證較高的生存力。

圖1為顯示MPLS骨干的故障恢復模型。其中存在兩條VPN故障恢復路徑：一條從PE1~PE2；另一條從PE3~PE4。粗線表示主要路徑，虛線表示備份路徑。圖1表示從PE1~PE2的主要路徑中發生鏈路或節點故障，而且這些故障也可能影響預先裝配的從PE3~PE4的備份路徑，即故障可能同時影響主要路徑和備份路徑。

包含故障的組件區域由故障點指出，為了使故障點能被局部地恢復，故障通告方法使在故障點發生的故障被通告到與這個VPN連接的PE節點，圖中箭頭指出故障通告的傳播方向。在多個故障同時發生的情況下，可以從多個故障點產生多個故障通告。一旦PE節點接收到這些通告，它就檢查故障的節點或者鏈路是否與它的主要路徑或備份路徑有關。如果故障組件影響到這些路徑之一，就嘗試動態地利用沒有被故障組件影響的節點和鏈路重建路徑。

路徑故障恢復非正式地定義為由于預料不到的事件使得系統的一些組件發生故障時，能提供具有最小干擾的通信業務和快速恢復到健全情況的能力。

下面給出故障恢復的形式化定義。

定義1 故障恢復。在MPLS VPN中的路徑故障恢復被形式化定義為一個具有實際值的函數：路徑故障恢復ξ=保護集1/m×（保護的組件數/總的組件數）（1）

其中：m是主路徑的多因素，定義為正在共享備份路徑或路徑段的主要路徑總數；保護集表示為保護主要路徑的所有備份路徑或路徑段的集合；總的組件數是指在一條路徑中組件的總數，不包括MPLS網絡的端節點數，因為端節點總是在主要路徑與備份路徑之間共享；保護的組件數表示由備份路徑保護的路徑中組件的總數。

2 備份路徑設計準則和存在條件

2.1 路徑設計準則

對快速構造備份路徑提出以下設計準則：

準則1 在路徑中節點僅被經過一次，即在路徑中不應該有環。

準則2 對于給定主要路徑的備份路徑，在兩者共享的子路徑中，備份路徑的節點和鏈路出現的順序必須與主要路徑中出現的順序相同。

圖2顯示違反路徑設計準則的情況。在圖2(a)中，路徑〈S，…，T，Q，D〉是一條主要路徑，給出兩種構造備份路徑的情況。圖2(a)顯示的備份路徑〈S，P，Q，R，T，Q，D〉違反了準則1，因為節點Q被經過兩次，有一個環〈Q，R，T，Q〉。圖2(b)顯示的備份路徑〈S，P，Q，R，T，W，D〉，雖然滿足準則1，但又因為備份路徑應該遵從主要路徑的子路徑〈T，Q，D〉中節點出現的次序，但該備份路徑沒有遵從這個順序，所以違反了準則2。

準則3 除了段的開始節點和終止節點以外，主要路徑中被保護的段與備份路徑中被保護的段無關。

準則3是指在主要路徑被保護的段中，除了被保護的段的開始和終止節點以外，沒有組件可用做備份路徑的構造。圖3表示違反準則3的情況。主要路徑為〈S，P，…，Q，…，T，D〉。其中段〈S，R，Q，W，D〉或段〈S，P，T，D〉為備份路徑構造的候選段，這兩個候選段中除了開始和終止節點以外，還有主要路徑中的節點，所以違反了準則3。

定理1 路徑拒絕規則。設計備份路徑時，不考慮從主要路徑中被保護段的一個節點擴散到另一個節點（除被保護段的端節點外）的任何鏈路。

證明 假設有一條路徑〈S，…，T，Q，…，D〉，如圖4所示。

不失一般性，假設圖4中段〈S，…，T〉中的標志X所指出的一些組件（鏈路/節點）發生故障，那么，為了要構造一條備份路徑保護段〈S，…，T〉，可以試著使用一個從開始節點S到主要路徑中另外的一個節點Q的直接鏈路〈S，Q〉。為了要在這種情況下建立一條備份路徑，可以從Q到R、Q到T或Q到D。使用〈Q，T〉鏈路或子路徑〈Q，…，D〉的選擇都會違反準則2。事實上，選擇路徑域中任何節點都會違反準則2。因此，鏈路〈Q，R〉是對于非路徑域中R的惟一選擇。

當到達節點R，就只能選擇鏈路〈R，T〉或使用非路徑域中其他節點W，才能回到節點T。當到達節點T，也有兩個選擇：使用鏈路〈T，Q〉或使用另一條鏈路。如果使用鏈路〈T，Q〉，則會產生環，違反準則1；如果使用到這條路徑中任何節點的另一條鏈路，則會違反準則2。因此，為了保護段〈S，…，T〉，從S到路徑域其他節點的直接鏈路構造的備份路徑都會違反準則1或準則2。通過結合準則1~3，可以得出結論，備份路徑設計不考慮從主要路徑節點擴散到主要路徑中其他節點的任何鏈路。

在圖4中，依照準則3，從節點S與T之間的中間節點擴散的任何鏈路都不應該作為備份路徑。直接連接被保護段的開始節點和終止節點的鏈路，是使用路徑域中節點構造備份段的惟一候選。

證畢。

2.2 可用備份路徑存在條件

下面給出在全連通MPLS VPN中路徑獨立的定義。

定義2 路徑獨立。對于全連通MPLS VPN的一個路徑，如果存在兩個路徑環，除了包含在這個路徑鏈路以外的所有鏈路都是不同的，那么這兩個環被稱為是路徑獨立的。

舉例來說，如圖5顯示的網絡，對于路徑〈S，P1，…，Pk+1，D〉，假設存在兩個路徑環C1和C2。其中C1=〈P1，R，Pk+1，…，P1〉和C2=〈P1，Q， Pk+1，…，P1〉。因為環C1和C2除了這條路徑以外沒有共享鏈路，所以它們是路徑獨立的。

定義3 k-保護。除了開始節點和終端節點以外，如果一條由k-1個鄰節點和連接這些節點的k條鏈路構成的任何路徑段，被備份路徑保護，那么稱這條路徑是k-保護的。

舉例來說，1-保護路徑是指被一條路徑的一條鏈路保護；2-保護路徑是指被一個節點和連到這個路徑中這個節點的兩條鏈路保護。

注意，如果有來自客戶的故障恢復需求，那么就能決定與這個需求相對應的k-保護路徑，原因在于，故障恢復能決定在路徑中保護的組件數。在這種情況下，主要路徑被稱為有一個長度為k的保護區域。

定理2 對于一條路徑，存在彼此路徑獨立的兩個環，每個環的k條鏈路與這條路徑共享。那么，對于任何一個環中沒被包含在這條路徑中鏈路的任何故障，都能構造一個k-保護路徑。

證明 不失一般性，如圖5所示，對于路徑〈S，P1，…，Pk+1，D〉，假設存在兩條路徑獨立的環C1和C2，C1=〈P1，R， Pk+1，…，P1〉和C2=〈P1，Q， Pk+1，…，P1〉。其中S和D分別代表入口節點和出口節點。注意節點R和Q沒被包含在這條路徑中。

假設某個環中除了子路徑〈P1，…，Pk+1〉之外的某條鏈路發生了故障，不妨設環C1發生故障，即〈P1，R〉或〈R，Pk+1〉發生故障。在這種情況下，能構造一條備份路徑〈S，P1，Q，Pk+1，…，D〉。因此，路徑〈S，P1，…，Pk+1，D〉在環C1發生故障情況下是k-保護的；同樣，可以證明環2發生故障時也能構造一條備份路徑〈S，P1，R，Pk+1，…，D〉；如果環C1和C2都發生故障，路徑被切斷，不能為這條路徑構造k-保護的備份路徑。

證畢。

現在給出滿足故障恢復約束的可用備份路徑的存在條件。

定理3 對于有M個節點的全連通結構的MPLS VPN，如果保護路徑的δ條鏈路發生故障，則使得任何有n個節點的路徑都是k-保護的條件由式（2）給出。其中M>3，k>1。

δ=(i×k)+(n-k)；i≤k

(i×k)+(j-k)+(n-k)； j＞k(2)

其中:n=i×k+j，j=0，1， …，（k-1)，i是一個非負整數。

證明 不失一般性，假設有n個節點的路徑〈P0，P1，…，Pn-2，Pn-1〉被配置如圖6所示。其中環〈P0，Pk，…，P1，P0〉、〈P1，Pk+1，Pk，…，P1〉和〈Pn-1-k，Pn-1，…，Pn-k，Pn-1-k〉等都是路徑獨立的環。容易看出這樣的環共有n-k個，每個環是由連接這條路徑中相距k條鏈路的兩個端節點的直接鏈路和這條路徑中相對應的k條鏈路構成。

接下來證明在圖6的較低部分從節點R開始有i×k個獨立環。

很明顯，環〈R，P0，P1，…，Pk，R〉和〈R，P1，…，Pk+1，R〉是獨立的。用同樣的方法，能構造從R開始直接鏈路〈R，P0〉，接下來另一個直接鏈路〈R，P1〉，…，一直到直接鏈路〈R，Pk-1〉。然而，當到達鏈路〈R，Pk〉時，發現不能讓環〈R，Pk，Pk+1，…，P2k，R〉是獨立環了，因為如果再繼續進行，鏈路〈R，Pk〉就被兩個環〈R，P0，P1，…，Pk，R〉和〈R，Pk，Pk+1，…，P2k，R〉共享了。

接下來，從鏈路〈R，Pk+1〉開始繼續構造獨立環，如果從Pk+1開始的路徑中存在多于k個節點，那么就可構造獨立環〈R，Pk+1，Pk+2， …，P2k，R〉。如果從Pk+1開始剩余節點比k少，那么就不能構造任何覆蓋k條鏈路的獨立環了。

假設有j個剩余節點。對于有n個節點的一條路徑，這條路徑能被表示成k的倍數與剩余j個節點的和，即n=k×i+j。其中i是一個非負的整數，其值等于節點數n除以k的商；j=0，1，…，（k-1)，其值等于節點數n除以k的余數。在這種情況下，如果n=ik，對于每個由k個節點構成的塊，存在k個獨立環，則獨立環總數為i×k。如果j≤k，獨立環數會仍然是i×k。如果j>k，能構造j-k個獨立環，則獨立環總數為(i×k)+(j-k)。

又因為有(n-k)個直接鏈路連接的獨立環，所以，對于j≤k情況，獨立鏈路總數為(i×k)+(n-k)。對于j>k的情況，獨立鏈路數等于(i×k)+(j-k)+(n-k)。

證畢。

注意，如果δ條鏈路中存在一條不發生故障的鏈路，就可以用它構造一個k-保護的備份路徑。所以，δ-1是保證發生故障時，存在k-保護備份路徑可允許的最大鏈路故障數。如果故障通告數超過上界，那么就不能保證存在k-保護的備份路徑段。

3 動態路徑管理算法

進行MPLS骨干主要路徑和備份路徑的動態建立和維護，是路徑故障恢復管理的關鍵問題。當故障影響主要路徑時，可能有兩種情況：備份路徑沒受影響；或備份路徑也受到影響。

如果在主要路徑中沒有故障，那么VPN業務數據進入源節點，而且被傳送到目的節點。如果主要路徑發生了故障，那么故障通告被送到源節點，當備份路徑不受影響時，執行合適的資源預定標記操作后，VPN數據流量就能被立刻轉到備份路徑上，而且數據可以經由這條備份路徑傳送到目的地。如果在備份路徑中有故障，又滿足可用備份路徑存在條件，那么，對任何組件發生故障的情況（不僅考慮鏈路故障，也考慮節點故障），都可以為一條給定的主要路徑快速構造至少一個獨立的備份路徑，將數據轉到新備份路徑上。

MPLS VPN動態路徑管理方法主要由下列三個階段組成。在這里，一個組件是一個節點或一條鏈路。

階段1 初始化；

階段2 當來自MPLS骨干的故障通告到達時，裝配新的VPN路徑集使業務干擾最少化；

階段3 MPLS骨干網絡以一個指定的時間間隔定期地更新主要路徑和備份路徑的可用性。

在階段1初始化，為每個VPN決定主要路徑和備份路徑集，可以考慮VPN業務的服務提供商的策略和故障恢復約束，這可能需要擴展VRF表和路由信息庫（RIB）。在階段2中，一旦發現P節點或連接它們的鏈路發生故障，PE節點執行下面描述的DPMA（dynamic path management algorithms，動態路徑管理算法）。當存在可用備份路徑時，執行故障恢復操作，使備份路徑工作，并且把數據流量轉換到備份路徑上。在階段3，定期檢查對于給定的VPN業務的主要路徑或者備份路徑是否可用。這里只是簡單地檢查路徑是否由于路徑構成組件發生故障而不可用。

當一個故障通告到達時，每個PE全都執行DPMA。如果路徑的任何組件與故障有關，那么這條路徑就受這個故障通告影響。如果從P節點到達的故障通告影響了主要路徑，那么PE節點立刻將VPN數據流量從主要路徑轉到可用的備份路徑；同時，對可能受故障影響的備份路徑也要重新構造。在故障組件被修復后，VPN流量被轉回到主要路徑上。

下面給出算法DPMA的詳細描述。

算法DPMA(故障通告總數NFN，故障恢復約束FRC);

/*當一個故障通告到達時每個PE都執行這個過程， 測試是否存在k-保護備份路徑，如果存在，則構造備份路徑*/

{步驟(1)根據使用者對故障恢復的需求，預先構造BackupPath;

步驟(2)if故障通告與本PE路徑不相關then

return(\"不恰當的故障通告\")，算法結束;

步驟(3)if故障通告影響path then

{if BackupPath可以滿足FRC

步驟(3A)then 把VPN流量轉到BackupPath上，算法結束;

步驟(3B) else 

/*通過以下各步測試定理3存在的條件，構造滿足故障恢復約束的另外一條備份路徑*/

步驟(3B-1){更新配置數據庫;

步驟(3B-2)使用式（2）計算構建有效k-保護BackupPath的δ值;

步驟(3B-3)if NFN<δ then

步驟(3B-3-1){運行算法CBPA尋找所有的可用的BackupPath;

步驟(3A-3-2)從可用的BackupPath集中選擇最小費用的BackupPath;

步驟(3A-3-3)把流量轉換到BackupPath上;}}

步驟(4)當Path的故障組件被修復，則將流量轉到Path上; }

在這里，為了解釋的簡化，NFN （number of failure notifications，故障通告數），可以通過分析MPLS骨干的所有P節點到PE節點的故障通告消息來識別故障組件數；Path和BackupPath分別表示主要路徑和備份路徑，兩者都是數組類型的數據，FRC（failure resilience constraint，故障恢復約束）一經指定故障恢復約束，對于一個k-保護的路徑值k就被確定了。注意，如果一個節點發生故障，那么連接到它的所有鏈路都被視為無連接，這就需要建立足夠小的計算節點故障數的時間間隔，避免由于故障而導致服務受干擾。

在算法DPMA的步驟(3B-3-1)中，使用算法CBPA（construct backup path algorithms，構造備份路徑算法）快速構造備份路徑。 當故障恢復約束大于或等于1，故障通告數大于或等于N-3時，則不可能構造一條獨立的備份路徑。算法CBPA首先檢查是否能為主要路徑構造獨立可用的備份路徑。獨立可用備份路徑的存在條件表示，如果MPLS骨干的組件故障數小于或等于N-3。其中N是MPLS骨干的節點數，則存在一條備份路徑，算法CBPA能構造這條與主要路徑獨立的可用備份路徑。

下面給出算法CBPA的詳細描述。

算法CBPA(故障通告數NFN，故障恢復約束FRC);

/* 這個算法使用備份路徑設計準則構造一條備份路徑*/

/*δ由能依次被故障恢復約束決定的k-保護主要路徑的值k決定*/

{if (FRC=1) and NFN ≤(N-3) or NFN≤δ then

{指針=0;BackupPath[指針]=入口PE;

Do{選擇一個滿足條件RPath and RBackupPath and 

一條鏈路〈BackupPath[指針]，R〉的節點R;

BackupPath[指針+1]=R;

指針=指針+1;}

Until (R=出口PE or 覆蓋了不屬于Path的所有節點);

} }

算法CBPA首先檢查由于過失導致至少NFN個鏈路發生故障的情況下，為主要路徑構造獨立的備份路徑是否可行。通過應用定理3中獲取可用備份路徑存在條件，如果滿足該條件，就存在一條可用的備份路徑，則快速建立獨立于主要路徑的備份路徑。為尋找可用的滿足故障恢復約束的備份路徑，這個算法使用第2章中的備份路徑設計準則。CBPA算法比較簡單，時間復雜度為O（n）。其中n是節點數。

總之，假定每個PE節點有關于整個MPLS網絡的信息，如拓撲、可用的帶寬數據、P節點能力等。可用路徑存在條件表明： 如果故障組件數是少于或等于由故障恢復約束決定的某個k值，那么，即使在骨干網絡中有多條鏈路同時發生故障，也可以為與VPN業務有關的一條給定的主要路徑構造至少一個獨立的備份路徑。

當執行算法DPMA時，假定與故障節點相鄰的節點能發現并定位故障，并使用MPLS的標簽協議將故障通告信息傳達到源節點，源節點通常等候一個非常短的時間間隔檢查是否有其他故障通告信息，然后，測試可用備份路徑存在條件，如果測試條件滿足，那么就能使用算法CBPA快速重建備份路徑，源節點立刻將輸入界數據流量轉到備份路徑上，使得業務受到最小干擾、有效性最高。在傳輸入界數據之前，源節點先檢查各節點的輸入緩沖區是否可用，如果可用，則將數據傳送給緩沖區；如果不可用，則丟棄數據或者根據負載共享策略把數據轉換到可用的備份路徑上。

4 仿真結果分析

利用C語言建立由1 000個節點構成的全連通BGP/MPLS VPN骨干網絡。其中每條鏈路的傳輸速率被假定為100 Mbps、傳輸延遲為10 ms、故障概率為0.01。輸入負載被假定用平均輸入率0.01的泊松概率分布。對于簡單情況，信息大小固定為1 KB。

利用C語言編程得到輸入負載從0.5~4Erlang范圍變化時呑吐量的變化數據，然后利用Excel繪制的圖表如圖7所示。在這里，呑吐率被定義為輸出和輸入數據流量的比。呑吐率通過改變故障恢復值進行測量，故障恢復ξ值分別為0、1、2。對于故障恢復值0的情況，當輸入數據率增加時，數據丟失率將快速增加。然而，當故障恢復值增加時，數據丟失率減少，這是因為隨著故障恢復的逐漸增加，數據能被更可靠地傳送。

舉例來說，對于故障恢復值為1的情況，輸入數據上升到2Erlang時，大約98%的輸入數據能從源節點傳輸到目的節點。然而，當輸入流量負載分別增加到2.5和3Erlang時，呑吐率慢慢地降低到大約85%，甚至降低到70%。從圖7的曲線可以看出，當輸入負載增加時，呑吐率通常減少。然而，當故障恢復值增加時減小的趨勢也下降。這是因為故障恢復值越大，主要路徑發生故障時，負載共享越大。



同時，利用C語言編程分別獲得三種方法所對應的業務可用性數據，業務可用性是指LSP正常運行的總計時間與LSP存在的總計時間之比，并通過Excel繪制出如圖8所示的業務可用性的平均變化情況表。為了比較本文所提出的動態路徑管理混合方法和早先在IETF標準中所描述機制的性能，在保護機制中假定，維持一條獨立的備份路徑，符合故障恢復值1的情況；在恢復機制中假定，當主要路徑中鏈路發生故障時，構造一條其他獨立可用的備份路徑。

通過仿真，比較保護機制、恢復機制與混合方法的業務可用性。如圖8所示，在改變輸入負載的情況下，混合方法的業務可用性比保護和重路由方法的業務可用性好。雖然保護機制的業務可用性與混合方法的幾乎相似，但是當輸入負載增加超過2.0時，保護機制的業務可用性急劇降低。因為當輸入負載增加時，在主要路徑中鏈路發生故障的機會將大量增加。在這種情況下，大多數輸入數據流量不能被傳送到目的節點。

與恢復機制相比較，混合方法能提供較好的業務可用性。因為混合方法中，備份路徑可以在保證故障恢復情況下維護；而恢復機制在每一次故障發生時，才尋找其他可用的備份路徑。當多個故障同時發生時，恢復機制可以試著解決每一個故障。與保護機制比較起來，如果備份路徑的一些組件發生故障，那么保護機制不能傳輸數據，而在混合方法中，可以找到一條新的備份路徑，利用這條新的備份路徑繼續傳輸數據。

此外，當嘗試找一條可行的備份路徑時，混合方法能處理多個同時發生的故障。雖然沒有在圖8中顯示出來，但是對于存在不允許構造任何備份路徑的多故障發生的情況，混合方法可以立刻注意到這個最壞情況，并可以提出使用一些啟發算法尋找次佳的解決方案。然而，傳統的恢復機制可能沒注意到這個最壞的情況，而且可能試著不斷地尋找根本不存在的備份路徑，最后導致業務受干擾的程度較大。

5 結束語

在MPLS VPN中， VPN客戶站點的無連接的IP流量是通過提供商MPLS骨干的面向連接的LSP透明傳輸的。在許多情況下，LSP是由網絡管理人員手工設計的。那么如何自動設計并維護這些路徑，在多個故障發生時給客戶提供最小或沒有干擾的服務，就成為研究的重點。本文提出一種運用故障恢復模型的MPLS VPN動態路徑管理算法。該算法在提出備份路徑設計準則的基礎上，測試在全連通MPLS VPN中滿足故障恢復約束的可用備份路徑的存在條件，若滿足條件，則使用快速備份路徑構造算法，在多故障發生時，能夠動態地構造MPLS VPN路徑，使MPLS VPN業務可用，且具有最小的干擾。通過仿真評價了在不同故障恢復值時DPMA的性能和業務可用性，其結果表明MPLS VPN動態路徑管理混合方法可以提供比保護機制和恢復機制更好的業務可用性。

參考文獻：

［1］AWDUCHE D，MALCOLM J，AGOGBUA J，et al.RFC 2702，Requirements for traffic engineering over MPLS[S].[S.l.]:IETF，1999.

［2］LI Guang-zhi，WANG Dong-mei，KALMANEK C，et al.Efficient distributed path selection for shared restoration connections[C]//Proc of IEEE INFOCOM 2002.[S.l.]:IEEE Press，2002:140-149.

［3］SHARMA V，HELLSTRAND F.RFC 3469，Framework for multi-protocol label switching(MPLS)-based recovery[S].[S.l.]:IETF，2003.

［4］HUANG Chang-cheng，SHARMA V，OWENS K，et al.Building reliable MPLS networks using a path protection mechanism[J].IEEE Communications Magazine，2002，40（3）：156-162.

［5］BANERJEE A，DRAKE J，LANG J，et al.Generalized multiprotocol label switching_an overview of signaling enhancements and recovery techniques[J].IEEE Communications Magazine，2001，39(7):144- 151.

［6］LI Guang-zhi，YATES J，DOVERSPIKE R，et al.Experiments in fast restoration using GMPLS in optical/electronic mesh networks[D].Anaheim，CA：[s.n.]，2001.

［7］DOVERSPIKE R，YATES J.Challenges for MPLS in optical network restoration[J].IEEE Communications Magazine，2001，39（2）：89-96.

［8］HO P H，MOUFTAH H T.A framework for service-guaranteed shared protection in WDM mesh networks[J].IEEE Communications Magazine，2002，40(2):97-103.

［9］LEE S K，GRIFFITH D.Hierarchical restoration scheme for multiple failures in MPLS networks[C]//Proc of ICPP Workshops.[S.l.]:IEEE Press，2002:177-182.

［10］CLOUQUEUR M，GROVER W D.Availability analysis of span-restorable mesh networks[J].Journal on Selected Areas in Communications，2002，20(4):810-821.