基于主機鄰域密度的ＱｏＳ保證的應用層多播模型
2008-12-31 00:00:00許建真滕張福炎
計算機應用研究 2008年7期
摘 要：提出了一種基于主機鄰域密度的QoS保證的應用層多播模型MCT，模型設計為典型的樹結構。主要闡述了多播節點的加入與退出過程，首先定義了主機鄰域密度的概念，并以此為標準對所有節點進行初次擇優，隨后運用服務質量路由算法RDSS進行二次擇優，得到多個網絡參數限制條件下最滿足QoS需求的接入路徑，最終達到應用層多播（ALM）拓撲結構的整體優化。仿真結果證明，模型的建立方法可以平等且有效地控制多個網絡參數，滿足了ALM應用的QoS需求。
關鍵詞：應用層多播； 服務質量； 多約束； 路由決策支持系統； 主機鄰域密度
中圖分類號：TP309 文獻標志碼：A
文章編號：1001-3695(2008)07-2121-03
QoS guaranteed application layer multicast model based on host-domain-density
XU Jian-zhen1，2，TENG Wen2，ZHANG Fu-yan1
(1. State Key Laboratory for Novel Software Technology，Dept.of Computer Science Technology， Nanjing University， Nanjing 210093， China; 2.College of Computer， Nanjing University of Posts Telecommunications， Nanjing 210003， China)
Abstract:
This paper presented a QoS guaranteed application layer multicast (ALM) model，which called MCT (multiple constrains ALM tree)，and designed as a typical tree structure. The paper focused on nodes joining and departure procedures，defined host-domain-density as the standard for the elementary selection， and RDSS QoS routing algorithm for further selection.It achieved an optimal access path constrained by multiple network parameters and an entire optimization of ALM topology. The simulation results show that the MCT method can control multiple network parameters equally and effectively， and can satisfy the required QoS of ALM applications.
Key words：application-layer multicast; quality of service (QoS); multi-constrains; routing decision support system(RDSS）； host-domain-density
目前基于ALM的各種應用技術飛速發展，形形色色的應用服務出于自身的特點對ALM模型的建立、路徑的選擇提出了不同的要求，如多媒體應用對時延提出了極高的要求，而文件傳輸服務則需要低的丟包率，很多服務甚至希望網絡能同時滿足多個限制條件。在多參數限制下如何選擇滿足QoS需求的應用層多播路徑，構建合理的ALM模型成為目前研究的重點之一。本文提出一種整體優化的ALM樹優先模型MCT，該模型基于一種滿足多個參數限制的服務質量路由算法RDSS[1]，通過選取滿足應用服務QoS需求的ALM路徑構建系統。
1 RDSS算法描述
Wang Zheng等人[2]中利用多個度量參數相結合以尋找一條滿足條件的路徑的方法是NP完全問題。目前用來簡化這類問題的方法大概可分為兩類：a）通過參數的線性疊加來形成新的參數，并依據新參數尋找路徑；b)基于路徑修剪的方法，先以某一個參數為標準刪除一些路徑，隨后在剩余路徑中以另外參數為標準尋找路徑。這兩者都有其自身的缺陷，前者會導致某些參數的信息丟失，后者則側重于其中一個參數。RDSS算法是一種平衡地滿足多參數限制的QoS路由算法，具體描述如下：
a）對于一個限定參數mj，找出所有可選路徑Ri(i=1，2，3，…，N)上對應mj的值m
b）從mij中取最大和最小狀態值，分別賦值給a和b。
c）通過下列方法將每個參數的多個路徑狀態值轉換為[-1，1]內的序列：
(a)s代表A→ F的映射關系，F R且F[-1，1]，s(a)=1，s(b)=-1。
(b)對于最小性度量參數，如果x < b，則s(x)=-1；如果x>a，則s(x)=1。對于可加性和可乘性度量參數，如果x
(c)所有其他x的值通過以下映射關系s轉換：
s(x)=2×(x-b)/(a-b)-1
d)以參數個數m為列，可選路徑個數n為行，逐個寫入路徑狀態值對應的映射值，生成m×n矩陣A。
e)由路徑的需求條件（如d=[delay=i，jitter=j]）生成n×1的向量V，將各約束閾值按c）中步驟轉換為[-1，1]區間內映射值。
f)A×V=O。其中O是一個m×1的向量，對應于m條可選路徑。從O中選取最大值，該值對應的路徑即為RDSS算法求出的最滿足條件的鏈路。
網絡層的選路需要服務質量路由算法進行優化，應用層多播中各種應用服務也同樣需要滿足應用類型所提出的QoS需求。
2 MCT模型生成及舉例
2．1 MCT模型的設計
傳統的ALM存在著組織混亂、效率低下等諸多不足。為了改善各種問題，很多優秀的ALM理論拓撲模型被提出，這些模型可以歸類為樹優先模型(如Yoid[3]、HMTP[4])、網狀優先模型（如Narada[5]）、層次結構模型（如NICE[6]）。本文將討論一種基于RDSS的樹優先模型MCT，它在多參數限制的條件下，每個新節點加入多播組時，通過兩次擇優方法局部選取最優接入點加入多播組，達到多播樹性能的整體優化，保證了應用程序的服務質量要求。
2．1．1 多播成員的加入
多播組的形成從數據源點的工作開始，希望得到多播服務的主機隨后逐個加入到多播組中，多播組逐漸擴大的過程即為新節點不斷加入的過程。設應用服務希望主機對之間的多播路徑滿足多參數限制m={m1=i，m2=j，…}。為了使局部多播路徑盡可能地滿足限制條件，同時又控制數據計算的復雜度，在每個新節點加入時均要進行兩次擇優過程。
為了增強組內節點的管理、集中所有節點信息，對每個多播組定義一個RP（rendezvous point）。該節點不屬于任何多播組，而是一臺具備較強處理能力的主機。任何新節點在加入多播組前先發送query_message給RP，在RP回傳主機信息和運算規則后開始計算，選擇出滿意的接入點加入多播組。RP內部存儲的節點信息的數據結構和初始化如表1所示。
已加入多播組的節點會以Δt的時間間隔周期性地向RP發送更新報文，更新RP節點中的out_degree、src和L_time信息。
假設當前組內合計N個節點，則可用集合G={1，2，3，…，N-1，N}表示多播組，N+1節點(記為P)到達并試圖加入多播組。新節點P首先向RP發送query_message，獲取組內節點的數據表；刪除out_degree=lim（lim為最大出度限制，等于lim表示節點已滿）的節點表項，根據剩余節點的序號提取IP_address；分別向這些地址發送探測數據包，獲取它們與本節點間跳數（hop）和應用服務所需求的網絡度量參數值；記錄并依據RP回傳的運算規則，按式(1)進行運算。其中：d為量化的網絡半徑值，下標i表示該值對應于s_number=i的節點，Hi表示節點到P的跳數，srci為節點持有的數據資源量，S為資源總量，timei為節點在系統中存在的時間，T為系統存在總時間，其中0 ≤ α， β，γ ≤1。
節點P按式(2)計算得到每個節點的量化距離值di。以節點P為圓心、量化值d為半徑畫圓，稱為d-鄰域。依次將d1，d2，…，dN與d進行比較，如果di
擇優過程希望第一次擇優所得節點數M和組內節點數N呈如下關系：
在計算出d-鄰域密度H后，如果|M/H-1|>δ（0<δ<1），則可認為M遠大于H或M遠小于H，此時需要調整半徑d的大小以縮小或擴大H值，使H與M數值逼近。以d值為節點值構建一棵二叉搜索樹，任意節點的左孩子值比其父節點值小，右孩子值比其父節點值大。設路徑權值Rj-1=0或1(j=1，2，3，…，j代表當前節點到根節點之間路徑數)，0表示M/H<1，d需要縮小；1表示M/H>1，d需要擴大。根據當前節點到根節點間的路徑權值Rj之和將d的調整規則定義為
其中：φ為d的調整控制量，0<φ<1 ；preNode_d為中序遍歷搜索樹的前驅節點值；subNode_d為中序遍歷搜索數的后繼節點值。
在d值經過每次擴大或縮小后，再次計算|M/H-1|，如果該值仍然大于δ，繼續調整；否則d調整完畢，退出循環，計算當前d-鄰域密度H。
在第一次擇優最終獲取的H個節點中，新節點P可能成為任意一節點的孩子加入多播組，從此H個節點存儲的信息中提取與限制條件相對應的參數值，運用RDSS算法計算出反映所有路徑優劣程度的H×1向量O。
節點P從向量O中找出最大值，該值所對應的節點即為最合適的接入點。新節點P向所得節點發送加入請求，成為其孩子；同時任意節點在添加了新的孩子以后立刻向RP通報更新報文。
2．1．2 成員的失效處理
參與應用層多播的節點均為擁有自主能力的主機，這些主機隨時可能正常地退出或因故障突發地離開多播組。在樹優先結構中，上層節點的離開對下層節點數據的獲得會造成很大的影響。這需要ALM模型擁有很強的自愈能力，迅速地解決節點離開帶來的問題，最小可能地影響服務效率。
MCT模型利用冗余信息的存儲來解決節點離開的問題。依據上述節點加入方法，新節點P成功地選擇了合適的接入點后，會從O中選取相對最佳路徑而言的次優路徑，即在O中小于當前選用值的最大值作為備份的冗余信息。某節點正常離開多播組會通知其所有孩子節點；如果非正常退出，則其孩子節點C會運用心跳算法在很小的時間間隔后檢測出父節點的離開。孩子節點一旦知道父節點的離開，立刻查找次優接入點重新加入多播組。如果此時次優節點出度已滿或者也已離開多播組，則節點C重新運行一次加入的過程，選擇當前的最優路徑再次加入多播組。RDSS算法的優勢之一在于使用切實的數據抽象了鏈路的優劣，直接通過數值的比較即可完成路徑的選擇。
2．2 MCT模型舉例
下面以具體實例來演示MCT模型實現中運用RDSS算法二次擇優節點、加入與退出多播組的過程。設應用服務希望主機對之間的多播路徑盡可能滿足限制條件m={delay=8，jitter=5}，經初次擇優后的d-鄰域內節點如圖1所示。一次擇優后的節點集合為{a1，a2，a3，a4}，新節點P可成為任何一個節點的孩子而加入多播組，則有四種接入路徑。經P發往各個節點的探測包反饋回可選路徑的網絡參數如表2所示。
下面通過RDSS算法計算出最佳路徑和冗余路徑：
從所得向量中可直觀地找出最大值1.13，該值對應的接入路徑為R_a2，即相對需求條件而言，R_a2即為最滿足服務質量需求的接入路徑。向量中次高值為0.65，對應的接入路徑R_a3可作為備份的冗余信息存儲在節點P中，一旦P發現其父節點丟失，則調用其所存儲的冗余路徑R_a3重新加入多播組。
3 模型性能分析
3．1 MCT模型性能分析
性能分析從仿真獲得的全局結果出發進行討論，實驗在Linux下NS-2仿真平臺中實現。仿真仍然選取雙參數m={delay=8，jitter=5}作為限制條件，隨機地選取[0，40]區間值作為供選擇路徑時延與抖動值，多播組規模從0遞增至1 000節點。HMTP是一個成功的樹優先模型，在時延的約束和多播組的管理方面非常有效。下面通過MCT模型與其比較來說明本文模型的有效性。
圖2描述了多播組中主機對之間平均時延的比較。HMTP模型通過遞歸尋找子樹中的最短時延路徑加入多播組從而生成多播樹，它對路徑時延的約束是非常有效的。從圖2中可以看出，節點數小于300時，MCT的路徑平均時延大于HMTP，但隨著多播組規模的擴展，MCT模型逐漸趨于穩定，優越性得到顯著體現。兩個模型均很好地滿足了時延限制條件delay=8（圖2中虛線）。
HMTP模型雖然對時延的約束非常有效，但是對抖動的控制幾乎毫無作用。圖3中顯示HMTP模型產生的路徑平均抖動保持在15左右，而MCT模型中抖動的統計結果很快即可保持在限制條件delay=5（圖3中虛線）之下。
以上分析說明，MCT模型同時而有效地控制了時延和抖動兩個參數；而HMTP模型僅能起到控制時延的作用，在另一參數的控制效果上比MCT相差甚遠。目前很多優秀的模型致力于優化ALM中某一個參數，多參數控制模型的提出不無裨益。
仿真還統計了MCT模型中滿足雙參數限制條件的路徑數占所有多播路徑數的比例，記為PSE（percentage of satisfied egdes）。設編號i和j之間的邊記為bij，定義bij上的一個權值Vbij如下：
由圖4可見，MCT模型中，隨著組內節點數目的增加，滿足條件的路徑比例不斷提高，當組內節點數大約到達500左右時，PSE值已經大于80%。相比而言，節點如果按HMTP模型方式加入多播組，其PSE值只能維持在10%左右。由此可見，隨著多播節點數目的增加，MCT模型中越來越高比例的局部路徑滿足雙參數限制條件，最終達到全局優化的效果。
3．2 RDSS算法的應用層擴展
RDSS算法是針對網絡層的選路問題而提出的，其運行主體是路由器；MCT模型是RDSS算法在應用層多播中的擴展，其運行主體是獨立主機。下層網絡中的很多路由器本身就承載著非常重的選路任務，而RDSS算法針對每條路徑的每個參數均要進行計算的特性給路由器帶來更大的負擔甚至是災難，這反而造成了網絡服務質量的不斷下降。MCT模型將RDSS算法擴展至應用層并用主機替代路由器，當前主機所具備的計算能力完全可以輕松承擔RDSS算法帶來的計算量；另外MCT模型通過主機鄰域密度概念的提出，將RDSS中矩陣運算的復雜度降低很多。應用層MCT模型使得RDSS算法的使用更加有效和合理。
4 結束語
本文提出一種新的提供QoS保證的ALM模型MCT，在此之前很多優秀ALM模型被提出，但它們都致力于解決或優化某一個QoS度量標準。MCT模型通過引進一個新穎高效的服務質量路由算法RDSS，局部選取最滿足多參數限制的多播路徑，最終達到ALM拓撲結構的整體優化。
本文提出的模型生成方法是一種建立多參數優化模型的通用方法，可以根據具體的服務類型選取時延、抖動、丟包率、帶寬等其中的一個或多個作為限制條件。但MCT模型依然存在對網絡變化的動態適應性較低等不足，在今后的工作中會致力于找到合適的方法增強模型對網絡動態變化的適應能力。
參考文獻：
［1］ GOODRIDGE W S，ROBERTSON W，PHILLIPS B，et al.Comparing a novel QoS routing algorithm to standard pruning techniques used in QoS routing algorithms［C］//Proc of Canadian Conference on Electrical and Compute Engineering.2004:805-808.
［2］ WANG Zheng，CROWCROFT J. Quality-of-service touting for supporting multimedia applications［J］. IEEE Journal on Selected Areas in Communications，1996，14(7):1228-1234．
［3］FRANCIS P.Yoid：extending the multicast Internet architecture[EB/OL].(1999-10-01).http://www.icir.org/yoid/docs/ycHtmlL/htmlRoot.html.
［4］ZHANG Bei-chuang， JAMIN S， ZHANG Li-xia. Host multicast：a framework for delivering multicast to end users［C］//Proc of the 21st Annual Joint Conference on Computer and Communications Societies.2002:1366-1375.
［5］CHU Yang-hua， RAO S G，ZHANG Hui.A case for end system multicast［C］//Proc of ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems.New York:ACM Press，2002:1456-1471.
［6］BANERJEE S，BHATTACHARJEE B，KOMMAREDDY C.Scalable application layer multicast［C］//Proc of ACM International Confe-rence on Measurement and Modeling of Computer Systems.New York:ACM Press，2002:205-217.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”
