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