摘 要： 提出一種適用于IP視頻會議" title="視頻會議">視頻會議的組播" title="組播">組播——基于分層排列圖的混合式組播。詳細介紹了其拓撲結(jié)構(gòu)" title="拓撲結(jié)構(gòu)">拓撲結(jié)構(gòu)，以及控制拓撲和數(shù)據(jù)拓撲的構(gòu)建過程，并對該組播技術(shù)進行了性能分析。
關(guān)鍵詞： 視頻會議系統(tǒng) 混合式組播 排列圖 IP組播島
IP視頻會議是利用視頻技術(shù)和IP數(shù)據(jù)通信技術(shù)通過IP網(wǎng)絡在兩點或多點之間建立可視通信，實現(xiàn)圖像、語音及數(shù)據(jù)交流的一種會議形式。IP視頻會議系統(tǒng)因其效率高、成本低、業(yè)務提供方式靈活等優(yōu)勢將代替?zhèn)鹘y(tǒng)的基于電路交換的視頻會議系統(tǒng)。然而要解決視音頻數(shù)據(jù)在IP網(wǎng)絡上實時傳輸?shù)膯栴}，并為視頻會議系統(tǒng)提供一定的QoS是一個技術(shù)難題，也是目前的研究熱點。
本文把IP組播與應用層組播" title="應用層組播">應用層組播結(jié)合起來并采用分層排列圖結(jié)構(gòu)，提出了一種適用于IP視頻會議的混合式組播方式——基于分層排列圖的混合式組播。
1 混合式組播
1.1 問題的提出
IP視頻會議屬于傳輸數(shù)據(jù)量大、對帶寬要求高的服務，為實現(xiàn)它的即時通信和互動溝通功能必須保證音視頻等數(shù)據(jù)在IP網(wǎng)絡上的實時傳輸。IP組播技術(shù)能夠有效地解決多點對多點數(shù)據(jù)通信的網(wǎng)絡帶寬問題。相對于單播和廣播方式來說，它能顯著節(jié)省網(wǎng)絡帶寬，提高數(shù)據(jù)傳輸?shù)男?，同時提高服務的質(zhì)量，因而它較適合于IP視頻會議系統(tǒng)。當前最流行的IP視頻會議標準H.323就采用了IP組播技術(shù)。然而，由于技術(shù)、市場、需求等原因，IP組播并沒有在Internet上得到廣泛應用[1]，使得目前只有少數(shù)用戶在局域范圍(稱為IP組播島)內(nèi)可以使用 IP 組播技術(shù)。因此基于IP組播技術(shù)的視頻會議只能在這些相互孤立的組播島上進行，與會成員受到很大的限制。
正是因為IP組播未能在Internet上廣泛應用，近年來人們提出了十幾種應用層組播方案，其中適用于IP視頻會議的系統(tǒng)有NARADA[2]和ALMI[3]。NARADA只能應用于與會成員很少的情況。ALMI中，當有多人發(fā)言時易形成網(wǎng)絡瓶頸，故在一定程度上限制了視頻會議的規(guī)模。
相對于應用層組播來說，IP組播能更多地節(jié)約網(wǎng)絡帶寬[4]、可靠性更好且數(shù)據(jù)轉(zhuǎn)發(fā)速率更高。而相對于IP組播來說，應用層組播與現(xiàn)今網(wǎng)絡結(jié)構(gòu)相符合，使用時不需變動現(xiàn)有的網(wǎng)絡協(xié)議與硬件，部署相對容易，同時具有較好的擴展性，可以適應網(wǎng)絡條件的動態(tài)變化。它已成為目前最可能解決IP組播中的路由器瓶頸問題的方案。為了在IP視頻會議中充分利用應用層組播和IP組播的優(yōu)勢，在此把二者結(jié)合起來，稱為混合式組播。本文以后所提到的混合式組播均以IP視頻會議這種特殊應用場合為例。
1.2 拓撲結(jié)構(gòu)
在采用混合式組播的IP視頻會議中，與會成員組成如圖1所示的拓撲結(jié)構(gòu)。在每個IP組播島內(nèi)，與會成員之間的數(shù)據(jù)傳輸使用IP組播，并選定一個與會成員作指定成員(Designate Member，DM)，把島內(nèi)除DM外的與會成員稱為其他成員(Pertinent Member，PM)，DM是島內(nèi)成員與島外成員之間通信的橋梁。島外成員與DM參加應用層組播疊加網(wǎng)[5](包括一個控制拓撲和一個數(shù)據(jù)拓撲)的構(gòu)建，將其稱為應用層組播成員(ALM Member，AM)，AM之間的數(shù)據(jù)傳輸使用應用層組播。IP組播島中PM通過DM與疊加網(wǎng)相連，DM與島外成員之間的數(shù)據(jù)傳輸采用應用層組播方式，與島內(nèi)的成員之間的數(shù)據(jù)傳輸使用IP組播的方式。DM負責將來自疊加網(wǎng)的數(shù)據(jù)以IP組播方式傳送給組播島中PM，PM的數(shù)據(jù)也通過IP組播方式傳送到DM，由DM以應用層組播的方式發(fā)送給疊加網(wǎng)上的其他與會成員。
DM的選取原則：島中第一個參加會議的成員被設(shè)為DM，以后可以根據(jù)某種策略(如參加會議的時間最長者或物理位置“中心”點成員，或剩余帶寬資源最多者等)選定某個成員作為DM。如果DM離開，則根據(jù)某種策略從島內(nèi)的PM中選擇一個作DM。
2 基于分層排列圖的混合式組播
2.1 控制拓撲構(gòu)建
在數(shù)學上，(n，k)維排列圖[6]用An，k表示，其中n和k是自然數(shù)，1≤k≤n-1。令
表示集合{1，2，……n}中k個符號的排列，An，k定義為無向圖(V，E)，其中：
一個排列圖實例A4，2的拓撲結(jié)構(gòu)如圖2所示。排列圖An，2僅能容納n(n-1)個主機。為使系統(tǒng)可容納任意多主機，可將參與主機組合成多個An，2結(jié)構(gòu)，這些An，2按照樹形結(jié)構(gòu)連接在一起，稱為分層排列圖結(jié)構(gòu)[6]。
混合式組播的核心任務是為AM完成拓撲(包括數(shù)據(jù)拓撲和控制拓撲)的構(gòu)建。由于網(wǎng)絡狀況的動態(tài)性，以及客戶端數(shù)量與客戶端加入系統(tǒng)時間的不確定性，當前的應用層組播方案一般需要每個結(jié)點定期與其他全部或一定比例的結(jié)點交換控制信息，以了解其他結(jié)點的狀態(tài)，形成控制拓撲，保障數(shù)據(jù)拓撲的健壯性。在結(jié)點個數(shù)逐漸增加時，網(wǎng)絡上的控制信息數(shù)量會占用大量的帶寬資源。應用層組播的數(shù)據(jù)拓撲可分為二大類：信源樹和共享樹。信源樹必須為每個組播源保存路由信息，這樣會占用大量的系統(tǒng)資源。共享樹傳輸延時較大。IP視頻會議系統(tǒng)屬于實時交互應用，視音頻數(shù)據(jù)占據(jù)很大的帶寬，并且對端到端傳輸延遲和網(wǎng)絡抖動的要求很高，需要尋找一種既可以減少交換控制信息又可以保證視音頻數(shù)據(jù)實時傳輸?shù)耐負錁?gòu)建方式。為利用排列圖的優(yōu)越特性(如結(jié)點和邊的對稱性、故障恢復能力和容錯能力、可以嵌入獨立的組播樹等)，這里采用分層排列圖的結(jié)構(gòu)來組織混合式組播中的AM。
本文先按照文獻[6]中的協(xié)議設(shè)計方法把參與IP視頻會議所有主機中的AM組織成分層排列圖結(jié)構(gòu)，作為混合式組播的控制拓撲，并在主機申請加入會議時根據(jù)其帶寬處理能力和一定的算法規(guī)定它的入度最大" title="最大">最大值和出度最大值，它們分別也是剩余入度和剩余出度的初始值。每個分層排列圖都對應一棵以排列圖為結(jié)點單位的樹。如圖3所示的以與會主機為單位的拓撲結(jié)構(gòu)是一個由3個A4，2結(jié)構(gòu)(AG1、AG2和AG3)所組成的分層排列圖。圖3也可以看作如圖4所示的以排列圖為單位的樹結(jié)構(gòu)，即以排列圖AG2為根、以AG1和AG3為葉子的一棵樹狀拓撲。設(shè)在分層排列圖中，父排列圖AGi中的結(jié)點i1和i2分別是子排列圖AGj的數(shù)據(jù)源結(jié)點和備用數(shù)據(jù)源結(jié)點，AGj中的結(jié)點j1和j2分別是i1和i2對應的根結(jié)點，則在樹拓撲中父排列圖AGi與子排列圖AGj的連線實際上包括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ù)拓撲構(gòu)建
基于分層排列圖的混合式組播的控制拓撲是分層排列圖，其數(shù)據(jù)拓撲在此基礎(chǔ)上構(gòu)建，具體算法如下：
設(shè)某排列圖中的與會成員主機ai，j發(fā)言，首先把分層排列圖對應的樹結(jié)構(gòu)轉(zhuǎn)換為以ai，j所在的排列圖為根的樹結(jié)構(gòu)，然后執(zhí)行步驟(1)～(2)。
把ai，j所處的排列圖作為當前排列圖，在當前排列圖中用文獻[6]中的算法生成以ai，j為根的組播樹，并修改當前排列圖中所有結(jié)點的剩余入度值和剩余出度值。
(1)為當前排列圖的所有子排列圖選擇數(shù)據(jù)源、備用數(shù)據(jù)源和根結(jié)點(為描述方便起見，這里分別把它們記為s1、s2和r)。為某個子排列圖選擇數(shù)據(jù)源s1、備用數(shù)據(jù)源s2和根結(jié)點r的算法如下：
①令與會成員主機結(jié)點子集A={am，n|am，n屬于當前排列圖，ai，j與am，n相鄰接并且am，n的剩余出度值大于0}。
·若|A|＞1，則在A中選擇剩余出度值最大者作為數(shù)據(jù)源s1，次大者作為備用數(shù)據(jù)源s2，此時一定可以選取合適的根結(jié)點使得組播樹獨立。
·若|A|=0，則選擇在當前排列圖中選擇最大剩余出度結(jié)點作為數(shù)據(jù)源s1，次大者作為備用數(shù)據(jù)源s2。
·若|A|=1，則選擇A中的結(jié)點作為數(shù)據(jù)源s1，選擇當前排列圖中其他成員中最大剩余出度結(jié)點作為備用數(shù)據(jù)源s2。
②s1和s2的剩余出度值分別減1。
?、墼诖俗优帕袌D中先后選取數(shù)據(jù)源s1對應的根結(jié)點r，并把選出的根結(jié)點的剩余入度值減1。當s1不能正常工作或失效時，s2作為r的數(shù)據(jù)源結(jié)點。選取根結(jié)點時既要考慮結(jié)點的剩余出度值和剩余入度值，又要注意盡量保證組播樹的獨立性。如果能保證組播樹獨立性的結(jié)點的剩余入度值全為零，則選取子排列圖中的剩余入度值最大者。
?、茉诖俗优帕袌D內(nèi)根據(jù)文獻[6]中的算法生成以r為根的組播樹，并修改相應結(jié)點的剩余出度值和剩余入度值。
(2)如果還有再下一級的子排列圖，則令ai，j=當前排列圖的相應子排列圖的根結(jié)點的r，轉(zhuǎn)(1)；否則，結(jié)束。
圖3給出了AG1中的a31和AG2中的a41發(fā)言時根據(jù)以上算法為實現(xiàn)應用層組播建立的組播樹，分別以虛線和實線表示。在AG1、AG2和AG3中分別由三個DM(a34、a42、a41)作為IP組播島的數(shù)據(jù)源結(jié)點，組播島內(nèi)的IP組播樹分別以它們?yōu)楦?，由它們傳輸?shù)絀P組播島中的PM。IP組播島中對應的IP組播樹在圖3中沒有畫出。
2.3 性能分析
與當前其他的應用層組播相比，在IP視頻會議中采用基于分層排列圖的混合式組播技術(shù)，有以下優(yōu)點：
(1)增強了系統(tǒng)的可擴展性。系統(tǒng)只需維護樹形式的分層排列圖即可，它就是應用層組播的控制拓撲，由它生成數(shù)據(jù)拓撲。IP組播島內(nèi)的數(shù)據(jù)傳輸由IP組播技術(shù)實現(xiàn)，系統(tǒng)只需選定DM，由DM來作為島內(nèi)成員與島外成員之間通信的橋梁。控制信息數(shù)量大大減少，節(jié)約了網(wǎng)絡帶寬，使更多的用戶可以加入會議。
(2)提高了系統(tǒng)的容錯能力，減少了網(wǎng)絡抖動。由于在An，2中可以建立n-2個獨立的組播樹，在用戶帶寬資源足夠豐富的情況下只要發(fā)言用戶數(shù)≤n-2就可以保證組播樹的獨立，使得每個用戶只在最多一棵組播樹上作為中間結(jié)點。這樣一個用戶出現(xiàn)故障最多影響一個組播樹中的數(shù)據(jù)傳輸。分層排列圖的這一性質(zhì)使基于分層排列圖的混合式組播能提高視頻會議系統(tǒng)的容錯能力，減少數(shù)據(jù)傳輸過程中的網(wǎng)絡抖動。
(3)縮短了用戶加入會議的時間。由于AM組織為分層排列圖結(jié)構(gòu)，IP組播島外的用戶加入會議的復雜度為O(log(N))，其中N表示IP視頻會議系統(tǒng)中AM數(shù)目。組播島內(nèi)的用戶加入更簡單，它不需要了解島外AM的任何信息就可以加入它所屬的IP組播島，通過該島上的DM與島外與會成員傳輸數(shù)據(jù)，因而一個申請加入會議的主機可迅速地完成加入過程。
本文為IP視頻會議系統(tǒng)提供了一種簡單、可靠的混合式組播方案。一方面能充分利用參與會議的主機資源，使系統(tǒng)能支持更多的用戶參加會議，另一方面也為視頻會議系統(tǒng)中視音頻數(shù)據(jù)在Internet上的實時傳輸提供較好服務質(zhì)量保障。
參考文獻
1 李珺晟，余鎮(zhèn)危，潘 耘.應用層組播綜述.計算機應用研究，2004；(11)：14～17
2 Chu Y H，Rao S，Zhang H.A case for end system multicast.ACM SIGMETRIC，2000；(6)：1～12
3 Pendakaris D，Shi S.ALMI：An application level multicast in-frastructure.In：The 3rd USENIX Symposium on Internet Technologies and Systems，San Francisco，CA，USA，2001：49-60
4 Banerjee S，Bhattacharjee B，Kommareddy C.Scalable application layer multicast.In：SIGCOMM′02，2002：205～217
5 Yeo C K，Lee B S，Er M H.A Survey of application level multicast techniques.Computer Communications，2004；(27)：1547～1568
6 田瑞雄，向 哲，李 星.基于分層排列圖結(jié)構(gòu)的流媒體應用層組播系統(tǒng).清華大學學報(自然科學版)，2004；44(4)：493～497