一種適用于IP視頻會(huì)議的混合式組播技術(shù)研究

ip視頻會(huì)議是利用視頻技術(shù)和ip數(shù)據(jù)通信技術(shù)通過ip網(wǎng)絡(luò)在兩點(diǎn)或多點(diǎn)之間建立可視通信,實(shí)現(xiàn)圖像、語(yǔ)音及數(shù)據(jù)交流的一種會(huì)議形式。ip視頻會(huì)議系統(tǒng)因其效率高、成本低、業(yè)務(wù)提供方式靈活等優(yōu)勢(shì)將代替?zhèn)鹘y(tǒng)的基于電路交換的視頻會(huì)議系統(tǒng)。然而要解決視音頻數(shù)據(jù)在ip網(wǎng)絡(luò)上實(shí)時(shí)傳輸?shù)膯栴},并為視頻會(huì)議系統(tǒng)提供一定的qos是一個(gè)技術(shù)難題,也是目前的研究熱點(diǎn)。

本文把ip組播與應(yīng)用層組播結(jié)合起來(lái)并采用分層排列圖結(jié)構(gòu),提出了一種適用于ip視頻會(huì)議的混合式組播方式——基于分層排列圖的混合式組播。

1 混合式組播

1.1 問題的提出

ip視頻會(huì)議屬于傳輸數(shù)據(jù)量大、對(duì)帶寬要求高的服務(wù),為實(shí)現(xiàn)它的即時(shí)通信和互動(dòng)溝通功能必須保證音視頻等數(shù)據(jù)在ip網(wǎng)絡(luò)上的實(shí)時(shí)傳輸。ip組播技術(shù)能夠有效地解決多點(diǎn)對(duì)多點(diǎn)數(shù)據(jù)通信的網(wǎng)絡(luò)帶寬問題。相對(duì)于單播和廣播方式來(lái)說,它能顯著節(jié)省網(wǎng)絡(luò)帶寬,提高數(shù)據(jù)傳輸?shù)男?同時(shí)提高服務(wù)的質(zhì)量,因而它較適合于ip視頻會(huì)議系統(tǒng)。當(dāng)前最流行的ip視頻會(huì)議標(biāo)準(zhǔn)h.323就采用了ip組播技術(shù)。然而,由于技術(shù)、市場(chǎng)、需求等原因,ip組播并沒有在internet上得到廣泛應(yīng)用[1],使得目前只有少數(shù)用戶在局域范圍(稱為ip組播島)內(nèi)可以使用 ip 組播技術(shù)。因此基于ip組播技術(shù)的視頻會(huì)議只能在這些相互孤立的組播島上進(jìn)行,與會(huì)成員受到很大的限制。

正是因?yàn)閕p組播未能在internet上廣泛應(yīng)用,近年來(lái)人們提出了十幾種應(yīng)用層組播方案,其中適用于ip視頻會(huì)議的系統(tǒng)有narada[2]和almi[3]。narada只能應(yīng)用于與會(huì)成員很少的情況。almi中,當(dāng)有多人發(fā)言時(shí)易形成網(wǎng)絡(luò)瓶頸,故在一定程度上限制了視頻會(huì)議的規(guī)模。

相對(duì)于應(yīng)用層組播來(lái)說,ip組播能更多地節(jié)約網(wǎng)絡(luò)帶寬[4]、可靠性更好且數(shù)據(jù)轉(zhuǎn)發(fā)速率更高。而相對(duì)于ip組播來(lái)說,應(yīng)用層組播與現(xiàn)今網(wǎng)絡(luò)結(jié)構(gòu)相符合,使用時(shí)不需變動(dòng)現(xiàn)有的網(wǎng)絡(luò)協(xié)議與硬件,部署相對(duì)容易,同時(shí)具有較好的擴(kuò)展性,可以適應(yīng)網(wǎng)絡(luò)條件的動(dòng)態(tài)變化。它已成為目前最可能解決ip組播中的路由器瓶頸問題的方案。為了在ip視頻會(huì)議中充分利用應(yīng)用層組播和ip組播的優(yōu)勢(shì),在此把二者結(jié)合起來(lái),稱為混合式組播。本文以后所提到的混合式組播均以ip視頻會(huì)議這種特殊應(yīng)用場(chǎng)合為例。

1.2 拓?fù)浣Y(jié)構(gòu)

在采用混合式組播的ip視頻會(huì)議中,與會(huì)成員組成如圖1所示的拓?fù)浣Y(jié)構(gòu)。在每個(gè)ip組播島內(nèi),與會(huì)成員之間的數(shù)據(jù)傳輸使用ip組播,并選定一個(gè)與會(huì)成員作指定成員(designate member,dm),把島內(nèi)除dm外的與會(huì)成員稱為其他成員(pertinent member,pm),dm是島內(nèi)成員與島外成員之間通信的橋梁。島外成員與dm參加應(yīng)用層組播疊加網(wǎng)[5](包括一個(gè)控制拓?fù)浜鸵粋€(gè)數(shù)據(jù)拓?fù)?的構(gòu)建,將其稱為應(yīng)用層組播成員(alm member,am),am之間的數(shù)據(jù)傳輸使用應(yīng)用層組播。ip組播島中pm通過dm與疊加網(wǎng)相連,dm與島外成員之間的數(shù)據(jù)傳輸采用應(yīng)用層組播方式,與島內(nèi)的成員之間的數(shù)據(jù)傳輸使用ip組播的方式。dm負(fù)責(zé)將來(lái)自疊加網(wǎng)的數(shù)據(jù)以ip組播方式傳送給組播島中pm,pm的數(shù)據(jù)也通過ip組播方式傳送到dm,由dm以應(yīng)用層組播的方式發(fā)送給疊加網(wǎng)上的其他與會(huì)成員。

dm的選取原則:島中第一個(gè)參加會(huì)議的成員被設(shè)為dm,以后可以根據(jù)某種策略(如參加會(huì)議的時(shí)間最長(zhǎng)者或物理位置“中心”點(diǎn)成員,或剩余帶寬資源最多者等)選定某個(gè)成員作為dm。如果dm離開,則根據(jù)某種策略從島內(nèi)的pm中選擇一個(gè)作dm。

2 基于分層排列圖的混合式組播

2.1 控制拓?fù)錁?gòu)建

在數(shù)學(xué)上,(n,k)維排列圖[6](用an,k表示,其中n和k是自然數(shù),1≤k≤n-1。令表示集合{1,2,……n}中k個(gè)符號(hào)的排列,an,k定義為無(wú)向圖(v,e),其中:

一個(gè)排列圖實(shí)例a4,2的拓?fù)浣Y(jié)構(gòu)如圖2所示。排列圖an,2僅能容納n(n-1)個(gè)主機(jī)。為使系統(tǒng)可容納任意多主機(jī),可將參與主機(jī)組合成多個(gè)an,2結(jié)構(gòu),這些an,2按照樹形結(jié)構(gòu)連接在一起,稱為分層排列圖結(jié)構(gòu)[6]。

混合式組播的核心任務(wù)是為am完成拓?fù)?包括數(shù)據(jù)拓?fù)浜涂刂仆負(fù)?的構(gòu)建。由于網(wǎng)絡(luò)狀況的動(dòng)態(tài)性,以及客戶端數(shù)量與客戶端加入系統(tǒng)時(shí)間的不確定性,當(dāng)前的應(yīng)用層組播方案一般需要每個(gè)結(jié)點(diǎn)定期與其他全部或一定比例的結(jié)點(diǎn)交換控制信息,以了解其他結(jié)點(diǎn)的狀態(tài),形成控制拓?fù)?保障數(shù)據(jù)拓?fù)涞慕研?。在結(jié)點(diǎn)個(gè)數(shù)逐漸增加時(shí),網(wǎng)絡(luò)上的控制信息數(shù)量會(huì)占用大量的帶寬資源。應(yīng)用層組播的數(shù)據(jù)拓?fù)淇煞譃槎箢?信源樹和共享樹。信源樹必須為每個(gè)組播源保存路由信息,這樣會(huì)占用大量的系統(tǒng)資源。共享樹傳輸延時(shí)較大。ip視頻會(huì)議系統(tǒng)屬于實(shí)時(shí)交互應(yīng)用,視音頻數(shù)據(jù)占據(jù)很大的帶寬,并且對(duì)端到端傳輸延遲和網(wǎng)絡(luò)抖動(dòng)的要求很高,需要尋找一種既可以減少交換控制信息又可以保證視音頻數(shù)據(jù)實(shí)時(shí)傳輸?shù)耐負(fù)錁?gòu)建方式。為利用排列圖的優(yōu)越特性(如結(jié)點(diǎn)和邊的對(duì)稱性、故障恢復(fù)能力和容錯(cuò)能力、可以嵌入獨(dú)立的組播樹等),這里采用分層排列圖的結(jié)構(gòu)來(lái)組織混合式組播中的am。

本文先按照文獻(xiàn)[6]中的協(xié)議設(shè)計(jì)方法把參與ip視頻會(huì)議所有主機(jī)中的am組織成分層排列圖結(jié)構(gòu),作為混合式組播的控制拓?fù)?并在主機(jī)申請(qǐng)加入會(huì)議時(shí)根據(jù)其帶寬處理能力和一定的算法規(guī)定它的入度最大值和出度最大值,它們分別也是剩余入度和剩余出度的初始值。每個(gè)分層排列圖都對(duì)應(yīng)一棵以排列圖為結(jié)點(diǎn)單位的樹。如圖3所示的以與會(huì)主機(jī)為單位的拓?fù)浣Y(jié)構(gòu)是一個(gè)由3個(gè)a4,2結(jié)構(gòu)(ag1、ag2和ag3)所組成的分層排列圖。圖3也可以看作如圖4所示的以排列圖為單位的樹結(jié)構(gòu),即以排列圖ag2為根、以ag1和ag3為葉子的一棵樹狀拓?fù)?。設(shè)在分層排列圖中,父排列圖agi中的結(jié)點(diǎn)i1和i2分別是子排列圖agj的數(shù)據(jù)源結(jié)點(diǎn)和備用數(shù)據(jù)源結(jié)點(diǎn),agj中的結(jié)點(diǎn)j1和j2分別是i1和i2對(duì)應(yīng)的根結(jié)點(diǎn),則在樹拓?fù)渲懈概帕袌Dagi與子排列圖agj的連線實(shí)際上包括2條:(1)i1與j1之間的連線;(2)i2與j2之間的連線。圖4中父排列圖ag2與其子排列圖ag1之間的連線有2條:(1)圖3中ag2的a14與ag1的a31之間的連線;(2)圖3 中ag2的a24與ag1的a41之間的連線。各排列圖之間的連線在混合式組播中并不一定作為數(shù)據(jù)傳輸路徑。

2.2 數(shù)據(jù)拓?fù)錁?gòu)建

基于分層排列圖的混合式組播的控制拓?fù)涫欠謱优帕袌D,其數(shù)據(jù)拓?fù)湓诖嘶A(chǔ)上構(gòu)建,具體算法如下:

設(shè)某排列圖中的與會(huì)成員主機(jī)ai,j發(fā)言,首先把分層排列圖對(duì)應(yīng)的樹結(jié)構(gòu)轉(zhuǎn)換為以ai,j所在的排列圖為根的樹結(jié)構(gòu),然后執(zhí)行步驟(1)～(2)。

把a(bǔ)i,j所處的排列圖作為當(dāng)前排列圖,在當(dāng)前排列圖中用文獻(xiàn)[6]中的算法生成以ai,j為根的組播樹,并修改當(dāng)前排列圖中所有結(jié)點(diǎn)的剩余入度值和剩余出度值。

(1)為當(dāng)前排列圖的所有子排列圖選擇數(shù)據(jù)源、備用數(shù)據(jù)源和根結(jié)點(diǎn)(為描述方便起見,這里分別把它們記為s1、s2和r)。為某個(gè)子排列圖選擇數(shù)據(jù)源s1、備用數(shù)據(jù)源s2和根結(jié)點(diǎn)r的算法如下:

①令與會(huì)成員主機(jī)結(jié)點(diǎn)子集a={am,n|am,n屬于當(dāng)前排列圖,ai,j與am,n相鄰接并且am,n的剩余出度值大于0}。

·若|a|>1,則在a中選擇剩余出度值最大者作為數(shù)據(jù)源s1,次大者作為備用數(shù)據(jù)源s2,此時(shí)一定可以選取合適的根結(jié)點(diǎn)使得組播樹獨(dú)立。

·若|a|=0,則選擇在當(dāng)前排列圖中選擇最大剩余出度結(jié)點(diǎn)作為數(shù)據(jù)源s1,次大者作為備用數(shù)據(jù)源s2。

·若|a|=1,則選擇a中的結(jié)點(diǎn)作為數(shù)據(jù)源s1,選擇當(dāng)前排列圖中其他成員中最大剩余出度結(jié)點(diǎn)作為備用數(shù)據(jù)源s2。

②s1和s2的剩余出度值分別減1。

③在此子排列圖中先后選取數(shù)據(jù)源s1對(duì)應(yīng)的根結(jié)點(diǎn)r,并把選出的根結(jié)點(diǎn)的剩余入度值減1。當(dāng)s1不能正常工作或失效時(shí),s2作為r的數(shù)據(jù)源結(jié)點(diǎn)。選取根結(jié)點(diǎn)時(shí)既要考慮結(jié)點(diǎn)的剩余出度值和剩余入度值,又要注意盡量保證組播樹的獨(dú)立性。如果能保證組播樹獨(dú)立性的結(jié)點(diǎn)的剩余入度值全為零,則選取子排列圖中的剩余入度值最大者。

④在此子排列圖內(nèi)根據(jù)文獻(xiàn)[6]中的算法生成以r為根的組播樹,并修改相應(yīng)結(jié)點(diǎn)的剩余出度值和剩余入度值。

(2)如果還有再下一級(jí)的子排列圖,則令ai,j=當(dāng)前排列圖的相應(yīng)子排列圖的根結(jié)點(diǎn)的r,轉(zhuǎn)(1);否則,結(jié)束。

圖3給出了ag1中的a31和ag2中的a41發(fā)言時(shí)根據(jù)以上算法為實(shí)現(xiàn)應(yīng)用層組播建立的組播樹,分別以虛線和實(shí)線表示。在ag1、ag2和ag3中分別由三個(gè)dm(a34、a42、a41)作為ip組播島的數(shù)據(jù)源結(jié)點(diǎn),組播島內(nèi)的ip組播樹分別以它們?yōu)楦?由它們傳輸?shù)絠p組播島中的pm。ip組播島中對(duì)應(yīng)的ip組播樹在圖3中沒有畫出。

2.3 性能分析

與當(dāng)前其他的應(yīng)用層組播相比,在ip視頻會(huì)議中采用基于分層排列圖的混合式組播技術(shù),有以下優(yōu)點(diǎn):

(1)增強(qiáng)了系統(tǒng)的可擴(kuò)展性。系統(tǒng)只需維護(hù)樹形式的分層排列圖即可,它就是應(yīng)用層組播的控制拓?fù)?由它生成數(shù)據(jù)拓?fù)洹p組播島內(nèi)的數(shù)據(jù)傳輸由ip組播技術(shù)實(shí)現(xiàn),系統(tǒng)只需選定dm,由dm來(lái)作為島內(nèi)成員與島外成員之間通信的橋梁?？刂菩畔?shù)量大大減少,節(jié)約了網(wǎng)絡(luò)帶寬,使更多的用戶可以加入會(huì)議。

(2)提高了系統(tǒng)的容錯(cuò)能力,減少了網(wǎng)絡(luò)抖動(dòng)。由于在an,2中可以建立n-2個(gè)獨(dú)立的組播樹,在用戶帶寬資源足夠豐富的情況下只要發(fā)言用戶數(shù)≤n-2就可以保證組播樹的獨(dú)立,使得每個(gè)用戶只在最多一棵組播樹上作為中間結(jié)點(diǎn)。這樣一個(gè)用戶出現(xiàn)故障最多影響一個(gè)組播樹中的數(shù)據(jù)傳輸。分層排列圖的這一性質(zhì)使基于分層排列圖的混合式組播能提高視頻會(huì)議系統(tǒng)的容錯(cuò)能力,減少數(shù)據(jù)傳輸過程中的網(wǎng)絡(luò)抖動(dòng)。

(3)縮短了用戶加入會(huì)議的時(shí)間。由于am組織為分層排列圖結(jié)構(gòu),ip組播島外的用戶加入會(huì)議的復(fù)雜度為o(log(n)),其中n表示ip視頻會(huì)議系統(tǒng)中am數(shù)目。組播島內(nèi)的用戶加入更簡(jiǎn)單,它不需要了解島外am的任何信息就可以加入它所屬的ip組播島,通過該島上的dm與島外與會(huì)成員傳輸數(shù)據(jù),因而一個(gè)申請(qǐng)加入會(huì)議的主機(jī)可迅速地完成加入過程。

本文為ip視頻會(huì)議系統(tǒng)提供了一種簡(jiǎn)單、可靠的混合式組播方案。一方面能充分利用參與會(huì)議的主機(jī)資源,使系統(tǒng)能支持更多的用戶參加會(huì)議,另一方面也為視頻會(huì)議系統(tǒng)中視音頻數(shù)據(jù)在internet上的實(shí)時(shí)傳輸提供較好服務(wù)質(zhì)量保障。