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

1、基于不定叉樹的應(yīng)用層組播協(xié)議摘要本文提出了一個合適小規(guī)模、低時(shí)延，基于不定叉樹的應(yīng)用層組播協(xié)議，重點(diǎn)講述了協(xié)議的設(shè)計(jì)思想、節(jié)點(diǎn)故障修補(bǔ)算法和性能優(yōu)化方法。協(xié)議已被成功應(yīng)用到一個視頻會議系統(tǒng)中，結(jié)果說明，這樣的一個協(xié)議能很好的適應(yīng)目前Internet上小規(guī)模多媒體應(yīng)用層組播系統(tǒng)。關(guān)鍵詞應(yīng)用層組播；不定叉樹；源指定樹；路由樹調(diào)整自應(yīng)用層組播的概念提出以來，已有很多各具特點(diǎn)的解決方案被提出。各個不同的應(yīng)用層組播系統(tǒng)具有不同的設(shè)計(jì)目的及系統(tǒng)構(gòu)造。如，ES(End-Systeultiast)1和ALI2合適時(shí)延要求不高的小規(guī)模多對多通信，而Satterast3和verasts4那么支持大規(guī)模的數(shù)據(jù)遞送系

2、統(tǒng)。在系統(tǒng)構(gòu)造方面，根據(jù)建立應(yīng)用層組播拓?fù)錁?gòu)造時(shí)采用的方案，將這些系統(tǒng)分為兩種：網(wǎng)優(yōu)先(eshFirst)和樹優(yōu)先(TreeFirst)，網(wǎng)優(yōu)先的系統(tǒng)會首先為覆蓋節(jié)點(diǎn)建立一個網(wǎng)狀的拓?fù)錁?gòu)造，然后按照某種路由協(xié)議來生成數(shù)據(jù)路由樹，如ES的Narada協(xié)議，會先構(gòu)建一個網(wǎng)，然后通過修改后的DVRP協(xié)議完成路由樹的生成；而樹優(yōu)先的系統(tǒng)那么是直接建立數(shù)據(jù)路由樹，ALI、verast、Hstultiastis5均屬于這種系統(tǒng)。一般來說，網(wǎng)優(yōu)先的系統(tǒng)穩(wěn)定性更好，不會形成回路，樹優(yōu)先的系統(tǒng)那么在效率上占優(yōu)勢。在多源的應(yīng)用層組播方案中，根據(jù)數(shù)據(jù)路由樹的使用和維持，可以分為SharedTree和Sure-spe

3、ifiTree兩種。SharedTree，就是所有的源使用同一棵樹；Sure-speifiTree，就是每個源維持一棵樹，前者不能保證每個源都能獲得較好的傳輸延遲。本協(xié)議根據(jù)視頻會議系統(tǒng)的應(yīng)用特點(diǎn)，采用效率較高的樹優(yōu)先的拓?fù)錁?gòu)造，使用Sure-speifiTree數(shù)據(jù)路由樹策略。樹的生成、維持由根(源)負(fù)責(zé)，集中點(diǎn)(RP)不參與，這點(diǎn)類似Hstultiast的做法，Hstultiast是分布的方式，每個組的數(shù)據(jù)路由樹都有一個根節(jié)點(diǎn)，每個新的組成員參加時(shí)，都要從該根節(jié)點(diǎn)開場依次協(xié)商，直到找到一個間隔 最近的節(jié)點(diǎn)為止。2.1協(xié)議設(shè)計(jì)思想我們的思路是，建立一個全分布的，支持多組、多源，低時(shí)延的，基于

4、不定叉源指定樹(Sure-speifiTree)的Tree-First應(yīng)用層組播協(xié)議平臺。由于目前Internet終端多數(shù)是以xDSL方式接入的，考慮到這些終端具有的極限帶寬是上傳512kbps(部分是1bps)，下載5bps(其余接入方式的終端一般具有更高的帶寬)，假定每個源每秒產(chǎn)生的實(shí)時(shí)數(shù)據(jù)流量為150kbps(如視頻會議)，按照90%極限上傳帶寬的可利用率，一個節(jié)點(diǎn)可以為3個節(jié)點(diǎn)實(shí)現(xiàn)分發(fā)任務(wù)；再假定組的規(guī)模控制在100個節(jié)點(diǎn)內(nèi)，假如按照三叉樹的組織構(gòu)造，這樣的樹將不超過4層，經(jīng)過4個節(jié)點(diǎn)的轉(zhuǎn)發(fā)，其時(shí)延根本可以控制在5秒內(nèi)。基于以上的假設(shè)，我們將在組應(yīng)用開場前建立n棵Sure-speifi

5、Tree，n等于組的節(jié)點(diǎn)數(shù)，每個節(jié)點(diǎn)負(fù)責(zé)生成一棵以它為根的滿三叉樹。我們又知道，有的節(jié)點(diǎn)的上傳才能可能不到3個，有的節(jié)點(diǎn)那么可能超過3個，而且這種才能可能是變動的。由此，這些樹必須根據(jù)網(wǎng)絡(luò)的實(shí)際狀態(tài)進(jìn)展調(diào)整，節(jié)點(diǎn)的分發(fā)孩子個數(shù)視其才能變動而定，分發(fā)才能的判斷，那么通過孩子節(jié)點(diǎn)反應(yīng)RTP信息包來計(jì)算丟包率。也就是說，滿三叉樹在應(yīng)用預(yù)運(yùn)行或運(yùn)行后成為動態(tài)調(diào)整的不定叉樹。2.2節(jié)點(diǎn)參加節(jié)點(diǎn)必須清楚自己屬于哪個組，然后參加到適宜的組中。RP(集中點(diǎn))為節(jié)點(diǎn)提供參加效勞。任一個節(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)通告單個節(jié)點(diǎn)參加

6、消息。2.3滿三叉樹的生成2.3.1“間隔 與“間隔 計(jì)算節(jié)點(diǎn)一旦成功參加，馬上與列表中的同組節(jié)點(diǎn)通信，估算節(jié)點(diǎn)之間的“間隔 。所謂的“間隔 ，指的是節(jié)點(diǎn)間的傳輸延遲和帶寬加權(quán)后的值，我們采取簡單做法，就是測試1KUDP包來回所需的時(shí)間。我們采取如下算法計(jì)算NdeA和NdeB節(jié)點(diǎn)間的“間隔 ：TieAS=urrentTiefNdeANdeASend1KbytestNdeBbyUDPithTieASNdeBRevivepaketfrNdeATieBR=TiehenNdeBRevivesthepaketTieBS=urrentTiefNdeBNdeBSend1KbytestAbyUDPithTie

7、AS,TieBRandTieBSNdeARevivepaketfrNdeBTieAR=TiehenNdeARevivesthepaketDistaneAB=TieAR-TieAS-(TieBS-TieBR)2.3.2樹生成開場時(shí)，每個源生成一棵不超過4層(源，即根，為0層)的滿三叉數(shù)據(jù)路由樹，樹的生成根據(jù)這樣的原那么，在樹中，離源較近的節(jié)點(diǎn)與源有更近的“間隔 ，而第2層的節(jié)點(diǎn)即與其第1層的父親節(jié)點(diǎn)有更近的“間隔 ，依此類推。首先，根選擇3個最適宜的節(jié)點(diǎn)作為它的第一層子節(jié)點(diǎn)，然后，根分別通知這3個子節(jié)點(diǎn)，去尋找它們適宜的孩子節(jié)點(diǎn)，過程不斷重復(fù)，直到所有的節(jié)點(diǎn)都參加到樹中。樹的生成是由覆蓋網(wǎng)中的所

8、有節(jié)點(diǎn)協(xié)同完成的，因此其生成算法是分布的，算法如下：nReEivereateTree(vid*paket)/根收到建樹命令,每個節(jié)點(diǎn)都需要生成一棵以其為根的樹按間隔 大小選擇3個孩子節(jié)點(diǎn);向選擇好的節(jié)點(diǎn)發(fā)送邀請其成為我的孩子節(jié)點(diǎn)的懇求包(以我為根的樹);nReeiveInviteTbehildReq(vid*paket)/收到i邀請為其孩子的懇求(j為根的樹)if(我還沒參加到以j為根的樹)發(fā)送承受邀請的回應(yīng)包;else發(fā)送回絕邀請的回應(yīng)包;nReeiveTBehildReply(vid*paket)/收到節(jié)點(diǎn)i對我邀請的回應(yīng)(j為根的樹)if(i承受我的邀請)將i置為以j為根的樹中的我的孩子

9、;將i參加到本地以j為根的樹已入樹節(jié)點(diǎn)列表;if(我是j)修改樹構(gòu)造;/根維持整棵樹的構(gòu)造描繪,樹生成后,分發(fā)給所有孩子else將i參加到本地在建以j為根的樹中回絕我的節(jié)點(diǎn)列表;if(重新選擇一個節(jié)點(diǎn)成功)向被選擇的節(jié)點(diǎn)發(fā)送邀請其成為我的孩子節(jié)點(diǎn)的懇求包(以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ā)送給根;nReeiveSelethildrenrder(vid*paket)/收到根的選擇孩子節(jié)點(diǎn)的命令將包中已入樹的節(jié)點(diǎn)列表復(fù)制到本地;fr(int

10、i=0;i3;i+)if(選擇一個節(jié)點(diǎn)成功)向其發(fā)送邀請其成為孩子的懇求;elsebreak;樹生成的算法是由分布在網(wǎng)絡(luò)上的多個節(jié)點(diǎn)機(jī)共同執(zhí)行的，為防止多個節(jié)點(diǎn)同時(shí)選擇一個節(jié)點(diǎn)為其孩子，因此，我們采用了應(yīng)答制。2.4性能優(yōu)化-不定叉樹的調(diào)整前面講到，在生成樹時(shí)，并沒有過多考慮樹的上傳才能，只是基于經(jīng)歷及網(wǎng)絡(luò)的一般現(xiàn)狀，假設(shè)每節(jié)點(diǎn)有才能完成對3個節(jié)點(diǎn)的視音頻數(shù)據(jù)轉(zhuǎn)發(fā)。但，實(shí)際情況可能是，有的節(jié)點(diǎn)的分發(fā)才能超過3，有的節(jié)點(diǎn)那么缺乏3。這樣，在應(yīng)用預(yù)運(yùn)行后，必須盡快對樹進(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秒

11、鐘，孩子節(jié)點(diǎn)向父親發(fā)送一個RTP包，告訴父親，最近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)會選擇帶寬較高的節(jié)點(diǎn)發(fā)送移交懇求。收到移交懇求的節(jié)點(diǎn)檢查其自身上傳才能，回應(yīng)承受懇求或不承受懇求，發(fā)送移交懇求的節(jié)點(diǎn)會一直嘗試，直到有節(jié)點(diǎn)同意移交，此外，上傳才能缺乏的節(jié)點(diǎn)可以啟用選幀，降低對帶寬的需求

12、，這屬于應(yīng)用層QS的任務(wù)，不在這里詳述。目前多數(shù)的AL協(xié)議，對底層網(wǎng)絡(luò)變動的適應(yīng)普遍采取整體變動的方法，這樣的代價(jià)相當(dāng)大，如NARADA，節(jié)點(diǎn)狀態(tài)的變化將導(dǎo)致網(wǎng)esh的重構(gòu)，從而導(dǎo)致所有sure-speifiTree的重構(gòu)，這個過程需要較長的收斂時(shí)間。我們采取部分變化的對策以適應(yīng)verlayNetrk的變化。圖1節(jié)點(diǎn)轉(zhuǎn)移實(shí)現(xiàn)優(yōu)化2.5樹的修補(bǔ)有邊相連的節(jié)點(diǎn)，互相為鄰居。節(jié)點(diǎn)每3秒鐘向鄰居發(fā)送“心跳信息?！靶奶畔⒖梢院唵蔚绞且粋€不斷增長的序列號。當(dāng)節(jié)點(diǎn)在30秒鐘收不到鄰居的“心跳信息后，節(jié)點(diǎn)認(rèn)為鄰居已經(jīng)出現(xiàn)故障。故障處理：1).為防止多個節(jié)點(diǎn)同時(shí)嘗試修補(bǔ)樹，我們規(guī)定，只允許上層節(jié)點(diǎn)對下層節(jié)點(diǎn)進(jìn)

13、展修補(bǔ)。假如根節(jié)點(diǎn)故障，樹的修補(bǔ)失去意義。2).后備選擇從故障節(jié)點(diǎn)的最左邊的子孫節(jié)點(diǎn)逐級往上提升，最左的節(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)嗎?2.1是，算法完畢2.2否，轉(zhuǎn)33.j有適宜的孩子嗎？3.1有，轉(zhuǎn)43.2沒有，算法完畢4.選擇適宜的孩子，向其發(fā)送接替j的通知5.T:=j圖2樹的修補(bǔ)任何節(jié)點(diǎn)k收到l發(fā)送給自己，要求自己接替節(jié)點(diǎn)j的通知，執(zhí)行如下算法：1.k是否葉子1.1是，向l發(fā)送jk、k0的通知1.2否，選擇適宜的兒子，向其發(fā)送接替k的通知，T:=j,T

14、1:=l任何節(jié)點(diǎn)k收到確認(rèn)接替的通知，執(zhí)行如下算法：1.接替串的第一個節(jié)點(diǎn)是自己嗎？1.1是，接替串:=Tk+接替串，向T1發(fā)送接替串1.2否，根據(jù)接替串交換樹，將新樹向所有節(jié)點(diǎn)發(fā)送本協(xié)議合適小規(guī)模、時(shí)延要求高的應(yīng)用層組播系統(tǒng)，我們在協(xié)議的根底上開發(fā)了一個視頻會議系統(tǒng)，經(jīng)試驗(yàn)，在網(wǎng)絡(luò)狀態(tài)變動不是太頻繁的前提下，系統(tǒng)能很好工作。協(xié)議對很多復(fù)雜問題做了簡化，這些簡化對協(xié)議的實(shí)現(xiàn)帶來很大的便利，但同時(shí)也使得協(xié)議的適應(yīng)才能存在著一定的問題，我們將在樹的優(yōu)化、修補(bǔ)上進(jìn)展改造，以使得協(xié)議具有更廣闊的適應(yīng)才能。1huY,RaS,ZhangH.AasefrEndSysteultiast.ASIGETRIS,20002PendarakisD.ALI:AnAppliatinLevelu