2001年3月通信學(xué)報Vol.22 No.3第22卷第3期JOURNAL OF CHINA INSTTUTE OF COMMUNICATIONSMarch 2001短文路由優(yōu)化中的費用問題董慶陽況勇李毓麟. (上海交通大學(xué)區(qū)域光纖通信網(wǎng)和新型光通信系統(tǒng)國家重點實驗室上海200030 )摘要本文研究了路由費用"的物理意義"費用”和網(wǎng)絡(luò)參數(shù)之間的關(guān)系以及不同的費用"對通信性能和網(wǎng)絡(luò)運行環(huán)境的影響。提出了-種廣義費用的概念將費用”的意義明確化。通過仿真結(jié)果表明廣義費用優(yōu)化既可改善網(wǎng)絡(luò)的運行環(huán)境,也可提高通信路由的綜合性能。關(guān)鍵詞路由優(yōu)化路由費用鏈路費用不對稱網(wǎng)絡(luò)多播路由中圖分類號:TN919.2文獻(xiàn)標(biāo)識碼A文章編號:1000- 436X( 2001 )03 - 0109- 051Cost" in optimization of routingDONG Qing-yang ,KUANG Yong L Yu-lin( National Laboratory on Local Fiber-Opic Conmunication Networks & AdvancedOptical Communication Systems Shanghai Jjiaotong University Shanghai 200030 ,China )Abstract :In this paper ,the plhysical meaning of' cost" ,the relation betweenh cost" and networks parameters andthe effect of' cost" on communication performance and operating environments of networks are studied. A gener-al cost is put forward ,which specifies the meaning of cost. The results of simulations indicate that the general costoptimization can improve integrate performance of routing and make operating environments of networks better.Key words routing optimization jtouting cost inetworks with asymmetric link cost imulticast routing1引言計算機(jī)通信網(wǎng)絡(luò)中,通信結(jié)點之間路由選擇是-個關(guān)鍵問題。對路由進(jìn)行優(yōu)化的主要目標(biāo)是降低路由費用。例如在點到點通信中需要降低兩點之間通信路徑所占的費用即路徑所占鏈路的費用之和。人們通常以鏈路長度作為鏈路費用網(wǎng)絡(luò)上兩個結(jié)點之間費用最優(yōu)的路徑:即最短的路徑。然而我們通過仿真發(fā)現(xiàn),鏈路長度并不是最好的鏈路費用。本文中我們將對鏈路費用和網(wǎng)絡(luò)物理參數(shù)之間的關(guān)系及其對通信性能和網(wǎng)絡(luò)運行環(huán)境的影響進(jìn)行研究以尋找一個優(yōu)化的鏈路費用。由于點到點通信是點到多點通信的一個特例而且點到多點通信的路由優(yōu)化要比點到點通信的路由優(yōu)化復(fù)雜得多,因此，,我們以點到多點通信(又稱多播)的路由優(yōu)化問題為研究對象。2鏈路費用不對稱網(wǎng)絡(luò)中的路由優(yōu)化問題大部分文獻(xiàn)1 ~ 4 ]在研究路由優(yōu)化時都用無向圖來描沭網(wǎng)絡(luò)這是從數(shù)學(xué)意義上來研究路由優(yōu)化。但在實際的網(wǎng)絡(luò)中,網(wǎng)絡(luò)鏈路的費用中國煤化工馬鏈路上被預(yù)留的帶寬作為鏈路費用全雙工鏈路在上行和下行兩個1YHCNMH G定相同即鏈路費用是不對稱的。鏈路費用不對稱網(wǎng)絡(luò)可以用有向圖來描述給定有向圖G =( V ,E rc),V是結(jié)點收稿日期雨亦數(shù)據(jù)_ 31修訂日期2000- 10-08通信學(xué)報2001年集合,E 是有向連接的集合邊費用函數(shù)c :E→R+( R+表示不包括0的正實數(shù)) 1 V|= n,1 E1= m任何屬于E的連接e =( u ,v )的存在隱含著連接e' =( v , )的存在(按網(wǎng)絡(luò)術(shù)語,即連接是全雙工的)連接e和e'分別對應(yīng)費用函數(shù)( e)(e' ),(e)和( e' )是不相關(guān)的。在有向圖上尋找-組結(jié)點之間費用最低路由(即路由所占的鏈路的費用之和為最小,又稱網(wǎng)絡(luò)費用最優(yōu))歸結(jié)為Steiner樹問題。該問題可以描述為給定非空的結(jié)點集合D和源結(jié)點s ,DCV ,1 D1= prs∈V\ D求以s為根擴(kuò)展到D所有成員的多播路由樹πs ,D),I( s ,D)cE,>e∈π.0( e )最小。Steiner樹是NP完全問題。目前僅有KMB、MPH、ADH等啟發(fā)式算法2]能在多項式時間內(nèi)求解該問題,而且這些算法只適用于無向圖即鏈路費用對稱的網(wǎng)絡(luò)。我們對目前最好的啟發(fā)式算法MPH3]進(jìn)行改進(jìn)使它適用于鏈路費用不對稱的網(wǎng)絡(luò)。改進(jìn)后的MPH算法稱為DMPH算法(directedMPH21)用Dijkstra算法尋找源s到D集合各結(jié)點的費用最低路徑并以費用最低的路徑作為初始Steiner 樹T; ,k: = 1 2)Vw∈V% ,V%是T;樹上的結(jié)點。求w到未加入T的D結(jié)點的費用最低路徑從中選擇費用最低的路徑P; ,Tμ←Tn∪P, k= h+1 3)如果k =p算法停止,得到的T,即準(zhǔn)Steiner樹。否則繼續(xù)步驟2)如果準(zhǔn)Steiner樹上有f個結(jié)點其中包括p個D結(jié)點和f - p個Steiner結(jié)點。DMPH算法.需調(diào)用f次Dijkstra算法故時間復(fù)雜性為0( fin2 )而MPH算法的時間復(fù)雜性是0( pn2 )f≥p可見DMPH算法的時間復(fù)雜性增加。3鏈路費用的比較針對鏈路e ,主要的參數(shù)有鏈路.上被預(yù)留的帶寬B(e )使用費用P(e入時延D(e)等。B( e )是指鏈路e上被預(yù)留的帶寬之和。P( e )是指路由使用鏈路e所支付的費用,它 與鏈路長度、通信質(zhì)量、路由在鏈路上預(yù)留的帶寬等因素有關(guān)。通常,-個通信進(jìn)程在路由經(jīng)過的鏈路上預(yù)留的帶寬是相同的并且支付的使用費用和其它鏈路參數(shù)的關(guān)系不大為簡單起見,可以將鏈路的使用費用歸一化為1[1]即各條鏈路的使用費用相同。D(e)是指信息通過鏈路e的時間延遲,包括排隊時延、交換時延、發(fā)送時延、傳輸時延等主要是傳輸時延,它與鏈路長度有關(guān)。3.1預(yù)留帶寬費用網(wǎng)絡(luò)中業(yè)務(wù)量的分布越均勻越好。業(yè)務(wù)量過于集中容易引起擁塞,導(dǎo)致分組排隊延遲增加、丟失率上升等問題。如果以鏈路上的預(yù)留帶寬B( e )作為鏈路費用，那么路由優(yōu)化算法會盡量選用預(yù)留帶寬較少即比較空閑的鏈路作通信路徑。這樣可以使業(yè)務(wù)流在網(wǎng)絡(luò)中的分布較為平均減少業(yè)務(wù)集中和擁塞的發(fā)生。我們通過下面的仿真來進(jìn)行驗證在結(jié)點數(shù)為20、平均連接度為4的ATM隨機(jī)網(wǎng)絡(luò)上針對某通信組規(guī)模(組成員數(shù)給定組成員隨機(jī)選擇)分別以B( e)D( e)或P( e )為鏈路費用,用DMPH算法尋找組成員之間的網(wǎng)絡(luò)費用最優(yōu)路由樹。觀察此通信組規(guī)模下網(wǎng)絡(luò)最多能接納的多播數(shù)。網(wǎng)絡(luò)接納的多播數(shù)越多,說明業(yè)務(wù)量在中國煤化工選用ATM網(wǎng)絡(luò)是因為ATM網(wǎng)絡(luò)具有接入分HCNMHGoncontrol)隨機(jī)網(wǎng)絡(luò)的構(gòu)造方法是網(wǎng)絡(luò)結(jié)點隨機(jī)分布在一個平面上結(jié)點間按概率P。{u ,)}4]進(jìn)行連接P。{(u,)}= BeadtD)(1)d(u ,心)是結(jié)點u和w之間的距離,L是結(jié)點間可能的最大距離。開始時網(wǎng)絡(luò)是空載的。隨著通信組數(shù)的增多數(shù)鍵路.上被預(yù)留的帶寬也增加。我們采用一種比較簡單的CAC機(jī)制:當(dāng)鏈路上被第3期董慶陽等路由優(yōu)化中的費用問題預(yù)留的帶寬總和大于鏈路容量的85%則認(rèn)為該鏈路已經(jīng)飽和不能再接納新的連接5]。如果連接請求使某條鏈路發(fā)生飽和則認(rèn)為該次連接請求失敗。如果失敗的連接數(shù)占所有連接請求(包括成功的或失敗的連接請求)數(shù)的15%以上則認(rèn)為網(wǎng)絡(luò)已處于飽和狀態(tài),不能再支持新的連接了。此時網(wǎng)絡(luò)上成功建立的連接數(shù)即網(wǎng)絡(luò)最多能接納的多播數(shù)。我們在仿真中使用等效帶寬為0.5Mbit/s的VBR視頻源。鏈路容量是155Mbit/so鏈路時延只考慮傳輸時延。構(gòu)造了30個隨機(jī)網(wǎng)絡(luò)(式1中a=0.3β=0.6),每個隨機(jī)網(wǎng)絡(luò)上進(jìn)行10次仿真。仿真結(jié)果是300次仿真的平均值,它符合置信系數(shù)為0.95置信區(qū)間和平均值之比不超過5%的要求(置信區(qū)間可以用學(xué)生氏t方法來估計)圖1是在鏈路費用分別為B(e)DX(e)或P(e)時網(wǎng)絡(luò)最多能接納的多播數(shù)橫坐標(biāo)為通信組的規(guī)模。從中可以看出當(dāng)鏈路費用是B(e)時,網(wǎng)絡(luò)接納的多播數(shù)最多。其次是鏈路費用P(e)當(dāng)鏈路費用是DX(e)時網(wǎng)絡(luò)能接納的多播數(shù)最少。原因很明顯,連接都在尋找較短的鏈路作路由,這些鏈路上就容易飽和,產(chǎn)生擁塞。既然鏈路費2500用是B( e )時網(wǎng)絡(luò)接納的多播數(shù)最多,那么反言之對于相+預(yù)留帶寬費用同的多播數(shù)如果以B(e)作鏈路費用時,業(yè)務(wù)量分布最為2000 '"使用費用均勻。這對于改善網(wǎng)絡(luò)的運行環(huán)境和提高服務(wù)質(zhì)量是非常1500-◆時延費用有利的。3.2使用 費用1000 F如果以鏈路的使用費用P( e )作為鏈路費用,那么網(wǎng)絡(luò)費用最優(yōu)路由樹的使用費用最低,這對于降低網(wǎng)絡(luò)資源00 t的使用量,減少網(wǎng)絡(luò)用戶支付的使用費用有利。那么以B(e)或D(e)作為鏈路費用時,網(wǎng)絡(luò)費用最優(yōu)路由樹的使2用費用又如何呢我們定義幾個參數(shù):P( b)是以B( e )作組成員數(shù)為鏈路費用時,網(wǎng)絡(luò)費用最優(yōu)路由樹R的使用費用,Pr( p)圖1網(wǎng)絡(luò) 支持的多播數(shù)是以P(e)作為鏈路費用時,網(wǎng)絡(luò)費用最優(yōu)路由樹R的使用費用,PI(d)是以D(e)作為鏈路費用時,網(wǎng)絡(luò)費用最優(yōu)路由樹R的使用。顯然對于相同的路由請求,P(p)最小。我們在-組結(jié)點數(shù)為50、平均連接度為4的隨機(jī)網(wǎng)絡(luò)(式1中a = 0.2 β= 0.3 )仿真平臺上來比較P( 6入PI[ p)和PI[ d )仿真方法是對于相同的路由請求,鏈路費用分別是B(e )P(e)或D(e)時,計算網(wǎng)絡(luò)費用最優(yōu)路由樹,再統(tǒng)計各路由樹的使用費用P(b入PI{p)和P( d)B( e )是在15和125之間任取的隨機(jī)數(shù)表示網(wǎng)絡(luò)鏈路的背景業(yè)務(wù)量。注意，鏈路在上行和下行兩個方向上被預(yù)留的帶寬是不相關(guān)的,仿真中鏈路時延只考慮傳輸時延。P( b)P(p)和P(d)的比較結(jié)果如圖2所示?？梢钥闯?，以B(e)或D(e)作為鏈路費用時,網(wǎng)絡(luò)費用最優(yōu)路由樹的使用費用和最優(yōu)的使用費用相差并不大?？梢哉f路由樹的使用費用對鏈路費用的選取并不敏感。3.3時延 費用中國煤化工如果以鏈路時延D( e )作為鏈路費用那么MHcNMHG樹是沒有意義的。因為人們關(guān)心的是源到每個目的地的時延而不是整個路由樹的時延之和。我們可以通過目的地平均費用來衡量時延費用。所謂的目的地平均費用,即源在路由樹上到各目的地(接收者)的費用的平均值。如果鏈路賽用是D(e),目的地費用最優(yōu)路由樹的目的地平均時延最低。那么如果以通信學(xué)報2001年B(e)或P(e)為鏈路費用時,目的地費用最優(yōu)路由樹的目的地的平均時延又如何呢?為了比較我們定義:D}(b)是以B(e)作為鏈路費用時,目的地費用最優(yōu)路由樹R的目的地平均時延;D,(p)是以P(e)作為鏈路費用時,目的地費用最優(yōu)路由樹R的目的地平均時延;D}(d)是以D(e)作為鏈路費用時,目的地費用最優(yōu)路由樹R的目的地平均時延。顯然對于相同的路由請求,D,[ d )最小。同樣在- -組結(jié)點數(shù)為50、平均連接度為4的隨機(jī)網(wǎng)絡(luò)仿真平臺上來比較D(b)D}( p)和D( d )，仿真方法和3.2節(jié)描述的一樣,B( e )仍然是在15和125之間任取的隨機(jī)數(shù)。仿真結(jié)果如圖3所示?？梢钥闯?D1( b)比D( d )高34%左右。如果B( e )的動態(tài)范圍擴(kuò)大這個值也會增大。DK p)比D)( d )高23%左右。也就是說,目的地費用最優(yōu)樹的平均時延對鏈路費用的選擇還是比較敏感的。.15.4F1. 101.3E+----+ D。(b)/D.(d)+ Pr(b)/Pn(p)+.05+Po(d)/Pe(p)1.2上●Dr(P)D。(d)1.00412202836組成員數(shù)1.1r41220"2836組戚員數(shù)圖2使用費用比較圖3 時延比較4廣義鏈路費用分析鏈路費用對于路由性能的影響可以看出單一的參數(shù)作為鏈路費用總是存在-定缺陷。鏈路上的預(yù)留帶寬作為鏈路費用時,網(wǎng)絡(luò)中的業(yè)務(wù)量分布比較平均,這對改善網(wǎng)絡(luò)的運行環(huán)境費用有利,但時延特性不能得到改善鏈路時延作費用時,可以改善路由的時延特性。但容易造成業(yè)務(wù)量集中;使用費用作為鏈路費用時,業(yè)務(wù)量的分布特性和時延特性介于預(yù)留帶寬費用和時延費用之間。為了進(jìn)-步提高網(wǎng)絡(luò)運行的性能,可以將上述幾種參數(shù)進(jìn)行綜合。綜合后的費用可稱為廣義費用( general cost )簡稱為GC。我們將預(yù)留帶寬和時延進(jìn)行綜合。期望它既能使業(yè)務(wù)量在網(wǎng)絡(luò)中均勻分布,又能改善路由的時延特性。綜合后的費用是Be).. Xe)GC.d e)= λB、+μDm(2)GCu(e)作為鏈路e的廣義費用。λ和μ是兩個系數(shù)入≥0yμ≥0,它們決定時延或預(yù)留帶寬在廣義費用中所占的比重,λ越大表明預(yù)留帶寬的作用越明顯，如此可以類推μ的意義。B是鏈路的最大帶寬;Dw是源到目的地最大的允許中國煤化工來考察廣義費用優(yōu)化對通信性能和網(wǎng)絡(luò)運行環(huán)境的影響。仿真中λ .YHCN MH G數(shù)只具有參考意義,實際應(yīng)用中還可以根據(jù)情況進(jìn)行調(diào)整。例如對時延要求不嚴(yán)格時μ可以取為0。)Bv取155Mbit/s ,Dw取0.04s。鏈路時延D( e )只考慮傳輸時延。假設(shè)是光纖鏈路數(shù)據(jù)在光纖內(nèi)的傳輸速率是真空中光速的2/3.我們把網(wǎng)絡(luò)結(jié)點隨機(jī)分布在3500km x 3000km的平面上,該平面與中國領(lǐng)土的充資陜和大小接近。第3期董慶陽等路由優(yōu)化中的費用問題113 .4.1業(yè)務(wù) 量分布將GCm(e)作為鏈路費用觀察業(yè)務(wù)量在網(wǎng)絡(luò)中的分布情況。觀察的方法仍是看按不同的鏈路費用優(yōu)化網(wǎng)絡(luò)費用時,網(wǎng)絡(luò)最多能接納的多播數(shù)。定義:A( GCp)是鏈路費用為GCl(e)時,網(wǎng)絡(luò)能接納的多播數(shù);A( b )是鏈路費用為B( e )時,網(wǎng)絡(luò)能接納的多播數(shù);同理定義A( d )和A(p)仿真環(huán)境和方法和3.1節(jié)描述的一樣。仿真結(jié)果如圖4所示?？梢钥闯鲦溌焚M用為廣義費用GCu(e)時業(yè)務(wù)量的均勻性比預(yù)留帶寬作鏈路費用時略差-些,但比使用費用和時延作鏈路費用時的業(yè)務(wù)分布都要好。因此,GC.(e)也可以優(yōu)化業(yè)務(wù)量的分布。4.2使用費用我們再來考察GC( e )對使用費用的影響。定義2.0P(GC)是以GCLe)作為鏈路費用時,網(wǎng)絡(luò)費用最優(yōu)-. A(GCu)/A(d)路由樹R的使用費用。把它與P( p )作比較。仿真環(huán)境和1.5E +t一 -+A(GCw)/A(p) .◆A( GCw)/A(b)方法和3.2節(jié)描述的一樣,結(jié)果如圖5所示。可以看出以GC,(e)作為鏈路費用時網(wǎng)絡(luò)費用最優(yōu)路由樹的使用費1.0用PI{ GC)和最優(yōu)的使用費用P[(p) 比較接近。).5CGC( e )可以代替使用費用。21組成員敷4.3時延1.12我們?nèi)岳?圖4網(wǎng)絡(luò)支持多播數(shù)比較+ D,( GCx)De(d)目的地費用最優(yōu)路由樹來考察GCu(e)對時延的影響。1.081.06. Pn(GCu)/Pu(p)定義D,(GC)是以GCL(e)作為鏈路費用時,目的地1.04費用最優(yōu)路由樹R的目的地平均時延。把它與D( d )作1.02比較。仿真環(huán)境和方法與3.2節(jié)描述的一樣結(jié)果如圖51.0036所示?？梢钥闯?以CGC( e )為鏈路費用時,目的地費用最優(yōu)路由樹的目的地平均時延D( GCuat )要比最優(yōu)的目圖5使用 費用和時延費用的比較的地平均時延D)( d )高12%左右。但GC( e )可以改善業(yè)務(wù)流在網(wǎng)絡(luò)中的分布減少業(yè)務(wù)量集中和擁塞發(fā)生的可能性，這也就降低了分組的排隊時延即GC(e)可以從另一個方面降低時延。5結(jié)束語論文研究了鏈路費用和網(wǎng)絡(luò)參數(shù)之間的關(guān)系及其對通信性能和網(wǎng)絡(luò)運行環(huán)境的影響對鏈路的預(yù)留帶寬、使用費用或時延作為鏈路費用時對網(wǎng)絡(luò)運行環(huán)境和路由性能的影響并在此基礎(chǔ)上提出了廣義費用的概念。廣義費用將不同的鏈路參數(shù)綜合使路由費用的意義明確化,提高了通信的綜合性能。我們還為評估費用對通信性能的影響程度提供了-種方法還可以利用這些方法來選擇更適合于應(yīng)用的費用參數(shù)。參考文獻(xiàn):中國煤化工[1] KUMAR K B JAFFE J M. Routing to muliple destinations in cu.MHCNMHGCom31( 3)343 - 351.[2] WINTER P. Steiner problem in networks a survey[ J ]. IEEE Networks ,1987 ,1K2):129- 161.[3] TAKAHASHI H ,MATSUYAMA A. An approximate solution for Steiner problens in graph[ J ]. Math Japonica ,1980 24 :573 - 577.[4 ] WAXMAN B M. Routing of multipoint connection[J ] IEEE JISAC ,1988 A( 9):1617- 1622.[5] SALAMA H F ,REEVES D s. Evaluation of multicast routing algorithm for real time conmunication on high-speed network[ J ]. IEEEJSAC 們分?jǐn)?shù)據(jù)332 - 345.