IP視頻會(huì )議混合式組播技術(shù)研究

2009/01/19

圖1 混合式組播拓撲結構圖

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

2.1 控制拓撲構建

　　在數學(xué)上,(n,k)維排列圖[6](用An,k表示,其中n和k是自然數,1≤k≤n-1。令表示集合{1,2,……n}中k個(gè)符號的排列,An,k定義為無(wú)向圖(V,E),其中: 一個(gè)排列圖實(shí)例A4,2的拓撲結構如圖2所示。排列圖An,2僅能容納n(n-1)個(gè)主機。為使系統可容納任意多主機,可將參與主機組合成多個(gè)An,2結構,這些An,2按照樹(shù)形結構連接在一起,稱(chēng)為分層排列圖結構[6]。

圖4 以排列圖

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

　　本文把參與IP視頻會(huì )議所有主機中的AM組織成分層排列圖結構,作為混合式組播的控制拓撲,并在主機申請加入會(huì )議時(shí)根據其帶寬處理能力和一定的算法規定它的入度最大值和出度最大值,它們分別也是剩余入度和剩余出度的初始值。每個(gè)分層排列圖都對應一棵以排列圖為結點(diǎn)單位的樹(shù)。如圖3所示的以與會(huì )主機為單位的拓撲結構是一個(gè)由3個(gè)A4,2結構(AG1、AG2和AG3)所組成的分層排列圖。圖3也可以看作如圖4所示的以排列圖為單位的樹(shù)結構,即以排列圖AG2為根、以AG1和AG3為葉子的一棵樹(shù)狀拓撲。設在分層排列圖中,父排列圖AGi中的結點(diǎn)i1和i2分別是子排列圖AGj的數據源結點(diǎn)和備用數據源結點(diǎn),AGj中的結點(diǎn)j1和j2分別是i1和i2對應的根結點(diǎn),則在樹(shù)拓撲中父排列圖AGi與子排列圖AGj的連線(xiàn)實(shí)際上包括2條 1)i1與j1之間的連線(xiàn);(2)i2與j2之間的連線(xiàn)。圖4中父排列圖AG2與其子排列圖AG1之間的連線(xiàn)有2條:(1)圖3中AG2的a14與AG1的a31之間的連線(xiàn);(2)圖3 中AG2的a24與AG1的a41之間的連線(xiàn)。各排列圖之間的連線(xiàn)在混合式組播中并不一定作為數據傳輸路徑。

2.2 數據拓撲構建

　　基于分層排列圖的混合式組播的控制拓撲是分層排列圖,其數據拓撲在此基礎上構建,具體算法如下:

　　設某排列圖中的與會(huì )成員主機ai,j發(fā)言,首先把分層排列圖對應的樹(shù)結構轉換為以ai,j所在的排列圖為根的樹(shù)結構,然后執行步驟(1)～(2)。

　　把ai,j所處的排列圖作為當前排列圖,在當前排列圖中用文獻[6]中的算法生成以ai,j為根的組播樹(shù),并修改當前排列圖中所有結點(diǎn)的剩余入度值和剩余出度值。

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

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

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


• 若|A|=0,則選擇在當前排列圖中選擇最大剩余出度結點(diǎn)作為數據源s1,次大者作為備用數據源s2。


• 若|A|=1,則選擇A中的結點(diǎn)作為數據源s1,選擇當前排列圖中其他成員中最大剩余出度結點(diǎn)為備用數據源s2。

全球IP通信聯(lián)盟