一種基于層次結構的可擴展應用層組播模型

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

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

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

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

1 基于層次結構的應用層組播模型

對于組播節點而言,采用多描述編碼技術不需要考慮描述的接收次序,因此特別適合于動態的網絡環境。基于層次結構的應用層組播模型RSA中采用該技術對節目內容進行編碼,并以此構建多樹的組播模型。

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

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

圖1 多樹模型的數據傳輸

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

2 模型設計

RAS模型結構如圖2所示,主要由描述資源的均勻分布算法和資源請求的最大覆蓋算法、組播過程中節點的加入、數據傳輸的優化和對節點失效的恢復等幾部分組成。

圖2 RSA模型結構圖

2.1 描述資源均勻分布優化算法

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

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

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

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

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

圖3 均勻分布算法中的數據結構

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

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

節點以Req_MX和Scan_MX為參數調用MAXC算法生成最大資源的覆蓋以及對應的請求,如圖3(a)所示。

2.2 節點加入

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

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

2.3 數據傳輸優化

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

2.4 節點失效時的視頻質量恢復

當發生節點失效時,系統按照以下步驟對視頻質量進行修復:

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

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

3)根據數據傳輸過程中的優化方法為節點生成新的請求集。

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

3 仿真試驗

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

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

在試驗的前500s內拓撲節點數量按指數遞增,從16增加到512,在系統穩定后的600～1100s內,每隔100s隨機安排16個節點離開,用來模擬在節點失效時數據接收率的變化。

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

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

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

圖4 節點加入時的平均數據接收率

4 結 語

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

圖5 節點失效時的平均數據接收率

圖6 節點加入時的平均鏈路強度

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

[2]黃偉紅,孫正興,張福炎.Internet視頻流中的自適應擁塞控制技術研究 [J].計算機學報,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]肖友能,薛向陽,曾瑋.視頻轉碼技術回顧 [J].通信學報,2002,23(8):72～80.

[8]李彬,黃峰,孫立峰,楊士強.一種魯棒靈活的非平衡多描述視頻編碼和傳輸方案 [J].計算機學報,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.