周艷玲，張思成

(合肥學(xué)院 計算機(jī)科學(xué)與技術(shù)系，安徽 合肥 230001)

1 引言

在多播中應(yīng)用網(wǎng)絡(luò)編碼技術(shù)，除了有提升網(wǎng)絡(luò)吞吐量的顯著優(yōu)勢，還有實現(xiàn)多播網(wǎng)絡(luò)的流量均衡、提高帶寬利用率、提升網(wǎng)絡(luò)的可靠性、降低最優(yōu)吞吐量問題的計算復(fù)雜度[1]等優(yōu)點.網(wǎng)絡(luò)編碼理論使得在單源多播的網(wǎng)絡(luò)環(huán)境下，數(shù)據(jù)的傳輸可以達(dá)到最大流最小割定理所決定的網(wǎng)絡(luò)流量理論上的最大值[2].在有向無環(huán)網(wǎng)絡(luò)中研究最早也較為成熟的網(wǎng)絡(luò)編碼是線性網(wǎng)絡(luò)編碼，在線性網(wǎng)絡(luò)編碼中網(wǎng)絡(luò)節(jié)點對傳輸?shù)男畔⑦M(jìn)行線性操作.在多播網(wǎng)絡(luò)中，只要在足夠大的有限域Fq中通過合適的線性網(wǎng)絡(luò)編碼，總能使多播傳輸達(dá)到其理論的最大容量.允許多播中的網(wǎng)絡(luò)節(jié)點進(jìn)行網(wǎng)絡(luò)編碼，網(wǎng)絡(luò)編碼能夠顯著改善網(wǎng)絡(luò)的性能，使得多播傳輸達(dá)到其理論傳輸容量.

本文在研究其它多播容錯算法和網(wǎng)絡(luò)編碼的基礎(chǔ)上，提出一個新的可靠多播方案，即，網(wǎng)絡(luò)編碼與家族體系下的可靠多播方案(Reliable Multicast Scheme Based on the Family System and Network Coding, RM-FSNC).通過引入家族等級關(guān)系和隧道技術(shù)對多播故障進(jìn)行有效的恢復(fù)，引入網(wǎng)絡(luò)編碼提高網(wǎng)絡(luò)的容量和安全性.在一定程度上節(jié)省了網(wǎng)絡(luò)資源，降低了網(wǎng)絡(luò)開銷，有效地提高了多播可靠性.

2 相關(guān)工作

隨著網(wǎng)絡(luò)的發(fā)展和網(wǎng)絡(luò)新應(yīng)用的出現(xiàn)，多播通信勢在必行.多播的可靠性是廣大用戶關(guān)心的頭等重要的問題.處理多播網(wǎng)絡(luò)通信的故障恢復(fù)也成為一個研究的熱點問題.近幾年來在多播故障恢復(fù)方面的研究卻很少.

傳統(tǒng)的多播中，數(shù)據(jù)流以樹結(jié)構(gòu)進(jìn)行分發(fā)，一條鏈路出現(xiàn)故障將影響它的下游多個多播組成員的通信.一些研究提出利用單播恢復(fù)方案來實現(xiàn)多播通信下的故障恢復(fù)，如文獻(xiàn)[3-4]分別提出了鏈路保護(hù)、路徑保護(hù)及改進(jìn)的鏈路保護(hù)方案.在鏈路保護(hù)方案中，多播樹上的每一條鏈路都建立了保護(hù)路徑.在路徑保護(hù)方案中，每個目的節(jié)點，都必須從源節(jié)點開始建立一條保護(hù)路徑.改進(jìn)的鏈路方案與鏈路方案不同的是故障的通知點不同，在鏈路保護(hù)方案中，故障的通知點為鏈路的端節(jié)點，而改進(jìn)的鏈路保護(hù)方案中，故障的通知點是鏈路端節(jié)點的父節(jié)點或兄弟節(jié)點.雙樹(“Dual-Tree”)[5]是Aiguo Fei等提出的一種容錯多播方案，它除了基本的多播樹外，還構(gòu)造了第二棵與第一棵節(jié)點無關(guān)多播樹作為備份結(jié)構(gòu).在基本多播樹出現(xiàn)故障的情況下，通過注入通信流到第二棵樹上來快速的重新連接受影響的多播節(jié)點.Vignesh[6]、M. Yazid[7]等人提出的一種容錯多播方案-雙森林("Dual-Forest”)多播容錯方案，它是對雙樹方案的改進(jìn).類似于雙樹容錯多播方案，雙森林方案使用簡化的拓?fù)浣Y(jié)構(gòu)來建立備份路徑的.除了基本的多播樹外，也是像雙樹方案一樣，構(gòu)造了一棵與基本多播樹節(jié)點無關(guān)的多播樹作為備份結(jié)構(gòu).在基本多播樹出現(xiàn)故障的情況下，通過發(fā)現(xiàn)故障的節(jié)點執(zhí)行雙森林算法1以及收到重組消息的節(jié)點執(zhí)行相應(yīng)的雙森林算法2來快速的重新連接受影響的多播節(jié)點，以確保多播樹的正常通信.Craig, A.Nandy[8]等人提出基于軟件層面上的流量工程下的故障恢復(fù)方案，此方案在網(wǎng)絡(luò)硬件出現(xiàn)故障時，其故障恢復(fù)的效率并不理想.

鏈路保護(hù)、路徑保護(hù)及改進(jìn)的路徑保護(hù)可以有效地實現(xiàn)單鏈路的故障恢復(fù)，但需要浪費不必要的帶寬資源.雙樹算法和雙森林雖然克服了前三種不能很好的處理單節(jié)點故障的缺陷，但算法的執(zhí)行比較復(fù)雜，冗余路徑的存在造成了資源的嚴(yán)重浪費，并且實現(xiàn)起來比較麻煩，不利于實際的應(yīng)用.

3 RM-FSNC方案描述

3.1 家族體系的引入

圖1 家族體系的多播樹和成員關(guān)系表圖 圖2 具有家族體系的多播通信圖

圖1有12個表達(dá)式的關(guān)系.根據(jù)圖1中的表達(dá)式關(guān)系，可以將圖1的多播樹轉(zhuǎn)化為圖2基于家族等級關(guān)系下的隧道容錯多播樹.在圖2中，當(dāng)節(jié)點2或鏈路1-2出現(xiàn)故障時，受到影響的多播組成員有(g1，g2，g3，g4)，數(shù)量大于多播樹節(jié)點的度2，此時多播組成員g2會通過隧道g2g6與成員節(jié)點g6進(jìn)行通信，并且主動向其他的成員節(jié)點發(fā)出請求建立內(nèi)部多播樹并繼續(xù)進(jìn)行信息傳輸.當(dāng)故障恢復(fù)時，多播成員g2受到了來自節(jié)點1的信息，此時就自動關(guān)閉隧道，恢復(fù)到正常的多播樹進(jìn)行信息傳遞.當(dāng)鏈路2-4出現(xiàn)故障時，收到影響的多播組成員有(g1，g2)，數(shù)量等于多播樹的度2，此時多播成員g1會通過隧道g1g3與成員節(jié)點g3進(jìn)行通信，并且將通過隧道g1g2與成員g2進(jìn)行通信.當(dāng)故障恢復(fù)時，多播組成員g1收到來自節(jié)點4的信息，此時就自動關(guān)閉隧道，恢復(fù)到正常的多播樹進(jìn)行信息的傳遞.

3.2 網(wǎng)絡(luò)編碼的引入

RM-FSNC方案將網(wǎng)絡(luò)編碼理論應(yīng)用于多播通信中，在網(wǎng)絡(luò)編碼多播中，源節(jié)點對數(shù)據(jù)包的處理功能由傳統(tǒng)的分塊、存儲、轉(zhuǎn)發(fā)三個基本功能，變成分塊、編碼、存儲、轉(zhuǎn)發(fā).保證了網(wǎng)絡(luò)中的數(shù)據(jù)包在傳輸?shù)倪^程中，不會因為哪個數(shù)據(jù)包的丟失而引起數(shù)據(jù)包無法正常接收.源節(jié)點發(fā)送的數(shù)據(jù)包始終是數(shù)據(jù)分塊的編碼后的數(shù)據(jù)包，因此網(wǎng)絡(luò)傳輸過程中的安全性和可靠性也顯著提高.目的節(jié)點所接受到的數(shù)據(jù)是由兩部分組成，一部分為線性網(wǎng)絡(luò)編碼后的信息流，另一部分為線性編碼系數(shù)向量.在目的節(jié)點所接受的信息流，不需要關(guān)心信息流的次序問題，只需要關(guān)心是否收到與目的節(jié)點入度數(shù)相同的信息流數(shù)量，然后將信息流分離，按照接收的次序，將線性編碼系數(shù)向量組成線性系數(shù)矩陣，將線性編碼后的信息流組成一個目的信息流向量，經(jīng)過運算得到原信息流的向量組合，最終形成原始數(shù)據(jù).這個方法較傳統(tǒng)方法的優(yōu)點是，算法簡單，不需要復(fù)雜的局部編碼矩陣和全局編碼矩陣的運算.減少了中間編碼節(jié)點的開銷，節(jié)省了時間，方便了計算.另外，在源節(jié)點就對信息流進(jìn)行了信息分割和信息編碼，使得信息在傳輸過程中安全系數(shù)更高，并且節(jié)點和相鄰鏈路，鏈路與相鄰節(jié)點之間的信息傳遞的計算時間降低，傳輸速度提高，不需要太多的緩沖存儲.具有編碼能力的網(wǎng)絡(luò)節(jié)點采用最簡單的線性網(wǎng)絡(luò)編碼.在編解碼的過程中需要的時間最短，編碼算法簡單.圖3為在多播通信樹中具有編碼能力的節(jié)點信息流圖與不具有編碼節(jié)點的信息流圖.圖4為在網(wǎng)絡(luò)編碼和家族體制支持下的多播通信樹圖.

圖3 編碼節(jié)點和非編碼節(jié)點信息轉(zhuǎn)發(fā)圖 圖4 具有網(wǎng)絡(luò)編碼和家族體系下的多播樹

3.3 RM-FSNC中故障恢復(fù)方案

在多播通信的過程中，源節(jié)點將信息劃分成幾個數(shù)據(jù)塊，一般情況下，數(shù)據(jù)塊的劃分的數(shù)量是根據(jù)節(jié)點的度來定的，在圖4中，節(jié)點1的度為2，所以源節(jié)點將信息劃分成兩個數(shù)據(jù)塊，然后進(jìn)行簡單的線性編碼和組合后形成新的編碼信息X1和X2，兩個信息在不同的分支上傳輸.中間節(jié)點2、3、4、5、6、7在多播通信過程中不需要編碼功能，直接轉(zhuǎn)發(fā)數(shù)據(jù)包到下行鏈路上.數(shù)據(jù)包X12是一個按照先后順序的一個包，先轉(zhuǎn)發(fā)X1再轉(zhuǎn)發(fā)X2，同理，X21也是一個按照時間先后順序的一個數(shù)據(jù)包，先轉(zhuǎn)發(fā)X2再轉(zhuǎn)發(fā)X1.在正常情況下，目的節(jié)點都能夠收到X1和X2數(shù)據(jù)包，然后通過線性編碼的逆運算就可以恢復(fù)原數(shù)據(jù)包.當(dāng)多播組成員節(jié)點在指定的時間內(nèi)沒有收到多播源的信息，這時系統(tǒng)就知道多播樹中的某節(jié)點或某鏈路發(fā)生了故障，在極短的時間內(nèi)啟動已經(jīng)建立好的備份隧道，并自由的建立受影響的多播組成員的內(nèi)部多播樹，此時多播通信正常進(jìn)行.當(dāng)故障恢復(fù)后，關(guān)閉備份隧道，受影響的多播組成員由內(nèi)部多播樹狀態(tài)轉(zhuǎn)換成正常的多播樹狀態(tài)，進(jìn)行多播信息的正常傳輸.如果故障一直沒有恢復(fù)，多播信息就一直通過備份隧道和內(nèi)部多播樹進(jìn)行受影響的多播組成員的信息傳輸.其算法流程圖如圖5所示.

3.4 RM-FSNC方案的特點

(1)多播指的是一點對多點的多播形式，在多播組中，首先，根據(jù)多播源和多播組成員建立一棵最短路徑樹.然后，根據(jù)分支節(jié)點的分支情況來劃分多播組成員，并建立成員的最高級的家族關(guān)系.本文以二叉樹為例，根節(jié)點為分支節(jié)點，這是劃分成兩個大的家族，再分別以每一大家族的根節(jié)點為分支節(jié)點，分別劃分各自的家族關(guān)系，直到組成員直接的分支節(jié)點將組成員劃分成組成員數(shù)量的最低級的家族關(guān)系.對于每一個等級的家族關(guān)系，找出家族之間的最短路徑，然后通過隧道來建立兩個同等級家族之間的路徑關(guān)系.

(2)線性網(wǎng)絡(luò)編碼在多播網(wǎng)絡(luò)中的應(yīng)用，保證在通信開始源節(jié)點就對原信息進(jìn)行了分塊和編碼，提高了網(wǎng)絡(luò)通信過程中的安全性.編碼和譯碼算法非常的簡單，因此，時間的消耗較以往也沒有增加.從而提高了多播網(wǎng)絡(luò)的可靠性.

(3)當(dāng)多播樹出現(xiàn)故障時，不管是節(jié)點故障還是鏈路故障，首先，分析受到影響的成員節(jié)點是屬于哪一等級的家族，然后，根據(jù)該家族的等級來尋找同一等級家族的隧道作為備份路徑，通過隧道來進(jìn)行信息的正常傳輸.直到故障解除后，再次恢復(fù)到正常工作路徑上進(jìn)行傳輸.

(4)當(dāng)受影響的多播組成員數(shù)量多于多播樹的節(jié)點度的平均值時，就在受影響的成員內(nèi)部以隧道節(jié)點為源節(jié)點建立最短多播路徑樹.

(5)基于家族等級關(guān)系的隧道容錯多播樹方案，不僅可以解決節(jié)點故障，而且可以解決鏈路故障，并且解決這兩種故障的方法都是一樣的，都是通過建立同等級家族間最短路徑隧道來進(jìn)行故障的容錯.當(dāng)故障恢復(fù)后，隧道端的主動節(jié)點自動關(guān)閉隧道，并切換到正常的多播樹繼續(xù)進(jìn)行多播信息的傳遞.

(6)在該方案中，故障的檢測是由多播組成員主動發(fā)起的，故障恢復(fù)后鏈路的切換也是由多播組成員主動發(fā)起的，因此，該算法將主動權(quán)和控制權(quán)集中在端節(jié)點，簡化了中間節(jié)點的功能，這樣有利于系統(tǒng)的維護(hù)，并且對于多播而言，動態(tài)性是多播的主要特性，多播組成員的動態(tài)變化對算法影響不大.

圖5 RM-FSNC方案下多播故障恢復(fù)算法流程圖 圖6 算法1和算法2時間復(fù)雜度比較圖

4 RM-FSNC方案的性能分析

RM-FSNC方案是繼雙樹容錯方案和雙森林容錯方案之后提出的一個新的多播容錯方案.雙樹容錯方案所建立的備份樹為所有成員節(jié)點之間的簡單的連接，并且在建立備份樹的過程中沒有考慮備份樹的額外開銷問題.雙森林容錯方案是用森林代替了備份樹，其容錯是通過備份森林來實現(xiàn)的，備份森林是兩部分多播組成員之間的連接，然后再通過一條最短路徑將兩部分成員進(jìn)行連接，在建立備份森林的過程中僅僅考慮到建立兩部分成員之間連接的路徑開銷問題，但沒有考慮到兩部分成員的額外開銷問題.RM-FSNC方案采取了雙樹和雙森林多播容錯方案的優(yōu)點，在建立備份樹的過程中，需要分析受影響的成員的家族等級，從而選擇相應(yīng)的隧道進(jìn)行通信恢復(fù)，同時，內(nèi)部最優(yōu)多播樹可以降低系統(tǒng)的額外開銷.雙樹容錯方案只能進(jìn)行鏈路故障的恢復(fù)，雙森林容錯方案能進(jìn)行鏈路故障和節(jié)點故障，但出現(xiàn)故障時，要先判斷故障類型，然后采用相應(yīng)的多播故障容錯算法進(jìn)行故障恢復(fù).RM-FSNC方案不僅能進(jìn)行鏈路故障恢復(fù)而且能進(jìn)行節(jié)點故障恢復(fù)，在出現(xiàn)故障時，不需要判斷故障的類型，直接采用RM-FSNC故障恢復(fù)算法進(jìn)行故障恢復(fù).

RM-FSNC故障恢復(fù)方案屬于主動式的故障恢復(fù)類型，在故障發(fā)生的時候，直接調(diào)用備份隧道進(jìn)行故障恢復(fù)，降低了網(wǎng)絡(luò)延遲，節(jié)省了大量的時間.

圖6為本文中的方案與傳統(tǒng)故障恢復(fù)發(fā)難復(fù)雜度的比較圖，算法1線為本文中的RM-FSNC方案中所體現(xiàn)的時間復(fù)雜度，算法2線為傳統(tǒng)的故障恢復(fù)算法所體現(xiàn)的時間復(fù)雜度.通過圖6可以看出，本文的方案隨著網(wǎng)絡(luò)節(jié)點的增多，其復(fù)雜度呈現(xiàn)緩慢增長的趨勢，而傳統(tǒng)的多項式復(fù)雜度網(wǎng)絡(luò)編碼算法其復(fù)雜度隨著網(wǎng)絡(luò)節(jié)點的增加呈現(xiàn)快速增長的趨勢.實驗證明，隨著網(wǎng)絡(luò)節(jié)點數(shù)的增加，該方案的優(yōu)勢更加突出.

5 結(jié)論

RM-FSNC方案是繼雙樹容錯方案和雙森林容錯方案之后提出的一個新的多播容錯方案.RM-FSNC方案采取了雙樹和雙森林多播容錯方案的優(yōu)點，在建立備份樹的過程中，首先分析受影響多播組成員的家族關(guān)系等級，然后選取相應(yīng)的隧道來進(jìn)行多播通信恢復(fù)，對于受影響的多播組成員根據(jù)數(shù)量來建立內(nèi)部最優(yōu)多播樹進(jìn)行備份樹的多播通信，在多播容錯恢復(fù)的過程中，始終考慮系統(tǒng)的額外開銷問題，盡量將系統(tǒng)的額外開銷減少的最小.該方案不僅能進(jìn)行鏈路故障恢復(fù)而且能進(jìn)行節(jié)點故障恢復(fù)，在出現(xiàn)故障時，不需要判斷故障的類型.該方案屬于主動式的故障恢復(fù)類型，在故障發(fā)生的時候，直接調(diào)用備份隧道進(jìn)行故障恢復(fù)，降低了網(wǎng)絡(luò)延遲.對于動態(tài)性多播通信，RM-FSNC方案有利于多播規(guī)模的擴(kuò)展，與以往的故障恢復(fù)算法進(jìn)行比較，可以發(fā)現(xiàn)新的多播容錯方案在節(jié)省時間和網(wǎng)絡(luò)帶寬上都有了進(jìn)一步的提高.

[參考文獻(xiàn)]

[1]陶少國,黃佳慶,等.一種改進(jìn)的最小代價網(wǎng)絡(luò)編碼算法[J].華中科技大學(xué)學(xué)報,2012,36(5):1-4.

[2]劉宴濤，夏桂陽,等.一種基于子樹分解的組播線性網(wǎng)絡(luò)編碼算法[J].計算機(jī)工程,2015,41(11)：153-159.

[3]C. Wu, W. Lee, Y.Hou, W.Chu. A new preplanned self-healing scheme for multicast ATM network[C].Bei Jing:IEEE ICCT'96,1996.

[4]C. Wu, W. Lee, Y. Hou. Back-up VP preplanning strategies for survivable multicast ATM networks[C].Canada: IEEE International Conference on Communications,1997.

[5]A.Fei, J.Cui, M.Gerla, D.Gavendish. A "Dual-Tree" Scheme for Fault-Tolerant Multicast[C].Helsinki: IEEE ICC,2001.

[6]Vignesh R R,C-H LUNC,A. PANDEY. A subtree-based approach to failure detection and protection for multicast in SDN[J].Frontiers of Information Technology & Electronic Engineering，2016,17(7):682-700.

[7]M. Yazid SAIDI, B.Cousin, M. Molnar. An Efficient Multicast Protection Scheme based on Dual-Forest[J].Irisa Internal Research Report,2006,28(3):34-40.

[8]Craig,A. Nandy,B.Lambadaris, et al. Load balancing for multicast traffic in SDN using real-time link cost modification[C].London :IEEE International Conference on Communications,2015.