最小化路徑代價和流量均衡模型及算法

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

①(北京郵電大學網絡與交換技術國家重點實驗室 北京 100876)②(電信科學技術研究院無線移動通信國家重點實驗室 北京 100083)

1 引言

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

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

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

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

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

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

2 最小路徑代價和模型

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

2.1 網絡模型

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

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

2.2 既有流量均衡模型

最小化最大鏈路利用率優(yōu)化模型，其優(yōu)化目標是最小化maxa∈A(l(a)/c(a))，即對網絡中最大利用率的鏈路進行優(yōu)化。這個優(yōu)化目標的優(yōu)點是直觀、比較容易實現(xiàn)，其缺點是只對最高利用率鏈路優(yōu)化，在該鏈路無法進一步優(yōu)化(如最高利用率鏈路為流量必經的瓶頸鏈路)時，不關心其余鏈路的流量優(yōu)化。

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

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

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

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

圖1 兩條路徑的簡單拓撲

圖2 路徑負載對比曲線

2.3 最小路徑代價和模型

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

下面再次以圖的拓撲為例說明，其中各鏈路容量c(a)=200,?a∈G，并有背景流量l(m, n)=40，其余鏈路均無背景流量，并假定(s,t)間的流量請求D(s,t)=100。

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

比較圖3和圖4的流量分布，網絡的流量分布均衡性比較如表1所示，其中鏈路負載最大差是拓撲中最大鏈路負載與最小鏈路負載之差，可見新的均衡分布的優(yōu)越性。

圖3 MCP算法流量分布

圖4 新的均衡流量分布

表1 流量均衡方式對比

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

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

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

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

2.4 負價環(huán)算法簡介

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

(1)非負性和有限性：

(2) 連續(xù)性：

共|N|?1個限制條件，滿足這些條件的流量分布稱為一個可行流。

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

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

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

(2)在圖上做補圖。

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

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

2.5 BMCP流量均衡算法

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

定義：同一流量請求在網絡中形成的路徑集合，按路徑上瓶頸鏈路的負載和容量求補圖，如果補圖上存在一個有向環(huán)，并且這個環(huán)流量的路徑代價和為負，則稱為一個路徑負價環(huán)。

那么BMCP算法把流量請求分布到網絡上的算法基本步驟如下：

(1)TM[m][n]內保存網絡流量請求數(shù)據(jù)；

(2)graph保存網絡拓撲；

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

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

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

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

(7) while(true){

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

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

(10) if !getNCostLoop(graph2)//補圖中已沒有路徑負價環(huán)

(11) break；

(12) delta = 增流量；

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

(14) }

(15) }

3 模型及算法驗證

為驗證最小化路徑代價和模型和BMCP路由算法的有效性，本文采用了Abilene2的網絡拓撲，如圖5所示(結點從0到11編號，其中0和1結點位置相同)，除了結點0和1間的雙向鏈路帶寬為2.5 G之外，其余雙向鏈路帶寬均為10 G。并采用Zhang在Abilene2網絡采集的24周流量數(shù)據(jù)[10]，流量采集的時間粒度是5 min，即每天產生288個流量矩陣。

圖5 Abilene2網絡拓撲

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

3.1 實驗1

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

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

表2 實驗數(shù)據(jù)描述

(1)讀取流量矩陣；

(2)為每個流量請求生成重尾分布特征的網絡流；

(3)對所有流量請求的網絡流隨機排序；

(4)取出下一個網絡流；

(5)以BMCP算法選擇路徑并加載該網絡流；

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

(7)如果還有待分布的網絡流，轉到(4)。

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

實驗結果如圖6，圖7所示，橫軸的每個時間點對應一個流量矩陣，縱軸對應這個流量矩陣分布后網絡中的最大鏈路利用率，結果分析見表3。

表3 實驗1MLU相對差分析

圖6 實驗1(I)最大鏈路利用率

圖7實驗1(II)最大鏈路利用率

表3是MCP算法下MLU最大位置時，BMCP算法對同一流量矩陣分布后的結果比較，從中可見兩次實驗中MLU下降相對差分別達到19.2%和17.1%。

3.2 實驗2

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

表4 實驗數(shù)據(jù)描述

實驗結果曲線如圖8。為更清晰地分析圖8的數(shù)據(jù)，根據(jù)圖中的縱軸數(shù)值(即流量優(yōu)化后的MLU)計算差值的百分比，得到圖9的曲線。可見，在關鍵流量請求逐漸增加的過程中，與MCP算法相比，BMCP算法降低最大鏈路利用率的相對百分比均值達12.1%。

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

圖8 關鍵流增長時MLU優(yōu)化對比

3.3 實驗3

本實驗考查流量遞增初始階段，BMCP對網絡流量均衡的控制能力，是實驗2的補充。類似實驗2，通過非關鍵流量請求的逐漸遞增，驗證BMCP算法調控網絡均衡性的能力，并與MCP算法做了比較，其實驗數(shù)據(jù)如表5所示。

表5 實驗數(shù)據(jù)描述

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

圖11是對圖10的縱軸數(shù)據(jù)(即流量優(yōu)化后的MLU)計算相對差后繪制的曲線，在流量請求開始主導網絡最大鏈路利用率后，MLU相對差呈明顯的上升趨勢，顯示BMCP算法相對于MCP算法可更好地抑制網絡擁塞。

圖9 關鍵流增長時MLU相對變化

圖10 非關鍵流增長時MLU優(yōu)化對比

圖11 非關鍵流增長時MLU相對變化

4 結束語

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

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

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

[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.