網(wǎng)絡(luò)編碼與家族體系下的可靠多播方案

周艷玲，張思成

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

1 引言

在多播中應(yīng)用網(wǎng)絡(luò)編碼技術(shù)，除了有提升網(wǎng)絡(luò)吞吐量的顯著優(yōu)勢(shì)，還有實(shí)現(xiàn)多播網(wǎng)絡(luò)的流量均衡、提高帶寬利用率、提升網(wǎng)絡(luò)的可靠性、降低最優(yōu)吞吐量問題的計(jì)算復(fù)雜度[1]等優(yōu)點(diǎn).網(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é)點(diǎn)對(duì)傳輸?shù)男畔⑦M(jìn)行線性操作.在多播網(wǎng)絡(luò)中，只要在足夠大的有限域Fq中通過合適的線性網(wǎng)絡(luò)編碼，總能使多播傳輸達(dá)到其理論的最大容量.允許多播中的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)編碼，網(wǎng)絡(luò)編碼能夠顯著改善網(wǎng)絡(luò)的性能，使得多播傳輸達(dá)到其理論傳輸容量.

本文在研究其它多播容錯(cuò)算法和網(wǎng)絡(luò)編碼的基礎(chǔ)上，提出一個(gè)新的可靠多播方案，即，網(wǎng)絡(luò)編碼與家族體系下的可靠多播方案(Reliable Multicast Scheme Based on the Family System and Network Coding, RM-FSNC).通過引入家族等級(jí)關(guān)系和隧道技術(shù)對(duì)多播故障進(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)，多播通信勢(shì)在必行.多播的可靠性是廣大用戶關(guān)心的頭等重要的問題.處理多播網(wǎng)絡(luò)通信的故障恢復(fù)也成為一個(gè)研究的熱點(diǎn)問題.近幾年來在多播故障恢復(fù)方面的研究卻很少.

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

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

3 RM-FSNC方案描述

3.1 家族體系的引入

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 RM-FSNC方案的性能分析

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

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

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

5 結(jié)論

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

[參考文獻(xiàn)]

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

[2]劉宴濤，夏桂陽,等.一種基于子樹分解的組播線性網(wǎng)絡(luò)編碼算法[J].計(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.