一種改進的應用層組播樹構建和維護算法

劉浩杰 金鑫

(武漢理工大學 信息工程學院，湖北武漢 430072)

0 引言

當前，為了緩解由于不斷增加的通信需求所帶來的網絡瓶頸問題，組播技術越來越受研究者的關注。而其中應用層的組播主要基于端到端的思想［1］，它保持網絡原有的簡單、不可靠、單播的轉發模式，由端系統實現組播轉發功能，讓網絡的核心部分用于數據通信而不實現特殊應用。因此，能夠有效地降低核心網絡的復雜性，便于升級維護，同時提高網絡的通用性和靈活性，在增加新應用時不必改變核心網絡。基于應用層組播技術設計的視頻會議系統、多媒體網絡教學系統以及媒體流的分發系統等，有著十分廣泛的應用，因此對應用層組播技術進行研究，具有重要的現實意義。

1 相關工作

目前，已經有眾多的研究者對應用層組播技術進行了研究，先后提出了一系列組播方法。如，文獻［2］在單播系統的基礎上，開發了一種基于組播的直播系統，系統測試表明，新的系統能夠提供較好、較穩定的流媒體服務;文獻［3］在綜合考慮了節點的性能和位置重要性的基礎上，提出了一種改進的組播算法PPE，仿真結果表明，PPE能有效地降低延遲和控制開銷，在大規模節點環境中能有效改善組播樹的性能。文獻［4］基于前向式重構技術，采用自底向上的方法將本地選擇策略和全局選擇策略進行有機結合。仿真結果表明，該算法相對于傳統的方法在計算開銷和轉發質量等方面都有一定的進步。另外，還有文獻［5］針對礦區網絡的視頻傳輸問題，開發了一種基于實時流媒體服務的多源應用層組播系統，該系統能夠大大降低網絡的丟包率;文獻［6］設計和實現了一種異構的多媒體會議系統集成框架。但是，該文僅僅只是談到如何利用組播技術來設計集成框架，而對于整個系統的其他關鍵模塊并沒有闡述。總的來說，已有的組播方法有其可取之處，但是都無法自適應地應對不同網絡應用場景下的轉發需求，轉發時延、系統的吞吐量等方面都還有待改善，鑒于此，本文從組播樹的建立和動態維護兩方面出發，提出了一種改進的組播算法，并通過仿真驗證了本文方法的有效性。

2 組播樹的建立

建立過程如下，首先，轉發節點之間形成一個穩定的覆蓋網，然后根據會議主題動態的創建組播樹，用于傳輸會議的數據。圖1給出了組播樹建立的全過程。其中，New Node表示要加入群組的新成員節點，Server是服務器，實心的節點和粗線條表示當前組播樹。

圖1 組播樹建立過程

算法的基本過程如下

Step1，New Node訪問服務器Server(圖中用1表示)，Server返回群組成員地址信息(圖中用2表示)與連接信息。在選擇Server時，New node主要考慮負載均衡和網絡延時的情況，選擇最近的Server作為父節點，下面給出節點與Server的距離定義:任意一個New Node n與任意一個標號為k的Server的距離為

其中，LB*(k)為標號為k的服務器的負載均衡歸一化值:

其中，Degree(k)表示服務器與節點相連的最大分支數，即標號為k的服務器的度;Constraints(k)表示當前服務器的資源占用情況。RTT(k)為n節點與標號為k的服務器的鏈路延時歸一化值

其中，RTTn(k)表示n節點與標號為k的服務器的鏈路延時;max{RTTn}和min{RTTn}分別表示n節點到組播樹服務器延時的最大值和最小值;w1和w2表示權重，滿足0≤w1，w2≤1，且w1+w2=1。

Step2，New Node進行其每一個鏈接的可用帶寬和連接性能(圖中用3表示)的測量。在測量帶寬時，本文借助MPEG視頻數據流隨時間做周期性變化特性實現對可用帶寬A的測量;

Step3，New-Node綜合考慮了度數、延時和帶寬等因素，利用啟發式規則，通過比較從各個候選父節點中選擇綜合性能最佳的節點進行連接。限于篇幅，本文僅給出基于度數約束的組播樹構造算法部分偽碼，如下所示，其中，dmax(i)表示節點i的最大度約束，dnow(i)表示節點 i的當前連接數，node(i)表示節點 i，ddegree(i)表示節點i的度約束。

算法1:基于度數約束的ALMT構造算法

在算法1中，本文設計的度數計算方法如下:假設，某一節點當前的可用網絡帶寬為N Kbps，CPU占用率為C，可用內存大小為M MB，進程數為P個。本文設計新節點選擇其父節點的過程按照下式的綜合評價值排隊

(4)式能夠確保那些CPU占用率低、可用內存大、系統進程數少的節點將總是擁有最高的優先級成為父節點。

3 組播樹的動態維護

3.1 節點的故障檢測

由于節點的退出，會導致組播樹在分發數據過程中出現故障。因此故障檢測是十分重要的，下面主要針對節點異常退出情況進行了故障檢測。

為了檢測節點的異常退出情況，組播樹中的節點定期的向組內發送Heartbeat消息來宣告自身的存在，同時監聽其鄰節點的消息并更新其鄰節點列表的狀態。本文提出的故障檢測算法的主要步驟如下

Step1.在DS中創建檢測算法的后臺線程;

Step 2.每隔100秒，DS向所有終端發送一帶特定標識的數據包Datas;

Step 3.終端收到Datas后做出回應，向DS發送應答數據包Datar;

Step 4.DS接收到Datar后，記錄終端的IP，并保存在數組ArrayIP中;

Step 5.如果某IP不在當前ArrayIP中，調用覆蓋網重構算法，對該節點的退出進行組播網重構;

Step 6.向所有在線的終端泛洪新的組播網信息。

3.2 組播樹的重構

對于任意節點Cj，本文先給出如下的定義描述和參數說明

定義1節點的總度Dt(Cj)Cj節點能轉發給別的終端數量;

定義2節點的已用度Du(Cj)Cj節點已經連接的終端用戶數;

定義3節點的剩余度Dr(Cj)Cj節點還能連接的終端用戶數;

下面將介紹組播樹的重構過程

如圖2所示，節點 bi有n個孩，有m-1個兄弟節點。在節點bi失效以前，要為bi的孩子節點找到一個備用父節點。過程如下

首先，在bi的孩子節點沒有找到備用父節點前，設bi為unhelpful。找到之后，設 bi為 helpful。

然后，計算bi所有的孩子節點的剩余度和，如果大于n-1;則在bi和它的所有孩子節點之間形成一棵生成樹;如小于n-1，則在 bi和它的 Dr(c0)+… +Dr(cn-1)個孩子節點之間重構組播樹，剩余孩子節點將向bi的helpful兄弟節點發出申請。如還有子節點沒找到備用父節點，則繼續向祖先節點申請。

每個節點維護一個兄弟節點和祖先節點的信息列表。在節點離開后，選擇一個該節點的孩子來繼承該節點的地位。本文在楊氏方法［8］的基礎上，選擇RTT值最小的節點來繼承。限于篇幅，具體的節點繼承過程不再詳述。

圖2 基于度數約束的生成樹

依據上述分析，組播樹重構算法的主要步驟如下

Step1，葉子節點狀態設為helpful，其他的所有節點狀態設為unhelpful;

Step2，如果有節點的狀態為unhelpful，將啟動節點內部修復計劃;

Step3，如果所有孩子節點找到了備用父節點，則將自己的狀態改為helpful。否則，向父節點的兄弟中為helpful的節點發出請求;

Step4，在所有孩子節點都找備用父節點后，如果節點請求離開，則所有孩子節點從備用父節接收數據;如果失效離開，通過Heartbeat檢測失效后，孩子節點都將從備用父節點開始接收數據。

Step5，在某個節點離開或者檢測到失效后，該節點的父節點設置為unhelpful，所有的孩子節點將重新按Step1開始尋找新的備用父節點。

4 實驗結果與分析

本文采用NS2進行模擬實驗。將本文提出的算法和隨機組播樹算法進行了對比。首先，我們從吞吐量方面出發比較了本文算法和隨機組播樹算法生成的組播樹的性能:分別用這兩種算法構建組播節點數為40的組播樹，然后從根節點發送10 Mb數據，記錄下每個節點的吞吐量情況，如圖3所示。

我們一共做了120組測試，依據這些實驗數據，給出了如表1所示的統計結果。

算法名稱平均吞吐量相對隨機算法的提高隨機組播樹算法402.570%本文的算法583.6845%從圖3和表1可知，本文算法在提高吞吐量方面明顯優于傳統算法。這是因為本文的方法綜合考慮了節點的度數、延遲以及帶寬等因素，利用啟發式規則，通過比較從各個候選父節點中選擇綜合性能最佳的節點進行連接。而隨機組播樹算法由于沒有考慮度數的限制，且對于帶寬的估計不夠準確，無法避開那些服務能力較差的節點，因此，影響了組播樹的物理連接質量。

圖3 吞吐量比較

表1 平均吞吐量比較

最后，本文對組播樹維護算法進行了性能測試，并將其與響應式方法和Tetsuya方法和楊式方法［8，9］進行了比較。實驗場景為:終端主機數量從50到250，鏈路傳輸數據時間從20ms到120ms，主機度從2到12。從圖4和圖5可以看出，響應式方法修復時間較長，本文算法與Tetsuya方法和楊式方法的修復時間基本一致，但是本文方法的平均轉發延時是所有方法中最低的。仔細分析其原因可知，這主要是因為本文的方法在對組播樹進行維護時，對非正常情況下節點的失效進行了故障監測，能夠及時做出反應，由于本文的方法通過對節點狀態進行helpful和 unhelpful的區分，有利于為孩子節點快速地找到替代的父親節點，避免了數據的丟失，降低了數據的轉發延遲。

5 結束語

本文提出了一種改進的組播樹構建和維護算法。仿真實驗表明，本文的方法能夠顯著地提高數據轉發的效率，避免數據的丟失，降低延遲。我們的下一步工作主要包括:(1)進一步分析節點的度與數據轉發延遲和丟包的關系，提出更優的組播書構建算法;(2)研究基于啟發式方法來對節點失效情況進行提前預測，從而為數據轉發的路徑進行更優的選擇，提高轉發數據包的成功率。

［1］李偉，沈長寧.應用層組播協議研究［J］.計算機工程與應用，2004，24(4):156-159.

［2］程鵬，吳秋峰，戴瓊海.基于應用層組播的流媒體直播系統［J］.計算機工程，2007，33(21):210-212.

［3］曾彬，張大方，黎文偉，呂磊.基于節點性能估算的應用層組播算法［J］.計算機工程，2009，35(8):13-16.

［4］鄧正偉，李鋒.自底向上的應用層組播樹重構算法［J］.計算機工程，2011，37(2):105-107.

［5］程德強，錢建生.基于實時流媒體服務的多源應用層組播系統［J］.計算機工程，2008，34(10):224-225.

［6］李律松，李靜.多媒體會議系統集成框架的研究和實現［J］.計算機工程，2006，32(21):206-208.

［7］潘耘，余鎮危，王行剛等。Overlay組播路由的負載平衡問題［J］.電子與信息學報，2007，29(3):739-742.

［8］M.Yang，Z.Fei.A Proactive Approach to Reconstructing Overlay Multicast Trees［C］//in proceedings of INFOCOM，2004:2743-2753.

［9］Tetsuya Kusumoto，Yohei Kunichika and Jiro Katto.Proactive Route Maintenance and Overhead Reduction for Application Layer Multicast［C］//Proceedings of P2PMMS'05，Singapore，2005:278-287.