一種基于非線性長度的多約束路由算法

(1.華南理工大學(xué) 電子與信息學(xué)院， 廣州 510640；2.廣東輕工職業(yè)技術(shù)學(xué)院 管理系， 廣州 510300) 

摘要：滿足多個約束的QoS路由問題已經(jīng)被證明是NP完全問題。在分析了多種路由算法的基礎(chǔ)上，設(shè)計(jì)了一種高效的多約束路由算法。該算法采用非線性路徑長度計(jì)算方法。為提高算法的成功率，在節(jié)點(diǎn)的松弛過程中設(shè)計(jì)了節(jié)點(diǎn)動態(tài)路徑長度計(jì)算，允許節(jié)點(diǎn)作多次松弛。為提高算法的執(zhí)行效率，在節(jié)點(diǎn)正向松弛和反向估計(jì)過程中引入了受控路徑的思想，使算法得到了優(yōu)化。大量仿真表明，該算法在最短路徑獲取和路由發(fā)現(xiàn)成功率方面都有高效的表現(xiàn)。



關(guān)鍵詞：服務(wù)質(zhì)量路由；多約束；非線性路徑長度

中圖分類號：TP393文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)11-3408-04



Algorithm for multi-constrained routing based on nonlinear path length



LIU Yong-guang1，2，YE Wu1， FENG Sui-li1

(1.School of Electronic Information Engineering， South China University of Technology， Guangzhou 510640， China；2.Dept. of Management， Guangdong Industry Technical College， Guangzhou 510300， China)Abstract:The problem of finding a path that satisfies multiple constraints has been proved a NP-complete problem.Based on the analysis of some algorithms in this field，proposed an efficient multi-constrained routing algorithm.The new algorithm adopted the idea of nonlinear path length. In order to improve the success ratio，designed a dynamic path selection method for nodes， which demanded that nodes be relaxed for more times.For the reason of improving algorithm efficiently，addedthe concept of dominated path to the process of selecting more weights sum for path calculation. Large simulations prove that the new algorithm has high efficiency in success ratio and finding the shorter path.

Key words:QoS routing; multi-constrained; nonlinear path length

0引言

在下一代通信網(wǎng)絡(luò)中，隨著網(wǎng)絡(luò)業(yè)務(wù)的多樣化和復(fù)雜化，如何為不同業(yè)務(wù)需求提供不同的服務(wù)質(zhì)量保證是下一代網(wǎng)絡(luò)能否順利實(shí)施的關(guān)鍵性因素。因此，對滿足多種度量的QoS路由算法研究一直是一個具有挑戰(zhàn)性的熱點(diǎn)領(lǐng)域，文獻(xiàn)[1]對當(dāng)前的研究進(jìn)展作了總結(jié)性論述。基于QoS的多約束路由問題通常分為兩類：a)鏈路約束。它可以轉(zhuǎn)換為整個路徑上瓶頸鏈路的約束，如帶寬。b）路徑約束。它是對組成端到端路徑上所有鏈路的約束。依據(jù)文獻(xiàn)[2]的分類，該類約束還可以分為加性約束和乘性約束，前者如延遲、抖動、花費(fèi)、跳數(shù)等，后者如可靠性、包丟失率等。對于鏈路約束，可以通過剪枝法預(yù)先去除不符合要求的鏈路，從而保證在剩余子圖中求得滿足約束條件的鏈路。本文研究的是路徑約束，而且僅限于加性約束，且滿足多個約束（約束個數(shù)K≥2）的情況。

對于在一個圖中尋找滿足多個約束條件的最優(yōu)路徑問題，已經(jīng)被證明是一個NP完全問題^[3]。對于這樣的NP完全問題，提出了一些啟發(fā)式算法。Iwata等人^[4]提出了一個多項(xiàng)式時間算法來解決多約束路徑問題。該算法首先基于一個QoS度量求出一條（或多條）最短路徑；然后檢查該條路徑是否滿足其他約束條件。如果條件不滿足，使用另外的一個度量。重復(fù)以上過程，直到發(fā)現(xiàn)一條滿足條件的路徑或者所有的度量都被嘗試到。這種算法的最大問題是對于單個的一個度量產(chǎn)生的最短路徑，無法保證其滿足其他度量產(chǎn)生的約束。但是，如果所有的鏈路權(quán)重是正相關(guān)的，如一個權(quán)重變小，其他的權(quán)重隨之變小，這種情況下該算法的表現(xiàn)最好。SAMCRA（self-adaptive multiple constraints routing algorithm）^[5]是一個確切算法，TAMCRA（tunable accuracy multiple constrained routing algorithm）^[6]是一個啟發(fā)式算法。這兩個算法都基于非線性路徑長度和k-shortest最短路徑方法。對于TAMCRA算法來說，由于k是固定的，該算法的復(fù)雜度是多項(xiàng)式時間的。但是對于確切算法SAMCRA來說，在最壞情況下k值會呈指數(shù)增長，所以k值的大小對該算法的復(fù)雜度起著決定性的影響，一個大的k值將使該算法失去使用價值。SAMCRA算法可以保證如果存在可行路徑，就能發(fā)現(xiàn)一條滿足約束條件的路徑。在這個過程中，該算法根據(jù)非支配思想來自適應(yīng)動態(tài)調(diào)整每個節(jié)點(diǎn)需要存儲的路徑數(shù)量，并分配相應(yīng)的存儲空間。而在TAMCRA算法中，k值是預(yù)先定義好的，空間也按照k值預(yù)先分配。Korkmaz等人^[7]提出了一種隨機(jī)啟發(fā)式算法來解決多約束路徑問題。該算法的核心思想是算法在搜索路徑的執(zhí)行過程中作出隨機(jī)決策，從而避免一些無法預(yù)料的陷阱。H_MCOP是Korkmaz等人^[8]提出的一種啟發(fā)式算法，該算法試圖采用非線性路徑長度來發(fā)現(xiàn)滿足約束的路徑。此外，該算法還試圖同時找到一條路徑長度最短的路徑。Yuan和Liu^[9，10]提出的極限路徑啟發(fā)式算法是一個擴(kuò)展的Bellman-Ford算法，并在算法中引入了TAMCRA算法的基本思想。Liu等人考慮不僅發(fā)現(xiàn)一條而是發(fā)現(xiàn)k條滿足約束路徑的算法，他們提出了一個稱為A*剪枝的確切算法^[11]。該算法采用了Jaffe的路徑長度，如果存在k條可行的路徑，該算法獲得滿足約束的那些路徑。

目前這些算法各有優(yōu)缺點(diǎn)，但是都具有較大的局限性：a）算法復(fù)雜且計(jì)算復(fù)雜度較高；b）算法性能表現(xiàn)不盡如人意，算法成功率較低且路徑長度優(yōu)化不理想；c）算法針對某些特殊情況，普適性較差。本文提出的啟發(fā)式算法，為降低算法的時間復(fù)雜度，在路徑計(jì)算方法上采用了H_MCOP算法的方法，但是在節(jié)點(diǎn)松弛過程中提出了多選擇計(jì)算長度的方法，有效地提高了算法的精確性。

為提高算法的執(zhí)行效率，在節(jié)點(diǎn)的松弛過程中又引入了受控路徑的思想，使算法的運(yùn)行效率更高。

1算法理論基礎(chǔ)

11多約束路徑（multi-constrained path，MCP）

定義1如果用圖G(V，E)來表示一個網(wǎng)絡(luò)拓?fù)洹Ｆ渲校篤是網(wǎng)絡(luò)節(jié)點(diǎn)的集合；E是連接邊的集合。每一個連接(i， j)∈E都具有K個加性權(quán)重wk（k=1，2，…，K），且wk≥0。給定K個約束ck（k=1，2，…，K），多約束路徑（MCP）問題就是從源節(jié)點(diǎn)s到目的節(jié)點(diǎn)t找一條路徑p，使p滿足以下條件：

wk(p)=(i， j)∈pwk(i， j)≤ck；k=1，2，…，K（1）

在源與目的節(jié)點(diǎn)之間可能存在滿足多約束條件的多條路徑，該路徑都是MCP的解。也就是說對于一個給定的MCP問題，可能存在多個滿足條件的解。然而對于這個解集，關(guān)鍵是要找到一條最優(yōu)的路徑，這就歸結(jié)為一個多約束優(yōu)化路徑問題。

定義2如果用圖G(V，E)來表示一個網(wǎng)絡(luò)拓?fù)洹Ｆ渲校篤是網(wǎng)絡(luò)節(jié)點(diǎn)的集合；E是連接邊的集合。每一個連接(i， j)∈E都具有K個加性權(quán)重wk（k=1，2，…，K），且wk≥0。定義一個路徑長度標(biāo)準(zhǔn)l(p)，多約束優(yōu)化路徑（multi-constrained optimal path，MCOP）問題就是從源節(jié)點(diǎn)s到目的節(jié)點(diǎn)t找一條路徑p，使p在滿足式（1）的條件下，最小化路徑長度標(biāo)準(zhǔn)，使l(p)≤l(p′)。其中p′為所有滿足式（1）的路徑集合。MCP和MCOP都是QoS路由中要解決的問題。

12多約束路徑的長度

如定義2所描述，為了在MCP解集中得到一條最優(yōu)路徑，需要定義一個路徑長度標(biāo)準(zhǔn)來對這些路徑進(jìn)行評估。對于這樣的路徑長度，目前提出的有兩類：線性路徑長度和非線性路徑長度。

Jaffe^[12]提出了一種線性路徑長度，其定義如下：

l(p)=Ki=1diwi(p)=d×w(p)，di＞0（2）

由于該長度定義的是一個線性長度，可以基于這個長度標(biāo)準(zhǔn)使用Dijkstra算法求得最短路徑。采用這種線性長度進(jìn)行搜索，當(dāng)di=1/ci時達(dá)到最優(yōu)^[6]。但是所獲得最短路徑不一定能滿足所有的約束條件。為了使這種長度最短的路徑更好地滿足約束條件，引入了非線性路徑長度^[6]：

lq(p)=Ki=1（wi(p)/ci）q1/q（3）

特別地，當(dāng)q→∞時：

l∞(p)=max1≤i≤K[(wi(p)/ci]（4）

這種非線性路徑長度的應(yīng)用，縮小了解空間的搜索范圍。根據(jù)文獻(xiàn)[6]的論述，使用式（4），位于約束區(qū)域內(nèi)的路徑長度一定小于位于約束區(qū)域外的約束長度。因此，如果求得的最短路徑長度位于約束區(qū)域外，一定不會存在滿足所有約束的路徑。這也就把尋找滿足多約束的路徑問題轉(zhuǎn)換為尋找滿足式（4）的最短路徑問題。但對于這種非線性路徑長度，卻無法用Dijkstra算法來求解，因?yàn)檫@種非線性路徑長度不具有可加性，必須采用其他的啟發(fā)式算法。

13受控路徑

定義3對于兩條路徑p和p′，如果對于所有的1≤i≤K，都有wi(p)＜wi(p′)，則稱路徑p′受控于路徑p。如果在搜索過程中發(fā)現(xiàn)一條路徑p′受控于另一條路徑p，那么就可以舍棄p′，尤其在使用k-shortest算法時。這樣就可以有效地減少節(jié)點(diǎn)內(nèi)儲存的路徑個數(shù)，提高算法的執(zhí)行效率。

2新算法設(shè)計(jì)

21新算法思想

在上述多種算法中，H_MCOP是綜合性能最好的一個算法。該算法實(shí)現(xiàn)簡單，在不采用堆排序的情況下時間復(fù)雜度為Dijkstra算法的K倍，并且在節(jié)點(diǎn)數(shù)較多（n≥200）時，可以達(dá)到95%的路由成功率。因此，本文的研究就建立在該算法的基礎(chǔ)上，尋求性能更好的啟發(fā)式算法。

首先通過一個例子來看該算法存在的問題，如圖1所示。

計(jì)算從源節(jié)點(diǎn)0到目的節(jié)點(diǎn)6的一條路徑，要求滿足兩個約束都是10，則很容易得出采用文獻(xiàn)[8]中算法得到的路徑為0→3→6，非線性路徑長度0.7。但是可以看到路徑0→2→3→4→6也能滿足約束，且其非線性路徑長度為0.6，是一條更優(yōu)的路徑。研究發(fā)現(xiàn)，產(chǎn)生上述缺陷的一個重要原因是節(jié)點(diǎn)3進(jìn)行路徑長度計(jì)算時始終采用的是一個由節(jié)點(diǎn)6產(chǎn)生的逆向權(quán)和41，但是節(jié)點(diǎn)3還有兩個后繼節(jié)點(diǎn)。在逆向過程中盡管它們到節(jié)點(diǎn)3的路徑不是線性最短路徑，但在正向非線性過程中，節(jié)點(diǎn)3到它們的路徑是最短路徑的一部分卻是有可能的。為此，在正向計(jì)算中，應(yīng)該把這兩個節(jié)點(diǎn)對節(jié)點(diǎn)3產(chǎn)生的逆向權(quán)和也考慮在內(nèi)。這樣，當(dāng)節(jié)點(diǎn)3的前驅(qū)節(jié)點(diǎn)松弛到節(jié)點(diǎn)3時，就不僅要計(jì)算逆向最短路徑提供的逆向權(quán)和，還要計(jì)算非最短路徑提供的逆向權(quán)和，并在所有計(jì)算產(chǎn)生的路徑長度中選擇最小的長度。如此考慮，就會給被松弛的節(jié)點(diǎn)在松弛方向上作更多的考慮和選擇。

盡管如此，并不是一個節(jié)點(diǎn)所有的后繼節(jié)點(diǎn)產(chǎn)生的逆向權(quán)和都要記錄在該節(jié)點(diǎn)內(nèi)。為了提高算法的效率，在算法設(shè)計(jì)上引入了逆向受控路徑思想，也就是那些逆向受控的路徑產(chǎn)生的逆向權(quán)和不會參與到非線性路徑的計(jì)算中。在圖1中可以看到，節(jié)點(diǎn)6在節(jié)點(diǎn)3產(chǎn)生的逆向權(quán)和是41，已經(jīng)加入到松弛計(jì)算中。節(jié)點(diǎn)4在節(jié)點(diǎn)3處產(chǎn)生的逆向權(quán)和是12+12=24。由于該數(shù)據(jù)和前一個路徑產(chǎn)生的數(shù)據(jù)比較起來不滿足受控路徑的條件，也把該數(shù)據(jù)加入到路徑計(jì)算中。同理可知，節(jié)點(diǎn)5在節(jié)點(diǎn)3處產(chǎn)生的逆向權(quán)和是22+21=43。可以看到，該路徑是受控于節(jié)點(diǎn)6到節(jié)點(diǎn)3這條路徑的，就不會參與松弛計(jì)算。通過這種方法，可以有效減少參與計(jì)算的路徑數(shù)目，從而提高算法的效率。

在其他啟發(fā)式算法和Dijkstra算法中，每個節(jié)點(diǎn)都只是松弛一次。但在本文的算法中，由于節(jié)點(diǎn)松弛過程中有多個逆向權(quán)和參與了計(jì)算，松弛過的節(jié)點(diǎn)保存的路徑長度不一定是最短路徑長度。為此，算法中允許節(jié)點(diǎn)重復(fù)松弛，只要通過節(jié)點(diǎn)的最短路徑比原來減少，該節(jié)點(diǎn)就要重新參與松弛，如節(jié)點(diǎn)3、4都會被松弛兩次。

最后，在正向計(jì)算過程中也引入了受控路徑的思想。當(dāng)一個節(jié)點(diǎn)松弛到它的后繼節(jié)點(diǎn)時，如果該節(jié)點(diǎn)到其后繼節(jié)點(diǎn)的實(shí)際路徑受控于其他節(jié)點(diǎn)到其后繼節(jié)點(diǎn)的實(shí)際路徑，則到該后繼節(jié)點(diǎn)的松弛過程就不再進(jìn)行，這樣也可以有效地提高程序的運(yùn)行效率。

22新算法（N_MCOP）描述

在第1行對表1中所列出的參數(shù)進(jìn)行了初始化，并完成逆向標(biāo)號過程^[8]。在第2行中通過判斷S2是否為空來決定算法是否退出。第3行與Dijkstra算法一樣，選擇在S2中且到源節(jié)點(diǎn)路徑最短的節(jié)點(diǎn)進(jìn)行松弛，選擇完畢后松弛該節(jié)點(diǎn)（第6行）。

節(jié)點(diǎn)的松弛過程如下：

其中：第1~5行判斷是否要把松弛到的節(jié)點(diǎn)產(chǎn)生的逆向權(quán)和插入到隊(duì)列中；第7行的計(jì)算根據(jù)式(4)來進(jìn)行，此處路徑長度l∞(p)=max1≤k≤K{[Gk(u)+Rk(u)]/ck}，并且多個Rk參與了計(jì)算；第9~12行更新松弛到的節(jié)點(diǎn)路徑長度和參數(shù)。

向節(jié)點(diǎn)內(nèi)插入Rk的過程如下：

其中：在第1行中首先判斷該路徑是否逆向受控，如果是則不再插入；然后第4行判斷其是否控制節(jié)點(diǎn)內(nèi)已存儲路徑，如果是則從節(jié)點(diǎn)內(nèi)刪除這些路徑的Rk；最后，第7、8行向節(jié)點(diǎn)內(nèi)插入該Rk。

3算法仿真

通過仿真對新算法N_MCOP和H_MCOP算法進(jìn)行比較，對算法的性能進(jìn)行評估。

31仿真模型

目前相關(guān)仿真中對于網(wǎng)絡(luò)拓?fù)涞慕＿€沒有統(tǒng)一的標(biāo)準(zhǔn)，文獻(xiàn)[13]中給出了一些常用的模型。在本算法的仿真中，采用了隨機(jī)圖的拓?fù)浣Y(jié)構(gòu)。該圖的生成是基于Waxman提出的一個網(wǎng)絡(luò)模型^[14]。在該模型中，通過均勻分布，在一個矩形區(qū)域內(nèi)隨機(jī)地產(chǎn)生需要的節(jié)點(diǎn)數(shù)，節(jié)點(diǎn)之間存在連接的概率用式（5）來表示：

P(u，v)=β exp[-d(u，v)/（Lα）]（5）

其中：d(u，v)為節(jié)點(diǎn)u與節(jié)點(diǎn)v之間的距離；L為所有節(jié)點(diǎn)間的最大長度；α、β是(0，1]的數(shù)。

隨機(jī)圖權(quán)重的產(chǎn)生方法參考了文獻(xiàn)[8]，對于每個有連接的邊使用了兩個不相關(guān)的權(quán)重：w1(u，v)~uniform(1，100)和w2(u，v)~uniform(1，200）。根據(jù)邊的權(quán)重，產(chǎn)生如下兩個隨機(jī)的路徑約束：c1~uniform(0.8×w1(p2)，12×w1(p2))和c2~uniform(0.8×w2(p1)，12×w2(p1))。其中：p1、p2是分別以w1和w2作為權(quán)重采用Dijkstra算法求得的最短路徑；w1(p2)指的是在p2這條路徑上權(quán)重w1的和；w2(p1)指的是在p1這條路徑上權(quán)重w2的和。

32仿真方法

在本仿真中，主要考察兩個性能指標(biāo)：a）路由成功次數(shù)。在給定的請求次數(shù)中，算法能夠成功找到滿足約束路徑的次數(shù)。b）路徑長度。在滿足約束的情況下，算法尋路成功獲得的非線性路徑長度。

在仿真中通過式（5）產(chǎn)生10個網(wǎng)絡(luò)圖，對每一個圖按照以上的方法產(chǎn)生兩個約束，并產(chǎn)生1 000個隨機(jī)源與目的間的請求。圖2是在不同的節(jié)點(diǎn)下兩種算法成功次數(shù)的一個比較。由曲線可以看出，新算法的成功率得到提高。圖3統(tǒng)計(jì)了N_MCOP和H_MCOP算法在滿足約束的條件下獲得的平均路徑長度。從圖中可以看到，新算法的最短路徑長度要小于H_MCOP算法。圖4和5是分別在有150個節(jié)點(diǎn)和300個節(jié)點(diǎn)條件的拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)中，在多于兩個約束條件下對兩個算法成功率的比較。從兩幅圖可以看出，與圖2中兩個約束的比較相似，在更多約束條件下，隨著節(jié)點(diǎn)數(shù)的增加，成功率提高。此外，隨著約束條件的增加，算法的成功率下降。

4算法性能分析

假設(shè)拓?fù)鋱D中有n個節(jié)點(diǎn)，則非k-shortest的H_MCOP算法在不使用堆排序的情況下時間復(fù)雜度為O(Kn2)。由于新算法允許節(jié)點(diǎn)作重復(fù)松弛，無法準(zhǔn)確得知算法的執(zhí)行次數(shù)，在對新算法的性能評估方面，主要通過對仿真數(shù)據(jù)進(jìn)行定量分析來獲得性能評估。

表2的數(shù)據(jù)是通過對10個拓?fù)鋱D、每個圖產(chǎn)生1 000次請求、利用新算法計(jì)算產(chǎn)生的結(jié)果。從表的每節(jié)點(diǎn)平均參與松弛的次數(shù)可以看到，在節(jié)點(diǎn)數(shù)目增加了30倍的情況下，每個節(jié)點(diǎn)參與松弛的次數(shù)變化緩慢，基本接近1。這說明盡管增加了節(jié)點(diǎn)的重復(fù)松弛，但算法的平均時間復(fù)雜度與原算法基本相同。同時，節(jié)點(diǎn)參與松弛的最大次數(shù)在節(jié)點(diǎn)數(shù)達(dá)到200后基本趨于穩(wěn)定，穩(wěn)定在5次左右。從該表可以看到，每個節(jié)點(diǎn)的平均度數(shù)增加很快，但是每個節(jié)點(diǎn)存放Rk的隊(duì)列長度卻遠(yuǎn)遠(yuǎn)小于節(jié)點(diǎn)的度數(shù)，且增長緩慢，這說明受控路徑算法發(fā)揮了很好的作用。此外，在節(jié)點(diǎn)數(shù)增加到200以后，盡管度數(shù)增長很快，但是最大隊(duì)列長度卻基本穩(wěn)定。如果把節(jié)點(diǎn)數(shù)量（NodeNum）和平均隊(duì)列長度(q_len)采用最小二乘法擬合成一條直線，則直線方程為q_len=0.002NodeNum+1312 2，得到平均需要增加的存儲空間為(0.002NodeNum+1312 2)NodeNum個隊(duì)列元素單位，如果考慮最壞情況，則需要(10~11)NodeNum個隊(duì)列元素單位，是算法性能改進(jìn)后所額外付出的代價。

表2新算法在不同節(jié)點(diǎn)數(shù)圖中的運(yùn)行參數(shù)

節(jié)點(diǎn)數(shù)量每節(jié)點(diǎn)的平均度數(shù)每節(jié)點(diǎn)平均參與松弛的次數(shù)

節(jié)點(diǎn)參與松弛最大次數(shù)節(jié)點(diǎn)存放Rk的平均隊(duì)列長度節(jié)點(diǎn)存放Rk的最大隊(duì)列長度

5結(jié)束語

通過前面的論述可看到，本文提出的N_MCOP算法在節(jié)點(diǎn)松弛計(jì)算上作了有效的設(shè)計(jì)，使算法平均時間復(fù)雜度在沒有顯著增加的情況下，算法的性能得到提高。本文在算法中采用了受控路徑的思想，使得新算法性能明顯優(yōu)化。盡管如此，對新算法的研究還有許多工作要做，如研究算法在最復(fù)雜的二維柵格拓?fù)浣Y(jié)構(gòu)下的性能表現(xiàn)，以及算法性能的進(jìn)一步改進(jìn)方案。

參考文獻(xiàn)：

［1］

MASIP-BRUIN X，YANNUZZI M，DOMINGO-PASCUAL J，et al.Research challenges in QoS routing[J].Computer Communications，2006，29(5):563-581.

[2]FU Y，CHENG X，TANG Y.Optimization theory and method[M].Chengdu:Press of UESTC，1996.

[3]WANG Zheng，CROWCROFT J.Quality-of-service routing for suppor-ting multimedia applications[J].IEEE Journal Select Areas Commun，1996，14(7):1228-1234.

[4]IWATA A，IZMAILOV R，LEE D S，et al.ATM routing algorithms with multiple QoS requirements for multimedia internetworking[J].IEICE Trans and Communications，1996，E79-B(8):999-1006.

[5]MIEGHEM P van，KUIPERS F A.Concepts of exact QoS routing algorithms[J].IEEE/ACM Trans on Networking，2004，12(5):851-864.

[6]DeNEVE H，MIEGHEM P van.TAMCRA:a tunable accuracy multiple constraints routing algorithm[J].Computer Communications，2000，23(7):667-679.

[7]KORKMAZ T，KRUNZ M.A randomized algorithm for finding a path subject to multiple QoS requirements[J].Computer Networks，2001，36(2-3): 251-268.

[8]KORKMAZ T，KRUNZ M.Multi-constrained optimal path selection[C]//Proc of IEEE INFOCOM 2001.Anchorage，AK:[s.n.]，2001:834-843.

[9]YUAN Xin，LIU Xing-ming.Heuristic algorithms for multi-constrained quality of service routing[C]//Proc of the 20th Annual Joint Conference on IEEE INFOCOM 2001.Anchorage，AK:[s.n.]，2001:844-853.

[10]YUAN Xin.Heuristic algorithms for multiconstrained quality-of-ser-vice routing[J].IEEE/ACM Trans on Networking，2002，10(2):244-256.

[11]LIU Gang，RAMAKRISHNAN K G.A* prune:an algorithm for fin-dingk-shortest paths subject to multiple constraints[C]//Proc of the 20th Annual Joint Conference on IEEE INFOCOM 2001.Anchorage，AK:[s.n.]，2001:743-749.

[12]JAFFE J M.Algorithms for finding paths with multiple constraints[J].Networks，1984，14(5):95-116.

[13]ZEGURA E W，CALVERT K L，BHATLACHARJEE S.How to model an internetwork[C]//Proc ofIEEE INFOCOM’96.Los Alamitos:[s.n.]，1996:594-602.

[14]WAXMAN B M.Routing of multipoint connections[J].IEEE Journal on Selected Areas in Communications，1988，6(9):1617-1622.