平面網絡中QOS多播路由算法研究與設計

梅創社

（陜西工業職業技術學院 陜西 咸陽 712000）

網絡路由[1]包括兩個方面的任務:一方面是收集網絡狀態信息并力求保持最新；另一方面，在獲取狀態信息的基礎上，為連接請求找到滿足某種要求的網絡路徑。目前所用到的大多數路由算法，不管是單播路由算法還是多播路由算法，都要求網絡中的每個節點維護著整個網絡的狀態信息。然而，由于網絡流量負載的快速變化，使得網絡中的節點所獲取的狀態信息變得不及時和不精確，即動態網絡中的狀態信息存在著固有的非精確性。

隨著Internet中多媒體業務與實時業務快速發展，QOS多播路由問題在網絡研究領域己經得到了越來越多的重視和關注。多播路由及其QOS擴展的主要目標是要構造一棵滿足某些性能約束（例如，端到端的延遲有界、延遲抖動有界、最小可用帶寬以及最大包丟失率等）并對某個目標函數（例如，能反應網絡資源利用的網絡代價）進行優化的多播樹。

傳統的多播路由協議，例如DVMRP和PIM，主要為“盡力而為”的數據流設計，其多播樹的構造主要是基于網絡拓撲的連接性，并且不帶有QOS約束。但最近卻出現了一些帶QOS約束的多播路由算法，這些算法通常運用一個啟發式的方案來化解帶約束的Steiner樹（例如，延遲受限的最小代價樹）這類NP一完全問題。然而，這些算法在計算路由時，通常需要用到全局的網絡狀態信息，而且也沒有能夠很好地處理多播組成員的動態加入和退出，消息交換的負載也很大，因此，它們中的多數在Internet中并不實用。

1 網絡模型

1.1 路由模型

設一加權有向連通圖 G=（V，E）表示整個通信網絡[2]，其中V是網絡中節點的集合，E是全雙工有向鏈路的集合，V和E分別表示網絡中的節點數和鏈路數。不失一般性，只考慮簡單圖（即每對節點之間最多只能有一條鏈路的網絡）。

假設 s（s∈V為一多播樹的源節點，M（M?c{V-{s}}）為該多播樹的目的節點集，R+為正實數集。對于任何一條鏈路e（e∈E），定義鏈路狀態信息（或稱為鏈路的QOS特征值）為:帶寬函數 bw（e）:E→R+，延遲函數 delay（e）:E→R+，代價函數cost（e）:E→R+。 類似地，對于任一節點 n∈V ，定義節點狀態信息（或稱為節點的QOS特征值）為:延遲函數delay（n）:V→R+。 用 T（s，M}表示一棵多播樹。

如前所述，盡管目前有一些分布式的QOS多播路由算法在路由計算時只使用了較為精確的局部（或本地）的狀態信息，但它們都是以單播源路由算法作為其路由計算的基礎，因此，同樣會不可避免地涉及到狀態信息的非精確性問題。

這里同樣采用概率分布的方式來描述狀態信息的非精確性，即希望找到最大可能地滿足連接請求對服務性能的要求并具有最小網絡代價的路由路徑。在全部的QOS度量中，例如，端到端的延遲、延遲抖動、最小可用帶寬、最大包丟失率以及網絡代價等，由于最小鏈路帶寬和端到端的延遲最具代表性，其它的特征值往往受到這兩個特征值的影響和制約，而網絡代價通常僅作為優化的目標，同時為了使問題的模型簡化，因此這里僅考慮帶寬和延遲這兩個QOS特征值。

假設B和D分別為多播樹T（s，硒中所有路徑的最小剩余帶寬和最大延遲約束，P*為源節點與某個目的節點t之間全部路徑中的最佳路徑，那么有帶寬和延遲保證的多播路由問題可以表示[3]為:

1.2 非精確狀態模型

網絡節點在進行路由計算時必然要用到網絡狀態信息（包括本地的和遠程的狀態信息），本地的狀態信息通常時及時的、精確的，而遠程狀態信息往往又是不及時和不精確的。同時，遠程的狀態信息被路由協議按照一定的頻率或者機制進行更新，狀態更新越頻繁，狀態信息就越精確，但是，過于頻繁的更新會增加網絡中的消息負載，反而會降低狀態信息的精確性。狀態信息[4]包括:1）網絡拓撲的連接性；2）鏈路狀態信息，包括鏈路的剩余帶寬、傳輸延遲和代價；3）節點狀態信息，包括節點中的隊列延遲以及節點的代價。

在這些狀態信息中，鏈路剩余帶寬和節點中隊列延遲的變化最為頻繁，由此而產生的不精確性也最為顯著。由于鏈路剩余帶寬和節點中隊列延遲最具代表性，為了使問題簡化，這里僅考慮這兩種狀態信息的不精確性。這種簡化對路由性能的影響不會太明顯，主要有以下幾點原因:

1）網絡的拓撲結構經常改變，但它的變化頻率要遠遠低于QOS特征值（如帶寬、延遲等）的變化頻率；

2）鏈路的傳輸延遲由鏈路的歐幾里得長度來決定，其變化量極小，可以忽略；

3）在所有的QOS度量中，網絡代價與其它的QOS特征值不同，它通常不作為一個QOS約束，而是作為一個目標函數進行優化，因此，網絡代價的非精確性可以被忽略。

2 QMRI算法描述

2.1 基本思想

我們所提出的路由算法工作在某些單播路由協議 （例如，距離向量協議）的上層，需要這些單播路由協議為我們的算法執行某些預計算。與其它的QOS多播路由算法不同，由QMRI構造的多播樹不僅能夠滿足帶寬和延遲的要求，而且能夠最大可能地滿足帶寬和延遲的要求，且具有最優（或近優）的整體代價。我們的算法是一種基于交通燈（（Traffic Lights，TL）的路由算法，它能夠在兩種工作模式下并行地探索多條可行的路由路徑，并通過觀察控制報文的顏色來決定路由。這種路由機制與交通燈控制道路交通的原理類似。

QMRI[5]所用到的主要控制報文定義如下:

1）加入請求報文（Join-Req）

Join-Req是一種加入請求的探測報文，它由準備加入多播會話的節點發向該多播會話的源節點，該報文不僅能沿路累計可加性的QOS度量（如延遲、延遲抖動、代價等），還可以記錄鏈路帶寬等凹性狀態參數的最小值；

2）綠色確認報文（Reply-G）

Reply-G是一種接受確認報文，它由接受加入請求的多播源節點發向準備加入的新成員（這里的成員指的是成員節點，為了描述方便，我們經常混用成員和成員節點的概念，其實，它們的含義并不相同），這就意味著某條路徑完全滿足帶寬和延遲的要求，該路徑稱為可行路徑；

3）黃色預警報文（Reply-Y）

Reply-Y是一種預警報文，它由某個上游節點發向準備加入多播會話的新成員節點，這意味著某條路徑只能部分滿足帶寬和延遲的要求，這種路徑稱為可能可行路徑；

4）紅色拒絕報文（Reply-R）

Reply-R是一種拒絕報文，它由某個拒絕加入的上游節點發向準備加入多播會話的節點，這就意味著某條路徑根本不能滿足帶寬和延遲的要求，這種路徑稱為不可行路徑。

在多播會話進行的過程中，其組成員應該能夠動態地加入/退出該多播會話，而且組成員的加入/退出不能對正在進行的多播會話產生干擾。為此，采取漸進生成多播樹的方式以實現多播會話各個狀態之間的無縫遷移[6]。另外，當一個多播成員欲退出多播會話時，它應沿著多播樹枝向樹上的分叉節點發送一退出報文，分叉節點在接收到退出報文后，將釋放相應的網絡資源，多播樹其它的部分保持不變。

2.2 資源預留

在加入請求報文最終到達了源節點并通過了合法性檢查之后，連接初始化和資源預留過程開始啟動。這時，資源預留報文Resv由源節點，加上時間戳T，之后發向新成員t，并沿著加入請求報文in-Req經過的路徑反向進行資源預留。當Resv到達某個中間節點（例如k，且k目前還不是多播樹上的節點）時，如果節點k有可供預留的資源，就為該多播會話預留資源并繼續前遞Resv，否則它將沿著Resv和Join-Req經過的路徑向s和t分別反向發送一預留撤消報文Resv-Und，通知它們資源預留過程失敗，并沿路撤消己經預留的資源。

2.3 退出過程

當成員節點t要求退出多播會話時，如果r是多播樹的葉子節點，則向其上游節點發送一剪枝報文Prune，Prune被傳送至樹叉節點后，樹又節點將刪除關于t的路由信息并釋放相關的網絡資源，多播樹其余的部分保持不變；否則，不需要作處理。從上述過程可以看出，在我們的算法中，中間節點能夠執行一個分布式的路由計算，因此QMRI是一個分布式的多播路由算法，具有分布式路由算法的優點，但它僅適用于平面網絡或層次網絡的域內工作環境。

3 正確性與復雜性

3.1 正確性

下面幾個非形式化的定理可以證明QMRI算法的正確性。

定理1在QMRI算法的UR工作模式下，如果有一條路徑滿足帶寬和延遲約束，那么，這條路徑是一條新成員節點連向多播樹的可行性路徑，并且也是最優的路徑。此時，算法只需要探索這條單一的路徑。證明如前所述，滿足帶寬與延遲約束的路徑的值等于可行性路徑，又因為UR模式使用了以網絡代價作為優化目標的鏈路狀態協議，因此，這條可行性路徑也是一條最優（代價最小）的路徑，算法只需要探索這條路徑。此定理得證口

定理2在TL工作模式下，如果存在一條最優或次優的路徑，那么，QMRI就能夠找到它。 證明在TL模式下，QMRI以分叉路由的方式啟動，分叉節點向多個直接上游節點發送多條探測報文，因此，多條可行的或者可能可性的路徑能

夠被探測到。多條Reply-G或Reply-Y消息被回送給分叉節點，相應的代價或概率值能夠被比較。在多條可行或者可能可性的路徑中，如果某條路徑的代價最小或者概率值最小，那么，這條路徑就是最優或次優的路徑。

定理3 QMRI所探測的可行或者可能可行的路徑不存在環路。證明在QMRI算法中，多播路由表的條目包括一個數據包入口和多個出口，因此，加入多播會話的成員節點將形成一個樹狀結構，QMRI所探測的可行性路徑或者可能可行的路徑也會形成一個樹形結構，從而不存在環路。此定理得證口

定理4如果存在一條可行或者可能可行的路徑，那么，QMRI能夠發現它。

證明在QMRI算法中，路徑探測過程以UR模式啟動，根據定理1，如果被探測的路徑滿足帶寬與延遲約束，那么該路徑即為可行且最優的路徑。當這種條件不成立的情況下，也就是當某個節點收到了Reply-Y或Reply-R消息的時候，QMRI就從UR模式切換到TL模式。在這種情況下，該節點將分別沿著多條路徑向源節點發送多條Join-Req信息，用于對各條可能路徑的探索。在這些分支路徑中，如果存在可行或者可能可行的路徑，那么，它們定能被發現。因此，使用UR和TL兩種工作模式，QMRI一定能發現那些可行或者可能可行的路徑。

3.2 復雜性

構造一棵多播樹的計算復雜性和所需要的消息數量是影響QOS多播路由算法復雜性的兩個主要因素。

如果采取按需路由的計算方式，那么，QMRI的計算復雜性僅僅依賴于QOS單播路由協議。目前，帶2個QOS度量約束（帶寬和延遲約束）的啟發式QOS單播路由算法的計算復雜度為 O（|V||E|）。這里的|V|為網絡中的節點數，|V|為鏈路數。對于大多數網絡，|E|=O|V|，因此，QOS單播路由算法的計算復雜度為O（|V|2）。對于有|M|個成員的多播組，其計算代價應為|V|2|M|，因此，QMRI的計算復雜度為 O（|V|2|M|）。

對于消息交換，QMRI主要處理4種類型的消息:Join-Req，Reply-G，Reply-Y和Reply-R。然而，在計算過程的每一步，QMRI最多只處理3種消息。這就意味著對于一個有|M|個成員的多播組，需要處理的消息數應該為3|M|。在被接受或被拒絕之前，Join-Req消息所經過的跳數至多為|E|，因此，在多個成員節點的加入過程中，需要處理的消息數最多為3|ME|。 由此可見，QMRI的消息復雜度應為 O（3|ME|）。

4 結束語

提出一種基于交通燈的分布式QOS多播路由算法一QMRI，該算法能有效地工作在狀態信息不精確的動態網絡中。大量的仿真實驗顯示了我們的路由算法具有較高的路由成功率和適度的消息負載[7]，而且生成的多播樹具有很低的網絡代價。最為重要的是，QMRI能夠高度適應網絡狀態信息的非精確性。

[1]張寶賢，劉越，陳常嘉.QOS路由的多路徑算法[J].電子學報 ，2000（7）：55-57.

ZHANG Bao-xian，LIU Yue，CHEN Chang-jia.QOS routing path algorithm[J].Chinese Journal of Electronics，2000（7）:55-57.

[2]李臘元，李春林.動態QOS多播路由協議[J].電子學報，2003（9）：23-24.

LI La-yuan，LI Chun-lin.Dynamic QOS multicast routing protocol[J].Chinese Journal of electronics，2003（9）：23-24.

[3]顧軍華，侯向丹，宋潔，等.基于螞蟻算法的QOS組播路由問題求解[J].河北工業大學學報，2002（4）：52-54.

GU Jun-hua，HOU Xiang-dan，SONG Jie，et al.Based on Ant Algorithm for solving QOS multicast routing problem[J].Journal of Hebei University of Technology，2002（4）:52-54.

[4]陸慧梅，向勇，史美林.支持QOS的層次組播路由算法框架QHMR[J].計算機學報，2004（6）：56-57.

LU Hui-mei，XIANG Yong，SHIMei-lin.QOS support hierarchical multicast routing algorithm framework of QHMR[J].Chinese Journal of Computers，2004（6）:56-57.

[5]王征應，石冰心.基于啟發式遺傳算法的QOS組播路由問題求解[J].計算機學報，2001（1）：65-68.

WANG Zheng-ying，SHI Bing-xin.Based on heuristic genetic algorithm for solving QOS multicast routing problem[J].Chinese Journal of Computers，2001（1）:65-68.

[6]閔應驊.計算機網絡路由研究綜述[J].計算機學報，2003（6）：41-42.

MIN Ying-hua.Survey on computer network routing[J].Chinese Journal of Computers，2003（6）:41-42.

[7]雷擎，王行剛.計算機網絡模擬方法與工具[J].通信學報，2001（9）：78-82.

LEI Qing，WANG Hang-gang.The computer network simulation methodologies and tools[J].Journal of communication，2001（9）:78-82.