一種基于層次結(jié)構(gòu)的可擴展應(yīng)用層組播模型

張有為 (長江大學(xué)計算機科學(xué)學(xué)院,湖北荊州434023)

雖然應(yīng)用層組播技術(shù)的應(yīng)用日益廣泛,但是其缺點也比較明顯,主要在于可靠性不高,并且缺乏網(wǎng)絡(luò)擁塞控制機制[1～2]?；?“單數(shù)據(jù)流”的應(yīng)用層組播協(xié)議,如 Narada[3]、HMTP[4]、NICE[5]、DONet[6]等可以解決應(yīng)用層組播某一方面的問題,但是無法兼顧系統(tǒng)的可擴展性和健壯性。

采用多描述編碼MDC(Multiple Description Coding,MDC)技術(shù)[7～8]的組播協(xié)議CoopNet[9]和SplitSream[10]通過多路并發(fā)傳輸?shù)姆绞捷^好地平衡了組播系統(tǒng)的可擴展性和健壯性。但多樹模型卻無法有效解決描述的同步問題,從而無法獲得較高的圖像質(zhì)量。此外,節(jié)點在加入系統(tǒng)時,多樹結(jié)構(gòu)的的控制開銷要遠大于單樹結(jié)構(gòu)。

為此,筆者充分考慮節(jié)點的異構(gòu)性以及節(jié)點失效而對性能造成的影響,提出了一種基于層次結(jié)構(gòu)的應(yīng)用層組播模型-RSA。RSA采用多描述編碼技術(shù)對媒體數(shù)據(jù)編碼,并以此構(gòu)造多樹的分層結(jié)構(gòu)模型,采用分布式算法實現(xiàn)了節(jié)點中描述資源和對資源請求的均勻分布,以提高流媒體系統(tǒng)的健壯性和可擴展性。

1 基于層次結(jié)構(gòu)的應(yīng)用層組播模型

對于組播節(jié)點而言,采用多描述編碼技術(shù)不需要考慮描述的接收次序,因此特別適合于動態(tài)的網(wǎng)絡(luò)環(huán)境。基于層次結(jié)構(gòu)的應(yīng)用層組播模型RSA中采用該技術(shù)對節(jié)目內(nèi)容進行編碼,并以此構(gòu)建多樹的組播模型。

RSA給出了一種基于多樹的分層結(jié)構(gòu)模型,這種結(jié)構(gòu)很好地解決了描述之間的同步問題,實現(xiàn)了節(jié)點的快速加入,并提高了圖像質(zhì)量。此外,RSA還提出了基于資源均勻分布的最大覆蓋算法MAXC-通過將節(jié)點對描述的請求均勻地分布在最多的父節(jié)點以實現(xiàn)模型的健壯性,同時也有利于實現(xiàn)圖像質(zhì)量快速恢復(fù)。

如圖1所示,節(jié)目內(nèi)容在源節(jié)點S被編碼成3個描述(D1,D2,D3),節(jié)點之間的可用帶寬按照式(1)映射成描述碼率的倍數(shù)Weight(其中SubDescription和Avail_BW分別為單個描述的碼率和節(jié)點間的可用帶寬):

圖1 多樹模型的數(shù)據(jù)傳輸

例如A→D之間的帶寬權(quán)值為3,表示D可以從A獲取3個描述。如圖1(a)所示,節(jié)點D可以從父節(jié)點集{A}、{A,B}、{A,C}或{A,B,C}中均能獲得最大的描述集(D1,D2,D3)。但是,只考慮圖像質(zhì)量這一個方面無法保障系統(tǒng)的健壯性。MAXC算法將對最大描述集的請求均勻地分布在最大的父親集中,從而保證在節(jié)點失效的情況下不至于出現(xiàn)圖像質(zhì)量的劇烈抖動。圖1中的節(jié)點D選擇{A,B,C}作為其父親集,并根據(jù)加權(quán)的MAXC算法將對(D1,D2,D3)的請求均勻地分布在3個父節(jié)點上。

2 模型設(shè)計

RAS模型結(jié)構(gòu)如圖2所示,主要由描述資源的均勻分布算法和資源請求的最大覆蓋算法、組播過程中節(jié)點的加入、數(shù)據(jù)傳輸?shù)膬?yōu)化和對節(jié)點失效的恢復(fù)等幾部分組成。

圖2 RSA模型結(jié)構(gòu)圖

2.1 描述資源均勻分布優(yōu)化算法

多樹組播模型在動態(tài)環(huán)境中有較好的健壯性,但是,如果描述資源在父節(jié)點中的分布不均勻,卻會造成對擁有豐富描述資源節(jié)點的過度依賴,進而在節(jié)點失效時產(chǎn)生圖像質(zhì)量的劇烈抖動。如圖 1(a)所示,當(dāng)節(jié)點A失效時,圖像質(zhì)量會下降,且無法依靠節(jié)點B、C(不包含描述D3)中已有的描述資源來進行恢復(fù),只能重新搜索新的父節(jié)點來進行圖像質(zhì)量的恢復(fù),但會產(chǎn)生較大的延遲。因此,筆者提出了一種描述資源均勻分布的方案,以此來提高動態(tài)網(wǎng)絡(luò)中的圖像質(zhì)量。

由圖1(a)可知,描述資源的分布比例為:D1＞D2＞D3。如果節(jié)點C不再請求D1而是D3,則會形成如圖1(b)所示的分布比例:D1=D2=D3,均勻分布。則節(jié)點D請求父親集{A}、{A,B}、{A,C}、{B,C}、{A,B,C}中的任一集合均能獲得最大的描述集;與此同時,當(dāng)節(jié)點D的父節(jié)點集{A,B,C}中任一節(jié)點的失效時,仍然可以通過調(diào)用MAXC算法來重新調(diào)整對父節(jié)點的描述請求,從在線的父節(jié)點中請求最大描述集,從而在不降低圖像質(zhì)量的情況下實現(xiàn)節(jié)點的無縫切換和快速恢復(fù)。

為實現(xiàn)描述資源在各層節(jié)點中的均勻分布,需要為節(jié)點中的描述設(shè)定屬性參數(shù) RefCount-“引用計數(shù)”。節(jié)點應(yīng)優(yōu)先請求父節(jié)點中RefCount的描述。圖3(a)所示為節(jié)點C(假設(shè)C在A,B之后加入組播樹)根據(jù)父親集信息生成的請求矩陣Req_MX,其中,Res_set為父節(jié)點中的描述資源,請求集 Req_set初始化為NULL。圖3(b)顯示父節(jié)點中描述資源的引用情況,其中D3的RefCount在C加入前為1,C加入后向S請求D3描述,其RefCount更新為2。圖3(c)顯示按以下規(guī)則生成所生成的掃描矩陣Scan_MX:

1)Res(描述資源)按照RefCount升序排列;

2)若RefCount相同,則按Res在所有父節(jié)點中的資源數(shù)量的升序排列;

圖3 均勻分布算法中的數(shù)據(jù)結(jié)構(gòu)

3)Pat(父節(jié)點)按擁有資源數(shù)量的升序排列;

4)矩陣中(i,j)為 “1” 表示Pat擁有 Res;“0”則表示Pat沒有 Res。

節(jié)點以Req_MX和Scan_MX為參數(shù)調(diào)用MAXC算法生成最大資源的覆蓋以及對應(yīng)的請求,如圖3(a)所示。

2.2 節(jié)點加入

為了避免節(jié)點失效造成過大的圖像質(zhì)量抖動,系統(tǒng)中節(jié)點的最大入度和出度設(shè)定為K(K為節(jié)目編碼的描述個數(shù))。當(dāng)節(jié)點加入組播樹時,從服務(wù)器獲取K個度小于K且Weight≥1的節(jié)點信息作為父親集。節(jié)點根據(jù)父親集信息生成請求矩陣Req_MX和Scan_MX作為MAXC算法的參數(shù),其偽代碼如下:

節(jié)點根據(jù)由MAXC算法生成的請求集向父節(jié)點請求資源請求描述,如圖1(b)所示,節(jié)點D的請求集為(A(D1),B(D2),C(D3))。

2.3 數(shù)據(jù)傳輸優(yōu)化

節(jié)點在加入組播后,需不斷調(diào)整父親集、更新請求集以提高系統(tǒng)的性能。其更新的基本思想為:①當(dāng)節(jié)點加入組播樹后,通過繼續(xù)搜索新的父節(jié)點來請求加入時所缺描述資源,以獲得最佳視頻質(zhì)量;②繼續(xù)為節(jié)點搜索最大請求集,若對某個父節(jié)點的描述請求數(shù)量大于1,則將其分裂為多個單一的描述請求,即將對K個描述的請求均勻地分配到K個父節(jié)點上。

2.4 節(jié)點失效時的視頻質(zhì)量恢復(fù)

當(dāng)發(fā)生節(jié)點失效時,系統(tǒng)按照以下步驟對視頻質(zhì)量進行修復(fù):

1)將離線的父節(jié)點從Req_MX刪除。

2)調(diào)用MAXC算法,對在線父節(jié)點中的資源請求重新分配。

3)根據(jù)數(shù)據(jù)傳輸過程中的優(yōu)化方法為節(jié)點生成新的請求集。

由于實現(xiàn)了描述資源和描述請求的均勻分布,在2)中,實現(xiàn)視頻質(zhì)量的無縫切換是大概率事件;通過3)中的優(yōu)化策略,節(jié)點能實現(xiàn)請求集的快速更新,能避免了圖像質(zhì)量的劇烈抖動。

3 仿真試驗

采用流行的網(wǎng)絡(luò)仿真器NS2對RSA模型進行仿真,對平均數(shù)據(jù)接收率 (Mean Receiving Rate,MRR)、平均恢復(fù)時間 (Mean Recovery Time,MRT)、平均鏈路強度 (Mean Link Stress,M LS)進行評估。

試驗中,將RSA和CoopNet進行對比。使用通用的網(wǎng)絡(luò)拓撲生成器GT-ITM生成 transit-stub類型的物理網(wǎng)絡(luò)拓撲,并且將碼率為300Kbps的媒體數(shù)據(jù)編碼成4個描述,服務(wù)器的度設(shè)定為64,節(jié)點度為4,節(jié)點之間的可用帶寬分布為200～400Kbps。

在試驗的前500s內(nèi)拓撲節(jié)點數(shù)量按指數(shù)遞增,從16增加到512,在系統(tǒng)穩(wěn)定后的600～1100s內(nèi),每隔100s隨機安排16個節(jié)點離開,用來模擬在節(jié)點失效時數(shù)據(jù)接收率的變化。

圖4表明,隨著節(jié)點的增加,CoopNet的MRR出現(xiàn)了的比較明顯的下降,但是RSA的MRR卻沒有顯著的變化,并且比CoopNet高出約20%。

圖5顯示,在節(jié)點失效時RSA中圖像質(zhì)量的抖動約為15%,而CoopNet達到了30%;另一方面,圖4顯示RSA在節(jié)點失效時,其MRT為20s,而CoopNet則為40s。

由于資源的均勻分布降低了鏈路的強度,圖6顯示,在0～500s內(nèi),RSA的MLS要比CoopNet的低20%。

圖4 節(jié)點加入時的平均數(shù)據(jù)接收率

4 結(jié) 語

筆者所提出RSA模型采用MAXC算法提高了節(jié)點的視頻接收質(zhì)量,實現(xiàn)了節(jié)點失效時視頻質(zhì)量的快速恢復(fù)。試驗證明,RSA具有很好的健壯性和可擴展性。

圖5 節(jié)點失效時的平均數(shù)據(jù)接收率

圖6 節(jié)點加入時的平均鏈路強度

[1]羅萬明,林闖,閻保平.TCP/IP擁塞控制研究[J].計算機學(xué)報,2001,24(1):1～18.

[2]黃偉紅,孫正興,張福炎.Internet視頻流中的自適應(yīng)擁塞控制技術(shù)研究 [J].計算機學(xué)報,2001,24(8):797～801.

[3]Chu Yanghua,Sanjay Rao,Zhang Hui.A Case For EndSystem Multicast[A].Selected Areas in Communications[C].Santa Clara,CA:IEEE June,2000.1456～1471.

[4]Zhang B,Jamin S,Zhang L.Host multicast:A frame work fo r delivering multicast to end users[A].T wenty-First Annual Joint Conference of the IEEE Computer and Communications Societies[C].California,US:IEEE June,2002.1366～1375.

[5]Suman Banerjee,Bobby Bhatacharjee,Christopher Kommareddy.Scalable Application Layer Multicast[A].Consumer Communications and Networking Conference[C].Karlsruhe,Germany.IEEE:Jan,2002.43～51.

[6]Zhang X,Liu J,Li B,et al.CoolStreaming/DoNet:A data-Driven Overlay network for peer-to-peer live Media Streaming[A].24th Annual Joint Conference of the IEEE Computer and Communications Societies[C].Miami,FL:IEEE.March,2005.2102～2111.

[7]肖友能,薛向陽,曾瑋.視頻轉(zhuǎn)碼技術(shù)回顧 [J].通信學(xué)報,2002,23(8):72～80.

[8]李彬,黃峰,孫立峰,楊士強.一種魯棒靈活的非平衡多描述視頻編碼和傳輸方案 [J].計算機學(xué)報,2008,31(7):1155～1164.

[9]Padmanabhan V,Wang H,Chou P,et al.Distributing streaming media content using cooperative networking[J].IEEE Transactions on Multimedia,2002,8(2):233～242.

[10]Castro M,D ruschel P,Kermarrec A M,et al.Split Stream:High-bandwidth content distribution in a cooperative environment[J].IEEE Transactions on Knowledge and Data Engineering,2003,20(9):1273～1281.