摘 　要： 多點組播是指一個源點傳送信息到多個目的節點，它是網絡支持多媒體業務的關鍵技術之一。以服務質量(QoS)指標中的帶寬和時延為優化選路準則，提出了一種受限的組播路由算法，仿真結果證明了該算法的有效性。
　　關鍵詞： 網絡 組播 路由
　　通信網絡在進入90年代后，向著綜合業務的方向發展。在傳統的數據網絡中，路由所需考慮的僅是可連接性^[1]，路由算法在尋找最優(短)路徑時采用單一的指標，如跳數或時延。新出現的多媒體通信帶來了多點組播的需求，即未來的計算機網絡應該能夠提供例如電視會議、視頻點播等具有點對多點的業務要求。而這種網絡應該支持范圍廣泛的服務質量(QoS)需求，確定路由需要相當復雜的模型來描述網絡，即路由的優化指標要包括時延、帶寬、丟失率等。
　　近年來，各國學者開始在這方面探索，提出了一些快速有效的算法。如：基于最短路徑的Dijkstra算法^[2]，即計算源點到各目的點的最短路徑；另一類是求最小網絡代價(NC)的應用斯坦利(Steiner)樹路由算法^[3]，即計算組播樹(Multicast tree)，使其在任意一對源和目的節點之間都存在通路，并使其代價(cost)最小。
　　本文使用改進的受限Steiner樹路由算法，構造樹型路由結構來實現多點通信(multicast或MC)。這是由于基于樹實現有效MC路由具有以下兩個優點：(1)分組以并行方式沿著樹枝發送到不同的信宿；(2)網絡中需要傳送的復制分組最小，而且分組的復制只是在樹叉處進行。在QoS的參數中，本文選取最小化占用鏈路總帶寬和滿足端到端的時延限制為優化準則。
1 受限組播路由的算法
1.1 網絡模型
　　一個網絡可以表示為圖G(V，E)；其中V是頂點的集合，包括n個頂點；E是邊的集合，包括m條邊。每條邊e∈E具有兩個參數：C(e)和D(e)，C(e)是邊e上的正實數代價函數，D(e)是e上的正整數時延函數。在給定信源S和信宿集合D條件下，給定允許延遲極限Δ，構造根為S，覆蓋所有信宿節點的受限Steiner樹，滿足條件v∈D，樹上路徑(i，j)的延遲小于Δ，即：如果P(i、j)是樹上從i到j的路徑，那么對v∈D滿足：
　　Σ_e∈PD(i、j)＜Δ　　　　(1)
　　在滿足式(1)的條件下，
　　Σ_e∈PC(e)最小。　　　　(2)
1.2 算法實現機理
　　由于網絡中的Steiner問題屬于圖論中的NP完備問題^[4]，即，一般地說，最優算法無法在多項式時間內完成。因此，用啟發式算法可降低算法難度，而在性能上逼近理論算法。由于構造最小生成樹(MST)相對簡單，因此常用的是MST啟發式算法。
　　本文通過改進Prim算法^[2]來求解MST問題。Prim算法的基本思想為：假定G＝(V，E)是連通圖，T是G上MST中邊的集合。算法從U＝{S}(S為源點)，T＝Φ開始，重復執行下列操作：在所有u∈U、v∈{V－U}的邊(u、v)∈E中找一條權值最小的邊(u₀、v₀)并入集合T，同時u₀并入U，直到U＝V為止，則T為G的MST。
　　改進算法的基本思想是：首先利用Dijkstra第k最短路徑算法，計算從源節點到目的節點以時延為優化準則的路徑，并將所求的路徑中最大的時延與Δ比較，若該值比Δ大則表明限制條件太苛刻，可令Δ等于該值。然后以cost最小為首要優化目標，用Prim算法求出圖G的MST樹。用Prim算法每生成一條邊(i、j)時，就計算由S到該邊的累計時延Σ_e∈PD(i、j)、若Σ_e∈PD(i、j)≤Δ，則用Prim算法繼續尋找下一條邊。否則令該邊對應的cost(i、j)為∞，并且將j(i∈U、j∈{V－U})仍保留在原來集合中。當用Prim算法完成一次全局搜索后，再對那些仍保留在{V－U}集合中的點重新進行全局搜索(除開前次讓cost(i、j)為∞的i點外)，尋找符合時延條件的新邊。當U中已包含全部組播目標節點Di后，算法結束。
1.3 算法的實現過程
　　可采用一個整型二維數組a[MAX][3]來表示在構造最小生成樹U，{V－U}和權值cost的變化。其中數組的第一列a[][0]放生成樹的頂點集合U中的各頂點，初始值為源點s；第二列a[][1]放頂點集合{V－U}中的各頂點；第三列a[]^[2]放{V－U}到U所構成的邊的最小權值。同時，采用二維數組mat[MAX][MAX]來存儲圖的鄰接矩陣，矩陣(i、j)對應的值就是邊(i、j)上的cost值。開始對a[MAX][3]的初始化可表示為：
　　a[i][0]＝1；
　　if(i＝＝1)
　　a[i][1]＝0；
　　else
　　a[i][1]＝i;
　　a[i][2]＝mat[1][i];
　　然后按前面所述的改進Prim算法來搜索MST。具體實現過程可以用C語言編程實現。其流程圖如圖1所示。這里設Δ是合理的時延限制值，且整個網絡有n個節點。

　　本文提出的算法兼顧了滿足時延限制和代價最小兩個QoS要求，仿真結果也證明了該算法在力求代介最小的前提下，能根據組播應用時延的限制要求，快速有效地構造組播樹，有較強的實時性。
參考文獻
1 Gupta S. On routing in ATM networks、modeling and performance evaluation of ATM Technology.North－Holland:Elsevier Science Publisher B.V、1993:229～239
2 劉振宏，蔡茂誠譯.組合最優化.北京：清華大學出版社，1998
3 Hwang F K、Richards D S.Steiner tree problems.IEEE Networks、1992;22(1):55～89
4 M.R.Garey and D.S.Johnson、Computers and Intractability:A Guide to the Theory of NP－Completeness. San Francisco、CA:Freeman、1979