王 立,黃俊年,余 鑫,劉 娣

(1.華中師范大學(xué) 信息技術(shù)系,湖北 武漢 430079;2.華中科技大學(xué) 電子與信息工程系,湖北 武漢 430074)

0 引 言

近年來,由于IPTV直播、視頻監(jiān)控等應(yīng)用的需求,支持實時多媒體傳輸?shù)慕M播通信技術(shù)的研究和方案日益增多.IP層組播能夠在通信時保證在每一條網(wǎng)絡(luò)鏈路中只存在一份數(shù)據(jù)報文,能夠極大地節(jié)省網(wǎng)絡(luò)帶寬,但由于組播需要底層路由器進行全面的升級支持如DVMRP[1]和IGMP[2]等路由協(xié)議,在部署方面存在較大的困難[3],同時由于組播路由器要為每一個組播組維護路由狀態(tài)信息,擴展性不好;另外,組播的可靠性、QOS、擁塞控制等方面目前仍處于研究階段,因此IP組播并沒有得到廣泛應(yīng)用.

于是,出現(xiàn)了一些對IP層組播的替代方案[4-5].有研究者提出將對組播通信功能的支持從IP層的路由器轉(zhuǎn)移到終端系統(tǒng)中,由應(yīng)用層的終端系統(tǒng)來負(fù)責(zé)組成員管理、報文的復(fù)制和分發(fā),并稱之為應(yīng)用層組播[6]:Application Level Multicast或者Overlay Multicast.應(yīng)用層組播利用現(xiàn)有的網(wǎng)絡(luò)傳輸協(xié)議,并不需要網(wǎng)絡(luò)的底層路由和傳輸結(jié)構(gòu)作調(diào)整,不存在部署困難的問題.同時應(yīng)用層組播的路由路徑可以隨著網(wǎng)絡(luò)狀況的變化動態(tài)地調(diào)整,應(yīng)用程序也可以參與路由策略的制定,能實現(xiàn)IP組播所沒有的靈活性和擴展性.

1 應(yīng)用層組播ALM

IP應(yīng)用層組播通常有兩種實現(xiàn)方式:一種是將路由和傳輸功能放在參加組播通信的各個主機中,組成P2P的overlay網(wǎng)絡(luò);另一種則是由分布在網(wǎng)絡(luò)中的多個組播節(jié)點完成組播功能,每個節(jié)點可以為多個客戶端同時服務(wù).第一種方法可以做到完全分布,第二種方法則可以提高組的規(guī)模.

在應(yīng)用層組播組的管理方面,根據(jù)建立應(yīng)用層組播拓?fù)浣Y(jié)構(gòu)時采用的方案,可采用兩種管理方式:網(wǎng)狀優(yōu)先(mesh first)和樹狀優(yōu)先(tree first)[6].網(wǎng)狀優(yōu)先的系統(tǒng)會首先在節(jié)點上建立一個網(wǎng)狀的拓?fù)浣Y(jié)構(gòu),節(jié)點間按照某種路由協(xié)議來生成路由樹.網(wǎng)狀優(yōu)先的模式下,系統(tǒng)的拓?fù)浣Y(jié)構(gòu)是確定的,但是路由樹結(jié)構(gòu)是不確定的.樹狀優(yōu)先系統(tǒng)中,節(jié)點直接通過某種算法在樹形關(guān)系中選擇其各自的父節(jié)點,并檢測和避免環(huán)路的產(chǎn)生.網(wǎng)狀優(yōu)先的系統(tǒng)能通過重新選擇鄰居、更改拓?fù)潢P(guān)系的方式,在很大的范圍內(nèi)更新路由樹的結(jié)構(gòu).因此,在多源的系統(tǒng)中,網(wǎng)狀優(yōu)先系統(tǒng)相對更加穩(wěn)固,能更加靈活的對不同源建立不同的組播樹.

樹狀優(yōu)先的方案有ALMI[7]等,大規(guī)模的網(wǎng)狀優(yōu)先應(yīng)用層組播方案的代表有NICE[8]和Zigzag[9],它們對單個數(shù)據(jù)源組播的問題,都使用了“分層”(Hierarchical)和“分群”(Cluster)的思路.大部分組成員位于分層結(jié)構(gòu)的底層,并只和少量固定數(shù)目的節(jié)點存在聯(lián)系,這樣就大大降低了大部分組播成員的處理開銷.

2 MCR組播拓?fù)?/h2>

本文提出的組播環(huán)拓?fù)銶CR(Multicast Cross Rings)將應(yīng)用層組播節(jié)點以集群的方式管理起來,建成以“環(huán)”為基本集群單元的層次化管理拓?fù)浣Y(jié)構(gòu),并且在此拓?fù)浣Y(jié)構(gòu)基礎(chǔ)上建立組播路由樹.

2.1 樹狀層次拓?fù)?/h3>

MCR采用的層次化樹形結(jié)構(gòu)的管理拓?fù)?分兩個級別管理所有節(jié)點間的邏輯關(guān)系.第一級別是樹形拓?fù)?第二級別是環(huán)形拓?fù)?集群子系統(tǒng)).如圖1所示,每個樹形節(jié)點均為一個集群子系統(tǒng),每個集群子系統(tǒng)保持環(huán)狀拓?fù)涞亩鄠€節(jié)點.

圖1 樹狀的層次拓?fù)?/p>

MCR將節(jié)點組織為多個cluster,再以多叉樹的方式來組織多個cluster形成層次化結(jié)構(gòu),其中每個cluster均為采用環(huán)狀結(jié)構(gòu)組織的多個節(jié)點集合,如圖1(b)所示.

若用k表示每個cluster的最大下級cluster數(shù),則MCR是一個由多個cluster組成的k叉樹.MCR的層次拓?fù)潆S著節(jié)點的加入而逐漸擴展,節(jié)點首先嘗試加入頂層cluster,如果失敗則逐級向下尋找一個有空閑的cluster加入.

組建層次拓?fù)涞慕M織基本準(zhǔn)則包括:

(1)MCR是由多個cluster組成的k叉樹(k>=3),每個cluster最多有k個下級分支cluster;

(2)最先加入的2k個節(jié)點組成的cluster為MCR的頂點L0,后續(xù)加入的節(jié)點尋找L0的一個分支加入;

(3)每個cluster環(huán)最多可包含2k個節(jié)點,其中兩個節(jié)點為RP節(jié)點(互為備份的集中點),其他節(jié)點為普通節(jié)點(L0環(huán)沒有RP節(jié)點);

(4)任何一個節(jié)點最多可以同時屬于2個cluster環(huán),即兩個關(guān)聯(lián)(相交)的cluster最多有2個公共節(jié)點;

如圖2所示,新節(jié)點在L0下屬子環(huán)中尋找一個未滿的環(huán)如圖2(c)所示,或新建一個環(huán)如圖2(b)所法加入,形成共2層的拓?fù)?

圖2 拓?fù)浣M織過程示例(k=3)

Li表示某環(huán)在分層拓?fù)渲械膶泳幪?L0是最頂層的環(huán),也是一級樹形拓?fù)涞母?如果要保證一級拓?fù)錁涞钠胶庑?L0的位置可能被拓?fù)涔芾硭惴ǜ?

定義:RS表示一個環(huán),Ai為該環(huán)上所有節(jié)點,W(Ai)為節(jié)點的重量,普通節(jié)點的重量為2,RP節(jié)點X的重量計算方式為:

如圖3(b)所示,通過計算可知Li+2上RP節(jié)點的W為6,Li+1上RP節(jié)點的W為14,Li上RP節(jié)點的W為30.事實上W值也代表了該環(huán)及下屬環(huán)鏈所包含的總的節(jié)點數(shù).

定理:某環(huán)的RP節(jié)點的W即為該RS環(huán)及其下屬子環(huán)所含總的節(jié)點的數(shù)量.

圖3 節(jié)點與環(huán)的關(guān)系

2.2 層數(shù)與節(jié)點數(shù)的關(guān)系

若用N表示拓?fù)渲锌偟墓?jié)點數(shù),H表示層次拓?fù)涞膶訑?shù).如圖3(a)所示,滿環(huán)情況下,將每個環(huán)的RP節(jié)點僅在主環(huán)上統(tǒng)計一次,某頂層環(huán)節(jié)點數(shù)為2k,其下屬各個環(huán)的節(jié)點數(shù)均為2k-2,第i層的總環(huán)數(shù)為(k-1)i.則滿環(huán)情況下,H層拓?fù)淙菁{的最大節(jié)點數(shù)為:

(k-1)(2k-2)+…+(k-1)H-1(2k-2)=

令j=k-1,k>=3,即j>=2,則:

于是,節(jié)點數(shù)確定時的MCR最小層數(shù)為:

3 MCR拓?fù)渚S護

根據(jù)前面描述的拓?fù)浣M建原則,新節(jié)點加入時,首先找到L0環(huán),請求加入該環(huán),當(dāng)L0環(huán)上的節(jié)點數(shù)已達到2k時,如果L0沒有子環(huán)則新建一個,否則通過子環(huán)選擇算法在其k個下屬子環(huán)中選擇一個加入.

3.1 子環(huán)選擇

節(jié)點加入時,應(yīng)保證拓?fù)錁涞目倢訑?shù)最小、枝的數(shù)量最少,即樹最矮,從而使組播路由的跳數(shù)最小.此算法的節(jié)點加入拓?fù)涞捻樞驁D4所示,層次結(jié)構(gòu)中將依次填滿L0、所有L1、所有L2…….拓?fù)浒乃协h(huán)僅有一個環(huán)的節(jié)點數(shù)小于2k,每次節(jié)點加入的算法就是找到層次拓?fù)渲泄?jié)點數(shù)小于2k的這個環(huán),并加入該環(huán).

圖4 拓?fù)鋽U展方式

子環(huán)選舉算法如下:

(4)找到L0環(huán)上w最大且小于Nmax的節(jié)點Xm,新節(jié)點向該節(jié)點(即以其為RP的環(huán))發(fā)起加入子環(huán)的流程.(注:若所有w均為2將建立新環(huán).)

3.2 組播路由

應(yīng)用層組播分發(fā)的關(guān)鍵問題是節(jié)點度與路由深度的平衡.節(jié)點度的表示節(jié)點分發(fā)數(shù)據(jù)流時的輸出端連接數(shù),路由深度表示數(shù)據(jù)流從源端到達接收端經(jīng)過的轉(zhuǎn)發(fā)次數(shù).組播路由要保證數(shù)據(jù)報文通過組播數(shù)據(jù)源到達加入該組播組的各個節(jié)點,同時要保證達到不同的節(jié)點時的轉(zhuǎn)發(fā)的跳數(shù)受控,從而提高轉(zhuǎn)發(fā)效率.

如圖5(b)所示,一個組播源source節(jié)點發(fā)送組播數(shù)據(jù),有兩個destination節(jié)點希望接收該組播數(shù)據(jù),即加入該組播組.其中一個destination節(jié)點與source處于同一子環(huán)內(nèi),另一個destination節(jié)點位于另一個子環(huán).此時組播分發(fā)路徑為:source節(jié)點將數(shù)據(jù)流發(fā)送給其所在RM環(huán)的RP1節(jié)點,該RP1節(jié)點將流轉(zhuǎn)發(fā)給同一RS環(huán)內(nèi)的destination1節(jié)點,同時將流分發(fā)給上級RM環(huán)的RP2節(jié)點.RP2將數(shù)據(jù)流轉(zhuǎn)發(fā)給RP3,RP3將數(shù)據(jù)轉(zhuǎn)發(fā)給RP4,RP4將數(shù)據(jù)轉(zhuǎn)發(fā)給最終目的destination2.分發(fā)采用的路由樹如圖中箭頭所示,對于圖5中所示的3層拓?fù)?路由樹的最大深度為5.

圖5 組播分發(fā)路徑

4 MCR的性能分析

MCR的復(fù)雜度分析如下:

(1)每個節(jié)點可能存在于兩個環(huán)中,每個環(huán)有2k-1個鄰接點,所以節(jié)點的度最大值為

2(2k-1)-1=4k-3

平均度為

2k+1

而在滿環(huán)配置情況下,中間節(jié)點的度均為

4k-3

最外環(huán)節(jié)點的度均為

2k-1

因此總度和平均度分別為:

總度:

[2k+(k-1)(2k-2)+…+

(k-1)H-2(2k-2)](4k-3)+

(k-1)H-1(2k-2)(2k-1)=

平均度:

4k-3-2(j-1)=2k+1

(2)路由的跳數(shù)即轉(zhuǎn)發(fā)次數(shù)受控,因此組播分發(fā)的端到端延時受控為O(logN)級別.

因為總層數(shù)為

因此最壞情況的組播轉(zhuǎn)發(fā)跳數(shù)為

(3)加入和離開拓?fù)涞目刂崎_銷為拓?fù)涞膶訑?shù),即

O(logN)

5 結(jié) 語

MCR采用網(wǎng)狀優(yōu)先的拓?fù)浣M織形式,將節(jié)點組成局部cluster后,再將cluster建為一個層次化樹形拓?fù)浣Y(jié)構(gòu),并在此層次化樹形集群系統(tǒng)基礎(chǔ)上建立組播樹.這種拓?fù)浣Y(jié)構(gòu)適合穩(wěn)定節(jié)點的組網(wǎng),大量組播源數(shù)據(jù)源在共享拓?fù)渖辖⑵鸩煌脑唇M播最短路徑樹.拓?fù)涔芾碇泄?jié)點的離開和加入僅僅影響局部cluster內(nèi)的節(jié)點和少量上級節(jié)點,對網(wǎng)絡(luò)全局拓?fù)洳划a(chǎn)生影響.并且通過設(shè)置兩個RP節(jié)點的方式保證節(jié)點失效時的業(yè)務(wù)連續(xù)和快速恢復(fù).

MCR采用與NICE和Zigzag類似的層次化拓?fù)?將節(jié)點組成多個小集群系統(tǒng),將小集群系統(tǒng)構(gòu)建成層次化拓?fù)?并在拓?fù)浠A(chǔ)上建立組播路由樹.與NICE和Zigzag不同的是,MCR中的節(jié)點自上而下加入層次化拓?fù)?而且節(jié)點最多同時出現(xiàn)在兩個相鄰的層中,因此最多需要維護的鄰接關(guān)系為4k-3.NICE和Zigzag中,節(jié)點自下而上加入拓?fù)?并且節(jié)點可以同時出現(xiàn)在多個層中.

MCR能提供基于應(yīng)用層組播的S2S服務(wù)對等網(wǎng)絡(luò),網(wǎng)絡(luò)的節(jié)點都是服務(wù)器.客戶端可以通過任何一個節(jié)點接入,從而可以訪問到整個網(wǎng)絡(luò)的資源,即資源是由整個網(wǎng)絡(luò)提供的.

參考文獻:

[1]Waitzman D,Partridge C, Deering S. Distance Vector Multicast Routing Protocol[S].RFC 1075,Internet Engineering Task Force,1988.

[2] Fenner W.Internet Group Management Protocol,version 2[S].IETF RFC 2236,Internet Engineering Task Force,1997.

[3]Diot C,Levine B N,Lyles B,et al.Deployment Issues for the IP Multicast Service and Architecture[J].IEEE Network Mag,2000,14(1):78-88.

[4]El-Sayed A, Roca V, Mathy L.A Survey of Proposals for an Alter-native Group Communication Service[J].IEEE Network Mag,2003,17(1):46-51.

[5]劉書,潘成勝,張德育.Mobile Agent在網(wǎng)絡(luò)系統(tǒng)監(jiān)控中數(shù)據(jù)采集的設(shè)計與應(yīng)用[J].武漢工程大學(xué)學(xué)報,2010,31(3):77-80.

[6]Hosseini M, Ahmed D T, hirmohammadi S, et al.A Survey of Application-Layer Multicast Protocols[J].IEEE Communications Surveys & Tutorials,2007,9(3):58-74.

[7]Pendarakis D, Shi S, Verma D, et al.ALMI:An Application Level Multicast Infrastructure[A].Proceedings of the 3rd conference on Usenix Symposium on Internet Technologies and Systems[C].San Francisco:USENIX Association,2001:49-60.

[8]Tran D A, Hua K A, Do T T.A Peer-to-Peer Architecture for Media Streaming[J].IEEE JSAC,2004,22(1):121-33.

[9]Banerjee S, Bhattacharjee B, Kommareddy C.Scalable Application Layer Multicast[A].Proceedings of the 2002 conference on Applications,technologies,architectures,and protocols for computer communications[C].College Park: ACM,2002:205-17.