王浩學，姜明，付吉

（1.解放軍信息工程大學，河南 鄭州 450001；2.杭州電子科技大學 計算機學院，浙江 杭州 310018）

1 引言

面對大量差異化業(yè)務的規(guī)模化應用，現(xiàn)有網絡構建方法因協(xié)議剛性分層、服務能力單一而無法適應，問題日趨凸現(xiàn)。 面向服務提供的一體化承載網絡研究[1,2]擺脫傳統(tǒng)網絡技術體系束縛，以用戶業(yè)務需求為驅動，構建邏輯承載網(LCN, logical carrying network)，提供多樣化的網絡服務。

邏輯承載網構建是通過全網綜合管理系統(tǒng)，將網絡服務需求映射到物理網絡資源的過程，思想與虛擬網構建[3]有相似之處。虛擬網構建分虛節(jié)點映射和虛鏈路映射2個步驟，即將虛節(jié)點映射到具有最大可用資源的基礎節(jié)點上[4,5]，以及將每個虛鏈路映射到 2個物理網節(jié)點間的最短路徑上[5～7]，但算法只考慮此次映射成功率，未考慮網絡整體負載狀態(tài)，影響后續(xù)虛擬網的構建，尤其在物理資源比較分散時，無法充分利用粒度較小的物理資源。本文基于路徑分割將建網需求映射到片資源，計算網絡負載狀態(tài)，以均衡利用物理資源，構建盡可能多的邏輯承載網，取得最大收益。

2 網絡模型及問題描述

物理網絡用無向多重圖GS表示，GS無自環(huán)，頂點集合V( GS)為網絡中的路由交換平臺集合，邊集E( GS)為鏈路集合。邏輯承載網是GS的子圖GU，邊集和頂點集分別記為E( GU)和V( GU)。邏輯承載網構建是將LCN構建需求映射到一個GU，即根據(jù)LCN的需求約束找到相應的E( GU)和V( GU)。

多個邏輯承載網建網需求到達時，研究問題抽象為多源多匯問題來求解，即在源、目節(jié)點對(si, ti)(i=1,…,N)間尋求滿足建網需求的節(jié)點、鏈路集合。W Szeto[8]將多源多匯問題轉化為多物質流[9](MCF, multi-commodity flow)模型求解，用于虛擬網資源分配，但構建成功的虛擬網會占用后續(xù)虛擬網所需物理網絡資源，影響后續(xù)虛擬網的構建。

邏輯承載網構建目的是增強物理網絡的服務提供能力，即構建盡可能地滿足需求的邏輯承載網，同時提高網絡資源利用率。因此，本文基于網絡的負載狀況，在MCF算法的基礎上，結合MIRA[10]和LCRA[11]算法思想，提出改進的MMCF (I-MMCF,improved min-cost multi-commodity flow) 算法。

3 基于負載均衡的邏輯承載網構建

虛擬網研究多采用節(jié)點上所承載的虛擬網的個數(shù)來反映節(jié)點的負載強度，這是因為虛擬網所考慮的節(jié)點大多為主機、服務器等資源，節(jié)點的主要資源為CPU，所承載的虛擬網越多，CPU負載越重。而邏輯承載網研究的節(jié)點是指路由交換平臺，其最主要的資源包括LE(FE)帶寬與交換容量。而交換容量是由其端口數(shù)與端口速率共同決定的，現(xiàn)有核心路由交換設備的節(jié)點強度評價方法并未考慮到節(jié)點交換容量的差異，本文采用歸一化的方式來屏蔽掉節(jié)點交換容量的差異，對各節(jié)點、鏈路當前的流量承載狀況進行評價。首先，進行如下定義。

定義1 鏈路強度Sl

其中，P為經過該鏈路的LCN的路徑數(shù)量，loadi表示每條路徑所用的帶寬，即每個LCN為該鏈路造成的負載，B為該鏈路總帶寬。

定義2 鏈路關鍵性KoL( l)

其中，KoL( l)是衡量該鏈路對LCN構建影響重要程度的指標。令其等于鏈路強度，即該鏈路上所有LCN負載之和與鏈路容量的比值。

可以看出，KoL( l)的值越大，表示鏈路l越關鍵，后續(xù)映射在鏈路l上的邏輯承載網構建成功率就低。

定義3 鏈路費用cm

其中，Bavail為該鏈路的可用帶寬。因此，cm將鏈路關鍵性與鏈路可用帶寬聯(lián)系在一起，使盡可能多的鏈路被用于構建LCN，以均衡地利用網絡資源[11]。Bavail越大，使用該鏈路構建LCN的費用越小，鏈路越關鍵，使用該鏈路構建LCN的費用越大。在以上定義基礎上，基于負載均衡思想，將LCN構建問題轉化為最小費用多物質流(MMCF)[9]問題，提出改進的MMCF算法，建立數(shù)學規(guī)劃進行求解。

即已知一流網絡G( V, E)，V為節(jié)點1,…,n所構成的有限集，E為節(jié)點對(i, j)所構成的鏈路集合，em=(i, j)，其中，鏈路em的容量為bm，費用為cm,m=1,…,M。假設有k件物質k=1,…,K，為鏈路m上物質k的流量。定義為k=(sk, tk, dk)，其中，sk和tk是物品k的源點及匯點，及dk是需求。則目標函數(shù)為

約束條件為

容量約束：

需求約束：

基于負載均衡的I-MMCF算法描繪如下。

Step1 根據(jù)節(jié)點位置約束及物理網絡節(jié)點組件類別約束選擇所需節(jié)點。

Step2 由基礎網中各節(jié)點所匯報的信息，根據(jù)建網跳數(shù)限制及帶寬需求約束計算出從源到匯所有可能的路徑，及各路徑的鏈路可用帶寬，組成子圖。

Step3 根據(jù)式(2)計算所有列出鏈路的關鍵性，進行降序排列，將關鍵性最大的鏈路從中刪除，得到余留網。

Step5 對于Step4無解的構建請求，等待下一個周期網絡資源的釋放，到Step2。

Step6 將邏輯承載網信息配置到物理承載節(jié)點，為數(shù)據(jù)建立路由交換通路。

為使算法易于網絡部署，本文做如下限定假設：減少路徑匹配的條數(shù)為2。即帶寬需求為Breq的業(yè)務，被匹配到2條不相交的獨立路徑資源Bp1和Bp2上，滿足Bp1+Bp2≥Breq。

4 仿真及結果

為衡量算法的性能，與使用最短路徑進行鏈路映射的VNE-baseline算法及VNE-splitting算法[7]性能加以比較。其中，VEA-baseline以最大可用資源為標準選取節(jié)點，將選取的節(jié)點用k-shortest 最短路徑尋路算法相連；VNE-splitting節(jié)點映射仍以最大可用資源為標準，采用多物質流模型中的最大流方法進行鏈路映射。

4.1 仿真環(huán)境

對VNE-baseline和VNE-splitting算法所采用的虛擬網嵌入仿真軟件VN embedding simulator(簡稱VNES)進行修改，生成適合邏輯承載網構建的仿真平臺。VNES主要由節(jié)點映射算法、鏈路映射算法等模塊組成，將其節(jié)點映射算法模塊移除，鏈路映射算法修改為I-MMCF算法，生成本文所需LCN構建仿真平臺。

使用GT-ITM隨機產生50個節(jié)點組成的基礎網拓撲，拓撲中任何節(jié)點都可以作為邏輯承載網的節(jié)點。每對節(jié)點的連接概率是0.5，帶寬資源在50到100間均勻分布，LCN請求到達過程服從以100時間單位均值為5(單位：個)為參數(shù)的泊松過程，即λ=5 (為考察不同負載到達的影響，還進行了λ=10的仿真)；每個LCN的生存時間服從參數(shù)為μ=1000的指數(shù)分布。LCN節(jié)點數(shù)在2到10之間均勻分布，而帶寬需求在0到50之間均勻分布，實驗共進行5次。用下列4個指標來衡量構建算法。

1) 網絡構建成功率。網絡構建成功率是一段時間內算法構建成功的LCN數(shù)占總構建請求數(shù)的百分比。即

2) 最大節(jié)點強度與平均節(jié)點強度。節(jié)點強度Sn定義為節(jié)點上所承載的邏輯承載網帶寬之和占節(jié)點總交換容量的比重。

其中，Bk為第k個邏輯承載網所用帶寬，K為所承載的邏輯承載網個數(shù)，而Bswitching為節(jié)點總的交換容量。

最大節(jié)點強度是路由交換節(jié)點承載的邏輯承載網Sn的最大值，最大節(jié)點強度用以衡量算法對節(jié)點的均衡使用。平均節(jié)點強度是路由交換節(jié)點承載邏輯承載網Sn的數(shù)學期望，即

其中，VLCN為LCN節(jié)點，VS為物理網節(jié)點，N為物理網絡節(jié)點數(shù)。

3) 平均鏈路利用率。平均鏈路利用率是構建的邏輯承載網絡所占鏈路帶寬之和與物理網絡分配的所有鏈路資源帶寬之和的比值。平均鏈路利用率用以衡量算法對鏈路的均衡使用。

4) LCN構建平均收益。構建收益是服務提供商構建LCN后，形成服務能力賣給業(yè)務提供商所獲得的收益，與業(yè)務提供商所需的LCN帶寬bwi( lv)成正比，構建平均收益為一段時間內網絡構建收益的平均值。

4.2 仿真結果及性能分析

仿真結果如圖1和圖2所示，圖中，橫軸為到來的 LCN構建請求中，允許路徑分割的建網請求占總請求數(shù)的比例(簡稱為允許分流的比率)。例如，0%代表不允許任何業(yè)務路徑分割，而100%代表所有的建網請求都允許路徑分割?？疾觳煌埱蟮竭_速率λ ( λ = 5 ,a = 1 0)下，不同路徑分割需求對LCN構建所造成的影響，及各算法對網絡構建效率及服務能力的貢獻。

1) 請求到達率λ=5

由圖1(a)可以看出，VEA-baseline構建成功率略高于55%，是3種算法中較低的，并且不隨允許分流的比率發(fā)生變化。VNE-splitting和I-MMCF由于允許路徑分割，構建成功率會隨著允許路徑分割的比率增加而增加，由于I-MMCF每次分配資源時，將鏈路負載與可用帶寬一起考慮，剩余資源均衡性更好，當允許分流的比率超過60%時，構建成功率比VNE-splitting大約高出7%左右。

從圖1(b)可看出，因為允許路徑分割的請求越多，構建 LCN的收益越大，如果所有請求都允許路徑分割，VNE-splitting算法得到的收益大概是不允許路徑分割算法的 120%。而 I-MMCF和VNE-splitting都允許路徑分割，故 I-MMCF比VNE-splitting的構建平均收益R并沒有相應增加，但都高于VEA-baseline。

圖1(c)是隨著允許路徑分割的請求數(shù)增多，平均鏈路利用率的變化?？梢钥闯觯斏俨糠謽I(yè)務允許路徑分割時，I-MMCF和VNE-splitting算法的平均鏈路利用率有大約30%的增加，而當允許分流的比率逐漸增加到100%時，I-MMCF和VNE-splitting算法的平均鏈路利用率顯著提高，比不允許路徑分割的算法大約有40%左右的增加。

由于VNE-splitting算法選取可用資源最大的節(jié)點進行節(jié)點映射，而I-MMCF在支持路徑分割的同時，比 VNE-splitting更注重避免過多使用關鍵性高的資源，資源使用均衡性更強。從圖1 (d) 可看出，網絡最大節(jié)點強度VNE-splitting比I-MMCF要高，說明 VNE-splitting對個別節(jié)點多次使用，使其負載相對過重。

圖1 λ=5時LCN構建性能比較

圖2 λ=10時LCN構建性能比較

2) 請求到達率λ=10

從圖2(a)可以看出，隨著負載增大，構建成功率提高并不明顯。由于負載增加的速度快，即使考慮了資源均衡使用的I-MMCF算法也沒有取得明顯的優(yōu)勢。還可看出，當構建請求中對 LCN規(guī)模需求較大時，即 LCN節(jié)點數(shù)較多，即使采用基于負載均衡的構建方法，也不一定能構建成功。這說明，基于負載均衡的構建方法是一種提高效率的構建方法，當這種方法也不能構建成功時，說明網絡的物理資源已不能滿足構建需求。

5 結束語

I-MMCF算法將邏輯承載網構建需求映射到不同粒度網絡資源，將已存在的網絡負載及物理網剩余資源映射為鏈路費用，既能區(qū)別對待具有不同服務能力的節(jié)點及鏈路，又增強了物理資源利用的可擴展性。模擬實驗結果表明，基于負載均衡的多粒度映射策略可以提高物理承載資源利用的靈活性，提高構建效率。在物理承載網負載均衡時，優(yōu)勢最大。

[1] 汪斌強, 鄔江興. 下一代互聯(lián)網的發(fā)展趨勢及相應對策分析[J].信息工程大學學報 , 2009, 10(1):1-10.WANG B Q, WU J X. Development trends and associated countermeasures analysis for NGN[J]. Journal of Information Engineering University, 2009, 10(1):1-10.

[2] 王浩學, 汪斌強, 于婧等. 一體化承載網絡體系架構研究[J].計算機學報, 2009,32(3): 371-376.WANG H X, WANG B Q, YU J, et al. Research on architecture of universal carrying network[J]. Chinese Journal of Computers, 2009,32(3): 371-376.

[3] PETERSON L, SHENKER S, TURNER J. Overcoming the internet impasse through virtualization[J]. IEEE Computer, 2005,38(4):34-41.

[4] YU M, YI Y, REXFORD J. Rethinking Virtual Network Embedding:Substrate Support for Path Splitting and Migration[R]. Princeton University, Technical Report TR-788-07, 2007.

[5] RICCI R. A solver for the network testbed mapping problem[J]. ACM Computer Communication Review, 2003,33(2):65-81.

[6] LU J, TURNER J. Efficient Mapping of Virtual Networks onto a Shared Substrate[R]. Washington University, Technical Report WUCSE-2006-35,2006.

[7] YU M, YI Y, JENNIFER R, et al. Rethinking virtual network embedding: substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008,38(2):17-29.

[8] SZETO W, IRAQI Y, BOUTABA R. A multi-commodity flow based approach to virtual network resource allocation[A]. IEEE GLOBECOM 2003[C]. San Francisca, USA, 2003. 3004-3008.

[9] AHUJA R K, MAGNANTI T L, ORLIN J B. Network Flows: Theory,Algorithms, and Applications[M]. London: Prentice Hall, 1993.

[10] KODIALAM M S, LAKSHMAN T V. Minimum interference routing with applications to MPLS traffic engineering[J]. Proc of IEEE INFOCOM, 2000,36(2): 884-893.

[11] 唐治果, 李樂民, 虞紅芳. 針對MPLS網絡流量工程的鏈路關鍵性路由算法[J].電子與信息學報, 2007,29(5):1187-1190.TANG Z G, LI L M, YU H F. Link criticality routing algorithm for MPLS traffic engineering[J]. Journal of Electronics & Information Technology, 2007,29(5):1187-1190.