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

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

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

1 引言

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

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

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

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

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

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

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

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

定義1 鏈路強(qiáng)度Sl

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

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

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

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

定義3 鏈路費(fèi)用cm

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

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

約束條件為

容量約束：

需求約束：

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

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

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

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

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

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

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

4 仿真及結(jié)果

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

4.1 仿真環(huán)境

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

使用GT-ITM隨機(jī)產(chǎn)生50個(gè)節(jié)點(diǎn)組成的基礎(chǔ)網(wǎng)拓?fù)?，拓?fù)渲腥魏喂?jié)點(diǎn)都可以作為邏輯承載網(wǎng)的節(jié)點(diǎn)。每對(duì)節(jié)點(diǎn)的連接概率是0.5，帶寬資源在50到100間均勻分布，LCN請(qǐng)求到達(dá)過(guò)程服從以100時(shí)間單位均值為5(單位：個(gè))為參數(shù)的泊松過(guò)程，即λ=5 (為考察不同負(fù)載到達(dá)的影響，還進(jìn)行了λ=10的仿真)；每個(gè)LCN的生存時(shí)間服從參數(shù)為μ=1000的指數(shù)分布。LCN節(jié)點(diǎn)數(shù)在2到10之間均勻分布，而帶寬需求在0到50之間均勻分布，實(shí)驗(yàn)共進(jìn)行5次。用下列4個(gè)指標(biāo)來(lái)衡量構(gòu)建算法。

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

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

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

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

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

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

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

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

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

1) 請(qǐng)求到達(dá)率λ=5

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

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

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

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

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

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

2) 請(qǐng)求到達(dá)率λ=10

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

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

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

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