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

《網(wǎng)絡(luò)編碼在OBS組播中的應(yīng)用.pptx》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、網(wǎng)絡(luò)編碼在OBS組播中的應(yīng)用傳統(tǒng)的多播傳輸是通過構(gòu)造多播樹實現(xiàn)的。典型的多播樹，如最小費的Steiner樹，其構(gòu)造過程一般是個NP完全問題[1]，因此大多數(shù)的近似算法[1-3]，均不能使多播傳輸達(dá)到“最大流最小割”(MAX-FLOWMIN-CUT)定理[4]確定的最大理論傳輸容量。這主要是因為：現(xiàn)有通信網(wǎng)絡(luò)中使用的路由機(jī)制認(rèn)為網(wǎng)絡(luò)中傳輸?shù)男畔⑹遣荒墀B加的,只能進(jìn)行存儲和轉(zhuǎn)發(fā)。圖1(b)表示的是網(wǎng)絡(luò)編碼方法，節(jié)點W對輸入的信息進(jìn)行模二加操作，然后將操作結(jié)果發(fā)送至輸出鏈路WX，然后又通過鏈路XY和XZ，最終達(dá)到信宿Y和Z。Y收到b1和后，通過譯碼操作就能解出b2，因此，信宿Y同時收到了b1

2、和b2。同理，通過譯碼操作，信宿Z也同時收到b1和b2。由此，基于網(wǎng)絡(luò)編碼的多播實現(xiàn)了理論上的最大傳輸容量網(wǎng)絡(luò)編碼優(yōu)缺點：1.提高網(wǎng)絡(luò)吞吐量如果為信源節(jié)點的符號空間，為通信網(wǎng)絡(luò)中的節(jié)點數(shù)目，則對于每條鏈路都是單位容量的通信網(wǎng)絡(luò)，基于網(wǎng)絡(luò)編碼的多播的吞吐量是路由多播的倍[16].2.均衡網(wǎng)絡(luò)負(fù)載圖2(a)所示的通信網(wǎng)絡(luò)，其各鏈路容量為2。圖2(b)表示的是基于多播樹的路由多播，為使各個信宿節(jié)點達(dá)到最大傳輸容量，該多播共使用SU、UX、UY、SW和WZ共5條鏈路，且每條鏈路上傳輸?shù)目尚辛鳛?；圖2(c)表示的是基于網(wǎng)絡(luò)編碼的多播，圖2(c)所示的網(wǎng)絡(luò)編碼多播所用的傳輸鏈路為9條，比圖2(b

3、)的多播樹傳輸要多4條鏈路。3.提高帶寬利用率圖2(b)消耗的總帶寬為：5×2=10；圖2(c)消耗總帶寬為：9×1=9，因此帶寬消耗節(jié)省了10%，提高了網(wǎng)絡(luò)帶寬利用率。網(wǎng)絡(luò)編碼的分類如果網(wǎng)絡(luò)節(jié)點對傳輸?shù)男畔⑦M(jìn)行線性操作，則稱為線性網(wǎng)絡(luò)編碼(LinearNetworkCoding)；否則稱為非線性網(wǎng)絡(luò)編碼。如果網(wǎng)絡(luò)節(jié)點對信息進(jìn)行操作的系數(shù)是隨機(jī)選取的，則稱為隨機(jī)網(wǎng)絡(luò)編碼；如果是通過算法確定出來的，則稱為確定性網(wǎng)絡(luò)編碼。另外有人已經(jīng)證明在有限域Fq中，只要域足夠大，則通過合適的線性網(wǎng)絡(luò)編碼，就能使多播傳輸達(dá)到最大的傳輸容量。目前，網(wǎng)絡(luò)編碼研究均限于有限域Fq中的線性網(wǎng)絡(luò)編碼。網(wǎng)絡(luò)編碼的構(gòu)

4、造算法網(wǎng)絡(luò)編碼構(gòu)造算法解決的主要問題是如何有效求得每條鏈路對應(yīng)的編碼向量，并運用該編碼向量進(jìn)行線性操作計算出鏈路上傳輸?shù)男畔⑾蛄俊＞幋a算法的復(fù)雜性是衡量網(wǎng)絡(luò)編碼能否有效實現(xiàn)的重要依據(jù)。典型的算法包括指數(shù)時間算法[6]、多項式時間算法[7]和貪婪算法[8]等，其中因多項式時間算法具有較低的復(fù)雜性，因此具有重要的理論和應(yīng)用價值。線性網(wǎng)絡(luò)編碼線性網(wǎng)絡(luò)編碼對單位容量的信道進(jìn)行編碼,當(dāng)連接兩個節(jié)點的有向鏈路的容量大于1時,把這條鏈路分成多條單位容量的信道。對于節(jié)點v∈V,記In(v)和Out(v)分別為輸入信道集和輸出信道集,

5、In(v)

6、和

7、Out(v)

8、分別為節(jié)點v的輸入信道數(shù)和輸出信道數(shù)。

9、組播網(wǎng)絡(luò)中,各節(jié)點收到對應(yīng)的單位信息,或稱為字符,在進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)前,需要對這些信息進(jìn)行編碼。我們將這類信息稱為源信息。假定一個節(jié)點的源信息為X1,X2,……X

10、In(v)

11、,那么應(yīng)用線性網(wǎng)絡(luò)編碼后各信道輸出的信息為:Yi=gi1X1+gi2X2+……+gi

12、In(v)

13、X

14、In(v)

15、公式(3)其中i=1,2,……,

16、Out(v)

17、,gi1,gi2,……,gi

18、In(v)

19、為有限域GF(2m)上的一組系數(shù)。我們將系數(shù)gi=(gi1,gi2,……,gi

20、In(v)

21、)稱為編碼向量,將Yi稱為信息向量。當(dāng)輸出信息Yi成為下游節(jié)點的輸入信息時,節(jié)點將對接收到的信息進(jìn)行新一輪的編碼。新的編碼信

22、息表示如下:Yi’=gi1’X1’+gi2’X2’+……+gi

23、In(v)

24、’X

25、In(v)

26、’公式(4)假設(shè)接收節(jié)點接收到的編碼向量為(g1,g2,……,gm),信息向量為(Y1,Y2,……,Ym),為了求出源點播出的信息,我們需要求解以下等式:Yj=gj1X1+gj2X2+……+gjnXn公式(5)其中,j=1,2,…,m。也相當(dāng)于求解如下的線性方程組:其中,X1,X2,…,Xn為源點播出的信息。要想恢復(fù)出源點播出的信息,只需要解以上的線性方程80組,由線性方程組的求解規(guī)則可知,公式(6)中需要m=n才有可能解碼,但是由于存在編碼向量線性相關(guān)的情況,所以m=n不是解碼成功的充分條件

27、。只有當(dāng)該方程組的系數(shù)矩陣的秩為源點的組播率h時,才能恢復(fù)出源點播出的信息。光網(wǎng)絡(luò)分層圖模型定義　網(wǎng)絡(luò)的物理拓?fù)錇镚(V,E,W)。其中:V表示節(jié)點集合,E表示鏈路,W為波長數(shù)。分層圖模型的基本思想是將原始網(wǎng)絡(luò)拓?fù)銰(V,E,W)復(fù)制W次,分層圖上的每一層對應(yīng)一個波長,也稱一個波長平面;然后在這個分層圖上計算源節(jié)點到目的節(jié)點之間的最優(yōu)路徑。光網(wǎng)絡(luò)的分層圖對業(yè)務(wù)的路由和波長選擇是在不同的波長層面上完成的,即在同一波長層面上完成了路由和波長的選擇。