多ＱｏＳ約束的自適應組播路由協議

摘要：在多加性QoS約束的自適應組播路由基礎上，提出了一種基于多QoS約束的自適應組播路由協議MQDMRP。采用多路徑尋路和受限泛播策略，有效限制了控制報文開銷；對MQDMRP與傳統協議進行仿真研究，表明新協議的接入成功率比傳統協議要好。

關鍵詞：服務質量； 組播； 多約束； 協議； 仿真

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2008)04－1189－04

與傳統的IP路由相比，QoS路由[1~3]能很好地滿足用戶對網絡服務質量的需求，并且可以有效地節約網絡資源，避免網絡擁塞。與InterServ和DiffServ不同，QoS路由是尋找滿足QoS參數要求的分組路由，在路由建立的過程中保證QoS。QoS路由大致可以分為兩類，即單約束的QoS路由和多約束QoS路由。其中，基于單個QoS約束的QoS路由往往不能完全滿足QoS要求。由于組播可以有效地利用網絡資源，近年來，基于多QoS約束的組播路由算法和協議已得到了研究人員的關注[4~6]。多QoS約束組播路由的目標是要尋找滿足多個QoS約束條件的組播樹，主要研究滿足業務質量要求的組播樹的連通性以及組播成員的有效加入和退出等問題。

目前，研究人員已經提出了一些多QoS約束組播路由協議，如YAM[4]、QoSMIC[5]和QMRP[6]。但這些協議在連接成功率、動態性和可擴展性等方面還存在一些有待解決的問題。

本文針對上述協議的不足，提出一種基于多QoS約束的自適應組播路由協議（multiple QoS－based dynamic multicast routing protocol，MQDMRP）。協議由接收方觸發，采用多路徑尋路方式和受限泛播策略，以動態的、自適應網絡狀態的方式來建立滿足多QoS約束條件的組播樹。仿真實驗表明，與以往協議相比，該協議較好地提高了組播請求連接成功率，有效地降低了網絡中控制消息包的開銷。

1MQDMRP

1．1協議的基本算法思想

為了闡述該協議的基本算法思想，有必要對協議中的一些基本概念進行說明。

定義1非線性鏈路選擇函數對加權的QoS參數進行非線性組合，具有不可加性。根據文獻[7]，具體的非線性鏈路選擇函數為L∞(P)=max1≤i≤m[wi(P)/Li]。其中：wi(P)表示某條路徑在第i個QoS約束條件上的開銷；Li是QoS約束條件；m是QoS約束的個數。如果L∞（P）＞1，則表明沒有路徑滿足所有的QoS約束條件；否則，表明有路徑滿足所有的QoS約束條件。

定義2對于路徑P，如果不存在另一條路徑P′，使得對于所有QoS條件i均滿足wi(P′)≤wi(P)，且至少存在一個j使得wj(P′)

在協議中采用非線性函數處理多個QoS約束條件，中間節點需要存儲多條從請求節點到組播樹節點的子路徑。中間節點在收到鄰居節點轉發來的路徑探測包后，首先按照非線性鏈路選擇函數對該路徑探測包經過的路徑P進行鏈路QoS開銷判斷。如果根據非線性鏈路選擇函數計算出來的L(P)>1，則表明路徑探測包經過的路徑P不滿足QoS約束條件，中間節點丟棄探測包；如果L(P)≤1，表明路徑P符合QoS約束條件，則中間節點將探測包中的路徑P與隊列中的其他路徑進行統治關系判斷。如果路徑P被隊列中的某條路徑統治了，則表明路徑P不是請求節點到組播樹加入路徑中的子路徑，中間節點將路徑P丟棄；否則，將路徑P加入到中間節點的存儲隊列中。

協議采用了受限泛播策略，即在采用泛播技術擴大路徑搜索范圍的同時，對探測包的轉發條件進行了嚴格限制。一方面采用非線性鏈路選擇函數，在節點轉發探測包時判斷路徑是否滿足QoS約束條件，避免了無效數據包的傳遞；另一方面采用非統治路徑思想，在每個節點中預測該路徑是否可能成為加入路徑的子路徑，從而進一步降低了網絡中控制消息包的開銷，使得泛播更加準確和有效。

1．2MQDMRP

協議采用受限泛播策略和多路徑尋路方式，在網絡節點轉發控制消息包時采用判斷機制，將不符合QoS約束條件以及無效的控制消息包丟棄，在提高組播加入請求成功率的同時，有效地避免了泛播技術對網絡帶來的沖擊。

1)組播請求節點的加入

假設原始組播樹T={vs}，vs表示組播源，其他節點通過加入組播樹的方式加入到組播組中。如果不在組播樹上的節點v要申請加入組播樹，則v向所有鄰居節點發送路徑探測包。路徑探測包包含以下五項內容：要加入的組播組ID、v的QoS約束條件、路徑探測包經過的路徑(初始化為v)、路徑上QoS約束條件的開銷W(w1，w2，…，wm)(初始化為0)以及經過的跳數(初始化為0)。如果要加入的節點已經在組播樹上，則首先檢查自己是不是組播樹的轉發節點。如果是，將自己的狀態從轉發節點轉為組播樹的接收節點，即完成了請求加入的過程。

6) 組播節點的退出

如果節點v∈T要離開組播組，檢查v是否為組播樹的中間節點。若是，則標記v為轉發節點，退出過程結束。如果v是組播樹的葉子節點，則它向上游節點發送退出消息，上游節點收到退出消息后，將相應的分支從組播樹中剪掉，同時檢查自己是否成為組播樹的葉子節點。若是，判斷自己是否為組播接收成員，是則退出過程結束。如果自己是轉發節點，則繼續向上游發送退出消息，如此循環，直到遇上非葉子節點為止。

2協議仿真研究

2．1仿真環境

本文利用OPNET仿真工具建立了Mbone和Waxman網絡模型，將本文提出的協議與兩種著名的協議QoSMIC和QMRP進行了對照研究。在三種協議的仿真研究中，采用了相同的拓撲結構和網絡參數。

本文在仿真過程中，在Mbone網上建立了84個節點和1個組播源，請求加入的節點數隨機生成，仿真時間長度為3 600 s；在Waxman網絡中，網絡節點數在4~100進行變化，1個組播源，鏈路帶寬1 024 kbps~2 Mbps均勻分布，鏈路中長連接和短連接所占的比重為0.2，網絡節點的平均節點度數為0.15。

2．2仿真結果分析

1) 平均QoS呼叫請求成功率

本文在Mbone網絡模型和Waxman模型上分析了MQDMRP、QoSMIC和QMRP三種協議在不同約束條件個數和不同群組規模條件下的平均QoS呼叫請求成功率。

在約束條件上，系統在Mbone和Waxman模型上均分別進行了仿真。約束條件有單個約束條件和兩個約束條件兩種。其中，單個約束條件采用時延約束作為度量，而在兩個約束條件中采用兩個加性約束條件作為度量。在仿真過程中，新成員均按照相同的QoS條件請求加入組播組。在群組規模上，系統在Waxman模型上進行了仿真。網絡的節點數為100，群組規模分別為5、10、15、20、25、30、35、40，組播組的成員都按照同構的QoS條件加入到組播組中。

同時，為了獲得平均的統計結果，在每一種網絡和仿真條件下系統運行了50次，最后得到的結果為50次仿真結果后的平均值。

圖3~6分別給出了MQDMRP、QoSMIC和QMRP在不同約束條件下的平均QoS呼叫請求成功率。從圖中可以看出，MQDMRP的成功率明顯高于QoSMIC和QMRP。當QoS約束比較緊時，MQDMRP仍可以保持一定的成功率，而QoSMIC和QMRP則只有較低的成功率。當QoS約束條件個數增多時，MQDMRP也能夠提供比QoSMIC和QMRP高出20%左右的成功率。這主要是MQDMRP采用了受限泛播技術和多路徑尋路方式，路徑探測包在整個網絡中具有更大的搜索空間，可以為請求節點提供更多的滿足QoS約束條件的路徑，因此整個協議具有較高的連接成功率。QoSMIC雖然也是采用多路經尋路方式，但是其采用了RPF的轉發方式來搜索組播樹上的節點，使得從新組播成員節點到組播樹節點的搜索路徑是相應兩節點之間的最短路徑，而實際上滿足QoS約束條件的可行路徑可能不是兩節點之間的最短路徑。因此，QoSMIC有可能找不到滿足QoS約束條件的路徑。QMRP先以單路徑的方式搜索連接新組播成員到組播樹滿足QoS約束條件的路徑，如果鏈路上的資源不能滿足QoS約束的要求，就切換到多路徑搜索。但是QMRP并不支持加性QoS度量，同時QMRP的效用取決于單路徑的搜索狀況。如果單路徑搜索的部分路徑的QoS屬性不太好，則多路徑搜索失敗的概率也會很大，因此影響了QMRP的成功率。

圖7、8分別給出了三種協議在不同群組規模下的平均QoS呼叫請求成功率。從圖中可以看出，隨著群組規模的增大，三種協議的請求成功率均有一定的提升。這主要是因為隨著網絡中組播組密度的變大，請求節點在進行路徑搜索的過程中更容易在局部范圍內找到組播樹節點，從而在一定程度上提高了請求成功率。但是相比而言，MQDMRP還是比QoSMIC和QMRP具有更高的請求成功率。這是由于MQDMRP采用的受限泛播技術和多路徑尋路方式具有較好的伸縮性，可以保證協議在不同的網絡特征下均具有較好的性能。

2) 呼叫加入平均控制消息包開銷

本文在Mbone網絡模型和Waxman模型上分析了MQDMRP、QoSMIC和QMRP三種協議在不同約束條件個數、不同群組規模和不同網絡規模條件下的呼叫加入平均控制消息包開銷。

在約束條件上，系統仍然采用了單個約束條件、兩個約束條件兩種方式，新成員都是按照相同的QoS條件請求加入組播組的。在群組規模上，群組規模分別為5、10、15、20、25、30、35、40，組播組成員均按照同構的QoS條件加入到組播組中。在網絡規模上，分別在4、9、16、25、36、49、64、81、100個網絡節點上進行分析。同理，為了獲得平均統計結果，在每一種網絡和仿真條件下系統運行50次，最后得到的結果為50次仿真結果后的平均值。

圖9~12分別給出了三種協議在不同約束條件下的呼叫加入平均控制消息包開銷。從圖中可以看出，QoSMIC的平均消息開銷明顯高于MQDMRP和QMRP。這主要是QoSMIC采用了多路徑尋路方式，在尋路的過程中并沒有考慮QoS約束條件而導致的盲目搜索。MQDMRP雖然也是采用的多路徑尋路方式，但是它在尋路過程中以是否滿足QoS約束條件作為控制消息包的轉發條件，減少了控制消息包在網絡中的泛洪，避免了尋路過程中的盲目搜索。QMRP具有最小的平均消息開銷，這是由于它在尋路過程中首先采用的是單路徑尋路方式，控制消息包按照一條路徑來進行搜索，只有當單路徑尋路方式不能找到滿足QoS約束條件時才轉到多路徑尋路方式，從而減少了消息包的開銷。

同時還可從圖中看出，隨著QoS約束條件越來越嚴格，QoSMIC和QMRP的平均消息開銷均有一定程度的增長，而MQDMRP的平均消息開銷卻呈現出下降趨勢。這是由于QoSMIC在尋路過程中采用了本地搜索和樹搜索兩個部分。隨著QoS約束條件越來越嚴格，本地搜索失敗的概率會很高，因此它將采用樹搜索的方式，這也給整個網絡和組播樹節點帶來了很大的消息開銷。QMRP采用的單路徑與多路徑混合尋路方式在QoS約束條件越來越緊時，單路徑尋路方式將很難成功，因此QMRP會啟動多路徑尋路方式，這也會對網絡帶來一定的沖擊。MQDMRP采用的是受限泛播技術，它將QoS約束條件與路由尋路過程相結合。隨著QoS約束條件越來越緊，不符合QoS條件的控制消息包會在尋路過程中被丟棄，從而減少了無效消息包在網絡中的傳輸和轉發，有效地提高了網絡的效率。

圖13和14分別給出了三種協議在不同群組規模下的呼叫加入平均控制消息包開銷。

從圖中可以看出，隨著群組規模的增大，MQDMRP和QMRP的平均控制消息開銷均在減少。這主要是由于隨著網絡中組播成員的增多，組播請求節點與組播樹節點之間的距離也在變短，在局部范圍內找到滿足QoS約束條件路徑的可能性也增大了，它們的平均控制消息開銷呈下降趨勢。而QoSMIC的平均控制消息開銷仍然在增長。這主要是由于隨著組播樹規模的增大，其樹搜索的耗費變得更為突出，而樹搜索的消息開銷是隨著組播樹規模的增大而增大的，QoSMIC的平均控制消息開銷呈現增長的趨勢。



圖15給出了三種協議在不同網絡規模下的呼叫加入平均控制消息包開銷。從圖中可以看出，隨著網絡節點數的增加，三種協議的平均控制消息包開銷均在增長。QoSMIC的平均控制消息包開銷增長迅速。這主要是由于它在尋路過程中沒有考慮QoS約束條件的因素，當網絡規模變大時，路由的盲目搜索空間也增大了。MQDMRP和QMRP的平均控制消息包開銷增長比較緩慢。這是因為MQDMRP采用的受限泛播技術有效地抑制了網絡規模的增長對控制消息包開銷帶來的影響，而QMRP的單路徑尋路方式也可以降低網絡規模增長對控制消息包開銷的影響。

3結束語

本文研究了多約束的QoS組播，采用了非性線選擇函數建立多QoS約束條件間的關系，引入了統治路徑的概念，并在此基礎上進一步提出了多QoS約束的動態組播協議（MQDMRP）。協議中采用了多路徑尋路方法，利用受限泛播技術提供多條滿足QoS約束的路徑供請求加入組播樹的成員選擇，然后確定其中代價最小的路徑將請求加入組播樹的成員加入到組播樹中。本文通過在OPNET仿真環境中，在兩個著名的網絡拓撲結構上(Mbone和Waxman)對三種協議QoSMIC、QMRP和本文所提出的協議的性能進行了仿真研究，結果表明，MQDMRP具有更好的呼叫請求成功率。

參考文獻：

[1]DAI Jun－quan，PUNG H K， ANGCHUAN T. A multicast routing protocol supporting multiple QoS constraints[C]//Proc ofICON 2002. Singapore: IEEE， 2002: 31-36.

[2]BO Rong，BENNANI M， KADOCH M，et al. Traffic engineering extension for traditional QoS multicast routing algorithms[C]//Proc of Communications(ICC 2005). Seoul: IEEE， 2005: 208-212.

[3]LI Suo－gang ，WU Jian－ping，XU Ke，et al. A modularized QoS multicasting approach on common homogeneous trees for heterogeneous members in DiffServ[C]//Proc of the 25th IEEE International Performance， Computing，and Communications Conference. Phoenix: IEEE， 2006.

[4]CARLBERG K，CROWCROFT J.Building shared tree using a one－to－many joining mechanism [J]. ACM SIGCOMM Computer Communication Review， 1997， 27(1): 5-11.

[5]FALOUTSOS M， BANERJEA A， PANKAJ R. QoSMIC: quality of service sensitive multicast Internet protocol [J]. ACM SIGCOMM Computer Communication Review， 1998， 28(4): 144-153.

[6]CHEN S， NAHRSTEDT K， SHAVITT Y. A QoS-aware multicast routing protocol[C]//Proc ofthe 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2000). Tel Aviv， Israel: IEEE， 2000: 26-30.

[7]GOLUB G H， VANLOAN C F. Matrix computations [M]. Oxford， UK: North Oxford Academic， 1983:579-633.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”