基于不定叉樹的應(yīng)用層組播協(xié)議

基于不定叉樹的應(yīng)用層組播協(xié)議

摘要本文提出了一個(gè)適合小規(guī)模、低時(shí)延，基于不定叉樹的應(yīng)用層組播協(xié)議，重點(diǎn)講述了協(xié)議的設(shè)計(jì)思想、節(jié)點(diǎn)故障修補(bǔ)算法和性能優(yōu)化方法。協(xié)議已被成功應(yīng)用到一個(gè)視頻會(huì)議系統(tǒng)中，結(jié)果表明，這樣的一個(gè)協(xié)議能很好的適應(yīng)目前Internet上小規(guī)模多媒體應(yīng)用層組播系統(tǒng)。關(guān)鍵詞應(yīng)用層組播；不定叉樹；源指定樹；路由樹調(diào)整

1概述自應(yīng)用層組播的概念提出以來，已有很多各具特點(diǎn)的解決方案被提出。各個(gè)不同的應(yīng)用層組播系統(tǒng)具有不同的設(shè)計(jì)目標(biāo)及系統(tǒng)結(jié)構(gòu)。如，ESM(End-SystemMulticast)[1]和ALMI適合時(shí)延要求不高的小規(guī)模多對(duì)多通信，而Scattercast和Overcasts則支持大規(guī)模的數(shù)據(jù)遞送系統(tǒng)。在系統(tǒng)結(jié)構(gòu)方面，根據(jù)建立應(yīng)用層組播拓?fù)浣Y(jié)構(gòu)時(shí)采用的方案，將這些系統(tǒng)分為兩種：網(wǎng)優(yōu)先(MeshFirst)和樹優(yōu)先(TreeFirst)，網(wǎng)優(yōu)先的系統(tǒng)會(huì)首先為覆蓋節(jié)點(diǎn)建立一個(gè)網(wǎng)狀的拓?fù)浣Y(jié)構(gòu)，然后按照某種路由協(xié)議來生成數(shù)據(jù)路由樹，如ESM的Narada協(xié)議，會(huì)先構(gòu)建一個(gè)網(wǎng)，然后通過修改后的DVMRP協(xié)議完成路由樹的生成；而樹優(yōu)先的系統(tǒng)則是直接建立數(shù)據(jù)路由樹，ALMI、Overcast、HostMulticastis均屬于這種系統(tǒng)。一般來說，網(wǎng)優(yōu)先的系統(tǒng)穩(wěn)定性更好，不會(huì)形成回路，樹優(yōu)先的系統(tǒng)則在效率上占優(yōu)勢。在多源的應(yīng)用層組播方案中，根據(jù)數(shù)據(jù)路由樹的使用和維持，可以分為SharedTree和Source-specificTree兩種。SharedTree，就是所有的源使用同一棵樹；Source-specificTree，就是每個(gè)源維持一棵樹，前者不能保證每個(gè)源都能獲得較好的傳輸延遲。本協(xié)議根據(jù)視頻會(huì)議系統(tǒng)的應(yīng)用特點(diǎn)，采用效率較高的樹優(yōu)先的拓?fù)浣Y(jié)構(gòu)，使用Source-specificTree數(shù)據(jù)路由樹策略。樹的生成、維持由根(源)負(fù)責(zé)，集中點(diǎn)(RP)不參與，這點(diǎn)類似HostMulticast的做法，HostMulticast是分布的方式，每個(gè)組的數(shù)據(jù)路由樹都有一個(gè)根節(jié)點(diǎn)，每個(gè)新的組成員加入時(shí)，都要從該根節(jié)點(diǎn)開始依次協(xié)商，直到找到一個(gè)距離最近的節(jié)點(diǎn)為止。

2基于不定叉樹的應(yīng)用層組播協(xié)議

協(xié)議設(shè)計(jì)思想我們的思路是，建立一個(gè)全分布的，支持多組、多源，低時(shí)延的，基于不定叉源指定樹(Source-specificTree)的Tree-First應(yīng)用層組播協(xié)議平臺(tái)。由于目前Internet終端多數(shù)是以xDSL方式接入的，考慮到這些終端具有的極限帶寬是上傳512kbps(部分是1Mbps)，下載5Mbps(其余接入方式的終端一般具有更高的帶寬)，假定每個(gè)源每秒產(chǎn)生的實(shí)時(shí)數(shù)據(jù)流量為150kbps(如視頻會(huì)議)，按照90%極限上傳帶寬的可利用率，一個(gè)節(jié)點(diǎn)可以為3個(gè)節(jié)點(diǎn)實(shí)現(xiàn)分發(fā)任務(wù)；再假定組的規(guī)?？刂圃?00個(gè)節(jié)點(diǎn)內(nèi)，如果按照三叉樹的組織結(jié)構(gòu)，這樣的樹將不超過4層，經(jīng)過4個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā)，其時(shí)延基本可以控制在5秒內(nèi)。基于以上的假設(shè)，我們將在組應(yīng)用開始前建立n棵Source-specificTree，n等于組的節(jié)點(diǎn)數(shù)，每個(gè)節(jié)點(diǎn)負(fù)責(zé)生成一棵以它為根的滿三叉樹。我們又知道，有的節(jié)點(diǎn)的上傳能力可能不到3個(gè)，有的節(jié)點(diǎn)則可能超過3個(gè)，而且這種能力可能是變動(dòng)的。由此，這些樹必須根據(jù)網(wǎng)絡(luò)的實(shí)際狀態(tài)進(jìn)行調(diào)整，節(jié)點(diǎn)的分發(fā)孩子個(gè)數(shù)視其能力變動(dòng)而定，分發(fā)能力的判斷，則通過孩子節(jié)點(diǎn)反饋RTCP信息包來計(jì)算丟包率。也就是說，滿三叉樹在應(yīng)用預(yù)運(yùn)行或運(yùn)行后成為動(dòng)態(tài)調(diào)整的不定叉樹。

節(jié)點(diǎn)加入節(jié)點(diǎn)必須清楚自己屬于哪個(gè)組，然后加入到合適的組中。RP(集中點(diǎn))為節(jié)點(diǎn)提供加入服務(wù)。任一個(gè)節(jié)點(diǎn)加入時(shí)，必須向RP報(bào)到，RP將新節(jié)點(diǎn)加入到組的節(jié)點(diǎn)列表中，然后將已加入的節(jié)點(diǎn)列表發(fā)給新節(jié)點(diǎn)，同時(shí)，向所有節(jié)點(diǎn)通告單個(gè)節(jié)點(diǎn)加入消息。

滿三叉樹的生成“距離”與“距離”計(jì)算節(jié)點(diǎn)一旦成功加入，馬上與列表中的同組節(jié)點(diǎn)通信，估算節(jié)點(diǎn)之間的“距離”。所謂的“距離”，指的是節(jié)點(diǎn)間的傳輸延遲和帶寬加權(quán)后的值，我們采取簡單做法，就是測試1KUDP包來回所需的時(shí)間。我們采取如下算法計(jì)算NodeA和NodeB節(jié)點(diǎn)間的“距離”：TimeAS=CurrentTimeofNodeANodeASend1KbytestoNodeBbyUDPwithTimeASNodeBRecvivepacketfromNodeATimeBR=TimewhenNodeBRecvivesthepacketTimeBS=CurrentTimeofNodeBNodeBSend1KbytestoAbyUDPwithTimeAS,TimeBRandTimeBSNodeARecvivepacketfromNodeBTimeAR=TimewhenNodeARecvivesthepacketDistanceAB=TimeAR-TimeAS-(TimeBS-TimeBR)樹生成開始時(shí)，每個(gè)源生成一棵不超過4層(源，即根，為0層)的滿三叉數(shù)據(jù)路由樹，樹的生成依據(jù)這樣的原則，在樹中，離源較近的節(jié)點(diǎn)與源有更近的“距離”，而第2層的節(jié)點(diǎn)即與其第1層的父親節(jié)點(diǎn)有更近的“距離”，依此類推。首先，根選擇3個(gè)最合適的節(jié)點(diǎn)作為它的第一層子節(jié)點(diǎn)，然后，根分別通知這3個(gè)子節(jié)點(diǎn)，去尋找它們合適的孩子節(jié)點(diǎn)，過程不斷重復(fù)，直到所有的節(jié)點(diǎn)都加入到樹中。樹的生成是由覆蓋網(wǎng)中的所有節(jié)點(diǎn)協(xié)同完成的，因此其生成算法是分布的，算法OnReceiveCreateTree(void*packet){//根收到建樹命令,每個(gè)節(jié)點(diǎn)都需要生成一棵以其為根的樹按”距離”大小選擇3個(gè)孩子節(jié)點(diǎn);向選擇好的節(jié)點(diǎn)發(fā)送邀請(qǐng)其成為我的孩子節(jié)點(diǎn)的請(qǐng)求包(以’我’為根的樹);}OnReceiveInviteTobeChildReq(void*packet){//收到i邀請(qǐng)為其孩子的請(qǐng)求(j為根的樹)if(我還沒加入到以j為根的樹)發(fā)送接受邀請(qǐng)的回應(yīng)包;else發(fā)送拒絕邀請(qǐng)的回應(yīng)包;}OnReceiveToBeChildReply(void*packet){//收到節(jié)點(diǎn)i對(duì)我邀請(qǐng)的回應(yīng)(j為根的樹)if(i接受我的邀請(qǐng)){將i置為以j為根的樹中的’我’的孩子;將i加入到本地以j為根的樹已入樹節(jié)點(diǎn)列表;if(我是j)修改樹結(jié)構(gòu);//根維持整棵樹的結(jié)構(gòu)描述,樹生成后,分發(fā)給所有孩子}else{將i加入到本地在建以j為根的樹中拒絕我的節(jié)點(diǎn)列表;if(重新選擇一個(gè)節(jié)點(diǎn)成功)向被選擇的節(jié)點(diǎn)發(fā)送邀請(qǐng)其成為我的孩子節(jié)點(diǎn)的請(qǐng)求包(以j為根的樹);}if((孩子數(shù)==3)||(已入樹節(jié)點(diǎn)數(shù)+拒絕我的節(jié)點(diǎn)數(shù)==組節(jié)點(diǎn)數(shù))){//以j為根的樹if((我是j){將孩子節(jié)點(diǎn)列表打包;向被選中的孩子節(jié)點(diǎn)發(fā)送選擇孩子的命令;}else將孩子節(jié)點(diǎn)列表打包,發(fā)送給根;}}OnReceiveSelectChildrenOrder(void*packet){//收到根的選擇孩子節(jié)點(diǎn)的命令將包中已入樹的節(jié)點(diǎn)列表復(fù)制到本地;for(inti=0;i3;i++){if(選擇一個(gè)節(jié)點(diǎn)成功)向其發(fā)送邀請(qǐng)其成為孩子的請(qǐng)求;elsebreak;}}樹生成的算法是由分布在網(wǎng)絡(luò)上的多個(gè)節(jié)點(diǎn)機(jī)共同執(zhí)行的，為避免多個(gè)節(jié)點(diǎn)同時(shí)選擇一個(gè)節(jié)點(diǎn)為其孩子，因此，我們采用了應(yīng)答制。

性能優(yōu)化--不定叉樹的調(diào)整前面講到，在生成樹時(shí)，并沒有過多考慮樹的上傳能力，只是基于經(jīng)驗(yàn)及網(wǎng)絡(luò)的一般現(xiàn)狀，假設(shè)每節(jié)點(diǎn)有能力完成對(duì)3個(gè)節(jié)點(diǎn)的視音頻數(shù)據(jù)轉(zhuǎn)發(fā)。但，實(shí)際情況可能是，有的節(jié)點(diǎn)的分發(fā)能力超過3，有的節(jié)點(diǎn)則不足3。這樣，在應(yīng)用預(yù)運(yùn)行后，必須盡快對(duì)樹進(jìn)行調(diào)整。

我們使用UDP協(xié)議進(jìn)行應(yīng)用數(shù)據(jù)的傳輸，父親在向孩子節(jié)點(diǎn)發(fā)送應(yīng)用數(shù)據(jù)包時(shí)，統(tǒng)計(jì)單位時(shí)間已向孩子節(jié)點(diǎn)發(fā)送了多少數(shù)據(jù)包，每隔3秒鐘，孩子節(jié)點(diǎn)向父親發(fā)送一個(gè)RTCP包，告訴父親，最近3秒，已接收其發(fā)送的數(shù)據(jù)包數(shù)量，父親節(jié)點(diǎn)據(jù)此計(jì)算單鏈路的丟包率，并根據(jù)所有鏈路的丟包率，結(jié)合幀率，估算其帶寬，然后通告帶寬。為將問題簡單化，并基于Internet現(xiàn)狀(xDSL節(jié)點(diǎn)是上傳能力不足，非下載能力不足)，我們規(guī)定，當(dāng)一定時(shí)間內(nèi)，丟包率超過一定程度時(shí)，總假定是父親節(jié)點(diǎn)上傳能力不足。當(dāng)父親節(jié)點(diǎn)認(rèn)為其上傳能力不足時(shí)，希望移交孩子節(jié)點(diǎn)，父親節(jié)點(diǎn)會(huì)選擇帶寬較高的節(jié)點(diǎn)發(fā)送移交請(qǐng)求。收到移交請(qǐng)求的節(jié)點(diǎn)檢查其自身上傳能力，回應(yīng)接受請(qǐng)求或不接受請(qǐng)求，發(fā)送移交請(qǐng)求的節(jié)點(diǎn)會(huì)一直嘗試，直到有節(jié)點(diǎn)同意移交，此外，上傳能力不足的節(jié)點(diǎn)可以啟用選幀，降低對(duì)帶寬的需求，這屬于應(yīng)用層QoS的任務(wù)，不在這里詳述。目前多數(shù)的ALM協(xié)議，對(duì)底層網(wǎng)絡(luò)變動(dòng)的適應(yīng)普遍采取整體變動(dòng)的方法，這樣的代價(jià)相當(dāng)大，如NARADA，節(jié)點(diǎn)狀態(tài)的變化將導(dǎo)致網(wǎng)Mesh的重構(gòu)，從而導(dǎo)致所有source-specificTree的重構(gòu)，這個(gè)過程需要較長的收斂時(shí)間。我們采取局部變化的對(duì)策以適應(yīng)overlayNetwork的變化。圖1節(jié)點(diǎn)轉(zhuǎn)移實(shí)現(xiàn)優(yōu)化

樹的修補(bǔ)有邊相連的節(jié)點(diǎn)，互相為鄰居。節(jié)點(diǎn)每3秒鐘向鄰居發(fā)送“心跳”信息?！靶奶毙畔⒖梢院唵蔚绞且粋€(gè)不斷增長的序列號(hào)。當(dāng)節(jié)點(diǎn)在30秒鐘收不到鄰居的“心跳”信息后，節(jié)點(diǎn)認(rèn)為鄰居已經(jīng)出現(xiàn)故障。故障處理：1).為避免多個(gè)節(jié)點(diǎn)同時(shí)嘗試修補(bǔ)樹，我們規(guī)定，只允許上層節(jié)點(diǎn)對(duì)下層節(jié)點(diǎn)進(jìn)行修補(bǔ)。如果根節(jié)點(diǎn)故障，樹的修補(bǔ)失去意義。2).后備選擇從故障節(jié)點(diǎn)的最左邊的子孫節(jié)點(diǎn)逐級(jí)往上提升，最左的節(jié)點(diǎn)不存在，則往右選擇。3).葉子節(jié)點(diǎn)故障將不修補(bǔ)。4).樹修補(bǔ)算法如圖2:i發(fā)現(xiàn)其兒子節(jié)點(diǎn)j故障后,執(zhí)行如下算法:1.向組內(nèi)所有節(jié)點(diǎn)通告j的故障2.j是葉子節(jié)點(diǎn)嗎?是，算法結(jié)束否，轉(zhuǎn)33.j有合適的孩子嗎？有，轉(zhuǎn)4沒有，算法結(jié)束4.選擇合適的孩子，向其發(fā)送接替j的通知5.T:=j圖2樹的修補(bǔ)任何節(jié)點(diǎn)k收到l發(fā)送給自己，要求自己接替節(jié)點(diǎn)j的通知，執(zhí)行如下算法：1.k是否葉子是，向l發(fā)送j?k、k?0的通知否，選擇合適的兒子，向其發(fā)送接替k的通知，T:=j,T1:=l任何節(jié)點(diǎn)k收到確認(rèn)接替的通知，執(zhí)行如下算法：1.接替串的第一個(gè)節(jié)點(diǎn)是自己嗎？是，接替串:=T?k+接替串，向T1發(fā)送接替串否，根據(jù)接替串替換樹，將新樹向所有節(jié)點(diǎn)發(fā)送

3性能測試

4小結(jié)及下一步工作本協(xié)議適合小規(guī)模、時(shí)延要求高的應(yīng)用層組播系統(tǒng)，我們?cè)趨f(xié)議的基礎(chǔ)上開發(fā)了一個(gè)視頻會(huì)議系統(tǒng)，經(jīng)試驗(yàn)，在網(wǎng)絡(luò)狀態(tài)變動(dòng)不是太頻繁的前提下，系統(tǒng)能很好工作。協(xié)議對(duì)很多復(fù)雜問題做了簡化，這些簡化對(duì)協(xié)議的實(shí)現(xiàn)帶來很大的便利，但同時(shí)也使得協(xié)議的適應(yīng)能力存在著一定的問題，我們將在樹的優(yōu)化、修補(bǔ)上進(jìn)行改造，以使得協(xié)議具有更廣闊的適應(yīng)能力。

參考文獻(xiàn)1ChuY,RaoS,ZhangH.ACaseforEndSystemMulticast.ACMSIGMETRICS,20002PendarakisD.ALMI:AnApplicationLevelMulti