劉浩杰 金鑫

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

0 引言

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

1 相關(guān)工作

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

2 組播樹的建立

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

圖1 組播樹建立過(guò)程

算法的基本過(guò)程如下

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

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

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

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

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

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

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

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

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

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

3.1 節(jié)點(diǎn)的故障檢測(cè)

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

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

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

Step 2.每隔100秒，DS向所有終端發(fā)送一帶特定標(biāo)識(shí)的數(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)算法，對(duì)該節(jié)點(diǎn)的退出進(jìn)行組播網(wǎng)重構(gòu);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

圖3 吞吐量比較

表1 平均吞吐量比較

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

5 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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