多域光網絡中采用條件風險分離度的生存性策略

趙季紅，曲樺，王力，毛宏寶

(1. 西安郵電學院 通信工程系，陜西 西安 710061; 2. 西安交通大學 電信學院，陜西 西安 710048)

1 引言

隨著通信網的發展和各種通信技術在網絡中的應用，使得應用不同通信技術的設備組成一個獨立的域，每個服務提供商也控制一個獨立的域，因而形成了多域光網絡[1]。多域光網絡的形成原因導致其域與域之間相對獨立，域與域的設備之間不能互操作[2]；同時，考慮到具有高帶寬需求的、動態的、跨越多個光網絡域的新業務的不斷涌現，對多域光網絡的生存性提出了更高的要求[3～6]。為了增強多域光網絡的生存性，在多域光網絡中應用保護機制為業務計算工作路由和保護路由，當工作路由發生故障后將業務倒換到保護路由上。但是在多域光網絡中，各個域的拓撲及帶寬分配信息被限制在單域范圍內，只有邊界節點信息對外部域可見，要讓某個節點掌握網絡的全局信息是不現實的，這種現象被稱作可擴展性約束[7]，由于可擴展性約束的存在，路由數據庫維護的只是不準確的網絡狀態信息，這就需要應用虛鏈路映射技術生成抽象拓撲，在抽象拓撲上應用路由算法為業務計算端到端的工作路由和保護路由，以減少網絡開銷和運營成本。

為了提高網絡生存性，IETF提出 SRLG[8]約束保護路由的計算，保證保護路由和工作路由物理故障分離，即保護路由和工作路由不會同時發生故障，達到了增強網絡生存性的目的，但是會造成業務阻塞率的增加。由于一條鏈路可能屬于多個SRLG，文獻[9, 10]提出用條件故障概率描述屬于同一 SRLG的鏈路發生故障的概率，文獻[11]提出一種不共享風險的路由算法。本文在條件故障概率的基礎上提出條件風險分離度（CRDD）定量描述工作路由和保護路由的故障關聯程度，提出一種部分共享風險的、基于CRDD的、區分業務可靠性的多域光網絡生存性策略，該策略首先應用基于CRDD的域內虛鏈路映射算法生成抽象拓撲，再根據業務請求可靠度，應用基于CRDD的端到端工作/保護路由算法在抽象拓撲上計算CRDD滿足其請求可靠度的工作/保護路由對，達到在多域光網絡中區分業務可靠性的目的。

文章安排如下：第2節給出CRDD的定義，比較基于CRDD計算保護路由和SRLG約束下計算保護路由的區別；第3節研究采用CRDD的區分業務可靠性的多域光網絡生存性策略，包括基于CRDD的域內虛鏈路映射算法和基于 CRDD的端到端工作/保護路由算法；第4節對基于CRDD的區分業務可靠性的多域光網絡生存性策略性能進行仿真分析；第5節總結全文。

2 條件風險分離度

CRDD是為了從數學角度定性地描述工作路由和保護路由的故障關聯程度而提出的。CRDD的概念建立在條件故障概率[10]的基礎上，條件故障概率（風險概率）是對物理鏈路的故障關聯性的定量描述。

定義 鏈路Li的SRLG集合表示為srlgi，P(srlgi)表示鏈路Li的條件故障概率，即風險概率。假設條件故障概率則對于屬于 srlgi的多條鏈路，當其中一條鏈路失效時，其他任意一條鏈路不受該故障影響的概率為1-k，即

設鏈路Li的SRLG集合為srlgi，鏈路Lj的SRLG集合為srlgj，鏈路Li和鏈路Lj的共同SRLG集合為為鏈路 Li的條件故障概率，P(srlgj)為鏈路Lj的條件故障概率，則鏈路Li和鏈路Lj的條件風險分離度定義為

設工作路由和保護路由所屬SRLG集合為其經過的鏈路所屬 SRLG的并集，即工作路由和保護路由的共同SRLG集合為則工作路由和保護路由的條件風險分離度定義為

應用CRDD定義和式（2）分析基于CRDD計算保護路由和SRLG約束下計算保護路由的區別，圖1為示例拓撲圖。

圖1 示例拓撲圖

設從節點1到節點5的工作路由為1→2→5，不考慮SRLG約束，它的備選保護路由有4條，分別是：1→3→5，1→3→4→5，1→4→5 和 1→6-→5；如果考慮 SRLG約束，鏈路 1→2、1→4和鏈路 1→3屬于SRLG1，保護路由1→3→5、1→4→5和1→3→4→5不可用，只有保護路由1→6→5可用，增加了業務的阻塞率。

討論基于CRDD為業務計算保護路由。備選保護路由BP1為1→6→5，它經過鏈路的SRLG集合為{srlg3, srlg4}；備選保護路由BP2為1→3→5，它經過鏈路的SRLG集合為{srlg1, srlg5}；備選保護路由 BP3為 1→4→5，它經過鏈路的 SRLG 集合為{srlg1, srlg2}。

再根據不同業務選擇 CRDD大于其請求可靠度的工作/保護路由對。相比SRLG約束，基于CRDD計算保護路由為業務提供了更多的備選保護路由，不僅降低了業務阻塞率，還達到了區分業務可靠度建立保護路由的目的。

3 采用 CRDD的區分業務可靠性的多域光網絡生存性策略

3.1 網絡模型

在多域光網絡中應用生存性策略為業務請求計算工作/保護路由對時，需要抽象多域光網絡，生成抽象拓撲，在抽象拓撲上計算工作/保護路由對。

為了區分業務可靠性，為不同業務請求計算不同可靠性的工作/保護路由對，本節提出基于CRDD的區分業務可靠性的多域光網絡生存性策略。其中信息聚合模塊應用基于 CRDD的域內虛鏈路映射算法，以CRDD為約束條件，將內部光路映射成反映工作光路和保護光路故障關聯程度的域內虛鏈路，構成抽象拓撲；路由模塊應用基于CRDD的端到端工作/保護路由算法區分業務請求可靠度，計算滿足要求的工作/保護路由對。

圖2為多域光網絡分層路由模型[12]。最底層是多域光網絡的物理拓撲，它由5個不同的路由控制域(RCD, routing control domain)互聯構成，每一個RCD都由邊界節點、內部節點及連接這些節點的物理鏈路組成，每一個RCD不包含其他RCD的任何信息，不使用骨干域進行通信，每個 RCD配置一個路由控制器(RC, routing controller)，負責完成該域的信息聚合、路由信息分發、路由計算等；中間層是由RC1、RC2、RC3、RC4和RC5互聯形成的互操作控制平面，其中RC1、RC2、RC3、RC4和RC5分別屬于 RCD1、RCD2、RCD3、RCD4和RCD5；頂層是聚合網絡，是由各域RC在控制平面內廣播各自的聚合信息形成的邏輯虛拓撲。

圖2 基于拓撲抽象的多域光網絡分層路由模型

3.2 基于CRDD的域內虛鏈路映射算法

在基于CRDD的區分業務可靠性的多域光網絡生存性策略中，需要路由控制器將工作/保護內部光路映射為域內虛鏈路，要求生成的域內虛鏈路具有可靠性差異，即能夠反映工作/保護內部光路的可靠性差異。

以圖2多域光網絡為例，它可以表示為D=(N,L)，它由5個相互獨立的單域構成，即m=1,…,5；N(Nm)和 L(Lm)分別表示 D(Dm)的節點集合和鏈路集合。

為了簡化分析，假設在單域光網絡中采用全網格拓撲抽象，以D3為例，如圖3所示，當D3的域內 RC3完成拓撲抽象后，得到 D3的抽象拓撲表示D3的邊界節點集合， C3VIRTUAL表示所有連接邊界節點的反映穿越該域特征信息的域內虛鏈路e的集合。

圖4給出了基于CRDD的域內虛鏈路映射算法流程圖，其中應用了 Dijkstra-improved算法，Dijkstra-improved算法是使用了雙尺度(P, C)的Dijkstra[13]算法，其中P表示內部光路q的條件故障概率，C表示內部光路q的代價，C=1/rq，rq為q的剩余帶寬容量。基于CRDD的域內虛鏈路映射算法流程如下。

圖3 全網格抽象生成候選內部光路組

圖4 基于CRDD的域內虛鏈路映射算法流程

Start初始化計數器j、k，置為1。

Step1如果j和k的值不相等，說明選定一條虛鏈路（j, k），跳轉至Step 2，否則跳轉至Step9。

Step2對選定的域內虛鏈路，使用 Dijkstraimproved算法得到最穩最短內部光路候選組 PjSkEL（候選內部光路總數 nSjkEL）。使用的尺度標準為（P,C），其中 P(L)表示物理鏈路 L的失效概率，表示物理鏈路L的代價，CLRES表示物理鏈路的剩余帶寬。仍以Dm為例，如圖3所示，4個邊界節點之間的任意一條虛鏈路都確定了可能的內部光路組。

失效概率

條件概率

其中，srlgi表示鏈路 Li的 SRLG；S(q)表示內部光路q的SRLG集合，即CS(q1,q2)表示內部光路q1和q2的共有SRLG集合，即

Step3通過判定分析虛鏈路（j, k）是否已經得到預期的內部光路，若沒有，則轉到Step 4；反之，跳轉至Step 9。

Step4對域內虛鏈路（j, k），在 PjSkEL中搜索工作內部光路q，并添加到集合Se中。搜索原則：對（j, k）而言，由于該內部光路的選入，新增的與備份虛鏈路的CRDD之和最大，ye1置1時表示內部光路 qe1屬于集合 PB，否則置0；i i e1其中 C 是q和 qe1的CRDD，根據式(2)表示如下

Step5根據在Step 4中得到的Se搜索q。搜索原則是：該q與已選工作內部光路的CRDD之和最大，其中，xe1置1時表示內i部光路 qe1i在PWe1中，否則置0，并做如下更新。

Step6搜索備份q。搜索原則是：對域內虛鏈路（j, k）而言，由于該內部光路的選入，新增的與工作虛鏈路的CRDD之和最大，并做如下更新：

Step7對于集合中的任意 q，沿著q的域內物理鏈路序列依次執行可用波長向量與運算，得到光路q的可用波長向量組。

Step8對集合中的所有 q，求和可用波長出現的次數，并基于門限Q限制得到最后的內部光路可用波長向量；跳轉至Step 9。

Step9對k的值加1，轉至Step 10。

Step10如果k的值大于該單域的邊界節點總數b，則說明已到達最后一個邊界節點，跳轉至Step 11；否則，跳轉至Step 1。

Step11對j的值加1，轉至Step 12。

Step12如果 j的值大于該單域的邊界節點總數 b，則說明已到達最后一個邊界節點，該域虛鏈路映射完成；否則，跳轉至Step 1。

End沒有搜索到滿足條件的工作/保護內部光路，或者

至此，單域RC完成了域內虛鏈路映射，得到相應的具有可靠性差異的備選工作/保護路由。

3.3 基于CRDD的端到端工作/保護路由算法

當所有單域完成拓撲抽象和虛鏈路映射后，RC通過域間路由協議在控制平面內廣播聚合信息，形成聚合網絡。由于聚合網絡直接關聯了域內光路和域間物理鏈路，因此基于聚合網絡的代價計算是準確且不失可擴展性的。基于 CRDD的端到端工作/保護路由算法的主要思想是：對那些與工作路由經過的鏈路具有相同SRLG標識的鏈路，并非直接刪除它，而是將其與工作路由的 CRDD作為選路依據，計算滿足業務可靠性要求的最優保護路由。端到端工作/保護路由算法如下。

Step1在聚合網絡上，使用最短通道優先算法計算工作路由p，跳轉至Step 2。

Step2對于跨越多域的工作路由 p，根據式(3)，計算p的失效概率。

根據式(4)計算p的條件故障概率：

Step3基于業務可靠性 R，計算，并且對任意，P(Sj)=0；其中，本質上是通過對SRLG進行分類處理以優化算法，計算的過程如下。

根據特定業務的可靠性需求，算法需要搜索這樣的工作和保護路由對：它們同時失效的概率不超過(1-R)，即

由貝葉斯公式得到

聯系p的條件故障概率公式

因此，滿足了式(12)也就滿足了業務可靠性需求。

由上面的分析可知，對于SRLG集合中的srlgi，如果，即當工作路由和保護路由同時關聯srlgi時，仍能滿足業務可靠性需求，稱該srlgi為不需要考慮風險的SRLG集合，否則為需要考慮風險的SRLG集合。由此，SRLG集合被分成2類：需要考慮風險的srlgi的集合和不需要考慮風險的 srlgi的集合在計算保護路由時，對于不需要考慮風險的 srlgi，其條件風險分離度置 1，即對任意

Step4刪除工作路由經過的內部光路，域間物理鏈路及節點，使用Dijkstra-improved算法計算保護路由。此處，Dijkstra-improved算法使用的雙尺度是（P, C），其中表示內部光路q的條件風險分離度；內部光路q的代價表示為表示內部光路q的剩余帶寬容量。

至此，源RC通過在聚合網絡上運行端到端工作/保護路由算法，向源節點返回包含端到端工作/保護路由的響應消息，隨后源節點發起資源預留請求。

4 仿真與數值分析

為了驗證多域光網絡中應用條件風險分離度的生存性策略的性能，以圖2所示多域光網絡為參考拓撲進行仿真。圖2所示多域光網絡包含28個節點和 46條物理鏈路，每條物理鏈路由一對方向相反的單向光纖組成，每根光纖支持8個波長，單域邊界節點具備波長轉換能力。

設網絡鏈路的可靠性隨機分布在0.8～1.0之間，鏈路的條件故障概率隨機為 0.1、0.2和 0.5。連接請求表示為R(s, d, B, R)，s和d分別是業務請求的源、目的節點，B為請求帶寬，R是業務請求可靠度且隨機分布在0.85～1.0之間。所有業務請求的源、宿節點對隨機生成，且連接請求按照平均速率服從參數為λ的泊松分布獨立到達網絡各節點，業務連接的持續時間服從均值為1/μ的負指數分布，網絡總負載為 λ/μ。算法依據業務請求可靠度 R建立光路，如果沒有成功，則連接阻塞，不存在排隊現象。

在仿真時，對于不同的網絡負載，分別產生106次業務連接請求，使用統計方法進行分析。

1) 仿真首先研究了所提生存性策略的阻塞率特性。為了更直觀地表現所提策略的優勢，同等條件下引入了2種已有技術：考慮物理分離的多域層次路由（MHR）算法和未區分業務可靠性的多域風險分離（SD）算法。

圖5比較了不同網絡負載下所提生存性策略和MHR、SD的阻塞率特性，由于所設計仿真網絡每條物理鏈路只支持8個波長，網絡資源有限，當網絡負載較大時，導致阻塞率偏高。

圖5 算法的阻塞率性能分析

由圖5可知，在網絡負載相同的情況下，所提生存性策略的阻塞率總是介于 SD和 MHR之間，這是因為相比 SD算法，本文所提生存性策略在搜索路由時，并不是直接將那些與工作路由經過的鏈路具有相同SRLG標識的鏈路刪除，而是基于CRDD選路，這大大增加了可用資源的使用效率，從而提高了建路成功的概率；另一方面，由于MHR算法只考慮了工作/保護路由的物理分離，所以在計算保護路由時獲得了相對較廣的可選網絡資源，得到了比本文所提生存性策略稍低的阻塞率。

同時，從圖5還可以發現，在網絡負載較輕的情況下，所提生存性策略的阻塞率非常低，顯示出它的建路能力絲毫不遜于考慮物理分離的MHR算法。

2) 仿真同時也對所提生存性策略區分可靠性的能力進行了研究。圖6統計了實際成功建立的工作路由的可靠度分布。

圖6 實際工作通路的可靠度分析

業務連接的請求可靠度在 0.924～0.962之間隨機取值，由圖6可見，實際工作路由的可靠度集中分布在 0.991～0.998之間，提高了網絡生存性，并且對于可靠性要求高的業務成功建立的工作路由的可靠度也相對較高，保證了區分業務可靠性的性能指標。同時，隨著網絡負載的增加，實際連接的可靠度呈現微弱下降的趨勢，說明當網絡負載增大時，對所提生存性策略的影響較為明顯。

5 結束語

可靠性是衡量網絡生存性的重要參數，考慮多域網環境缺乏完整的關于網絡拓撲和帶寬分配的信息，本文引入CRDD，提出基于CRDD的域內虛鏈路映射算法構建的抽象拓撲，在抽象拓撲上應用基于CRDD的端到端工作/保護路由算法，區分業務可靠性，為業務建立工作/保護路由對。仿真結果表明，相比先前的多域光網絡生存性技術，該策略很好地實現了區分業務可靠性的目的，有效地降低了網絡阻塞率，而且能夠提供平均高于業務請求6.5%的可靠性。同時，作為區分業務可靠性的的手段，CRDD的概念也可以應用在單域光網絡和多層網絡中。

[1] IETF RFC 4726. A Framework for Inter-domain MPLS Traffic Engineering[S].

[2] SARADHI C V, RAMAMURTHY B, SCHUPKE D A, et al. Guest editorial-multidomain optical networks∶ issues and challenges[J]. IEEE Communications Magazine, 2008,46(6)∶ 76-77.

[3] PICKAVET M, AUDENAERT P, VANHAVERBEKE J, et al. Optimizing reliable multidomain optical routing[A]. 2006 International Conference on Transparent Optical Networks[C]. Nottingham，Britain,2006. 1-4.

[4] ZHAO J H, MAO H B, QU H. Research on survivability in multi-service-based multi-domain optical networks[A]. 11th International Conference on Advanced Communication Technology[C].Phoenix Park, Phoenix Park, Republic of Korea, 2009. 161-165.

[5] TAKEDA T, IKEJIRI Y, FARREL A, et al. Analysis of inter-domain label switched path (LSP) recovery[EB/OL]. http∶//tools.ietf.org/html/draft- ietf-ccamp-inter-domain-recovery-analysis-03,2008.

[6] 趙季紅, 曲樺. 基于約束的 GMPLS恢復算法[J]. 電子科技大學學報, 2005,34(1)∶101-104.ZHAO J H, QU H. GMPLS recovery algorithm based on constrained[J]. Journal of University of Electronic Science and Technology of China, 2005, 34 (1)∶ 101-104.

[7] IETF RFC 4105. Requirements for Inter-Area MPLS Traffic Engineering[S].

[8] PAPADIMITRIOU D, POPPE F, JONES J, et al. Inference of shared risk link groups[EB/OL]. http∶//tools.ietf.org/html/draft-many- inferencesrlg-02. 2001,11.

[9] 虞紅芳, 溫海波, 王晟等. 網狀WDM網中支持區分可靠性的共享通路保護算法[J].電子與信息學報, 2005,27(8)∶1295-1298.YU H F, WEN H B, WANG S, et al. Shared-path protection algorithm with differentiated reliability in mesh WDM networks[J]. Journal of Electronics & Information Technology, 2005,27(8)∶ 1295-1298.

[10] 謝暉, 曹振海, 錢松榮. 一種基于SRLG條件失敗概率限制的保護算法[J]. 計算機工程與設計, 2004,10(34)∶ 1742-1744.XIE H, CAO Z H, QIAN S R. Path-protection algorithm under conditional failure probability of SRLG constrains[J]. Computer Engineering and Design, 2004,10(34)∶1742-1744.

[11] 周韜, 郭磊, 虞紅芳. WDM光網絡中一種不共享風險的路由算法[J].電子科技大學學報, 2006,35(4)∶440-442.ZHOU T, GUO L, YU H F. A routing algorithm with no-shared-risk for wdm optical networks[J]. Journal of University of Electronic Science and Technology of China, 2006,35(4)∶440-442.

[12] Implementation Agreement E-NNI OSPF-based routing-1.0 (Intra-Carrier)[EB/OL]. http∶//www.oiforum. com/public/documents/OIFENNI-OSPF-01.0.pdf, 2007.

[13] 張仁平, 周慶忠, 熊偉. A*算法改進算法及其應用[J]. 計算機系統應用,2009,9(27)∶99-100.ZHANG R P, ZHOU Q Z, XIONG W. Updated A* algorithm and application[J]. Applications of the Computer Systems, 2009, 9(27)∶99-100.