一種改進(jìn)的應(yīng)用層組播樹構(gòu)建和維護(hù)算法

劉浩杰 金鑫

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

0 引言

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

1 相關(guān)工作

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

2 組播樹的建立

建立過程如下，首先，轉(zhuǎn)發(fā)節(jié)點之間形成一個穩(wěn)定的覆蓋網(wǎng)，然后根據(jù)會議主題動態(tài)的創(chuàng)建組播樹，用于傳輸會議的數(shù)據(jù)。圖1給出了組播樹建立的全過程。其中，New Node表示要加入群組的新成員節(jié)點，Server是服務(wù)器，實心的節(jié)點和粗線條表示當(dāng)前組播樹。

圖1 組播樹建立過程

算法的基本過程如下

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

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

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

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

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

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

算法1:基于度數(shù)約束的ALMT構(gòu)造算法

在算法1中，本文設(shè)計的度數(shù)計算方法如下:假設(shè)，某一節(jié)點當(dāng)前的可用網(wǎng)絡(luò)帶寬為N Kbps，CPU占用率為C，可用內(nèi)存大小為M MB，進(jìn)程數(shù)為P個。本文設(shè)計新節(jié)點選擇其父節(jié)點的過程按照下式的綜合評價值排隊

(4)式能夠確保那些CPU占用率低、可用內(nèi)存大、系統(tǒng)進(jìn)程數(shù)少的節(jié)點將總是擁有最高的優(yōu)先級成為父節(jié)點。

3 組播樹的動態(tài)維護(hù)

3.1 節(jié)點的故障檢測

由于節(jié)點的退出，會導(dǎo)致組播樹在分發(fā)數(shù)據(jù)過程中出現(xiàn)故障。因此故障檢測是十分重要的，下面主要針對節(jié)點異常退出情況進(jìn)行了故障檢測。

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

Step1.在DS中創(chuàng)建檢測算法的后臺線程;

Step 2.每隔100秒，DS向所有終端發(fā)送一帶特定標(biāo)識的數(shù)據(jù)包Datas;

Step 3.終端收到Datas后做出回應(yīng)，向DS發(fā)送應(yīng)答數(shù)據(jù)包Datar;

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

Step 5.如果某IP不在當(dāng)前ArrayIP中，調(diào)用覆蓋網(wǎng)重構(gòu)算法，對該節(jié)點的退出進(jìn)行組播網(wǎng)重構(gòu);

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

3.2 組播樹的重構(gòu)

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

定義1節(jié)點的總度Dt(Cj)Cj節(jié)點能轉(zhuǎn)發(fā)給別的終端數(shù)量;

定義2節(jié)點的已用度Du(Cj)Cj節(jié)點已經(jīng)連接的終端用戶數(shù);

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

下面將介紹組播樹的重構(gòu)過程

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

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

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

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

圖2 基于度數(shù)約束的生成樹

依據(jù)上述分析，組播樹重構(gòu)算法的主要步驟如下

Step1，葉子節(jié)點狀態(tài)設(shè)為helpful，其他的所有節(jié)點狀態(tài)設(shè)為unhelpful;

Step2，如果有節(jié)點的狀態(tài)為unhelpful，將啟動節(jié)點內(nèi)部修復(fù)計劃;

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

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

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

4 實驗結(jié)果與分析

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

我們一共做了120組測試，依據(jù)這些實驗數(shù)據(jù)，給出了如表1所示的統(tǒng)計結(jié)果。

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

圖3 吞吐量比較

表1 平均吞吐量比較

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

5 結(jié)束語

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

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

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

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

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

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

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

［7］潘耘，余鎮(zhèn)危，王行剛等。Overlay組播路由的負(fù)載平衡問題［J］.電子與信息學(xué)報，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.