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

陳虹宇

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

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

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

1 網絡編碼在光組播中的應用

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

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

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

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

圖1 傳統組播與基于網絡編碼的組播

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

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

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

2 網絡編碼在光網絡抗毀性中的應用

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

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

3 網絡編碼的1+N保護算法

基于傳統的1∶1保護、1+1保護、1∶N保護，美國Ahmed E.Kamal基于網絡編碼提出了1+N共享保護機制［10］。基于網絡編碼的1+N保護具有保護切換時間短、資源利用率高的優點，其基本思想如下:

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

圖2 基于網絡編碼的1+N保護

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

4 結束語

本文主要對網絡編碼的原理，網絡編碼在光組播中的應用及其在光網絡抗毀性中應用研究進行了描述和分析，重點介紹了網絡編碼在光層組播中的算法和1+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超高速傳送系統發展及趨勢［J］.現代電信科技，2010(4)：28-31.

［3］王占碩，張芙蓉，張建.100G WDM傳輸系統的發展研究［J］.現代電信科技，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］王靜，劉景美，王新梅.一種網絡編碼的多播路由算法［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.