王浩學(xué)，姜明，付吉

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

1 引言

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

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

2 網(wǎng)絡(luò)模型及問題描述

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

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

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

3 基于負載均衡的邏輯承載網(wǎng)構(gòu)建

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

定義1 鏈路強度Sl

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

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

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

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

定義3 鏈路費用cm

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

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

約束條件為

容量約束：

需求約束：

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

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

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

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

Step5 對于Step4無解的構(gòu)建請求，等待下一個周期網(wǎng)絡(luò)資源的釋放，到Step2。

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

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

4 仿真及結(jié)果

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

4.1 仿真環(huán)境

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

使用GT-ITM隨機產(chǎn)生50個節(jié)點組成的基礎(chǔ)網(wǎng)拓撲，拓撲中任何節(jié)點都可以作為邏輯承載網(wǎng)的節(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個指標(biāo)來衡量構(gòu)建算法。

1) 網(wǎng)絡(luò)構(gòu)建成功率。網(wǎng)絡(luò)構(gòu)建成功率是一段時間內(nèi)算法構(gòu)建成功的LCN數(shù)占總構(gòu)建請求數(shù)的百分比。即

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

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

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

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

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

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

4.2 仿真結(jié)果及性能分析

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

1) 請求到達率λ=5

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

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

圖1(c)是隨著允許路徑分割的請求數(shù)增多，平均鏈路利用率的變化。可以看出，當(dāng)少部分業(yè)務(wù)允許路徑分割時，I-MMCF和VNE-splitting算法的平均鏈路利用率有大約30%的增加，而當(dāng)允許分流的比率逐漸增加到100%時，I-MMCF和VNE-splitting算法的平均鏈路利用率顯著提高，比不允許路徑分割的算法大約有40%左右的增加。

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

圖1 λ=5時LCN構(gòu)建性能比較

圖2 λ=10時LCN構(gòu)建性能比較

2) 請求到達率λ=10

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

5 結(jié)束語

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

[1] 汪斌強, 鄔江興. 下一代互聯(lián)網(wǎng)的發(fā)展趨勢及相應(yīng)對策分析[J].信息工程大學(xué)學(xué)報 , 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] 王浩學(xué), 汪斌強, 于婧等. 一體化承載網(wǎng)絡(luò)體系架構(gòu)研究[J].計算機學(xué)報, 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網(wǎng)絡(luò)流量工程的鏈路關(guān)鍵性路由算法[J].電子與信息學(xué)報, 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.