一種具有時延約束的組播路由算法研究

摘 要:對于多媒體應用等實時組播業務而言，組播路由算法不僅要考慮優化代價，還要考慮時延約束。針對這一問題，提出一種支持動態組播的時延受限低代價組播路由啟發式算法(delay-constrained multicast algorithm，DCMA)。該算法基于DDMC算法進行擴展，采用新的指示函數和鏈路選擇函數，綜合考慮了時延和代價，有效保證了組播樹的性能，而且時間復雜度低，可用于實際的應用系統中。

關鍵詞:組播路由算法; 時延約束; Steiner樹

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

文章編號:1001-3695(2009)09-3259-04

doi:10.3969/j.issn.1001-3695.2009.09.016

New delay-bounded constraint multicast routing algorithm

ZHOU Xian-wei，LIU Zhen-zhen，LIN Lin， LIU Tao， WANG Chao

(Dept. of Communication Engineering， School of Information Engineering， University of Science Technology Beijing， Beijing 100083， China)

Abstract:For real-time multicast business such as multimedia applications， multicast routing algorithms must optimize both cost and delay.In response to this problem， proposed a heuristic algorithm DCMA， which joined destination nodes to the multicast tree dynamically.This algorithm was based on DDMC algorithm and improved by using new indicator function and link choice function.Considering the optimization of delay and cost， the algorithm efficiently guarantees the performance of multicast tree， with advantage of low time complexity and easy operation in real system.

Key words:multicast routing algorithm; delay-constraint; Steiner tree

0 引言

隨著通信技術的發展，人們的應用需求越來越多樣化，不同的應用對服務質量的要求也不相同。組播應用的QoS要求主要有帶寬、時延、時延抖動等。對于視頻點播、電視會議等采用組播方式的多媒體業務來說，時延和代價是兩個必須考慮的指標。如果時延過長，就會引起用戶聽覺和視覺上的不適應，甚至引起語義無法理解。因而時延約束的組播路由問題的研究是目前組播路由算法研究的重要問題[1，2]。

Alpert等人在文獻[3]中所提出的AHHK算法來源于兩種著名的算法，即Prim的最小生成樹算法和Dijkstra的最短路徑樹算法，并采用基于貪婪策略的思想將兩者進行結合。

Matta等人[4]在文獻[1]中所提的QDMR算法調整了DDMC算法，使其能夠根據到目的節點的時延與給定的時延上限的比值來動態調整建樹的策略。如果到目的節點的時延與給定的時延上限還相差很遠，QDMR算法給予目的節點高優先級，將其作為源節點看待。如果已經快逼近時延上限，QDMR算法將給目的節點較低的優先級，從而生成多分支樹，以盡量避免違反時延上限。

Aissa等人在文獻[2]中提出的EPDT算法是基于QDMR算法進行改進的，該算法通過改變QDMR算法的指示函數來進一步降低組播樹的開銷。對于節點時延逼近時延上限時是有效的，但是在算法初始階段，即到目的節點的時延與給定的時延上限還相差很遠時，所建組播樹的代價并不一定優于QDMR。

在以上所述的三種算法的基礎上，本文提出一種新的具有時延約束的組播路由算法，即DCMA。

1 問題定義

具有時延約束的組播路由問題，本章給出數學描述。

用賦權圖G=(V，E)來表示網絡。其中:V是網絡節點的集合，每個節點表示主機或路由器;E為連接網絡節點的通信鏈路的集合。在每條鏈路e=(u， v)∈E上定義兩個權值函數:a)鏈路代價函數C(e):E→R+，表示每條鏈路的費用(這里的費用是一個廣義的費用，它可以根據有關鏈路的各種因素定義);b)鏈路時延函數D(e):E→R+，鏈路時延為數據包經過鏈路的度量，包括排隊、發送和傳輸時延等。

對圖G，給定一個源節點s∈V和目的節點集合D，DV-{s}稱為組播組成員。給定一個時延上限Δ，即Δ為從源節點到任一目的節點所允許的時延上限。假定從源節點到目的節點的路徑為P(s， v)，則時延受限Steiner樹問題就是要尋找一棵覆蓋給定目的節點集合D且費用最小的滿足時延約束的最優Steiner樹T=(VT，ET)，其中DVTV，ET∈E，即考慮下述優化問題:

min∑e∈TC(e)

∑e∈P(s，v)D(e)Δv∈D

構建最小代價樹問題可形式化為圖論中的Steiner樹問題的求解，后者已經證明是一個NP完全問題[5]，即不可能在多項式時間內求得其精確解。在可接受的計算時間內，只能計算得到一棵近似的最優組播樹，而不可能獲得真正意義上的最優組播樹。

2 MST-SPT算法的結合

Prim的最小生成樹(MST)算法最小化了圖中生成樹的費用，但可能會導致比最優樹更大的路徑費用(路徑費用指的是樹中源節點到單個目的節點路徑的最大費用);相對的，SPT只是最小化了路徑費用但是可能會引起更大的開銷[3]。因此這兩種經典算法一般并不直接用于組播建樹。

AHHK算法通過利用一個值在(0，1)區間的指示函數結合了這兩種經典算法。如文獻[3]所述，當AHHK算法中指示函數的值增加時，它所建立的樹有著更高的總體開銷和更小的路徑費用;當指示函數是0時，AHHK與Prim算法是一樣的，建立的樹是最小開銷;當指示函數是1時，AHHK與Dijkstra算法一樣，最小化了路徑費用。

文獻[2]指出，當指示函數的值在(0，1/2)時，此時得到的樹代價較低，路徑費用較大，相比起(1/2，1)區域內所得的樹更為可取。在本文所提算法中，將指示函數ID(u)控制在(0，1/2)的區間內，保證所獲得組播樹的低代價。

3 算法描述

3.1 指示函數

DDMC[4]是一種無約束的建立低代價組播樹的算法，它定義了一個新加入節點vT經由節點u∈T的開銷:

cost(v)=ID(u)cost(u)+c(u，v)

其中:cost(v)是從源節點s到新加入節點v的路徑的總費用，c(u，v)是從節點u到節點v的費用。

指示函數ID(u)定義如下:

ID(u)= 0 當u∈D 1 其他

其中:D是目的節點集合。

如上式所示，當添加新節點連到樹T時，通過目的節點的路徑優先級更高，但是這可能導致組播樹更像是目的節點的一條鏈，會使某些目的節點違反時延約束。

時延約束算法QDMR修改了DDMC算法，通過檢查源節點到目的節點的時延與時延上限之間的比值大小來動態地調整樹。那些離時延上限越遠的目的節點，作為其他新加入的節點的父節點的可能性越高。如果對某些目的節點而言，時延約束將要違反，那么會生成多分支樹將這些節點連入。

QDMR算法的指示函數如下:

ID(u)=delay(u)/Δ 當u∈D1其他

其中:delay(u)是指樹T中從源節點s到節點u的所有鏈路時延的總和，Δ是給定的時延上限。QDMR的指示函數有個很大的缺點，那就是只有delay(u)遠遠小于時延上限Δ時才會有效[2]。當delay(u)越接近Δ，它對目的節點和非目的節點的區分就越小，越無法提高鏈路的共享性，使得組播樹的代價偏大。

文獻[2]中所提的EPDT算法對QDMR的這個缺點作了改進。該算法的指示函數是:

ID(u，v)=delay(u)/(delay(v)+delay(u))當u∈D1其他

從該式可以看出，當delay(u)/Δ的值大于1/2時，即delay(u)接近時延上限時，delay(v)+delay(u)的值一定大于Δ，同時還一定大于delay(u)的2倍，此時所建的組播樹比QDMR更有效。但是算法初始時， 即delay(u)/Δ的值小于1/2時，delay(v)+delay(u)的值與Δ的大小關系無法判定，此時比起QDMR，它所建樹的開銷反而可能更大。而且EPDT算法的指示函數給予了鏈路時延(即delay(v))大的目的節點更高的優先級，這是不合理的。因為這會導致新選擇加入的節點到源節點的時延偏大、剩余時延偏小，選路受到的限制更多。所以筆者發現EPDT算法并不能保證它所建的樹的性能一定優于QDMR 。因此，文獻[2]中的EPDT所建樹的代價小于QDMR的定理并不成立。

為了在初始階段及樹的邊界階段使得算法所建的樹都具有較低的開銷，本文提出的指示函數如下:

ID(u)=delay(u)/(Δ+delay(u)) 當u∈D1其他

顯而易見，對于任何目的節點u∈D，指示函數ID(u)均滿足:ID(u)1/2。

DCMA的指示函數ID(u)1/2，也就是說它符合文獻[2]中的指示函數在(0，1/2)區間的條件，能夠得到代價較低的樹。這是更可取的。

定理1 與QDMR算法相比，DCMA算法所建立的組播樹的代價更小。

證明 按照文獻[2，3]所述，指示函數值越小，所產生的費用就越少;隨著指示函數值的增加，算法AHHK建的組播樹的費用將會增加，路徑費用將會減少。本文所提算法和QDMR算法的指示函數值都是ID(u)。因此，為了證明定理1，實際需要證明的就是ID(u)QDMRID(u)DCMA

。即

delay(u)/ΔDelay(u)/(Δ+delay(u))

很明顯Δ+delay(u)Δ，定理1得證。

證明DCMA算法所建立的組播樹代價小于EPDT算法的方法同上。該證明方法與文獻[2]類似。

3.2 鏈路選擇函數

對于時延受限問題，為無約束問題設計的DDMC算法，它只考慮了優化費用而沒有考慮時延約束，會導致許多源節點到目的節點的路徑不滿足時延上限。QDMR指示函數只考慮了時延上限，未考慮加入樹的節點的剩余時延。而且EPDT和QDMR只是直接考慮費用累加最小，在本文中將時延和費用進行折中。對此，參考文獻[6]和算法KPP[7]中的加入了剩余時延的選擇函數，并綜合盡可能讓更多鏈路得到共享的思想，筆者采用這樣的鏈路選擇函數:

當Δ-delay(u)-delay(u，v)>0時，

cost(v)=ID(u)cost(u)+c(u，v)/(Δ-delay(u)-delay(u，v))

在不滿足該條件時，cost(v)的值為無窮大。

Delay(u，v)是u到節點v之間鏈路的時延。函數后面部分的分母代表了將v加入后，合成的樹里從源節點s到節點v的剩余時延。該鏈路選擇函數不僅考慮了給予目的節點優先級，還同時給予低時延路徑一定的優先。如果選擇cost(v)值較低的節點加入樹，選擇的就不僅是代價較小的路徑，同時也是剩余時延較大的路徑，使得路徑的選擇是時延和代價的一種折中。而且在選擇路徑時，由于對低時延路徑給予了一定的優先，能盡量降低由于只考慮代價而造成目的節點只能通過最小時延路徑連接進樹的可能性。

3.3 關鍵節點(key node)

建樹的主要目的是在滿足時延約束的情況下使樹的費用最小，即要使樹的鏈路數盡可能少。為了達到這個目的，建樹時就要盡量選擇共享性高的鏈路。

文獻[8]提出了關鍵(KN)節點的概念，指出若能在建樹時盡量采用組播節點間最短路徑通過次數較多的節點，那么選擇的鏈路共享性更高。結合鏈路選擇函數后將每條鏈路代價重新計算為c(u，v)/(Δ-delay(u，v))。其中u和v均是圖中節點，算法不是直接計算代價最小的路徑，而是計算上述值的和最小的組播節點間的路徑。按文獻[8]的所述方法，選用該最短路徑通過次數較多的節點作為KN節點并給予它們與目的節點一樣的優先級，使得建成的組播樹費用更小。

DCMA算法加入關鍵節點思想后，其指示函數ID(u)可寫成:

ID(u)=delay(u)/(Δ+delay(u)) 當u∈D∪K

1其他

4 算法步驟

算法的核心就是不斷重復尋找cost(v)最小的節點，并把它加入樹T。下面介紹算法將用到的幾個符號的含義。

Pred[v]:存放樹中節點v的父節點;

S:已經加入樹的節點的集合;

Q:圖中所有節點組成的隊列，到源節點路徑費用最低的節點有最高的優先級。

算法大致步驟如下:

a)用Dijkstra算法構建包含所有目的節點的時延最小組播樹。若源節點到任一目的節點路徑的時延不滿足所要求的Δ，證明給定Δ過小，算法停止。

b)重新計算每條鏈路代價，按文獻[8]所述方法計算節點權值，根據權值按高低找出0.5D(D為目的節點個數)個KN節點。

c)初始化。對于源節點s，令cost(s)=0，delay(s)=0，T=，S={s}，Q為圖中所有節點。從s開始搜索。圖中其他節點父節點置空，費用置為無窮大，把所有節點都放入優先級隊列Q。

d)節點添加階段。首先搜索與s相連的節點，選擇cost(u)最小的節點加入樹，置S=S∪{u}，更新Q，pred[u]=s。

然后搜索與已加入樹中的節點u相連的所有節點v，根據本文所提的指示函數ID(u)和鏈路選擇函數計算各自的cost(v)，選擇cost(v)值最小的節點加入樹，更新delay(v)，即S=S∪{v}，更新Q，v的父節點置為u;

如果DS，則算法結束，刪除所有不是目的節點的葉節點即為滿足時延限制的組播樹。否則重復搜索直到Q=。

e)合并并刪除回路。盡管在鏈路選擇函數中考慮了低時延路徑，但在時延約束較小的情況下，仍無法保證所有目的節點都能在上述步驟下全部添加進樹。對于最后仍沒能加入樹的目的節點d，處理思想與QDMR算法一樣。選擇將a)所建的路徑P′(s，d)與從b)~d)生成的子樹T′進行合并。為確保所有的目的節點滿足時延約束，當產生回路時保留時延最小的路徑，即刪除時應保留P′(s，d)的路徑。

通過上述過程將最終生成一棵滿足時延限制的組播樹T。

5 算法正確性的證明和復雜性分析

5.1 定理2

只要符合時延約束的組播樹存在，DCMA算法總能找出一棵符合約束條件的費用優化的組播樹。

證明 如果存在滿足時延約束的組播樹，那么從源節點到每個目的節點之間一定存在至少一條路徑滿足delay(s，v)Δ。若一些目的節點不能通過DCMA前四步所建立的初始樹建立起到源節點的滿足時延約束的低代價路徑，那么就選擇a)中的最小時延路徑與初始樹進行合并。最壞的情況是直接利用最小時延路徑連接源節點。所以綜上所述，可以找到滿足時延約束的組播樹。

5.2 算法時間復雜度分析

DCMA算法第一步中用Dijkstra算法求最短路徑樹，時間復雜度是O(n2);第二步計算關鍵節點的復雜度為O(mn2);第三步到第四步算法按文獻[1]中的方法可求得為O(Elogn)。所以算法總的時間復雜度是O(mn2)。

6 算法的動態性

當目的節點經常性變化，參與的節點會隨時加入或離開，需要對組播樹進行更新，這時的組播路由問題就是動態組播路由問題。如果用靜態啟發式算法來重新運算組播樹，那么代價是有一定的計算開銷，而且會造成正在傳送的數據丟失。在實際的網絡中，組播成員的變化可能會很頻繁，所以這種方法并不實用。因此，一個理想的動態組播路由算法是無須重組、復雜度低、樹的費用低的算法。利用DCMA算法并結合貪婪算法的思想來適應這一動態性，只會對原有的樹作局部的改變，而無須對整棵樹進行重組。

a)當有新節點d加入，如果d∈VT，即d是原組播樹上的一個中間轉發節點，這時無須對組播樹作修改，只需令d開始接收數據即可;如果dVT，根據DCMA的思想，先求d到樹中各個節點 (用u表示)的最小費用路徑(用c(u，d)表示)，然后再根據選擇函數進行計算:

當Δ-delay(u)-delya(u，d)>0時，

cost(d)=ID(u)cost(u)+c(u，d)/(Δ-delay(u)-delay(u，d))

其他條件下值為無窮大。

選擇cost(d)最小的路徑連接d。

b)目的節點d∈D請求離開組播樹:同貪婪算法。

7 應用舉例

假定網絡如圖1所示，源節點為s，目的節點集合為D={a，c，e}，鏈路的參數為(代價，時延)，時延約束Δ=7。

按照本文算法DCMA所得的組播樹如圖2(a)所示，其總代價為7(圖中粗線表示);按照DCMPH算法[9]所得的組播樹如圖2(b)所示，其總代價為11(圖中粗線表示)。按照QDMR算法所得的組播樹如圖2(c)所示，其總代價為9(圖中粗線表示)。CSDCM[10]、EPDT算法所建組播樹同QDMR。

在表1中對這五種算法所得的不同組播樹作了詳細的比較，QDMR、CSDCM、EPDT三種算法構建組播樹相同，DCMPH構建組播樹代價最大，時延最長，DCMA所構建組播樹代價和時延相比較而言性能較優。

8 結束語

本文提出了一種簡單的滿足時延約束的組播路由算法DCMA。它基于DDMC算法的基本思想進行擴展，采用綜合考慮了時延和代價的指示函數和鏈路選擇函數，并能支持動態組播。與基于信源的KPP[7]等算法相比，DCMA復雜度較低，更具實用性。

參考文獻:

[1]LIANG Guo， MATTA I.QDMR:an efficient QoS dependent multicast routing algorithm[C]//Proc of the 5th IEEE Real-time Technology and Applications Symposium. Vancouver， BC:[s.n.]， 1999:213-222.

[2]AISSA M， MNAOUER A B.A new delay-constrained algorithm for multicast routing tree construction[J]. International Journal of Communication Systems， 2004，17(10):985-1000.

[3]ALPERT C J，HU T C ，HUANG J H， et al. A direct combination of the prim and Dijkstra construction for improved performance-driven global routing[C]//Proc of IEEE International Symposium on Circuits and Systems. Chicago:[s.n.]， 1993:1869-1872.

[4]SHAIKH A，SHIN K. Destination-driven routing for low-cost multicast[J].IEEE Journal on Selected Areas in Communications，1997， 15(3):373-381.

[5]KARP R M. Reducibility among combinatorial problems[C]//Proc of Complexity of Computer Computations. New York : Plenum， 1972:85-103.

[6]RAQHAVAN S， MANIRNARAN G，SIVARARN M C. A rearrangeable algorithm for the construction of delay-constrained dynamic multicast trees[J]. IEEE/ACM Trans on Networking， 1999， 7(4):514-529.

[7]VACHASPATHI P ， KOMPELLAJ C， PASQUALE G， et al. Multicast routing for multimedia communication [J]. IEEE Slash ACM Trans on Networking， 1993， 1(3):286-292.

[8]余燕平.多播路由算法的研究[D]. 杭州:浙江大學，2002.

[9]周靈，孫亞民. 基于MPH的時延約束Steiner樹算法[J].計算機研究與發展，2008，45(5):810-816.

[10]KABAT M R， MOHANTY S K， MALL R， et al.An efficient heuristic algorithm for QoS-driven multicast tree generation[C]//Proc of the 14th International Conference on Advanced Computing and Communications. 2006:407-412.