網絡編碼與家族體系下的可靠多播方案

周艷玲，張思成

(合肥學院 計算機科學與技術系，安徽 合肥 230001)

1 引言

在多播中應用網絡編碼技術，除了有提升網絡吞吐量的顯著優勢，還有實現多播網絡的流量均衡、提高帶寬利用率、提升網絡的可靠性、降低最優吞吐量問題的計算復雜度[1]等優點.網絡編碼理論使得在單源多播的網絡環境下，數據的傳輸可以達到最大流最小割定理所決定的網絡流量理論上的最大值[2].在有向無環網絡中研究最早也較為成熟的網絡編碼是線性網絡編碼，在線性網絡編碼中網絡節點對傳輸的信息進行線性操作.在多播網絡中，只要在足夠大的有限域Fq中通過合適的線性網絡編碼，總能使多播傳輸達到其理論的最大容量.允許多播中的網絡節點進行網絡編碼，網絡編碼能夠顯著改善網絡的性能，使得多播傳輸達到其理論傳輸容量.

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

2 相關工作

隨著網絡的發展和網絡新應用的出現，多播通信勢在必行.多播的可靠性是廣大用戶關心的頭等重要的問題.處理多播網絡通信的故障恢復也成為一個研究的熱點問題.近幾年來在多播故障恢復方面的研究卻很少.

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

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

3 RM-FSNC方案描述

3.1 家族體系的引入

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

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

3.2 網絡編碼的引入

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

圖3 編碼節點和非編碼節點信息轉發圖 圖4 具有網絡編碼和家族體系下的多播樹

3.3 RM-FSNC中故障恢復方案

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

3.4 RM-FSNC方案的特點

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

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

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

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

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

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

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

4 RM-FSNC方案的性能分析

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

RM-FSNC故障恢復方案屬于主動式的故障恢復類型，在故障發生的時候，直接調用備份隧道進行故障恢復，降低了網絡延遲，節省了大量的時間.

圖6為本文中的方案與傳統故障恢復發難復雜度的比較圖，算法1線為本文中的RM-FSNC方案中所體現的時間復雜度，算法2線為傳統的故障恢復算法所體現的時間復雜度.通過圖6可以看出，本文的方案隨著網絡節點的增多，其復雜度呈現緩慢增長的趨勢，而傳統的多項式復雜度網絡編碼算法其復雜度隨著網絡節點的增加呈現快速增長的趨勢.實驗證明，隨著網絡節點數的增加，該方案的優勢更加突出.

5 結論

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

[參考文獻]

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

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