單鏈路故障的一種1+N保護策略

陳虹宇

(重慶工商職業(yè)學院電子信息工程學院，重慶 400000)

在傳統(tǒng)的網(wǎng)絡中，網(wǎng)絡節(jié)點(路由器、交換機等)只對數(shù)據(jù)進行路由、轉(zhuǎn)發(fā)或復制，很難達到網(wǎng)絡的最大傳輸容量。2000年，Ahlswede等［1］基于網(wǎng)絡信息流提出了網(wǎng)絡編碼的思想，其基本思想是在網(wǎng)絡節(jié)點引入編碼融合功能，網(wǎng)絡節(jié)點對接收到的多個數(shù)據(jù)分組進行編碼后再以多點傳送方式(組播)轉(zhuǎn)發(fā)出去，不同于傳統(tǒng)網(wǎng)絡節(jié)點的簡單存儲和轉(zhuǎn)發(fā)操作。目的結(jié)點收到數(shù)據(jù)后依據(jù)相應的編碼系數(shù)進行解碼恢復原始數(shù)據(jù)。通過允許網(wǎng)絡中間節(jié)點進行編碼，可以達到網(wǎng)絡最大流傳輸理論的上界。

網(wǎng)絡編碼概念的提出使原先分立于物理層的“編碼”與網(wǎng)絡層的“路由”得到了有機地統(tǒng)一。同時，其顯著的技術(shù)優(yōu)勢也已被應用到網(wǎng)絡其他重要方面的研究，如在保障網(wǎng)絡鏈路數(shù)據(jù)傳輸?shù)目煽啃?、安全性，以及提高網(wǎng)絡帶寬的利用效率等。特別地，隨著Internet的迅猛發(fā)展，以及移動互聯(lián)網(wǎng)，高清視頻點播、高速寬帶上網(wǎng)和云計算等高寬帶應用的不斷興起，基于IP的數(shù)據(jù)業(yè)務量爆炸式增長。據(jù)統(tǒng)計，IP業(yè)務流量年平均增長率達到50%以上。按此計算，6 a后的網(wǎng)絡帶寬需求將是當前網(wǎng)絡的10倍以上［2，3］，這就對傳統(tǒng)的光網(wǎng)絡提出了新的容量、功能和性能上的需求，也為其發(fā)展提供了新的機遇和強大的驅(qū)動力量。超高速、超大容量、動態(tài)靈活的全光互聯(lián)網(wǎng)是未來光網(wǎng)絡發(fā)展的方向。如何提高光網(wǎng)絡的生存性能，即提高網(wǎng)絡的抗毀性，同時，最大程度地提高網(wǎng)絡帶寬、波長資源的利用率，已成為光網(wǎng)絡通信研究的重要問題之一。目前，網(wǎng)絡編碼已被國際學術(shù)界和業(yè)界認定為解決網(wǎng)絡傳輸問題的重要手段［4，5］。

1 網(wǎng)絡編碼在光組播中的應用

近年來，IPTV、視頻點播、視頻會議、數(shù)字電視、遠程教育和遠程醫(yī)療等業(yè)務需求的快速增長，這類多目的節(jié)點通信需求的增長和全光網(wǎng)技術(shù)的發(fā)展，使光層組播(multicast)技術(shù)成為人們關(guān)注和研究的熱點。在IP over WDM網(wǎng)絡結(jié)構(gòu)下網(wǎng)絡組播可分為3種模式:IP組播、基于光路(light path)的組播和直接在WDM層采用分光技術(shù)(Light splitting)實現(xiàn)的組播(光層組播)［6-8］。

在IP組播模式下，依然采用基于IP的逐跳復制轉(zhuǎn)發(fā)方法，光層僅在IP路由器之間提供點到點的單播光信道。在基于light path的模式下，利用light path構(gòu)造的虛拓撲，將數(shù)據(jù)流直接由源沿一條light path以單路由跳(single IP router-hop)的方式發(fā)向各個目的接收點。由于從源到每個目的點僅有單個路由跳，減少了不必要的光-電-光轉(zhuǎn)換，提高了轉(zhuǎn)發(fā)效率且保證了業(yè)務質(zhì)量。但是，這種基于光路的組播模式是采用單播光路實現(xiàn)的光組播模擬，網(wǎng)絡帶寬使用效率低。在光層實現(xiàn)的光層組播則利用某些光器件(如分光器)的組播(分光)能力直接在光層以“光樹”的形式實現(xiàn)組播，網(wǎng)絡波長資源(波長信道)使用效率較高。

圖1是傳統(tǒng)光層組播與基于網(wǎng)絡編碼的光組播的比較，其中 S 為源節(jié)點、T1、T2 為目的接收節(jié)點，1、2、3、4 為中間節(jié)點。假設各鏈路無差錯、無時延，圖1(a)中各邊的容量為2個波長容量，由最大流最小割定理可知:從源節(jié)點S到目的接收節(jié)點T1、T2最大傳播速率不可能超過4個波長容量。

圖1(b)是一個典型的單會話型光組播，光組播樹源節(jié)點和目的節(jié)點之間只有唯一的一條光路進行數(shù)據(jù)傳輸，此時每個接收節(jié)點(T1、T2)接收數(shù)據(jù)所達到的最大傳送速率為1個波長容量。采取如圖1(c)所示的多會話型光組播可提高網(wǎng)絡組播速率，圖1(c)中每個會話建立一條源節(jié)點和目的節(jié)點之間的光路。此時每個接收節(jié)點(T1、T2)接收數(shù)據(jù)所達到的最大傳送速率為均為3個波長容量，但仍小于由最大流最小割定理確定的最大傳播速率4個波長容量。因此，傳統(tǒng)的單會話型光組播和多會話型光組播都不能最大限度地利用網(wǎng)絡傳輸能力，提高網(wǎng)絡組播效率。

圖1 傳統(tǒng)組播與基于網(wǎng)絡編碼的組播

為了改善傳統(tǒng)光組播性能，可將網(wǎng)絡編碼的思想應用到光組播中。如圖1(d)所示，通過允許中間節(jié)點2對收到的數(shù)據(jù)a和c，b和d分別進行編碼(異或)操作，其編碼后產(chǎn)生新的數(shù)據(jù)分別表示為a⊕c和b⊕d。由此，原來傳輸?shù)?個波長容量的數(shù)據(jù)壓縮為2個，然后分別在兩個光路上發(fā)送到目的接收節(jié)點T1和T2。T1和T2通過另外兩條鏈路傳來的數(shù)據(jù)a、b和c、d分別進行解碼(異或)操作，從而恢復出原始發(fā)端數(shù)據(jù)。對節(jié)點T1，當收到數(shù)據(jù)a、b、a⊕ c、b⊕d后，它可以通過解碼得到數(shù)據(jù)c、d，即:c=a⊕(a⊕c)、d=b⊕(b⊕b4)。同樣地，節(jié)點T2也可以從數(shù)據(jù)c、d、a⊕c、b⊕d中解碼得到數(shù)據(jù)a、b。

顯然地，采用網(wǎng)絡編碼后，接收節(jié)點T1和T2均可接收到數(shù)據(jù)a、b、c，d，從而達到了網(wǎng)絡的最大傳播速率4個波長容量。除此外，采用網(wǎng)絡編碼后，可達到網(wǎng)絡負載均衡。例如:圖1(b)中傳統(tǒng)單會話型光組播使用了網(wǎng)絡中的4條鏈路，閑置了另外5條鏈路，使得網(wǎng)絡中的鏈路帶寬資源占用不平衡;而圖1(d)中采用網(wǎng)絡編碼的光組播算法則均衡地利用了網(wǎng)絡中的全部9條鏈路。

通過上述分析可以得出，在光組播中應用網(wǎng)絡編碼，能提高組播速率，實現(xiàn)組播最大容量，并能實現(xiàn)網(wǎng)絡負載均衡。

2 網(wǎng)絡編碼在光網(wǎng)絡抗毀性中的應用

網(wǎng)絡的抗毀性即生存性(Network Survivability)泛指網(wǎng)絡在經(jīng)受各種網(wǎng)絡故障時鏈路，節(jié)點失效，仍能維持可接受的業(yè)務質(zhì)量的能力。在WDM光網(wǎng)絡中，一根光纖可以支持成百上千個波長信道，而每個波長的傳輸速率每秒鐘可達幾十吉比特，一根光纖的失效將會導致大量業(yè)務的中斷。相比傳統(tǒng)的IP層客戶所采用的恢復機制，如傳統(tǒng)IP網(wǎng)絡采取的“重路由”恢復機制，光層的恢復機制技術(shù)具有速度快、靈活、透明、恢復簡單、可靠性高以及成本低等優(yōu)點。所以WDM光網(wǎng)絡的生存性問題成為了當前研究的熱點問題［9］。

WDM光網(wǎng)絡的生存性技術(shù)可以分為保護(Protection)和恢復(Restoration)兩大類。保護是指事先為業(yè)務預留保護資源，當故障發(fā)生時，業(yè)務可以切換到備用資源上承載［6-9］?；謴褪侵覆⒉皇孪葹闃I(yè)務預留保護資源，當故障發(fā)生后，再動態(tài)地尋找網(wǎng)絡中的空閑資源來承載那些受故障影響的業(yè)務。從保護資源(備份資源)的使用情況來分，WDM網(wǎng)絡中的保護機制可以分為專用保護(dedicated protection)和共享保護(shared protection)。在專用保護中，保護路上的備份資源(波長)被保護路所獨享，專用保護可分為1+1和1∶1兩種方式。在1+1保護方式中，源節(jié)點通過工作路和保護路同時向目的節(jié)點發(fā)送數(shù)據(jù)，目的節(jié)點則采用擇優(yōu)接收的方式從工作路和保護路選擇一路信號接收。1+1保護方式中，只需要目的節(jié)點檢測到信號質(zhì)量劣化就可以立即完成保護倒換，其保護切換時間短。在1∶1保護中，源節(jié)點和目的節(jié)點之間也存在著兩條事先建立好的路徑:一條為工作路徑，一條為保護路徑。但在網(wǎng)絡正常運轉(zhuǎn)的情況下，僅利用工作路徑傳送業(yè)務;只有當工作路徑出現(xiàn)故障時，才通過一定的信令過程將業(yè)務切換到保護路徑上傳輸。相比1+1保護方式，1∶1保護方式的保護切換時間較長。對于1∶N保護而言，保護路徑可以被N條工作路徑所共享，當工作路徑出現(xiàn)故障時，該工作路徑上的業(yè)務通過一定的信令過程將業(yè)務切換到保護路徑上傳輸。相比1+1、1∶1保護，1∶N保護方式資源利用率高。

3 網(wǎng)絡編碼的1+N保護算法

基于傳統(tǒng)的1∶1保護、1+1保護、1∶N保護，美國Ahmed E.Kamal基于網(wǎng)絡編碼提出了1+N共享保護機制［10］?；诰W(wǎng)絡編碼的1+N保護具有保護切換時間短、資源利用率高的優(yōu)點，其基本思想如下:

如圖2中的網(wǎng)絡模型所示，網(wǎng)絡中有3條單向連接的工作通路和一條保護通路，保護路徑保護3條工作路徑。源節(jié)點 Sj(j=1，2，3)同時發(fā)送相應的數(shù)據(jù)單元 sj(j=1，2，3)至對應的目的節(jié)點Dj(j=1，2，3)和節(jié)點A。3個源節(jié)點發(fā)送至A節(jié)點的數(shù)據(jù)單元在A節(jié)點處通過模二加進行線性組合，然后A節(jié)點將模二加之和sum1=s1⊕s2⊕s3發(fā)送至另一節(jié)點X。目的節(jié)點Dj除在對應的工作通路上接收對應源節(jié)點Sj發(fā)送來的數(shù)據(jù)單元sj之外，并將接受到的數(shù)據(jù)單元sj發(fā)送給B節(jié)點。所有目的節(jié)點發(fā)送至B節(jié)點的數(shù)據(jù)單元在B節(jié)點處通過模二加進行線性組合，然后B節(jié)點將模二加之和sum2=s1⊕s2⊕s3發(fā)送至節(jié)點X(此過程中的節(jié)點A、B、X可能是網(wǎng)絡中的同一節(jié)點或不同節(jié)點)。節(jié)點A、B、X是否是網(wǎng)絡中的同一節(jié)點或不同節(jié)點是由各源節(jié)點之間、各目的節(jié)點之間的位置所決定的。

圖2 基于網(wǎng)絡編碼的1+N保護

節(jié)點X將節(jié)點A發(fā)送來的模二加之和sum1與節(jié)點B發(fā)送來的模二加之和sum2再進行模二加，并將線性組合sum1⊕sum2回送給各目的節(jié)點Dj。當整個網(wǎng)絡運行正常時，線性組合sum1⊕sum2等于0。當網(wǎng)絡中有一鏈路發(fā)生故障失效時，例如S2至D2的工作通路上有一鏈路發(fā)生故障，此時D2節(jié)點將接收不到S2節(jié)點發(fā)送來的數(shù)據(jù)單元S2，因此其傳送給節(jié)點B的數(shù)據(jù)單元的值為0。節(jié)點X從節(jié)點B處接收到的數(shù)據(jù)為sum2=s1⊕s3，然后節(jié)點X再將線性組合sum1⊕sum2(等于s2)回送給D2。這樣雖然節(jié)點D2在工作通路上接收不到s2發(fā)送來的數(shù)據(jù)，但其可通過保護通路接收到恢復的數(shù)據(jù)，實現(xiàn)了網(wǎng)絡的抗毀性。與1+1保護相比此保護方法用一條保護通路保護N條工作通路，節(jié)省了昂貴的保護資源，提高了網(wǎng)絡資源利用率;與1∶N保護相比，當網(wǎng)絡中工作通路發(fā)生故障時，該保護方法不必通過信令過程將工作路徑上的業(yè)務切換到保護路徑上傳輸，因此其保護切換時間較短。

4 結(jié)束語

本文主要對網(wǎng)絡編碼的原理，網(wǎng)絡編碼在光組播中的應用及其在光網(wǎng)絡抗毀性中應用研究進行了描述和分析，重點介紹了網(wǎng)絡編碼在光層組播中的算法和1+N保護算法。在光網(wǎng)絡中還可利用網(wǎng)絡編碼在信息處理和融合上的優(yōu)勢，將其應用到光網(wǎng)絡的故障定位機制中，可使從單個信源發(fā)出的信息經(jīng)過不同的探測通路后得到不同的處理。網(wǎng)絡編碼的理論創(chuàng)新具有普遍意義，應用前景十分廣闊，自其提出以來，網(wǎng)絡編碼理論在信息論、編碼、通信網(wǎng)絡、網(wǎng)絡交換理論、無線通信、計算機科學、密碼學、矩陣論等研究領(lǐng)域都受到人們的普遍關(guān)注。

［1］Li S Y，Yeung R W.Linear network coding［J］.IEEE Trans.on 1nformation Theory，2003，49(2)：371-381.

［2］李暉，唐留城.40G/100G超高速傳送系統(tǒng)發(fā)展及趨勢［J］.現(xiàn)代電信科技，2010(4)：28-31.

［3］王占碩，張芙蓉，張建.100G WDM傳輸系統(tǒng)的發(fā)展研究［J］.現(xiàn)代電信科技，2011(8)：61-70.

［4］Agarwal A，Charikar M.On the advantage of network coding for improving network th roughput［C］//Information Theory Workshop，2004：247-249.

［5］Langberg Michael，Sprintson，Alexander，et al.The encoding complexity of network coding［J］.IEEE Transactions on Information Theory，June，2006，52(6)：2386-2397.

［6］MOB M，NGUYEN B.QoS-guaranteed one-to-many and many-to-many multicast routing［J］.Computer Communications，2003，26(7)：652-669.

［7］王靜，劉景美，王新梅.一種網(wǎng)絡編碼的多播路由算法［J］.西安電子科技大學學報，2008，35(1)：25-27.

［8］Zhang Xijun.Wei J，Qiao Chunming.Constrained multicast routing in WDM networks with sparse light splitting［J］.IEEE/OSA.Lightwave Technology，2000，12(18)：1917-1927.

［9］Zhou D，Subramaniam S.Survivability in optical networks［J］.IEEE Network，2000(14)：16-23.

［10］Kamal A E，Al-Kofahi O.Efficient and Agile 1+N Protection，Communications，IEEE Transactions on，2011(1)：169-180.