隨冬梅

(商丘師范學(xué)院軟件學(xué)院,河南商丘 476000)

基于N ICE協(xié)議的應(yīng)用層組播穩(wěn)定性研究

隨冬梅

(商丘師范學(xué)院軟件學(xué)院,河南商丘 476000)

應(yīng)用層組播樹是由終端用戶組成,其穩(wěn)定性不能得到保證.本文面向P2P視頻直播應(yīng)用,基于N ICE協(xié)議,通過分析終端用戶的行為和能力,提出一種新的簇首選擇算法來提高組播樹的穩(wěn)定性,另外,在改進(jìn)的N ICE協(xié)議上建立冗余虛擬鏈路來重構(gòu)組播樹,以保證組播的穩(wěn)定性.

應(yīng)用層組播;冗余虛擬鏈路;視頻直播＊

0 概述

組播是一種高效的多點(diǎn)通信方式,IP組播效率高,但需專門的組播路由器,代價大,以至于許多ISPS不愿意提供對IP組播的支持,限制了IP組播的實(shí)際部署,因此,研究人員提出了應(yīng)用層組播的概念,并成為研究熱點(diǎn).應(yīng)用層組播利用現(xiàn)有的網(wǎng)絡(luò)作為底層的基礎(chǔ)設(shè)施為終端用戶提供組播服務(wù),終端用戶在物理網(wǎng)絡(luò)上自主組織成一個虛擬的覆蓋網(wǎng)絡(luò),組播數(shù)據(jù)沿著組播樹進(jìn)行分發(fā).這種易部署性是應(yīng)用層組播較之IP組播最大的優(yōu)點(diǎn).但是,因?yàn)闃?gòu)成組播樹的中間節(jié)點(diǎn)并不是專門的網(wǎng)絡(luò)路由器,而是自主的終端主機(jī),所以應(yīng)用層組播樹會因?yàn)閱蝹€終端主機(jī)的退出和失效而影響用戶接受組播數(shù)據(jù)的連續(xù)性,尤其是在P2P視頻直播應(yīng)用中.在P2P視頻直播中,當(dāng)用戶的數(shù)量巨大時,每時每刻都有很多節(jié)點(diǎn)的加入與離開,致使數(shù)據(jù)傳輸暫時中斷,影響該節(jié)點(diǎn)的子孫用戶的視頻觀看.因此,提高應(yīng)用層組播的穩(wěn)定性是提高應(yīng)用層組播服務(wù)質(zhì)量的必然要求.

本文面向可擴(kuò)展流媒體視頻直播應(yīng)用,改進(jìn)N ICE協(xié)議[1]的簇首選擇算法和數(shù)據(jù)拓?fù)浣Y(jié)構(gòu),以達(dá)到在組播樹創(chuàng)建時就達(dá)到較高的穩(wěn)定性.并在組播樹上部署冗余虛擬鏈路來解決節(jié)點(diǎn)失效后的組播樹的重構(gòu)問題,縮短節(jié)點(diǎn)失效后組播樹恢復(fù)時間.

1 NICE協(xié)議概述

1.1 NICE協(xié)議的層結(jié)構(gòu)

如圖1所示,所有的節(jié)點(diǎn)都要加入第0層,每層的節(jié)點(diǎn)被分在一個個簇(c luster)中,每個簇的規(guī)模在K～3K-1之間,其中,K為常數(shù).每個簇都有一個簇首,簇首是這個簇的圖論中心.

在N ICE協(xié)議中,組播數(shù)據(jù)分發(fā)時,如果該節(jié)點(diǎn)僅是最底層的一個成員,那么組播數(shù)據(jù)首先會到達(dá)該群的所有節(jié)點(diǎn),然后由該群的簇首通知其它群的簇首,然后逐步擴(kuò)展到所有群的所有節(jié)點(diǎn).在這個組播樹中,簇首的性能對整個網(wǎng)絡(luò)的傳輸性能影響較大.N ICE協(xié)議沒有考慮轉(zhuǎn)發(fā)節(jié)點(diǎn)的能力差異,它的簇首僅僅是根據(jù)圖論的中心論選出來的節(jié)點(diǎn),這可能會造成能力弱的節(jié)點(diǎn)處于轉(zhuǎn)發(fā)樹的高層,使節(jié)點(diǎn)負(fù)載較高,致使系統(tǒng)穩(wěn)定性大為降低.因此,依據(jù)面向流媒體視頻直播的應(yīng)用背景,通過分析P2P網(wǎng)絡(luò)中終端節(jié)點(diǎn)的行為,并考慮終端節(jié)點(diǎn)的服務(wù)能力,對N ICE協(xié)議作了相應(yīng)的改進(jìn).

1.2 組播節(jié)點(diǎn)的加入與失效

1.節(jié)點(diǎn)的加入:當(dāng)一個成員要加入組播組的時候必須映射到L0層的某個簇上.首先,新節(jié)點(diǎn)向RP提出加入請求,RP返回高層節(jié)點(diǎn)的信息(邏輯和物理地址),請求者與獲得的所有節(jié)點(diǎn)進(jìn)行聯(lián)系以確定距離自己最近的節(jié)點(diǎn),并以此類推,順序查詢至L0層某簇.如果這個簇未滿,則加入,否則簇分裂.

圖1 NICE協(xié)議的層結(jié)構(gòu)

2.節(jié)點(diǎn)失效:簇中的其他主機(jī)接收不到離開節(jié)點(diǎn)的刷新信息,經(jīng)過一定的時間就認(rèn)為該成員失效了.如果離開的主機(jī)是這個簇中的領(lǐng)導(dǎo)成員,那么就在剩下的成員中選擇一個作為新的領(lǐng)導(dǎo)成員.

2 改進(jìn)的NICE協(xié)議

2.1 一種新的簇首選擇算法

文獻(xiàn)[2]驗(yàn)證了文獻(xiàn)[3]中得到的在P2P視頻直播中用戶在線時間符合對數(shù)正態(tài)分布的結(jié)論,并指出用戶平均剩余在線時間會隨著用戶已經(jīng)在線時間的增大而增大.本文對N ICE的改進(jìn)主要是根據(jù)節(jié)點(diǎn)的能力(節(jié)點(diǎn)的服務(wù)帶寬)和節(jié)點(diǎn)在線時間長短,提出一種新的簇首選擇算法.根據(jù)文獻(xiàn)[2]的分析,節(jié)點(diǎn)已在線的時間越長,其繼續(xù)停留的平均時間越大,退出概率越小.我們定義p rob(i,t)為節(jié)點(diǎn)i已在線時間為t時離開組播樹的概率,則t↑?E(p rob(i,t))↓.in tr(i)為節(jié)點(diǎn)i離開時所影響的所有子孫節(jié)點(diǎn)的個數(shù),即節(jié)點(diǎn)i的失效恢復(fù)代價.顯然整個組播樹T的期望失效恢復(fù)代價可以表示公式:

其中in tr(i)與j＊O(k)有關(guān).j為節(jié)點(diǎn)i所在最高層.k為節(jié)點(diǎn)i所屬簇的大小.

因?yàn)镋(p rob(i,t))的大小僅僅與節(jié)點(diǎn)i的已在線時間有關(guān),我們不能改變其大小,所以降低失效恢復(fù)代價可行的方法是盡量減少在線時間短的節(jié)點(diǎn)處于組播樹的高層.因此,在選擇簇首時,要把能力不足和退出組播組可能性大的節(jié)點(diǎn)排除,在能力強(qiáng)和在組播組中繼續(xù)停留的可能性大的節(jié)點(diǎn)中選擇簇首.

設(shè)Cap(i)為節(jié)點(diǎn)i總服務(wù)能力.rem(i,j)為節(jié)點(diǎn)i在j層時的剩余能力.設(shè)j層某簇節(jié)點(diǎn)的集合為SPHj,節(jié)點(diǎn)個數(shù)為Cn個.

具體算法描述如下:

1)首先對SPHj中所有節(jié)點(diǎn)按照節(jié)點(diǎn)的可用帶寬rem(i,j)進(jìn)行降序排序,得到集合SPHj1.這樣具有較大帶寬服務(wù)能力的節(jié)點(diǎn)占據(jù)SPHj1中的靠前位置.

2)取SPHj1中前αCn個節(jié)點(diǎn)按照節(jié)點(diǎn)的已在線時間t進(jìn)行降序排序,得到SPHj2.這里參數(shù)α可根據(jù)應(yīng)用需求選擇(α≤1).我們用αCn調(diào)節(jié)在帶寬服務(wù)能力強(qiáng)的節(jié)點(diǎn)中選擇穩(wěn)定度大的節(jié)點(diǎn)的個數(shù).

3)選取SPHj2中排名最前的節(jié)點(diǎn)為該簇的簇首.

2.2 冗余虛擬鏈路

RVL(Redundant Virtual Link)算法[4]是一種支持應(yīng)用層組播樹快速重構(gòu)的算法,該算法在組播樹結(jié)構(gòu)的基礎(chǔ)上增加冗余的虛擬連接作為備用連接.當(dāng)節(jié)點(diǎn)離開后,受影響節(jié)點(diǎn)迅速利用備用連接恢復(fù)組播數(shù)據(jù)接收.RVL算法將應(yīng)用層組播樹節(jié)點(diǎn)區(qū)分為葉節(jié)點(diǎn)和中轉(zhuǎn)節(jié)點(diǎn),備用連接增加策略有多種,有的策略是在任意節(jié)點(diǎn)間增加任意數(shù)目的備用連接;有的策略是中轉(zhuǎn)節(jié)點(diǎn)可以與任意數(shù)目的備用連接相連,而葉節(jié)點(diǎn)只能與一條備用連接相連等.RVL算法縮短了節(jié)點(diǎn)離開后組播樹的恢復(fù)時間.這類算法雖然增加了維護(hù)備用連接的控制開銷,但是在節(jié)點(diǎn)離開較為頻繁的組播環(huán)境中,提高應(yīng)用層組播穩(wěn)定性的效果比較明顯.

在改進(jìn)簇首選擇算法后,由于簇首不再是簇拓?fù)浣Y(jié)構(gòu)的中心節(jié)點(diǎn),它到其他所有節(jié)點(diǎn)的距離之和也不一定是這個簇中最小的.而在視頻直播應(yīng)用中,對網(wǎng)絡(luò)延遲有嚴(yán)格的限制.從數(shù)據(jù)源到接收者的端到端延時應(yīng)保證在流媒體傳輸?shù)臅r延范圍之內(nèi),保證組播參與者盡快地收到組播包,因此在構(gòu)建組播樹時應(yīng)考慮減少時延.原N ICE協(xié)議使用的是基本路徑樹,這種數(shù)據(jù)傳輸樹不是一棵基于約束的優(yōu)化樹,為了減小傳輸時延,本文采用最小延遲樹作為數(shù)據(jù)拓?fù)?因?yàn)樵诿總€簇中,簇首通過信息交換了解簇中所有節(jié)點(diǎn)之間的延遲信息,由簇首執(zhí)行D ijk stra算法在簇中形成最小延遲樹.

本文在每個簇的最小延遲樹中相隔兩代的節(jié)點(diǎn)間以概率P增加一條冗余虛擬鏈路,即在祖父節(jié)點(diǎn)和孫子之間增加一條鏈路.概率P的大小決定增加鏈路的數(shù)量.P越大,需要增加的冗余虛擬鏈路越多,這增大了節(jié)點(diǎn)的處理負(fù)擔(dān),P越小,則組播樹的穩(wěn)定性也會隨之下降,因此,應(yīng)根據(jù)情況選擇一個較優(yōu)的P值.

3 仿真實(shí)驗(yàn)

為了驗(yàn)證改進(jìn)的協(xié)議的性能,采用N S2網(wǎng)絡(luò)仿真工具對N ICE協(xié)議在改進(jìn)前后的穩(wěn)定性進(jìn)行對比分析.實(shí)驗(yàn)中節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)溆蒅T-ITM生成,N ICE協(xié)議參數(shù)K=5,節(jié)點(diǎn)的在線時間的概率密度分布采用參數(shù)為m=4.4n=1.6的對數(shù)正態(tài)分布.在N ICE原始組播樹的基礎(chǔ)上,使用前面的策略為組播樹增添冗余虛擬鏈路,并設(shè)概率P=0.5.

失效恢復(fù)代價也即當(dāng)中間節(jié)點(diǎn)退出或失效后所影響的所有子孫節(jié)點(diǎn)個數(shù).在組播樹中,樹的失效恢復(fù)代價越小,組播樹越穩(wěn)定,我們用累積失效恢復(fù)代價來表示組播樹的穩(wěn)定性.

圖2 N ICE改進(jìn)前后的累計(jì)失效恢復(fù)代價的比較

圖3 節(jié)點(diǎn)失效情況下組播樹的平均恢復(fù)時間

如圖2所示,當(dāng)節(jié)點(diǎn)失效時,改進(jìn)后的N ICE協(xié)議的穩(wěn)定性效果非常明顯.這是因?yàn)楦倪M(jìn)后N ICE在選擇簇首時,使節(jié)點(diǎn)能力弱的和離開組播樹可能性大的節(jié)點(diǎn)為非簇首,節(jié)點(diǎn)能力強(qiáng)的和繼續(xù)留在組播樹中可能性大的節(jié)點(diǎn)為簇首,從而降低了節(jié)點(diǎn)的失效恢復(fù)代價.

從圖3可以看出,改進(jìn)后的組播樹的平均恢復(fù)時間遠(yuǎn)遠(yuǎn)小于原協(xié)議的組播樹的平均恢復(fù)時間.這是因?yàn)橐环矫娓倪M(jìn)后的組播樹降低了節(jié)點(diǎn)的失效率,另一方面,以概率P增加的冗余虛擬鏈路也大大減少了組播樹的恢復(fù)時間.

4 結(jié)語

P2P系統(tǒng)的節(jié)點(diǎn)行為總是不可控制的,每時每刻都有很多節(jié)點(diǎn)的加入與離開,嚴(yán)重影響應(yīng)用層組播系統(tǒng)的穩(wěn)定性.本文針對應(yīng)用層組播生成樹的穩(wěn)定性進(jìn)行分析,基于p2p的節(jié)點(diǎn)特性提出了一種改進(jìn)的N ICE簇首選擇算法.并采用在生成樹中增加冗余虛擬鏈路的方法以增加組播樹的穩(wěn)定性,縮短節(jié)點(diǎn)失效后組播樹的恢復(fù)時間.仿真實(shí)驗(yàn)結(jié)果顯示,與N ICE協(xié)議相比,改進(jìn)后的N ICE協(xié)議具有良好的穩(wěn)定效果.

[1]S.Banerjee,B.Bhattacharjee,C.Kommareddy,Scalable application layermulticast[C].In Proceedings of 2002 ACM Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications(SIGCOMM’02), 2002:205-217.

[2]羅建光,趙黎,楊士強(qiáng).基于用戶行為分析的應(yīng)用層組播樹生成算法[J].計(jì)算機(jī)研究與發(fā)展,2006,43(9): 1557-1563.

[3]Veloso E,AlmeidaV,MeiraW.A Hierarchical Characterization of a Live Streaming Media Work load[C]//Proc.of ACM SIGCOMM Workshop on Internet Measurement.New York,USA:[s.n.],2002.

[3]Roca V.A Host-based Multicast(HBM)So lution for Group Communications[C]//Proc.of IEEE Int’1 Conf.on Networking.Colmar,France:[s.n.],2001.

[4]A ynan El-Sayed.Application Level Multicast Transmission Techniques Over the Internet[D].paris:University of Paris,2004.

Abstract:The application level multicast tree is composed of the end hosts which can no t ensure the stability of them ulticast tree.Based on live streaming,this paper proposes a new cluster-leader selected algorithm in NICE protoco l through analyzing of end hosts’behavior and capabilities,and adds the Redundant Virtual Link to reconstruction of the application level multicast tree,in order to imp rove the stability of NICE protoco l.

Keywords:Application Level Multicast;Redundant Virtual L ink;live streaming

Research on Stability of Application Layer Multicast Based on NICE Protocol

SUI Dong-mei
(Soft Academy,Shangqiu Teachers College,Shangqiu 476000,China)

TP393

A

1004-7077(2010)02-0056-04

2010-01-25

隨冬梅(1978-),女,河南省商丘人,碩士研究生,主要研究方向?yàn)榫W(wǎng)絡(luò)通信。

[責(zé)任編輯:袁 偉]