陳虹宇

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

本文主要對網(wǎng)絡(luò)編碼的原理，網(wǎng)絡(luò)編碼在光組播中的應(yīng)用及其在光網(wǎng)絡(luò)抗毀性中應(yīng)用研究進(jìn)行了描述和分析，重點(diǎn)介紹了網(wǎng)絡(luò)編碼在光層組播中的算法和1+N保護(hù)算法。在光網(wǎng)絡(luò)中還可利用網(wǎng)絡(luò)編碼在信息處理和融合上的優(yōu)勢，將其應(yīng)用到光網(wǎng)絡(luò)的故障定位機(jī)制中，可使從單個(gè)信源發(fā)出的信息經(jīng)過不同的探測通路后得到不同的處理。網(wǎng)絡(luò)編碼的理論創(chuàng)新具有普遍意義，應(yīng)用前景十分廣闊，自其提出以來，網(wǎng)絡(luò)編碼理論在信息論、編碼、通信網(wǎng)絡(luò)、網(wǎng)絡(luò)交換理論、無線通信、計(jì)算機(jī)科學(xué)、密碼學(xué)、矩陣論等研究領(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)絡(luò)編碼的多播路由算法［J］.西安電子科技大學(xué)學(xué)報(bào)，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.