平面網(wǎng)絡(luò)中QOS多播路由算法研究與設(shè)計(jì)

梅創(chuàng)社

（陜西工業(yè)職業(yè)技術(shù)學(xué)院 陜西 咸陽(yáng) 712000）

網(wǎng)絡(luò)路由[1]包括兩個(gè)方面的任務(wù):一方面是收集網(wǎng)絡(luò)狀態(tài)信息并力求保持最新；另一方面，在獲取狀態(tài)信息的基礎(chǔ)上，為連接請(qǐng)求找到滿足某種要求的網(wǎng)絡(luò)路徑。目前所用到的大多數(shù)路由算法，不管是單播路由算法還是多播路由算法，都要求網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)維護(hù)著整個(gè)網(wǎng)絡(luò)的狀態(tài)信息。然而，由于網(wǎng)絡(luò)流量負(fù)載的快速變化，使得網(wǎng)絡(luò)中的節(jié)點(diǎn)所獲取的狀態(tài)信息變得不及時(shí)和不精確，即動(dòng)態(tài)網(wǎng)絡(luò)中的狀態(tài)信息存在著固有的非精確性。

隨著Internet中多媒體業(yè)務(wù)與實(shí)時(shí)業(yè)務(wù)快速發(fā)展，QOS多播路由問(wèn)題在網(wǎng)絡(luò)研究領(lǐng)域己經(jīng)得到了越來(lái)越多的重視和關(guān)注。多播路由及其QOS擴(kuò)展的主要目標(biāo)是要構(gòu)造一棵滿足某些性能約束（例如，端到端的延遲有界、延遲抖動(dòng)有界、最小可用帶寬以及最大包丟失率等）并對(duì)某個(gè)目標(biāo)函數(shù)（例如，能反應(yīng)網(wǎng)絡(luò)資源利用的網(wǎng)絡(luò)代價(jià)）進(jìn)行優(yōu)化的多播樹(shù)。

傳統(tǒng)的多播路由協(xié)議，例如DVMRP和PIM，主要為“盡力而為”的數(shù)據(jù)流設(shè)計(jì)，其多播樹(shù)的構(gòu)造主要是基于網(wǎng)絡(luò)拓?fù)涞倪B接性，并且不帶有QOS約束。但最近卻出現(xiàn)了一些帶QOS約束的多播路由算法，這些算法通常運(yùn)用一個(gè)啟發(fā)式的方案來(lái)化解帶約束的Steiner樹(shù)（例如，延遲受限的最小代價(jià)樹(shù)）這類NP一完全問(wèn)題。然而，這些算法在計(jì)算路由時(shí)，通常需要用到全局的網(wǎng)絡(luò)狀態(tài)信息，而且也沒(méi)有能夠很好地處理多播組成員的動(dòng)態(tài)加入和退出，消息交換的負(fù)載也很大，因此，它們中的多數(shù)在Internet中并不實(shí)用。

1 網(wǎng)絡(luò)模型

1.1 路由模型

設(shè)一加權(quán)有向連通圖 G=（V，E）表示整個(gè)通信網(wǎng)絡(luò)[2]，其中V是網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，E是全雙工有向鏈路的集合，V和E分別表示網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)和鏈路數(shù)。不失一般性，只考慮簡(jiǎn)單圖（即每對(duì)節(jié)點(diǎn)之間最多只能有一條鏈路的網(wǎng)絡(luò)）。

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

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

這里同樣采用概率分布的方式來(lái)描述狀態(tài)信息的非精確性，即希望找到最大可能地滿足連接請(qǐng)求對(duì)服務(wù)性能的要求并具有最小網(wǎng)絡(luò)代價(jià)的路由路徑。在全部的QOS度量中，例如，端到端的延遲、延遲抖動(dòng)、最小可用帶寬、最大包丟失率以及網(wǎng)絡(luò)代價(jià)等，由于最小鏈路帶寬和端到端的延遲最具代表性，其它的特征值往往受到這兩個(gè)特征值的影響和制約，而網(wǎng)絡(luò)代價(jià)通常僅作為優(yōu)化的目標(biāo)，同時(shí)為了使問(wèn)題的模型簡(jiǎn)化，因此這里僅考慮帶寬和延遲這兩個(gè)QOS特征值。

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

1.2 非精確狀態(tài)模型

網(wǎng)絡(luò)節(jié)點(diǎn)在進(jìn)行路由計(jì)算時(shí)必然要用到網(wǎng)絡(luò)狀態(tài)信息（包括本地的和遠(yuǎn)程的狀態(tài)信息），本地的狀態(tài)信息通常時(shí)及時(shí)的、精確的，而遠(yuǎn)程狀態(tài)信息往往又是不及時(shí)和不精確的。同時(shí)，遠(yuǎn)程的狀態(tài)信息被路由協(xié)議按照一定的頻率或者機(jī)制進(jìn)行更新，狀態(tài)更新越頻繁，狀態(tài)信息就越精確，但是，過(guò)于頻繁的更新會(huì)增加網(wǎng)絡(luò)中的消息負(fù)載，反而會(huì)降低狀態(tài)信息的精確性。狀態(tài)信息[4]包括:1）網(wǎng)絡(luò)拓?fù)涞倪B接性；2）鏈路狀態(tài)信息，包括鏈路的剩余帶寬、傳輸延遲和代價(jià)；3）節(jié)點(diǎn)狀態(tài)信息，包括節(jié)點(diǎn)中的隊(duì)列延遲以及節(jié)點(diǎn)的代價(jià)。

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

1）網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)經(jīng)常改變，但它的變化頻率要遠(yuǎn)遠(yuǎn)低于QOS特征值（如帶寬、延遲等）的變化頻率；

2）鏈路的傳輸延遲由鏈路的歐幾里得長(zhǎng)度來(lái)決定，其變化量極小，可以忽略；

3）在所有的QOS度量中，網(wǎng)絡(luò)代價(jià)與其它的QOS特征值不同，它通常不作為一個(gè)QOS約束，而是作為一個(gè)目標(biāo)函數(shù)進(jìn)行優(yōu)化，因此，網(wǎng)絡(luò)代價(jià)的非精確性可以被忽略。

2 QMRI算法描述

2.1 基本思想

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

QMRI[5]所用到的主要控制報(bào)文定義如下:

1）加入請(qǐng)求報(bào)文（Join-Req）

Join-Req是一種加入請(qǐng)求的探測(cè)報(bào)文，它由準(zhǔn)備加入多播會(huì)話的節(jié)點(diǎn)發(fā)向該多播會(huì)話的源節(jié)點(diǎn)，該報(bào)文不僅能沿路累計(jì)可加性的QOS度量（如延遲、延遲抖動(dòng)、代價(jià)等），還可以記錄鏈路帶寬等凹性狀態(tài)參數(shù)的最小值；

2）綠色確認(rèn)報(bào)文（Reply-G）

Reply-G是一種接受確認(rèn)報(bào)文，它由接受加入請(qǐng)求的多播源節(jié)點(diǎn)發(fā)向準(zhǔn)備加入的新成員（這里的成員指的是成員節(jié)點(diǎn)，為了描述方便，我們經(jīng)常混用成員和成員節(jié)點(diǎn)的概念，其實(shí)，它們的含義并不相同），這就意味著某條路徑完全滿足帶寬和延遲的要求，該路徑稱為可行路徑；

3）黃色預(yù)警報(bào)文（Reply-Y）

Reply-Y是一種預(yù)警報(bào)文，它由某個(gè)上游節(jié)點(diǎn)發(fā)向準(zhǔn)備加入多播會(huì)話的新成員節(jié)點(diǎn)，這意味著某條路徑只能部分滿足帶寬和延遲的要求，這種路徑稱為可能可行路徑；

4）紅色拒絕報(bào)文（Reply-R）

Reply-R是一種拒絕報(bào)文，它由某個(gè)拒絕加入的上游節(jié)點(diǎn)發(fā)向準(zhǔn)備加入多播會(huì)話的節(jié)點(diǎn)，這就意味著某條路徑根本不能滿足帶寬和延遲的要求，這種路徑稱為不可行路徑。

在多播會(huì)話進(jìn)行的過(guò)程中，其組成員應(yīng)該能夠動(dòng)態(tài)地加入/退出該多播會(huì)話，而且組成員的加入/退出不能對(duì)正在進(jìn)行的多播會(huì)話產(chǎn)生干擾。為此，采取漸進(jìn)生成多播樹(shù)的方式以實(shí)現(xiàn)多播會(huì)話各個(gè)狀態(tài)之間的無(wú)縫遷移[6]。另外，當(dāng)一個(gè)多播成員欲退出多播會(huì)話時(shí)，它應(yīng)沿著多播樹(shù)枝向樹(shù)上的分叉節(jié)點(diǎn)發(fā)送一退出報(bào)文，分叉節(jié)點(diǎn)在接收到退出報(bào)文后，將釋放相應(yīng)的網(wǎng)絡(luò)資源，多播樹(shù)其它的部分保持不變。

2.2 資源預(yù)留

在加入請(qǐng)求報(bào)文最終到達(dá)了源節(jié)點(diǎn)并通過(guò)了合法性檢查之后，連接初始化和資源預(yù)留過(guò)程開(kāi)始啟動(dòng)。這時(shí)，資源預(yù)留報(bào)文Resv由源節(jié)點(diǎn)，加上時(shí)間戳T，之后發(fā)向新成員t，并沿著加入請(qǐng)求報(bào)文in-Req經(jīng)過(guò)的路徑反向進(jìn)行資源預(yù)留。當(dāng)Resv到達(dá)某個(gè)中間節(jié)點(diǎn)（例如k，且k目前還不是多播樹(shù)上的節(jié)點(diǎn)）時(shí)，如果節(jié)點(diǎn)k有可供預(yù)留的資源，就為該多播會(huì)話預(yù)留資源并繼續(xù)前遞Resv，否則它將沿著Resv和Join-Req經(jīng)過(guò)的路徑向s和t分別反向發(fā)送一預(yù)留撤消報(bào)文Resv-Und，通知它們資源預(yù)留過(guò)程失敗，并沿路撤消己經(jīng)預(yù)留的資源。

2.3 退出過(guò)程

當(dāng)成員節(jié)點(diǎn)t要求退出多播會(huì)話時(shí)，如果r是多播樹(shù)的葉子節(jié)點(diǎn)，則向其上游節(jié)點(diǎn)發(fā)送一剪枝報(bào)文Prune，Prune被傳送至樹(shù)叉節(jié)點(diǎn)后，樹(shù)又節(jié)點(diǎn)將刪除關(guān)于t的路由信息并釋放相關(guān)的網(wǎng)絡(luò)資源，多播樹(shù)其余的部分保持不變；否則，不需要作處理。從上述過(guò)程可以看出，在我們的算法中，中間節(jié)點(diǎn)能夠執(zhí)行一個(gè)分布式的路由計(jì)算，因此QMRI是一個(gè)分布式的多播路由算法，具有分布式路由算法的優(yōu)點(diǎn)，但它僅適用于平面網(wǎng)絡(luò)或?qū)哟尉W(wǎng)絡(luò)的域內(nèi)工作環(huán)境。

3 正確性與復(fù)雜性

3.1 正確性

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

定理1在QMRI算法的UR工作模式下，如果有一條路徑滿足帶寬和延遲約束，那么，這條路徑是一條新成員節(jié)點(diǎn)連向多播樹(shù)的可行性路徑，并且也是最優(yōu)的路徑。此時(shí)，算法只需要探索這條單一的路徑。證明如前所述，滿足帶寬與延遲約束的路徑的值等于可行性路徑，又因?yàn)閁R模式使用了以網(wǎng)絡(luò)代價(jià)作為優(yōu)化目標(biāo)的鏈路狀態(tài)協(xié)議，因此，這條可行性路徑也是一條最優(yōu)（代價(jià)最?。┑穆窂?，算法只需要探索這條路徑。此定理得證口

定理2在TL工作模式下，如果存在一條最優(yōu)或次優(yōu)的路徑，那么，QMRI就能夠找到它。 證明在TL模式下，QMRI以分叉路由的方式啟動(dòng)，分叉節(jié)點(diǎn)向多個(gè)直接上游節(jié)點(diǎn)發(fā)送多條探測(cè)報(bào)文，因此，多條可行的或者可能可性的路徑能

夠被探測(cè)到。多條Reply-G或Reply-Y消息被回送給分叉節(jié)點(diǎn)，相應(yīng)的代價(jià)或概率值能夠被比較。在多條可行或者可能可性的路徑中，如果某條路徑的代價(jià)最小或者概率值最小，那么，這條路徑就是最優(yōu)或次優(yōu)的路徑。

定理3 QMRI所探測(cè)的可行或者可能可行的路徑不存在環(huán)路。證明在QMRI算法中，多播路由表的條目包括一個(gè)數(shù)據(jù)包入口和多個(gè)出口，因此，加入多播會(huì)話的成員節(jié)點(diǎn)將形成一個(gè)樹(shù)狀結(jié)構(gòu)，QMRI所探測(cè)的可行性路徑或者可能可行的路徑也會(huì)形成一個(gè)樹(shù)形結(jié)構(gòu)，從而不存在環(huán)路。此定理得證口

定理4如果存在一條可行或者可能可行的路徑，那么，QMRI能夠發(fā)現(xiàn)它。

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

3.2 復(fù)雜性

構(gòu)造一棵多播樹(shù)的計(jì)算復(fù)雜性和所需要的消息數(shù)量是影響QOS多播路由算法復(fù)雜性的兩個(gè)主要因素。

如果采取按需路由的計(jì)算方式，那么，QMRI的計(jì)算復(fù)雜性僅僅依賴于QOS單播路由協(xié)議。目前，帶2個(gè)QOS度量約束（帶寬和延遲約束）的啟發(fā)式QOS單播路由算法的計(jì)算復(fù)雜度為 O（|V||E|）。這里的|V|為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)，|V|為鏈路數(shù)。對(duì)于大多數(shù)網(wǎng)絡(luò)，|E|=O|V|，因此，QOS單播路由算法的計(jì)算復(fù)雜度為O（|V|2）。對(duì)于有|M|個(gè)成員的多播組，其計(jì)算代價(jià)應(yīng)為|V|2|M|，因此，QMRI的計(jì)算復(fù)雜度為 O（|V|2|M|）。

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

4 結(jié)束語(yǔ)

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

[1]張寶賢，劉越，陳常嘉.QOS路由的多路徑算法[J].電子學(xué)報(bào) ，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]李臘元，李春林.動(dòng)態(tài)QOS多播路由協(xié)議[J].電子學(xué)報(bào)，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組播路由問(wèn)題求解[J].河北工業(yè)大學(xué)學(xué)報(bào)，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].計(jì)算機(jī)學(xué)報(bào)，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]王征應(yīng)，石冰心.基于啟發(fā)式遺傳算法的QOS組播路由問(wèn)題求解[J].計(jì)算機(jī)學(xué)報(bào)，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]閔應(yīng)驊.計(jì)算機(jī)網(wǎng)絡(luò)路由研究綜述[J].計(jì)算機(jī)學(xué)報(bào)，2003（6）：41-42.

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

[7]雷擎，王行剛.計(jì)算機(jī)網(wǎng)絡(luò)模擬方法與工具[J].通信學(xué)報(bào)，2001（9）：78-82.

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