一種區(qū)分業(yè)務的共享保護算法

唐良瑞，許浩偉，樊 冰

(華北電力大學新能源電力系統(tǒng)國家重點實驗室，北京102206)

0 引言

電力通信光網(wǎng)絡中波分復用技術(shù)的使用，使網(wǎng)絡容量和傳輸速率迅速提高，網(wǎng)絡故障造成的損失也更加嚴重。光網(wǎng)絡可靠性技術(shù)的研究已經(jīng)成為現(xiàn)在的研究熱點。保護技術(shù)能夠快速地恢復業(yè)務，深入研究網(wǎng)絡的保護機制，對提高電力通信網(wǎng)的可靠性有重要意義。

保護技術(shù)包括專用保護和共享保護。共享保護允許共享保護資源，并且能夠在單SRLG 故障的情況下為業(yè)務提供100%的恢復，有效提高了網(wǎng)絡的資源利用率，故而受到青睞。文獻［1］在波長一致性限制下，利用分層圖為業(yè)務計算SRLG 分離的兩條路由;文獻［2］為工作路徑的部分鏈路提供備份光路，為業(yè)務提供滿足可靠性要求的保護，提高了資源利用率;文獻［3］提出對不同業(yè)務的可靠性要求進行區(qū)分，提供不同水平的保護;文獻［4］提出支持區(qū)分可靠性的動態(tài)雙鏈路權(quán)重算法，保證了業(yè)務的可靠性，節(jié)約網(wǎng)絡資源;文獻［5］利用k-最短路徑為業(yè)務計算工作路徑和保護路徑，在不同保護路徑之間共享鏈路，提高保護資源的利用率，降低業(yè)務的阻塞率。文獻［6］為不同等級的業(yè)務動態(tài)地選擇工作路徑，并實現(xiàn)各級業(yè)務之間的保護路徑共享。此外，還有的研究工作考慮到了業(yè)務的時延要求。文獻［7］把業(yè)務時延作為代價因素之一，選擇綜合代價最小的保護方案;文獻［8］基于波長轉(zhuǎn)換對時延的影響，為業(yè)務計算時延最短的保護方案。

電力通信網(wǎng)業(yè)務對可靠性的要求普遍較高，區(qū)分可靠性的保護算法在電力通信網(wǎng)中的應用有一定的局限性。然而在時延要求方面，電力業(yè)務之間存在較大的差異?？紤]到以往的成果只是側(cè)重于降低業(yè)務時延，本文提出一種能夠在時延上對業(yè)務進行區(qū)分的共享保護算法，通過在不同時延要求的業(yè)務之間協(xié)調(diào)資源，并且充分利用保護資源，不但能保證業(yè)務的阻塞率和時延性能，在資源利用率等方面也有明顯改善。

1 問題描述

光網(wǎng)絡可以用G(N，L，W)來表示，其中N 為網(wǎng)絡的節(jié)點集合，L 為物理鏈路集合，W 為每條物理鏈路內(nèi)部的波長數(shù)。光網(wǎng)絡的節(jié)點由光交叉連接設備(OXC)和IP 路由器組成，具有O/E/O 轉(zhuǎn)換能力。網(wǎng)絡的業(yè)務在節(jié)點之間均勻分布，默認每個業(yè)務的帶寬要求為一個波長，不考慮業(yè)務疏導的問題。

網(wǎng)絡故障包括節(jié)點故障和鏈路故障，電力通信網(wǎng)中的節(jié)點可靠性較高，本文只考慮鏈路故障［9］。業(yè)務到來時，為保證業(yè)務的可靠性，要為業(yè)務計算一條工作路徑和一條保護路徑?？紤]到實際網(wǎng)絡中SRLG［10］問題，應該保證工作路徑和保護路徑是SRLG 分離的。隨著通信網(wǎng)運維水平的提高，兩個及以上SRLG 同時發(fā)生故障的概率很小，所以本文只針對單SRLG 故障的情況。

在電力通信網(wǎng)中，不同業(yè)務對時延的要求有很大差異。例如，在調(diào)度數(shù)據(jù)網(wǎng)中，調(diào)度自動化業(yè)務要求傳輸時延在100 ms 以內(nèi)，電能計量遙測業(yè)務的時延要求則在秒級以下，安穩(wěn)管理信息業(yè)務時延上限為15 min。將電力通信業(yè)務按照時延要求分為三類:時延敏感業(yè)務、時延次敏感業(yè)務、時延不敏感業(yè)務，分別用type =1，2，3 表示。為這些業(yè)務計算路徑時，若都取最短路徑，時延不敏感的業(yè)務可能占據(jù)時延低的路徑，從而導致時延敏感/次敏感業(yè)務路由失敗。在公網(wǎng)通信中根據(jù)SLA［11］為業(yè)務提供符合其QoS 要求的服務是保證網(wǎng)絡運行水平的有效手段，在電力通信網(wǎng)中，也需要在業(yè)務之間協(xié)調(diào)資源，為時延要求不同的業(yè)務設計不同的路由方式。

分析光網(wǎng)絡中的時延影響因素［12］可知，信號在光纖中傳輸?shù)臅r延很小，時延主要來自于節(jié)點處的O/E/O 轉(zhuǎn)換，減少信號傳輸過程中的O/E/O轉(zhuǎn)換次數(shù)能夠大幅降低時延。業(yè)務在入口、出口節(jié)點處分別要進行一次O/E、E/O 轉(zhuǎn)換，所以業(yè)務傳輸過程中O/E/O 轉(zhuǎn)換次數(shù)至少為1。本文在為業(yè)務計算路由時，將傳輸過程中的O/E/O 轉(zhuǎn)換次數(shù)做為表征時延的參數(shù)。

2 區(qū)分時延的共享保護算法

2.1 網(wǎng)絡模型

光網(wǎng)絡中的路由和波長分配通常被分解為路由選擇和波長分配兩個子問題分別解決。本文使用分層圖模型［13］，將物理鏈路中的波長資源映射為分層圖中的鏈路，同時解決路由和波長分配問題，使算法得以簡化。如圖1所示，節(jié)點數(shù)N =4，鏈路波長數(shù)為W =3 的光網(wǎng)絡可以擴展為一個3層的分層圖。

為分層圖中的節(jié)點逐層進行編號，虛線連接的點代表物理拓撲中的同一點，將虛線稱為O/E/O 鏈路，表示某一波長能夠轉(zhuǎn)換到其它任意波長。

實線表示某一波長平面內(nèi)實際存在的鏈路，稱之為波長鏈路。實際的物理鏈路由一對方向相反的單向光纖構(gòu)成，所以分層圖中的波長鏈路是雙向鏈路。下文中，在不做區(qū)分時，O/E/O 鏈路和波長鏈路統(tǒng)稱為鏈路。

根據(jù)網(wǎng)絡拓撲的實際情況，給鏈路分配SRLG 編號ri，所有的ri構(gòu)成SRLG 集合R={r1，r2，…ri，…}。為每條鏈路設置標識tag、srlg、b_number 和b_srlg。其中，tag 的取值范圍為0，1，2，分別表示空閑、工作和保護鏈路;srlg 存儲鏈路所屬的SRLG 編號;b_num 代表保護鏈路所保護的業(yè)務數(shù)，最大值為M;b_srlg 存儲的是鏈路用于保護時，所保護的所有業(yè)務經(jīng)過的SRLG 的并集。為了描述方便，規(guī)定業(yè)務的源、宿節(jié)點編號限制在［1，N］范圍內(nèi)，業(yè)務在接入、離開網(wǎng)絡時完成O/E、E/O 轉(zhuǎn)換，經(jīng)過源、宿節(jié)點內(nèi)部的O/E/O 鏈路時僅僅完成波長選擇的功能。設業(yè)務路徑P 經(jīng)過k 條鏈路，則業(yè)O/E/O 務在路由過程中轉(zhuǎn)換次數(shù)hops 為

圖1 分層圖模型Fig.1 Layered graph

其中，ci的取值為

圖1 中箭頭所示的路徑，源節(jié)點為1，宿節(jié)點為3，兩點之間的路徑為1-5-8-12-11-3。其中，鏈路1-5、11-3 是源、宿節(jié)點內(nèi)部的O/E/O鏈路，表示業(yè)務在進入、離開網(wǎng)絡時分別使用波長λ2 、λ3，除源、宿節(jié)點內(nèi)部的鏈路1-5、11-3 外，業(yè)務路徑經(jīng)過的O/E/O 鏈路還有8-12，表示業(yè)務路徑使用的波長從λ2 變換到λ3，業(yè)務在傳輸過程中進行的O/E/O 轉(zhuǎn)換次數(shù)為2。

2.2 算法實現(xiàn)

網(wǎng)絡中接入部分業(yè)務以后，不同層面的剩余鏈路數(shù)也不盡相同。剩余鏈路數(shù)較少的層面完整性較差，時延敏感業(yè)務在使用這些層面的資源時，經(jīng)常需要在多個層面之間跳轉(zhuǎn)才能形成一條完整的路徑。這樣的路徑很可能超出業(yè)務的O/E/O轉(zhuǎn)換次數(shù)限制，導致路由失敗。為時延不敏感業(yè)務選路時，如果為這些資源賦以較低的代價值優(yōu)先利用，允許多次O/E/O 轉(zhuǎn)換，避免對完整層面的破壞，就能夠提高時延敏感/次敏感業(yè)務的成功率。

基于以上考慮，本文設計了以下工作和保護路由算法。

業(yè)務到來時，先為業(yè)務計算工作路徑。先刪除分層圖中已經(jīng)用作工作路徑和保護路徑，再根據(jù)業(yè)務的種類為鏈路設置代價函數(shù)值。若li為波長鏈路，其代價函數(shù)為

若li是O/E/O 鏈路，其代價函數(shù)為

以上兩式中:N 表示網(wǎng)絡的物理節(jié)點數(shù);L′表示鏈路li所在層面剩余的鏈路數(shù);L 表示物理鏈路數(shù)，可知L′≤L。

對于時延敏感業(yè)務，將波長鏈路的代價設置為1，使其能夠在任一層面內(nèi)選路。在有N 個節(jié)點的網(wǎng)絡中，兩點間路徑包含的鏈路數(shù)最多為N-1，將O/E/O 鏈路的代價設置為N-1 能夠保證所選的路徑經(jīng)過最少次數(shù)的O/E/O 轉(zhuǎn)換。

對于時延次敏感和不敏感業(yè)務，將波長鏈路代價設置為所在層面的剩余鏈路數(shù)，選路時優(yōu)先使用鏈路數(shù)較少的層面，避免對較完整層面的破壞，提高時延敏感業(yè)務的成功率。為了保證時延次敏感業(yè)務的時延性能，將O/E/O 鏈路的代價設置為一個較大值，以減少O/E/O 轉(zhuǎn)換次數(shù);對于時延不敏感業(yè)務，將O/E/O 鏈路代價設置為1，允許在選路時進行多次O/E/O 轉(zhuǎn)換，從而避免與時延要求較高的業(yè)務爭用資源。

為鏈路設置代價函數(shù)值以后，利用dijkstra 算法為業(yè)務計算一條代價最小的工作路徑wp，并且判斷該路徑的O/E/O 轉(zhuǎn)換次數(shù)是否滿足時延要求。如果wp 不存在或者不滿足時延要求，則應拒絕該業(yè)務。

為業(yè)務成功計算工作路徑以后，還需計算一條與工作路徑SRLG 分離的保護路徑。計算保護路徑前，在上文得出的鏈路代價的基礎(chǔ)上，依照SRLG 分離的要求對鏈路代價進行調(diào)整:

式中:srlgi為鏈路li所屬的SRLG 編號集合;srlgwp為工作路徑wp 經(jīng)過的SRLG 的編號集合。

此外，還應該將已經(jīng)用做保護資源的鏈路添加到網(wǎng)絡中，其代價函數(shù)為

可知，當保護鏈路可用時，代價值小于1，目的在于使業(yè)務在選擇保護路徑時，優(yōu)先使用共享保護資源，以提高保護資源的利用率。

調(diào)整鏈路代價以后，同樣利用dijkstra 算法計算一條代價最小且滿足O/E/O 轉(zhuǎn)換次數(shù)限制的保護路徑bp。

區(qū)分業(yè)務的共享保護算法流程如下:

(1)請求到來，如果是接入請求，轉(zhuǎn)到(2)，如果是拆除請求，轉(zhuǎn)到(5)。

(2)在原始的分層圖中，刪除tag ≠0 的鏈路，判斷業(yè)務種類，根據(jù)式(3)、(4)設置鏈路代價，計算工作路徑wp。如果沒有可達路徑，則拒絕業(yè)務，返回(1);否則判斷wp 的O/E/O 轉(zhuǎn)換次數(shù)。如果O/E/O 轉(zhuǎn)換次數(shù)滿足業(yè)務的時延要求，轉(zhuǎn)到(3)，否則拒絕業(yè)務，返回(1)。

(3)求出wp 經(jīng)過的SRLG 編號集合srlgwp，將tag=2 的鏈路加入分層圖中，根據(jù)式(5)、(6)修改鏈路代價，計算保護路徑bp。如果沒有可達路徑，則拒絕業(yè)務，返回(1)，否則判斷bp 的O/E/O轉(zhuǎn)換次數(shù)如果滿足時延要求，轉(zhuǎn)到(4)，否則拒絕業(yè)務，返回(1)。

(4)記錄業(yè)務的wp、bp，修改所經(jīng)過鏈路的標識tag、srlg、b_number 和b_srlg，進入等待狀態(tài)。

(5)釋放資源，修改該業(yè)務的wp、bp 所經(jīng)過鏈路的tag、srlg、b_number 和b_srlg，進入等待狀態(tài)。

3 算法仿真和結(jié)果分析

為了驗證本文算法的性能，將其與文獻［8］提出的算法進行對比仿真。在仿真中，時延敏感、次敏感、不敏感業(yè)務所占的比例分別為20%、30%、50%，O/E/O 轉(zhuǎn)換次數(shù)的限制分別為1、2、無限制，業(yè)務在網(wǎng)絡中均勻分布。物理鏈路中可用波長數(shù)W=8。網(wǎng)絡拓撲使用圖2所示的14 節(jié)點、21條邊的NSF 網(wǎng)絡，SRLG 設置如圖中虛線圈所示，鏈路旁邊的數(shù)字表示鏈路所屬的SRLG 的編號。鏈路在用于保護時，保護的最大業(yè)務數(shù)M =3。業(yè)務若被拒絕，則不進行重傳。在不同業(yè)務強度下，本文算法與對比算法各方面性能對比結(jié)果如下。

圖2 NSF 網(wǎng)絡拓撲Fig.2 NSF network

圖3所示是不同業(yè)務強度下，各等級業(yè)務的阻塞率性能對比?？傮w而言，隨著業(yè)務強度增大，阻塞率逐漸升高。不論是本文算法還是對比算法，業(yè)務對時延越敏感，阻塞率越高。這是因為時延敏感業(yè)務和次敏感業(yè)務在選路時有O/E/O 轉(zhuǎn)換次數(shù)限制，在網(wǎng)絡資源狀況相同的情況下，允許的O/E/O 轉(zhuǎn)換次數(shù)越少，可選的路由方案也就越少，成功路由的概率越低。本文算法在為時延敏感度較低的業(yè)務計算路由時，允許通過較多次的O/E/O 轉(zhuǎn)換，在剩余鏈路數(shù)較少的層面選路，盡量避免使用較完整層面，以提高時延敏感度較高業(yè)務的成功路由概率總體而言，時延敏感業(yè)務的阻塞率比對比算法要低15～20 個百分點，有很明顯的改善;時延次敏感業(yè)務對在阻塞率性能方面也有一定的改善，但是因為這類業(yè)務對于O/E/O 轉(zhuǎn)換的次數(shù)限制較低，兩種算法的路由成功率相差不是很大;時延不敏感業(yè)務沒有嚴格的O/E/O 轉(zhuǎn)換次數(shù)限制，阻塞率性能沒有明顯的差異。

圖3 業(yè)務阻塞率Fig.3 Blocking rate

圖4 中可以看出本文的選路策略對時延次敏感、不敏感業(yè)務的O/E/O 轉(zhuǎn)換次數(shù)的影響。其中時延次敏感業(yè)務在業(yè)務強度較低時，本文算法的O/E/O 轉(zhuǎn)換次數(shù)大于對比算法，但隨著業(yè)務強度的增加，差別逐漸減小，在業(yè)務強度為24 Erl 左右時，兩者重合。業(yè)務強度大于24 Erl 時，本文算法的O/E/O 轉(zhuǎn)換次數(shù)小于對比算法，并且變化趨于平緩，而對比算法的上升趨勢很明顯。這是由于在業(yè)務強度較小時，網(wǎng)絡中同時存在的業(yè)務量也較少，不同的波長平面相對較完整。對比算法為業(yè)務選擇最短相應的的路由，相應的O/E/O 轉(zhuǎn)換次數(shù)也較少;業(yè)務強度較大時，網(wǎng)絡中的業(yè)務增多，本文算法在為時延不明感業(yè)務選路時，盡量避免對各波長平面完整性的破壞，所以此時本文算法在時延方面能取得較好的性能。對于時延不敏感業(yè)務，業(yè)務強度較小時，本文算法下的O/E/O轉(zhuǎn)換次數(shù)大約比對比算法高0.5 次左右，但隨著業(yè)務強度的增加，基本保持不變，與對比算法的之間的差異也逐漸減小。

結(jié)合圖3 與圖4 的對比結(jié)果可知，本文算法在不影響時延不敏感業(yè)務阻塞率的前提下，以其有限的時延為代價，大大降低了時延敏感業(yè)務的阻塞率，并且在業(yè)務強度較高時，使時延次敏感業(yè)務的阻塞率和時延性能都得到改善?？紤]到時延不敏感業(yè)務自身對時延的要求較低，時延的變化對業(yè)務性能的影響有限，這樣的代價是可以接受的。

圖4 O/E/O 轉(zhuǎn)換次數(shù)Fig.4 The number of O/E/O conversion

圖5所示是兩種算法下工作資源比例的對比。本文算法下，工作資源所占比例高于對比算法，隨著業(yè)務強度的增加，差別逐漸明顯。通過上文阻塞率性能對比可知，使用本文算法時，業(yè)務整體的阻塞率得以降低，網(wǎng)絡能夠容納更多的業(yè)務，所以網(wǎng)絡中工作資源所占的比例也相應提高。分析圖5 中的數(shù)據(jù)可知本文算法下，工作資源所占比重提高不是很明顯(總體上小于6%)，這是因為兩種算法的阻塞率差異主要體現(xiàn)在時延敏感業(yè)務上，這類業(yè)務在所有業(yè)務中的比例較小(20%)，對網(wǎng)絡中工作資源所占比例的影響不如時延敏感業(yè)務的阻塞率差別明顯。

圖5 工作資源所占比例Fig.5 Work resource rate

除了提高時延較敏感業(yè)務的性能，本文還注重對于共享資源的利用。在計算保護路徑時，由于賦給可用的共享保護鏈路的權(quán)重低于其他鏈路，所以在尋路時會優(yōu)先使用這些資源。圖6所示是兩種算法下平均每條保護鏈路所保護的業(yè)務數(shù)量比較。隨著業(yè)務強度的增加，兩條曲線略有上升。本文算法能夠更有效地利用保護資源，每條保護鏈路所能保護的業(yè)務數(shù)量比對比算法要多0.6 以上。這樣就能夠利用較少的保護資源完成對網(wǎng)絡業(yè)務的保護，如圖7所示，本文算法下，保護資源所占的比例比對比算法平均要低10 個百分點左右，有效地節(jié)省了網(wǎng)絡資源，使網(wǎng)絡能夠容納更多的業(yè)務，這也是本文算法的阻塞率性能優(yōu)于對比算法的原因之一。

圖6 平均每條保護鏈路保護的業(yè)務數(shù)Fig.6 The average number of services protected by per protection link

圖7 保護資源所占比例Fig.7 Protection resource rate

4 結(jié)論

針對電力通信網(wǎng)中不同業(yè)務的時延要求有明顯差異的情況，本文基于分層圖模型設計了一種區(qū)分業(yè)務的共享保護算法。計算工作路徑前，根據(jù)業(yè)務的種類和當前網(wǎng)絡資源的使用情況設置不同的鏈路代價，在時延要求不同的業(yè)務之間協(xié)調(diào)資源。同時，算法還考慮到對保護資源的充分利用。通過為可利用的保護資源設置較低的代價值，在選路時優(yōu)先加以利用。仿真實驗表明，算法能夠降低時延較敏感業(yè)務阻塞率，提高了工作資源所占比例，實現(xiàn)了對網(wǎng)絡資源的充分利用，還提高了保護資源的利用率，節(jié)約了網(wǎng)絡資源。

［1］何榮希，張治中，李樂民，等.IP/MPLS over WDM網(wǎng)中基于共享風險鏈路組限制的共享通路保護算法［J］.電子學報，2002，30 (11):1638-1642.

［2］Saradhi C V，Murthy C S R.Routing differentiated reliable connections in single and multi-fiber WDM optical networks［C］.Proceedings of SPIE-The I nternational Society for Optical Engineering，2001，4599:24-35.

［3］Saradhi C V，Gurusarny M，Zhou L Y.Differentiated QoS for survivable WDM optical networks［J］.IEEE Communications Magazine，2004，42 (5):S8-14.

［4］黃樂天，孫強.WDM 光網(wǎng)絡中一種支持區(qū)分可靠性的迭代式路徑保護算法［A］.2011 International Conference on Information，Services and Management Engineering，Beijing，China，26 Dec.，2011:5.

［5］Tarhan A，Cavdar C.Shared path protection for distance adaptive elastic optical networks under dynamic traffic［C］.Almaty:2013 5th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT)，Almaty，Kazakhstan，10-13 Sept.，2013:62-67.

［6］梁俊，沈建華.一種基于區(qū)分業(yè)務等級的光網(wǎng)絡共享通路保護算法［J］.光通信研究，2013，(2):19-21.

［7］熊軻，裘正定，張煜，等.多加性QoS 約束下的鏈路分離路由算法［J］.通信學報，2010，31 (6):127-135.

［8］李潔，王興偉，黃敏，等.一種基于時延約束的光網(wǎng)絡共享通路保護機制［J］.東北大學學報(自然科學版)，2014，35 (2):179-183.

［9］樊冰，唐良瑞.電力通信網(wǎng)脆弱性分析［J］.中國電機工程學報，2014，34 (7):1191-1197.

［10］Poppe F，Jones J Venkatachalam S.Inference of shared risk link groups［EB/OL］.http://www.watersprings.org/pub/id/draft-many-inference-srlg-02.txt，2001-11-14.

［11］Fawaz W，Daheb B，Audouin O，et al.Service level agreement and provisioning in optical networks［J］.IEEE Communications Magazine，2004，42 (1):36-43.

［12］滕玲，丁慧霞，劉革，等.光纖復用保護通道傳輸時延差指標研究［J］.電信科學，2010，(S3):102-105.

［13］徐洋，葛文萍，李艷超，等.光網(wǎng)絡中基于誤碼率感知RWA 算法性能研究［J］.激光雜志，2014，(1):26-28.