一種節點高穩定狀態的應用層組播方案

崔建群 ,馬 媛, 常亞楠, 吳黎兵

1(華中師范大學 計算機學院, 武漢 430079 )2(武漢大學 計算機學院, 武漢 430072)

1 引 言

近年來，由于IPTV直播，視頻點播等應用的需求，使得多媒體傳輸的組播技術研究日益發展.組播(Multicast)是滿足一點對多點通信需求的一種全新高效的技術，將源節點數據流的副本以多路復用的方式通過網絡發送到一組接受者[1]，而源節點只需產生并發送一份數據流，經過組播樹中路由器的復制與轉發，將數據流傳送到一組目的節點.

IP組播是網絡層組播[2]，在通訊時保證在網絡鏈路中只存在一份數據報文，因此可大量節省服務器成本與網絡帶寬，通過路由器來進行組播數據的復制和轉發，減輕了服務器的負擔和視頻傳輸時延等問題.但是IP組播仍然存在較多并未解決的缺陷.例如組成員管理，組播擁塞控制以及難以部署等問題，圖1(a)是IP組播.取而代之的是逐漸興起的應用層組播(application layer multicast，ALM)[3,4]，應用層組播將組播功能由網絡層轉移到終端，由終端主機進行數據分發，而節點

DataPackageLinkrouterserverrouterrouterrouter(a) 網絡層組播DataPackageLinkserverrouterrouterrouterrouter(b) 應用層組播

圖1 組播類型
Fig.1 Multicast classification

間的數據傳輸則通過傳統的單播技術來實現，如此便解決了IP組播部署困難的問題，實現了組播的靈活性與擴展性，圖1(b)是應用層組播.

對于應用層組播，端系統的穩定性與性能不如路由器，這就造成了應用層組播在穩定性與效率上不如網絡層組播.由于組播樹的性能會影響轉發數據的效率，所以端節點的穩定狀態與其在組播樹中的位置直接關系到組播樹的整體表現，本文針對以上問題設計了一種基于節點穩定狀態的應用層組播方案.

2 相關工作

在已有的組播樹構造算法中，組播協議分為集中式算法與分布式算法，分布式算法又分為網優先算法、樹優先算法與隱含式算法.

集中式算法由集中控制點RP(Rendezvous Point)負責收集成員節點的網絡信息，并周期性計算應用層組播樹.RP負責數據分發，易于維持組播樹的一致性，但容易單節點負載過重并且擴展性差，適用于小規模、多數據源情況，典型協議有ALMI[5]與HBM[6].

圖2 基于網狀的應用層組播樹結構Fig.2 Data structure of mesh-basedoverlay multicast

分布式算法組播樹構造與維護依賴于各個節點維護的局部信息，因此具有良好的擴展性.網優先算法將節點分布式自組織成Mesh，Mesh中各個節點都要維護全部或者部分成員狀態信息，來迅速恢復網絡分割，并運行組播路由協議.其優點是組成員管理、負載均衡與數據傳輸效率高，缺點是復雜度較高，維護代價比較大與有限的擴展性.典型協議有Narada[7]、PRO[8]和Prime[9]等.基于網狀的應用層組播數據結構如圖2所示，其中節點A是組播源節點.

圖3 基于樹狀的應用層組播樹結構Fig.3 Data structure of tree-based overlay multicast

樹優先算法是成員節點直接在組內選擇父節點構建組播樹，與非鄰居節點建立并維護控制鏈接，其優點是用戶節點便于直接控制，缺點是進行單獨的檢測與回路避免處理.典型協議有TBCP[10]、Overcast[11]、PROMISE[12]等，基于樹狀的應用層組播數據結構如圖3所示，其中節點A是組播源節點.隱含式算法在構造控制拓撲與數據拓撲方面沒有先后次序之分，節點之間也沒有其余交互信息，控制拓撲中隱含著數據拓撲.其優點是大幅度降低組播成員的處理開銷，具有良好的擴展性.典型協議有NICE[13]、ZIGZAG[14]、Scribe[15]等.

文獻[20]提出一種基于gossip的應用層組播方案，將數據分發過程分為上層分發以及底層簇內分發兩個階段.該方案具有較高的數據分發成功率，但增加了控制開銷.已有的研究協議大多針對某一特定應用，在特定的前提下以生成最小延時組播樹為目標，由于網絡的易構性以及終端節點用戶的不穩定性，必須綜合考慮節點性能以及所在位置對組播樹的影響.已有的研究協議大多針對某一特定應用，在特定的前提下以生成最小延時組播樹為目標，由于網絡的易構性以及終端節點用戶的不穩定性，必須綜合考慮節點性能以及所在位置對組播樹的影響.

針對節點穩定狀態與延時的問題，我們抽象出一種合理的問題模型-T-DTD (Spanning tree based on degree-constrained, max on-session time and depth bound for ALM) 模型.在應用層組播樹生成過程中，該模型綜合考慮了終端節點的轉發能力與在線時長，以及節點所在組播樹中位置這三個因素，構造高穩定性、低延時應用層組播樹.

3 T-DTD模型及相應的概念

3.1 組播樹穩定性

節點的穩定狀態對組播樹的穩定性有至關重要的作用.從節點的行為屬性來看，在線時間越長的節點、位于組播樹中越高層位置的節點，組播樹越穩定；從節點度的角度看，組播樹中間節點轉發能力越強組播樹越穩定.文獻[16]用穩定度來衡量組播系統的穩定性，應用層組播穩定度定義為公式(1).

(1)

并由此推出公式(2).

(2)

1)直接將帶寬與節點已在線時間乘積值作為節點所在的位置，而沒有考慮在實際問題中帶寬與已在線時間對組播樹穩定性影響權重比例問題；

圖4 完全無向圖Fig.4 Complete undirected graph

2)Tan默認高度低的組播樹延遲小，但是對應用層組播樹而言可能不正確.因此，要提高應用層組播樹穩定性，既要綜合考慮節點度與在線時間，還要考慮它們對組播樹穩定性影響的權重問題.

3.2 組播路由問題描述

T-DTD問題模型：在組播路由問題中，通訊網絡通常用完全無向圖G(V,E)表示，如圖4，其中V是待加入節點集合，E是路徑集合，算法過程是由圖G生成樹T，將G中的節點及相關邊加入到T中.

定義1.節點度是衡量一個節點轉發能力的指標.B(vi)為節點vi的上行帶寬，R為流媒體播放速度，節點在加入組播樹時帶有自己的出度，根據數據流的狀態可以計算節點出度.節點vi的出度定義為節點上行帶寬與流媒體傳輸速率的比值，可用公式(3)表示.

Deg(vi)=B(vi)/R

(3)

定義2.節點深度表示節點所在組播樹中的層次，根節點層次為1.若根節點不空時深度記為1；若根節點為空時則深度記為0，在此模型中都假設根節點不空.節點的深度可表示為公式(4).

(4)

定義3. 在應用層組播樹中，所有節點組成集合V，V(T)={v1,v2,…,vn-1,vn}，n為組播樹中節點個數，則組播樹T的平均深度按公式(5)所示.

(5)

定義4.節點在線時間表示從節點成功加入到組播樹的時間到當前時刻的時間段，在線時間越長，表示節點繼續停留平均時間也越大，節點退出概率越小.節點的在線時間可用公式(6)表示，其中Tjoin(vi)表示節點vi的請求加入時間，t表示當前時間.

Ton-session(vi)=t-Tjoin(vi)

(6)

定義5.節點穩定度因子(Nodedegreeofstability,NSD)是表示節點穩定狀態的指標，NSD越大，表示節點越穩定，節點越穩定，組播樹性能越好.節點vi(1≤i≤n)的出度Deg(vi)，節點在線時間Ton-session(vi)，則公式(7)可表示節點的穩定度因子.

(7)

其中?為穩定度因子權重系數，根據不同的應用環境權重系數取不同的值.Bishop和Rao等人研究異構環境中組播樹穩定性問題[19]，實驗結果顯示，基于節點度的策略優勢明顯優勝于基于節點已在線時間的策略，基于節點在線時間的策略中，節點頻繁的更改自己的位置，其優勢不明顯.因此在綜合計算節點穩定度因子時，這里設置度所占權重?為大于0.5小于等于1的實數.

4 基于節點穩定狀態的組播方案

為了更好地對算法進行說明，本文將組播樹中已有節點用三元組N(T,Deg,C)信息來表示，如圖5所示.其中T表示節點在線時間，Deg表示節點的轉發能力，C為候選父節點集合.實線部分表示已構建的組播樹，虛線部分表示待加入節點有可能的位置.在構建組播樹的過程中，節點候選位置集合為ST={E,F,G,H}.

4.1 組播樹的建立

本文將解決T-DTD(Spanning tree based on degree-constrained, maxon-session time and depth bound for ALM)問題模型的算法定義為DTD-H(DTD-heuristic)算法.DTD-H基本數據結構與具體算法可以描述如下：

m為組播樹中小于平均節點深度的節點數目.

圖5 組播樹
Fig.5 Multicast tree

臨時集合(Templeset,TS)：記錄組播樹中深度小于等于平均樹深度并且具有度剩余的節點集合，TS={v1,v2,…,vm-1,vm}.

候選父節點優先級集合(priority set of candidate parents,CPPS)：記錄可以納入新孩子節點的節點集合，并按照節點穩定度因子降序排序.

輸入：G(V,E)，圖中每個節點帶有出度Deg(Vi)，深度Dep(Vi) ，以及節點在線時間.

輸出：樹T.

初始化待求樹T=φ，將源節點s納入到樹T中.

1) 計算組播樹平均深度Depavg(T)，圖5中Depavg(T)=(1+2+2+2+3)/5=2.

2) 取V′中深度不大于?Depavg(T)」 且有剩余出度的節點位置得到集合TS，如果所有候選位置深度都大于?Depavg(T)」，則取深度最小的候選位置得TS.

3) 計算TS中的候選父節點的節點穩定度因子NSD，并按照節點穩定度因子大小降序排序得CPPS.

4) 取CPPS中穩定度因子最大的節點作為待加入節點N的最佳候選父節點.每成功加入一個節點，候選父節點度減少1.

5) 實時更新修改集合TS、CPPS.

算法偽代碼如下：

DTD-H Algorithm

Input：G(V,E),for anyv∈V

Output：T(V,E′)

Procedure:

1)T=φ;TS=φ.

2)V(T)←s;

3)TS←{s};

5)FOR each node in V′

6)IF node′s out-degree is not full and node′s depth≤?Depavg(T)」

7)TS←v.

8) END IF

9) END FOR

10) FOR each node inTS

11) calculateNSDof each node and sort the nodes ofCPPS

12) father←select the first node ofCPPS

13) out-degree[father]= out-degree[father]-1.

14) updateTSandCPPS

15) END FOR

16) END WHILE

4.2 組播樹的維護

4.2.1 組播樹調整

在文獻[17]中，對視頻日志進行統計分析，驗證了用戶在線時間符合對數正態分布，并指出用戶剩余在線時間隨著用戶在線時間增大而增大.本文對文獻[17]中統計數據進行分析，將節點分為以下三類：當節點在線時間小于200秒時，有超過70%的節點會在連接后的200秒內選擇退出，為保證組播樹的穩定狀態，應當使該節點遠離根節點；在線時間在200秒到2000秒之間的節點，對降低節點的退出概率相比第一類節點已有較大提升；而在線時間超過2000秒的節點，其剩余在線時間在10的三次方數量級以上，節點已處于相對穩定的狀態，所以為保證組播樹的穩定狀態，應當使該節點靠近根節點.

節點不僅要維護自己的信息，還要保存孩子節點的信息.當新節點加入組播樹后，分別計算父節點與子節點的NSD值，當父節點的穩定度因子小于子節點的穩定度因子時，則將父節點與子節點進行交換.本文將節點交換的周期設置為200秒，即每隔200秒對組播樹內的節點進行動態維護.

4.2.2 節點離開

節點離開組播樹有兩種方式：友好離開方式，將離開消息通知給父節點與子節點；意外離開方式，由于外在故障原因未能將離開消息告知父節點與子節點.

當節點離開時，非葉子節點的離開會導致其子孫節點離開組播樹從而中斷數據傳輸，最簡單的一種解決方法是使中斷連接的節點重新申請加入到組播樹中，但是這樣會花費較多時間，降低組播樹的服務質量，因此針對以上兩種節點離開方式，本文分別給出兩種快速恢復組播樹機制.設F(A)為A的父節點，C(A)為A的孩子節點集.

1)友好離開

當節點A離開時，告知父節點F(A)與子節點C(A)自己將要離開的消息，F(A)收到離開消息后將A的有關信息刪除，C(A)收到A的離開消息后則將C(A)中節點按照NSD值排序.因為A節點的離開，F(A)一定有空余出度，然后將C(A)中排序后的節點依次作為F(A)的子節點.若C(A)中還存在子孫節點，則剩余節點以集合中NSD值最大的節點作為父節點加入組播樹.

2)意外離開

這種情況下A離開時，并未告知父節點F(A)與子節點C(A).子節點在一段時間未收到A節點發送的數據，則向A節點發送心跳探測消息.若A節點回應則說明節點仍然在組播樹上，無需進行任何操作；若A一段時間未回應則說明A節點已失效，C(A)將A失效已離開的消息告知F(A)，后續操作和節點友好離開組播樹的處理方式相同.

5 仿真實驗

本文將通過仿真實驗對比DTD-H算法與NICE算法和度優先算法以及隨機算法在平均加入時延、最大加入時延和鏈路伸展度這三方面性能.NICE[13]協議是一種典型的分層分簇的應用層組播協議，它可以支持大量不同的數據轉發樹，有較強的可擴展性.度優先算法[19]是優先考慮有最大度的節點并且以最大度節點為父節點加入新節點的過程.隨機算法是隨機選擇組播樹中仍有剩余出度的節點將新節點加入組播樹的過程.

5.1 仿真實驗的環境

為了驗證DTD-H算法的性能，本節對算法進行實驗.這里使用OMNet++作為模擬環境，以OverSim[21]為基礎進行代碼編寫和模擬實驗.

OMNet++是Objective Modular Network Testbed in C++的縮寫，是一個免費且開源的網絡環境模擬軟件，其通過對基礎底層網絡事件的模擬可以精確的復現出近似實際網絡的結果.而OverSim則是基于OMNet++實驗環境的一套覆蓋網絡模擬框架，該框架包含了基本的組播覆蓋網絡實現算法，為實現自定義的各種覆蓋網絡算法提供了較為便利的開發環境.通過復用OverSim的部分代碼，可以很容易的開發并設計出自己想要的覆蓋網絡模型.該仿真器可以運行于 Linux和Windows 等多個平臺.圖6是節點數目為150時，DTD-H算法的模擬仿真架構圖.

圖6 模擬仿真架構圖Fig.6 Simulation framework diagram

5.2 實驗參數設置

下列是對實驗中相關參數的設置情況：

1)節點的出度代表著節點的轉發能力，節點的最大出度表現為該節點能夠容納孩子節點的最大數目.根據文獻[22,23]中采用的實驗參數，本文在仿真實驗中采用節點的最大出度degmax(vi)服從整數區間[2,6]之間的均勻分布；

2)在文獻[17]中，對視頻日志進行統計分析時，當節點在線時間小于200秒時，有超過70%的節點會在連接后的200秒內選擇退出，為保證組播樹的穩定狀態，因此在實驗中設置組播樹更新調整維護周期為200s.

5.3 性能指標

平均加入時延：當新的節點要加入組播樹中時，在組播樹中找到最合適的父節點，并且向父節點發送加入請求，父節點發出回應后才能順利加入.從開始找父節點到最后順利加入到組播樹中所花費的時間的平均值.加入時延越小，新節點就能越迅速加入到組播樹中，也就能更快接收到數據.假設vi節點發送加入請求時刻為t0，父節點發送回應消息的時刻為t(vi)，組播樹中節點總數為n，則平均加入時延tave的計算如公式(8)所示.

(8)

最大加入時延：新節點在加入組播樹的過程中，在組播樹中找到最合適的父節點，向父節點發送加入請求后才能順利加入.假設vi節點發送加入請求時刻為t1，父節點發送回應消息的時刻為tmax，則最大加入時延的計算如公式(9)所示.

tdelay=tmax-t1

(9)

平均鏈路伸展長度：對于組播樹中的每個成員節點，數據從數據源經過其他節點轉發到達該節點所走過的路徑長度，是衡量組播數據路徑質量的主要標準.設數據從數據源經過其他節點轉發到節點vi所走過的路徑長度為Leg,則平均鏈路伸展長度的計算公式如公式(10)所示.

(10)

5.4 仿真結果分析

將DTD-H算法與Nice算法、度優先算法、隨機算法在平均加入時延、最大加入延時與平均鏈路伸展長度方面對比.

圖7統計了當節點數目為10～150時，節點加入到組播樹中所需要的平均時間，當節點數目為10的時候，度優先算法在比較少的節點里可以快速找到有最大度的父節點，度優先算法加入時延比DTD-H算法快0.02s，比NICE協議快0.05s，加入時延會優先于其余三個算法.但是在節點數目逐漸增多時，NICE算法在由上至下每次尋找最近的成員會需要較多時間，而隨機算法在組播樹中隨機加入有剩余度的節點.當節點數目為100時，DTD-H算法的平均加入時延為0.15s，明顯小于NICE協議的0.43s和隨機算法的0.42s，因此DTD-H算法的平均加入時延會優于隨機算法與NICE算法；度優先算法在所有節點中選出最大度的節點的過程，而DTD-H算法只在滿足穩定狀態的節點集合中選擇父節點，DTD-H算法的平均加入時延小于度優先算法0.02s，隨著節點個數越來越多，DTD-H算法在減少節點加入時延方面相對于度優先算法的優勢也越來越大.

圖7 平均加入延時與節點數目的關系圖Fig.7 Relation graph of average delay of the spanning tree and the number of nodes

圖8統計了當節點數目為10～150時，節點加入到組播樹中所需要的最大時延.當節點數目為10～20之間時，四種算法在最大加入時延方面均呈現遞增趨勢，隨機算法與NICE協議的最大加入時延分別分布在0.32s到0.4s之間以及0.41s到0.8s之間，度優先算法在比較少的節點里可以快速找到有最大度的父節點，最大加入時延分布在0.16s到0.53s之間，而本文提出的DTD-H算法的最大加入時延分布在0.22s到0.40s之間，所以節點數目略小時，度優先算法最大時延會優先于其他三個算法.但節點數目逐漸增多時，NICE算法在由上至下每次尋找最近的成員時所需要的時間也越來越長，最大加入時延分布在0.8s到1.73s之間，所以NICE算法最大加入延時最大；隨機算法在所有具有度剩余的節點中隨機選出父節點，最大加入延時低于NICE算法，分布在0.45s到1.18s之間；度優先算法會在眾多節點中選出最大度的節點，最大加入延時分布在0.53s到0.57s之間；DTD-H算法的最大加入時延分布在0.44s到0.52s之間.因此節點數目多于20個時，DTD-H算法的最大加入時延會略優于度優先算法，而明顯優于NICE算法以及隨機算法.

圖8 最大加入延時與節點數目的關系圖Fig.8 Relation graph of max delay of the spanning tree and the number of nodes

圖9所示統計了100～1000個節點數目時，DTD-H算法與對比算法的平均鏈路伸展長度.隨著節點數目逐漸增多時，四種算法的平均鏈路伸展度均呈現遞增趨勢.NICE協議采用的分層分簇結構，大部分節點位于分層結構的最底層，組播樹中成員節點加入的過程由上至下尋找最近的節點，一旦某一層出現誤差將會影響下層節點簇的選擇，在實現數據轉發的過程中路徑長度越來越大；而度優先的算法不考慮其他因素，只選擇最大度的節點加入；隨機算法任意加入組播樹中，將存在出度剩余的節點作為父節點；而本文的算法在考慮路徑長度的前提下選擇穩定度因子最大的節點作為父節點加入.仿真數據顯示，DTD-H算法降低了平均鏈路伸展長度.

圖9 平均鏈路伸展長度與節點數目的關系圖Fig.9 Relation graph of average link stretch length and the number of nodes

6 結束語

針對應用層組播的終端節點隨機任意退出的問題，本文主要研究了如何構造高穩定性的應用層組播樹.本文的主要貢獻為提出了一種合理的問題模型-T-DTD模型，在應用層組播樹生成過程中，該模型綜合考慮了終端節點的轉發能力與在線時長，以及節點所在組播樹中位置這三個因素，并且對主要影響因素進行比重控制構造高穩定性、低延時應用層組播樹.最后通過仿真實驗，對比了本文DTD-H算法與NICE協議和度優先算法以及隨機算法在平均加入延時、最大加入延時以及平均鏈路伸展度這三個方面的性能，仿真結果表明本文提出的算法能夠有效地降低組播樹的時延以及鏈路伸展度.

本文對應用層組播的構建算法進行了研究，但還存在諸多不足和有待繼續完善的地方，在未來的研究中，我們將繼續深入研究T-DTD模型中調整組播樹的算法，以更加精確有效的提高組播樹服務質量.我們也將進一步探索求解T-DTD問題模型的算法，以獲得更優的解法.另外，從分布式和組成員動態管理的方面對本文提出的算法進行改進，使之能適應成員節點規模較大的應用層組播場景，這也是我們下一步研究方向.同時，由于本文中對利用DTD-H算法構建的應用層組播樹性能的驗證，是通過OMNet++仿真實驗實現的，還沒有考慮到實際網絡中的環境，所以下一步工作也會將本算法投入到實際應用中，以驗證算法的優越性.