楊華衛(wèi) 王洪波 程時(shí)端 陳山枝 林 宇

①(北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 100876)②(電信科學(xué)技術(shù)研究院無(wú)線(xiàn)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 100083)

1 引言

隨著IP網(wǎng)絡(luò)規(guī)模的快速增長(zhǎng)和流量請(qǐng)求的迅速增加，網(wǎng)絡(luò)流量的不均衡分布日趨明顯：局部網(wǎng)絡(luò)鏈路出現(xiàn)擁塞的同時(shí)，網(wǎng)絡(luò)其余鏈路輕載或空閑的情形卻普遍存在。在網(wǎng)絡(luò)硬件快速發(fā)展的情形下，高速的交換和路由單元以及大容量的網(wǎng)絡(luò)鏈路使得運(yùn)營(yíng)商可為網(wǎng)絡(luò)大量增加硬件資源。但這種帶寬過(guò)量供給的方式是以網(wǎng)絡(luò)資源低利用率為代價(jià)的，并不能有效地解決熱點(diǎn)鏈路的擁塞問(wèn)題。流量工程通過(guò)控制路由實(shí)現(xiàn)流量的優(yōu)化分布[1]，在提高網(wǎng)絡(luò)資源利用率的同時(shí)減少網(wǎng)絡(luò)擁塞。根據(jù)網(wǎng)絡(luò)拓?fù)浜土髁烤仃嘯2]建模后，得到優(yōu)化的路由，直觀而言，就是把流量分布到帶寬允許的路徑上，并達(dá)到流量的均衡。

文獻(xiàn)[1]從不同角度對(duì)流量工程中的路由算法進(jìn)行了劃分，從中可見(jiàn)，現(xiàn)有的流量均衡模型按路由優(yōu)化目標(biāo)可分為兩類(lèi)：最大鏈路利用率最小化模型以及最小化鏈路代價(jià)和模型，下面就兩類(lèi)模型分別描述。

文獻(xiàn)[3]為流量工程中的流量均衡首次提出疊加式(overlay approach)的顯式路由算法，與基于目的地址的路由相比可更有效地提高網(wǎng)絡(luò)利用率，文中最基本的問(wèn)題是在滿(mǎn)足流量請(qǐng)求的情形下優(yōu)化網(wǎng)絡(luò)性能，模型的目標(biāo)即是最小化擁塞和最大化流量承載潛力。文獻(xiàn)[4]提出通過(guò)集成式(integratedapproach)的網(wǎng)絡(luò)路由方式優(yōu)化流量分布，同時(shí)指出了通過(guò)合理設(shè)置鏈路權(quán)值，顯式路由在理論上轉(zhuǎn)化為最短路徑的可能性。文獻(xiàn)[5]給出了約束路由的流量均衡算法，這是MPLS路由在大規(guī)模網(wǎng)絡(luò)中建立路徑的數(shù)目受限情形下提出的。上述的模型或算法為避免擁塞采用優(yōu)化最大鏈路利用率的方式來(lái)達(dá)到流量的均衡分布。最小化最大鏈路利用率是流量工程中均衡流量分布的直觀算法，其優(yōu)點(diǎn)是建模過(guò)程中優(yōu)化目標(biāo)簡(jiǎn)單、易于獲得最優(yōu)解，其缺點(diǎn)是未從整體網(wǎng)絡(luò)的角度考慮流量均衡。

文獻(xiàn)[6]為一般路由優(yōu)化建立了基本數(shù)學(xué)模型，流量可在網(wǎng)絡(luò)OD(Origin-Destination)對(duì)的所有路徑間任意分布；其中引入了流量通過(guò)鏈路的路由代價(jià)函數(shù)，以懲罰高負(fù)載鏈路傳送流量的路由方式。文獻(xiàn)[7]正式提出基于IP路由協(xié)議的流量工程，并探討了OSPF(Open Shortest Path First)和IS-IS(Intermediate System to Intermediate System)的應(yīng)用。文獻(xiàn)[8]總結(jié)了調(diào)整路由協(xié)議參數(shù)的優(yōu)化模型和算法，使得不關(guān)注網(wǎng)絡(luò)流量的傳統(tǒng)路由協(xié)議可以通過(guò)優(yōu)化參數(shù)而均衡分布流量。上述模型和算法把網(wǎng)絡(luò)看作所有鏈路的綜合，在考慮流量均衡分布時(shí)，優(yōu)化的結(jié)果是選擇使得所有鏈路路由流量代價(jià)和最小的流量分布。這類(lèi)模型盡管避免了最小化最大鏈路利用率模型的缺陷，但他們考慮的是鏈路路由流量的代價(jià)，而非路徑路由流量的代價(jià)。

本文認(rèn)為，網(wǎng)絡(luò)中流量分布的均衡性決定于路由時(shí)各路徑間流量的分配，而路徑上分配的流量又決定于該路徑路由流量的代價(jià)。為此，本文提出了最小化路徑代價(jià)和模型，它的優(yōu)化目標(biāo)是流量請(qǐng)求在所有可用路徑上路由流量的路徑代價(jià)和最小化，并且定義路由流量的路徑代價(jià)為路徑上瓶頸鏈路路由流量的代價(jià)。隨后，本文提出利用負(fù)價(jià)環(huán)算法求得流量的最優(yōu)網(wǎng)絡(luò)分布，并通過(guò)實(shí)驗(yàn)證了該模型可顯著降低網(wǎng)絡(luò)最大負(fù)載鏈路的利用率。

本文的內(nèi)容安排如下，第2節(jié)描述本文提出的流量均衡模型，實(shí)驗(yàn)和相關(guān)的驗(yàn)證在第3節(jié)討論，最后總結(jié)全文并提出待研究問(wèn)題。

2 最小路徑代價(jià)和模型

本節(jié)假定流量矩陣已知，建立網(wǎng)絡(luò)中所有路徑間均衡分布流量的優(yōu)化模型，并在負(fù)價(jià)環(huán)算法基礎(chǔ)上實(shí)現(xiàn)優(yōu)化流量分布的路徑路由算法。

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

IP網(wǎng)絡(luò)以有向圖G(N,A)表示，N是路由器的集合，A是路由器間有向鏈路的集合。有向鏈路的容量c(a)定義為鏈路可承受流量的最大帶寬。流量矩陣D給出每個(gè)OD對(duì)(s,t)間要求傳送的流量請(qǐng)求。那么路由問(wèn)題即可定義為非零D(s,t)在s到t的路徑間的流量分布。

流量路由結(jié)果用一個(gè)矩陣R表示，其中鏈路a上負(fù)載D(s,t)的流量比例表示為R(s,t,a)。那么鏈路a上的負(fù)載即可表示為其帶寬利用率為l(a)/c(a)。

2.2 既有流量均衡模型

最小化最大鏈路利用率優(yōu)化模型，其優(yōu)化目標(biāo)是最小化maxa∈A(l(a)/c(a))，即對(duì)網(wǎng)絡(luò)中最大利用率的鏈路進(jìn)行優(yōu)化。這個(gè)優(yōu)化目標(biāo)的優(yōu)點(diǎn)是直觀、比較容易實(shí)現(xiàn)，其缺點(diǎn)是只對(duì)最高利用率鏈路優(yōu)化，在該鏈路無(wú)法進(jìn)一步優(yōu)化(如最高利用率鏈路為流量必經(jīng)的瓶頸鏈路)時(shí)，不關(guān)心其余鏈路的流量?jī)?yōu)化。

文獻(xiàn)[3,8]克服了最小化最大鏈路利用率模型的缺陷，提出流量路由的最小化鏈路代價(jià)和模型，其優(yōu)化目標(biāo)是最小化其中的代價(jià)函數(shù)φ()是鏈路利用率的函數(shù)，為懲罰路由方案中的高負(fù)載鏈路情形，函數(shù)定義為分段線(xiàn)性遞增凸函數(shù)。文獻(xiàn)[6]從分組級(jí)別解釋了模型中流量路由的方式，當(dāng)分組經(jīng)過(guò)從s到t的一條路徑時(shí)，要為路徑中的每個(gè)鏈路付出路由代價(jià)，那么，Φ即是所有分組路由時(shí)的路徑代價(jià)之和。為引述方便，下文中稱(chēng)該模型的流量路由算法為最小代價(jià)路徑(Minimal Cost Path, MCP)路由優(yōu)化算法，其中的路徑代價(jià)是路徑上所有鏈路代價(jià)之和。

最小化鏈路代價(jià)和模型以路徑上鏈路代價(jià)之和作為流量路由時(shí)的路徑代價(jià)，在這樣的路徑代價(jià)定義下，可能導(dǎo)致下述的流量分布不均衡現(xiàn)象。路徑p1包含擁塞鏈路，p2為無(wú)擁塞鏈路，在前者的路徑代價(jià)較小時(shí)，分組將優(yōu)先選擇路徑p1；而這樣的選擇更加重了路徑p1上擁塞鏈路的負(fù)擔(dān)。在鏈路利用率比較均勻時(shí)，路徑上鏈路的數(shù)目成為路徑代價(jià)的主要影響因素；顯然，跳數(shù)少的路徑更具吸引力，使得短路徑趨向滿(mǎn)載的幾率比長(zhǎng)路徑更大。

下面示例MCP算法在分布流量時(shí)引起流量不均衡分布的情形。圖1是一個(gè)簡(jiǎn)單的網(wǎng)絡(luò)拓?fù)?，在結(jié)點(diǎn)(s,t)間有兩條路徑p1(s, l, n, t)和p2(s, l, m, n, t)。假設(shè)鏈路容量c(a)=200,?a∈G，在流量請(qǐng)求D(s,t)從0遞增到200的過(guò)程中，按照最小化鏈路代價(jià)和模型中的φ()函數(shù)對(duì)流量請(qǐng)求在路徑p1和p2間分配，兩條路徑上的流量負(fù)載之比l(p2)/l(p1)隨流量增加的變化趨勢(shì)如圖2所示。

由圖可見(jiàn)，在流量加載的前半段，兩條路徑的負(fù)載差別較大，p2的負(fù)載接近于p1負(fù)載的1/2；在流量遞增的后續(xù)過(guò)程中，流量在兩條路徑間的分布無(wú)確定趨勢(shì)。在既定路徑代價(jià)定義下，MCP算法在路徑間分布流量時(shí)均衡性明顯不足，而這對(duì)避免網(wǎng)絡(luò)擁塞和提高網(wǎng)絡(luò)容納未知流量的能力是極其不利的。

圖1 兩條路徑的簡(jiǎn)單拓?fù)?/p>

圖2 路徑負(fù)載對(duì)比曲線(xiàn)

2.3 最小路徑代價(jià)和模型

由于最小化鏈路代價(jià)和模型和MCP路由優(yōu)化算法存在缺陷，要實(shí)現(xiàn)流量的均衡分布、最小化網(wǎng)絡(luò)擁塞，必須構(gòu)造新的優(yōu)化模型，實(shí)現(xiàn)相應(yīng)的優(yōu)化算法。本文的觀點(diǎn)是流量在各路經(jīng)間的均衡分布決定了網(wǎng)絡(luò)流量分布的均衡性，亦即網(wǎng)絡(luò)的擁塞特性；流量在路徑間的均衡分布是與路徑的擁塞特征相關(guān)的，而路徑的擁塞特征取決于路徑上瓶頸鏈路的擁塞特征。

下面再次以圖的拓?fù)錇槔f(shuō)明，其中各鏈路容量c(a)=200,?a∈G，并有背景流量l(m, n)=40，其余鏈路均無(wú)背景流量，并假定(s,t)間的流量請(qǐng)求D(s,t)=100。

根據(jù)MCP算法，鏈路(lm)(mn)(ln)剩余容量滿(mǎn)足要求時(shí)，流量分布如圖3所示，(lm)和(mn)的鏈路代價(jià)和與(ln)的鏈路代價(jià)相等(值是90.8)。在圖3中，由于(mn)上背景流量的存在，使得(mn)成為路徑(lmn)的瓶頸鏈路。根據(jù)本文觀點(diǎn)，(mn)的擁塞特征決定了路徑(lmn)的擁塞特征，即在路徑(lmn)和(ln)間分布流量時(shí)應(yīng)按照他們的瓶頸鏈路(mn)和(ln)(單鏈路構(gòu)成的路徑)的擁塞特征分布流量，這時(shí)，合理的新的流量分布如圖4所示。

比較圖3和圖4的流量分布，網(wǎng)絡(luò)的流量分布均衡性比較如表1所示，其中鏈路負(fù)載最大差是拓?fù)渲凶畲箧溌坟?fù)載與最小鏈路負(fù)載之差，可見(jiàn)新的均衡分布的優(yōu)越性。

圖3 MCP算法流量分布

圖4 新的均衡流量分布

表1 流量均衡方式對(duì)比

因此，本文提出最小化路徑代價(jià)和流量均衡模型，定義路由流量的路徑代價(jià)為路徑上瓶頸鏈路路由流量的代價(jià)，其優(yōu)化目標(biāo)是路由所有流量請(qǐng)求的路徑代價(jià)和最小化。

定義 設(shè)p為(s,t)間任一路徑，鏈路ak∈p，并且l(ak)/c(ak)=maxa∈p(l(a)/c(a))，即ak是p上的瓶頸鏈路，那么，p的路徑代價(jià)就定義為φp?φ(l(ak)/c(ak))。

在定義流量經(jīng)過(guò)路徑p路由的路徑代價(jià)φp后，就可以建立網(wǎng)絡(luò)流量均衡的優(yōu)化目標(biāo)了。假設(shè)，P(s,t)為(s,t)間所有路徑的集合，則(s,t)間路徑間分布流量的路徑代價(jià)和就是。那么，網(wǎng)絡(luò)的流量均衡是最小化分布所有流量的路徑代價(jià)和，最小化目標(biāo)如公式(1)所示。

為取得上述目標(biāo)下的最優(yōu)流量分布，本文在負(fù)價(jià)環(huán)算法[9]基礎(chǔ)上提出了基于瓶頸鏈路的最小代價(jià)路徑(Bottleneck-based Minimal Cost Path, BMCP)路由算法。該算法的基本思想是：(s,t)間存在兩條以上路徑時(shí)，總有改變D(s,t)在這些路徑間分配流量的可能性，這種改變使得流量路由的路徑代價(jià)和發(fā)生改變，而代價(jià)和最小的分配方式才是最優(yōu)的流量分布。下文簡(jiǎn)要介紹負(fù)價(jià)環(huán)算法后，描述BMCP算法。

2.4 負(fù)價(jià)環(huán)算法簡(jiǎn)介

因在流量均衡算法中的應(yīng)用，下面簡(jiǎn)要介紹負(fù)價(jià)環(huán)算法。有向圖G(N,A)表示一個(gè)通信網(wǎng)，ai,j是ni到nj的有向邊，邊的容量是ci,j，邊上的實(shí)際負(fù)載是li,j。在單源s單宿t情形下，一個(gè)大小為Fs,t的流量請(qǐng)求在網(wǎng)絡(luò)中分布必須滿(mǎn)足下列條件：

(1)非負(fù)性和有限性：

(2) 連續(xù)性：

共|N|?1個(gè)限制條件，滿(mǎn)足這些條件的流量分布稱(chēng)為一個(gè)可行流。

在保持總量Fs,t不變的情況下，給出一個(gè)初始可行流，按鏈路上的負(fù)載和容量作出G(N,A)的補(bǔ)圖，補(bǔ)圖上若存在一個(gè)有向環(huán)，并且各邊的費(fèi)用之和為負(fù)，則稱(chēng)為一個(gè)負(fù)價(jià)環(huán)。沿負(fù)價(jià)環(huán)方向增流，并不破壞環(huán)上各結(jié)點(diǎn)的流量連續(xù)性，也不破壞各邊的非負(fù)性和有限性，結(jié)果得到一個(gè)總費(fèi)用降低的新可行流。

負(fù)價(jià)環(huán)算法步驟歸納如下：

(1)在圖上找到任一可行流作為初始可行流。

(2)在圖上做補(bǔ)圖。

(3)在補(bǔ)圖上找負(fù)價(jià)環(huán)，若負(fù)價(jià)環(huán)則算法終止，若有則沿負(fù)價(jià)環(huán)方向增流。

(4)修改原圖各邊負(fù)載，返回(1)。

2.5 BMCP流量均衡算法

本節(jié)的流量均衡算法BMCP建立在負(fù)價(jià)環(huán)算法基礎(chǔ)上，由于應(yīng)用環(huán)境的改變做了適應(yīng)性的改變，下面先定義路徑負(fù)價(jià)環(huán)。

定義：同一流量請(qǐng)求在網(wǎng)絡(luò)中形成的路徑集合，按路徑上瓶頸鏈路的負(fù)載和容量求補(bǔ)圖，如果補(bǔ)圖上存在一個(gè)有向環(huán)，并且這個(gè)環(huán)流量的路徑代價(jià)和為負(fù)，則稱(chēng)為一個(gè)路徑負(fù)價(jià)環(huán)。

那么BMCP算法把流量請(qǐng)求分布到網(wǎng)絡(luò)上的算法基本步驟如下：

(1)TM[m][n]內(nèi)保存網(wǎng)絡(luò)流量請(qǐng)求數(shù)據(jù)；

(2)graph保存網(wǎng)絡(luò)拓?fù)洌?/p>

(3)初始化一個(gè)可行流，參數(shù)是graph和TM；

(4)for (i=0, j=0; i＜m, j＜n; i++, j++){

(5) pathset = OD對(duì)(i,j)間的路徑；

(6) graph1=由pathset生成的子圖；

(7) while(true){

(8) pathneckset = OD對(duì)(i,j)間路徑上瓶頸鏈路；

(9) graph2 = 由graph1和pathnecknet生成的補(bǔ)圖；

(10) if !getNCostLoop(graph2)//補(bǔ)圖中已沒(méi)有路徑負(fù)價(jià)環(huán)

(11) break；

(12) delta = 增流量；

(13) 用delta值更新graph1的鏈路負(fù)載；

(14) }

(15) }

3 模型及算法驗(yàn)證

為驗(yàn)證最小化路徑代價(jià)和模型和BMCP路由算法的有效性，本文采用了Abilene2的網(wǎng)絡(luò)拓?fù)洌鐖D5所示(結(jié)點(diǎn)從0到11編號(hào)，其中0和1結(jié)點(diǎn)位置相同)，除了結(jié)點(diǎn)0和1間的雙向鏈路帶寬為2.5 G之外，其余雙向鏈路帶寬均為10 G。并采用Zhang在Abilene2網(wǎng)絡(luò)采集的24周流量數(shù)據(jù)[10]，流量采集的時(shí)間粒度是5 min，即每天產(chǎn)生288個(gè)流量矩陣。

圖5 Abilene2網(wǎng)絡(luò)拓?fù)?/p>

本文進(jìn)行了3次實(shí)驗(yàn)，在實(shí)驗(yàn)中著重考查了BMCP算法和MCP算法在流量均衡分布中調(diào)控能力的對(duì)比(由于最小化最大鏈路利用率優(yōu)化算法較MCP的明顯劣勢(shì)，詳見(jiàn)2.2節(jié)，文中不與該模型作對(duì)比實(shí)驗(yàn))。實(shí)驗(yàn)以流量?jī)?yōu)化后的最大鏈路利用率(Maximum Link Utilization，MLU)作為流量分布均衡性的指標(biāo)，下文描述各實(shí)驗(yàn)的詳細(xì)過(guò)程和結(jié)果分析。

3.1 實(shí)驗(yàn)1

為了觀察BMCP路由優(yōu)化算法在網(wǎng)絡(luò)流量變化過(guò)程中對(duì)流量均衡性的控制能力，本文選擇了24周數(shù)據(jù)中的兩個(gè)48 h數(shù)據(jù)分別進(jìn)行了實(shí)驗(yàn)，數(shù)據(jù)信息如表2所示。

由于最終流量分布的均衡性完全由BMCP算法在流量分布時(shí)選擇的路由決定，實(shí)驗(yàn)中流量分布時(shí)把每個(gè)流量請(qǐng)求分割成若干個(gè)流，流大小符合重尾分布[11]，在加載流時(shí)選擇隨機(jī)序列。在實(shí)驗(yàn)中，流量矩陣間的分布是獨(dú)立的，BMCP算法分布流量時(shí)的基本步驟如下：

表2 實(shí)驗(yàn)數(shù)據(jù)描述

(1)讀取流量矩陣；

(2)為每個(gè)流量請(qǐng)求生成重尾分布特征的網(wǎng)絡(luò)流；

(3)對(duì)所有流量請(qǐng)求的網(wǎng)絡(luò)流隨機(jī)排序；

(4)取出下一個(gè)網(wǎng)絡(luò)流；

(5)以BMCP算法選擇路徑并加載該網(wǎng)絡(luò)流；

(6)更新所選路徑上所有鏈路的網(wǎng)絡(luò)流數(shù)據(jù)；

(7)如果還有待分布的網(wǎng)絡(luò)流，轉(zhuǎn)到(4)。

MCP算法與BMCP算法的實(shí)驗(yàn)步驟相同，只是在選擇路徑時(shí)采用MCP算法(僅步驟(5)不同)，而且采用相同的網(wǎng)絡(luò)流分布和加載序列。

實(shí)驗(yàn)結(jié)果如圖6，圖7所示，橫軸的每個(gè)時(shí)間點(diǎn)對(duì)應(yīng)一個(gè)流量矩陣，縱軸對(duì)應(yīng)這個(gè)流量矩陣分布后網(wǎng)絡(luò)中的最大鏈路利用率，結(jié)果分析見(jiàn)表3。

表3 實(shí)驗(yàn)1MLU相對(duì)差分析

圖6 實(shí)驗(yàn)1(I)最大鏈路利用率

圖7實(shí)驗(yàn)1(II)最大鏈路利用率

表3是MCP算法下MLU最大位置時(shí)，BMCP算法對(duì)同一流量矩陣分布后的結(jié)果比較，從中可見(jiàn)兩次實(shí)驗(yàn)中MLU下降相對(duì)差分別達(dá)到19.2%和17.1%。

3.2 實(shí)驗(yàn)2

該實(shí)驗(yàn)是在給定初始流量矩陣后，考查BMCP算法在關(guān)鍵流量請(qǐng)求增大時(shí)對(duì)網(wǎng)絡(luò)最大鏈路利用率的優(yōu)化作用，其中的關(guān)鍵流量請(qǐng)求是指對(duì)網(wǎng)絡(luò)最大鏈路利用率起關(guān)鍵影響作用的流量矩陣元素。在實(shí)驗(yàn)中，關(guān)鍵流量請(qǐng)求逐步遞增，直到網(wǎng)絡(luò)最大鏈路利用率最終達(dá)到100%，實(shí)驗(yàn)的數(shù)據(jù)信息如表4所示。

表4 實(shí)驗(yàn)數(shù)據(jù)描述

實(shí)驗(yàn)結(jié)果曲線(xiàn)如圖8。為更清晰地分析圖8的數(shù)據(jù)，根據(jù)圖中的縱軸數(shù)值(即流量?jī)?yōu)化后的MLU)計(jì)算差值的百分比，得到圖9的曲線(xiàn)?？梢?jiàn)，在關(guān)鍵流量請(qǐng)求逐漸增加的過(guò)程中，與MCP算法相比，BMCP算法降低最大鏈路利用率的相對(duì)百分比均值達(dá)12.1%。

從圖8和圖9可見(jiàn)，網(wǎng)絡(luò)最大鏈路利用率在49%-81%間時(shí)，MLU相對(duì)差值較大，最大達(dá)到16.9%。即網(wǎng)絡(luò)負(fù)載較重時(shí)，OD間普遍存在可用的輕載路徑，BMCP算法可有效控制網(wǎng)絡(luò)的擁塞；而在最大鏈路利用率繼續(xù)增加時(shí)，OD間的所有路徑趨于滿(mǎn)載，兩種算法都將無(wú)力控制網(wǎng)絡(luò)逐漸擁塞的趨勢(shì)。

圖8 關(guān)鍵流增長(zhǎng)時(shí)MLU優(yōu)化對(duì)比

3.3 實(shí)驗(yàn)3

本實(shí)驗(yàn)考查流量遞增初始階段，BMCP對(duì)網(wǎng)絡(luò)流量均衡的控制能力，是實(shí)驗(yàn)2的補(bǔ)充。類(lèi)似實(shí)驗(yàn)2，通過(guò)非關(guān)鍵流量請(qǐng)求的逐漸遞增，驗(yàn)證BMCP算法調(diào)控網(wǎng)絡(luò)均衡性的能力，并與MCP算法做了比較，其實(shí)驗(yàn)數(shù)據(jù)如表5所示。

表5 實(shí)驗(yàn)數(shù)據(jù)描述

結(jié)果數(shù)據(jù)繪制成曲線(xiàn)，如圖10。從中可見(jiàn)，非關(guān)鍵流量請(qǐng)求在流量初始分布時(shí)，并不影響整個(gè)網(wǎng)絡(luò)的最大鏈路利用率，隨著該流量請(qǐng)求的增加，成為關(guān)鍵的流量請(qǐng)求；同時(shí)，無(wú)論選定流量請(qǐng)求是否是關(guān)鍵流量請(qǐng)求，BMCP算法與MCP算法相比都有顯著優(yōu)勢(shì)。

圖11是對(duì)圖10的縱軸數(shù)據(jù)(即流量?jī)?yōu)化后的MLU)計(jì)算相對(duì)差后繪制的曲線(xiàn)，在流量請(qǐng)求開(kāi)始主導(dǎo)網(wǎng)絡(luò)最大鏈路利用率后，MLU相對(duì)差呈明顯的上升趨勢(shì)，顯示BMCP算法相對(duì)于MCP算法可更好地抑制網(wǎng)絡(luò)擁塞。

圖9 關(guān)鍵流增長(zhǎng)時(shí)MLU相對(duì)變化

圖10 非關(guān)鍵流增長(zhǎng)時(shí)MLU優(yōu)化對(duì)比

圖11 非關(guān)鍵流增長(zhǎng)時(shí)MLU相對(duì)變化

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

盡管運(yùn)營(yíng)商在網(wǎng)絡(luò)工程中有帶寬過(guò)量供給的趨勢(shì)，但這種以資源低效利用換取服務(wù)質(zhì)量的措施并不能從根本上解決網(wǎng)絡(luò)擁塞。網(wǎng)絡(luò)擁塞往往是流量請(qǐng)求匯聚的結(jié)果，而相對(duì)空閑的鏈路并未受到這些流量的青睞，旁路擁塞鏈路上的流量到空閑路徑上同時(shí)保證資源的有效利用是本文的研究主題。

為了最小化網(wǎng)絡(luò)擁塞，本文在指出網(wǎng)絡(luò)擁塞決定于流量路由時(shí)所選路徑的擁塞特征后，建立了流量分布的最小路徑代價(jià)和模型。在流量路由選擇路徑時(shí)，以負(fù)價(jià)環(huán)算法為基礎(chǔ)，提出基于瓶頸鏈路的最小代價(jià)路徑路由算法。實(shí)驗(yàn)驗(yàn)證了該模型和算法的有效性。在實(shí)際的流量工程中，該模型的流量分布結(jié)果可作為評(píng)價(jià)依據(jù)；因流量矩陣的全局特性，該模型在集中式的流量工程中更有優(yōu)勢(shì)。

本文在優(yōu)化流量分布時(shí)，未把服務(wù)質(zhì)量要求作為約束條件，原因是實(shí)踐中的流量質(zhì)量要求因業(yè)務(wù)類(lèi)型而異，而且滿(mǎn)足服務(wù)質(zhì)量的流量分布往往與流量均衡目標(biāo)相悖。隨著覆蓋網(wǎng)絡(luò)發(fā)展，其自私特性的網(wǎng)絡(luò)流量對(duì)流量分布的動(dòng)態(tài)適應(yīng)能力提出了更高要求。我們將在這方面開(kāi)展進(jìn)一步的研究工作。

[1] Wang N, Kin H, and Pavlou G, et al.. An overview of routing optimization for internet traffic engineering[J]. IEEE Communications Surveys & Tutorials, 2008, 10(1): 36-56.

[2] Rincon D, Roughan M, and Willinger W. Towards a meaningful MRA of traffic matrices[C]. Proceedings of the 8th ACM SIGCOMM Conference on Internet measurement,Vouliagmeni, Greece, 2008: 331-336.

[3] Wang Y and Wang Z. Explicit routing algorithms for internet traffic engineering[C]. Computer Communications and Networks, Boston, MA, USA, 1999: 582-588.

[4] Wang Y, Wang Z, and Zhang L. Internet traffic engineering without full mesh overlaying[C]. IEEE Infocom Proceedings, Anchorage, Alaska, USA, 2001, 1: 565-71.

[5] Cugola G and Nitto E. On adopting content-based routing in service-oriented architectures[J]. Information and Software Technology, 2008, 50(1-2): 22-35.

[6] Fortz B and Thorup M. Internet traffic engineering by optimizing ospf weights[C]. IEEE Infocom Proceedings, Tel Aviv, Israel, Aug, 2000, 2: 518-528.

[7] Fortz B, Rexford J, and Thorup M. Traffic engineering with traditional ip routing protocols[J]. IEEE Communications Magazine, 2002, 40(10): 118-124.

[8] Resende M and Pardalos P. Handbook of Optimization in Telecommunications[M]. New York, Springer Science +Business Media, 2006: 679-700.

[9] Ahuja R, Magnanti T, and Orlin J. Network Flows: Theory,Algorithms, and Applications[M]. New Jersey, Prentice Hall,2005: 294-356.

[10] Zhang Y. 6 months of Abilene traffic matrices. Http://www.cs.utexas.edu/～yzhang/, 2009.

[11] Kundu S, Pal S, and Basu K, et al.. An architectural framework for accurate characterization of network traffic[J].IEEE Transactions on Parallel and Distrituted Systems, 2009,20(1): 111-123.