劉向東，劉 奎，王 聰

(東北大學秦皇島分校計算機與通信工程學院，河北 秦皇島 066004)

1 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展，現(xiàn)有的互聯(lián)網(wǎng)架構(gòu)已經(jīng)難以滿足互聯(lián)網(wǎng)新型應(yīng)用的發(fā)展，在一定程度上呈現(xiàn)出僵化現(xiàn)象。更重要的是隨著云計算技術(shù)的出現(xiàn)，迫切要求能夠?qū)⑽锢砭W(wǎng)絡(luò)內(nèi)的資源靈活、動態(tài)地租賃給若干用戶使用。網(wǎng)絡(luò)虛擬化[1]被認為是解決網(wǎng)絡(luò)僵化及多租賃問題的重要途徑，其中的虛擬網(wǎng)絡(luò)映射問題研究如何將具有虛擬節(jié)點需求(如CPU)和虛擬鏈路需求(網(wǎng)絡(luò)帶寬)的用戶虛擬網(wǎng)絡(luò)映射到資源有限的基礎(chǔ)設(shè)施網(wǎng)絡(luò)中，是網(wǎng)絡(luò)虛擬化的基礎(chǔ)問題[2]。在進行虛擬網(wǎng)絡(luò)映射時需要同時考慮資源約束、拓撲多樣性等多方面的問題，這樣的優(yōu)化問題已經(jīng)被證明是NP困難的[3]，研究思路是先給出映射模型及約束條件，再給出優(yōu)化目標，然后利用智能算法進行求解。

目前，已有一些虛擬網(wǎng)絡(luò)映射算法，根據(jù)是否將節(jié)點映射和鏈路映射分離可以分為一階段算法和兩階段算法。在一階段算法中，Ines H等人[4]在假定底層物理網(wǎng)絡(luò)資源無限的前提下，提出了一種分布式的虛擬網(wǎng)絡(luò)映射算法，通過多代理機制同時映射虛擬節(jié)點和鏈路。Jens L等人[5]設(shè)計基于子圖重構(gòu)的虛擬網(wǎng)絡(luò)映射算法，逐步映射節(jié)點和鏈路并引入了回溯算法，以擴大搜索空間，當下一步的映射方案無法滿足約束時回溯到上一步重新選擇映射的物理節(jié)點。在兩階段算法中，Minlan Y等人[6]提出的兩階段映射方案首先根據(jù)約束映射節(jié)點，然后將虛擬鏈路映射問題看成多商品流問題進行求解，相較傳統(tǒng)一階段算法，該算法提高了虛擬網(wǎng)絡(luò)的接受率和底層物理網(wǎng)絡(luò)的收益。Yong Z等人[7]使用貪心算法盡可能為虛擬節(jié)點選擇負載較輕的物理節(jié)點，然后通過最短路徑算法構(gòu)建兩個物理節(jié)點間的鏈路以映射虛擬鏈路。Cheng Xiang等人[8]提出了基于粒子群的虛擬網(wǎng)絡(luò)映射算法，同樣是先映射節(jié)點再根據(jù)最短路徑映射邊，該算法相較以前的算法可以獲得更好的收益和虛擬網(wǎng)絡(luò)接受率，但是沒有考慮節(jié)點可重用技術(shù)也沒有對群體初始位置進行優(yōu)化。另外，當前主機虛擬化技術(shù)已較為完備，VMware、Xen等產(chǎn)品均已支持駐留在同一物理主機上的虛擬機之間可以通過內(nèi)存交換代替虛擬鏈路上的數(shù)據(jù)交換[9]，這為虛擬網(wǎng)絡(luò)映射問題帶來了新的解決思路，即同一物理網(wǎng)絡(luò)上的虛擬機可以映射到同一個物理主機上，這樣可以抵消掉一部分鏈路帶寬需求，這種技術(shù)稱為節(jié)點可重用技術(shù)。

本文在Cheng Xiang等人[8]工作的基礎(chǔ)上引入了節(jié)點可重用技術(shù)，重新規(guī)劃了優(yōu)化模型并設(shè)計了增強型粒子初始位置分配機制。利用可重用技術(shù)能夠以虛擬機間內(nèi)存數(shù)據(jù)交換代替網(wǎng)絡(luò)數(shù)據(jù)交換的優(yōu)點，通過在求解時對粒子群的初始位置進行有針對性的賦值，盡量將同一虛擬網(wǎng)絡(luò)的節(jié)點映射到同一物理網(wǎng)絡(luò)節(jié)點之上，從而節(jié)省物理網(wǎng)絡(luò)的帶寬。本文算法的目的是進一步提高底層物理網(wǎng)絡(luò)的資源利用率，從而獲得更好的性能和虛擬網(wǎng)絡(luò)接受率。

2 虛擬網(wǎng)絡(luò)映射問題描述

虛擬網(wǎng)絡(luò)映射的目標是在盡可能多地接受虛擬網(wǎng)絡(luò)請求的前提下，使用最少的物理網(wǎng)絡(luò)資源，從而使得底層網(wǎng)絡(luò)所有者的成本最小化。對于主機資源如CPU、內(nèi)存、硬盤等資源來說，需求和成本永遠相等，在構(gòu)建優(yōu)化模型時這部分的成本可以不予考慮，僅需考慮資源是否滿足約束條件；而由于采用了可重用技術(shù)，可以用內(nèi)存交換替代網(wǎng)絡(luò)交換以節(jié)省物理網(wǎng)絡(luò)的帶寬資源，那么映射方案的好壞對于網(wǎng)絡(luò)資源的成本支出是有影響的，因此對于每個虛擬網(wǎng)絡(luò)請求，其映射優(yōu)化問題可以描述為：

s.t. ?n∈NV, ?j∈NS

?w∈EV, ?(i,j)∈pS,

(1)

(2)

優(yōu)化問題(1)中的第一個約束條件是主機資源約束需滿足的條件，即當前物理節(jié)點的空閑資源要小于待映射虛擬節(jié)點請求的資源；第二個約束條件是物理帶寬約束，即虛擬邊的映射方案占用的每條物理鏈路的空閑帶寬必須大于虛擬鏈路請求的帶寬。

3 基于粒子群的虛擬網(wǎng)絡(luò)映射算法

對于優(yōu)化問題(1)，可以采用離散粒子群DPSO(Discrete PSO)[8]算法進行求解。離散粒子群算法是傳統(tǒng)粒子群算法的變種，由于虛擬網(wǎng)絡(luò)映射問題是離散問題，而傳統(tǒng)的粒子群算法具有連續(xù)的本質(zhì)，不太適合求解離散問題，因此將傳統(tǒng)算法離散化是必要的。本節(jié)首先描述映射優(yōu)化問題的離散粒子群求解算法，然后給出針對節(jié)點可重用的群體位置初始化算法，以形成整體算法。

3.1 針對虛擬網(wǎng)絡(luò)映射問題的離散粒子群算法

Xk+1=Xk⊕Vk+1

(3)

定義1位置的減法X*-X：結(jié)果是一個新的位置向量X′，表示虛擬網(wǎng)絡(luò)映射方案X*和X的差異。如果X*和X在相同維度上的值相同，則新向量對應(yīng)維度上的值為1，否者為0。

定義2位置的和φ1X′+φ2X″：結(jié)果是一個速度向量，其中φ1、φ2為常數(shù)，且φ1+φ2=1。φ1X′+φ2X″的運算定義為：如果X′和X″在相同維度上值相同，則新速度在相應(yīng)維度上的值保持不變，否則，以φ1的概率保持X′，以φ2的概率保持X″。

定義3位置和速度的和Xk⊕Vk：結(jié)果是一個新的位置向量，即當前映射方案Xk按照Vk調(diào)整虛擬節(jié)點的映射位置，如果Xk對應(yīng)的Vk相應(yīng)維度上的值為1，意味著當前位置需要保留，為0時需要為當前維度所代表的虛擬節(jié)點重新隨機選擇一個滿足主機資源約束條件的物理節(jié)點。

DPSO_Mapping (GV,GS){

輸入：虛擬網(wǎng)絡(luò)GV, 物理網(wǎng)絡(luò)GS;

輸出：最優(yōu)映射方案 solution。

移除空閑資源小于 GV中最小節(jié)點CPU和鏈路帶寬需求的物理節(jié)點和物理鏈路;

for(int i=0; i

particle[i].initialposition();}

for(int i=0; i

gbestpre=particles.getgBest();

for(int j=0; j

particle[j].calculateFitness();

particle[j].updateSpeed();

particle[j].updatePosition();}

if(gbestpre==particles.getgBest()){

numofit++;}

else{numofit=0;}

if(numofit==10){break;}

}

if(particles.getgBest()!=+∞){

solution=Particle.getGbsolution();}

return solution;

}

在算法中，移除空閑資源小于最小請求的節(jié)點和邊的目的是為了盡量縮小搜索空間。算法結(jié)束的條件是群體最優(yōu)位置gbestpre 在10輪內(nèi)不變或者計算輪數(shù)超過給定的最大迭代次數(shù)MaxItCount。

3.2 針對可重用的粒子位置分配機制

位置的初始化及更新機制對于粒子群算法的收斂速度有著重要影響，特別是在針對實際問題的離散粒子群求解過程中更加重要。在3.1節(jié)的算法中，與位置相關(guān)的關(guān)鍵函數(shù)是updatePosition()和initialposition( )，只隨機選取物理節(jié)點的編號不利于節(jié)省帶寬資源。為了充分發(fā)揮可重用能夠節(jié)省物理帶寬消耗的優(yōu)勢，應(yīng)當盡量把每個虛擬網(wǎng)絡(luò)的虛擬節(jié)點映射到同一物理節(jié)點上。為此需要對算法的位置更新及初始化函數(shù)針對可重用特性進行強化。

在強化過程中，既要保證盡量發(fā)揮可重用的特性又不能使得虛擬節(jié)點過度集中于某幾個物理節(jié)點。因為如果在位置初始化的時候就令虛擬節(jié)點過度集中，那么很可能每個粒子都不會獲得可行解，在沒有可行解的情況下無法獲得最優(yōu)適應(yīng)度的fitness值，也就無法獲得群體最優(yōu)位置，這將會導(dǎo)致粒子無法更新自己的位置。另外還要考慮，在虛擬網(wǎng)絡(luò)映射問題中，每個虛擬網(wǎng)絡(luò)請求的節(jié)點數(shù)量都不相同，在每個維度上重復(fù)分配同一個物理節(jié)點的次數(shù)應(yīng)當與虛擬節(jié)點數(shù)量建立動態(tài)對應(yīng)關(guān)系。本文采用動態(tài)機制結(jié)合虛擬網(wǎng)絡(luò)節(jié)點數(shù)來強化可重用特性，為此引入因子k=(rnd.nextInt(numofpynodes)+m)/m，對于粒子位置向量的每個維度來說，如果其維度n模k等于0，則重新隨機選擇一個物理節(jié)點，否則保持前一維度所選擇的物理節(jié)點。通過調(diào)整m的值可以獲得合理的k值，這樣可以將映射方案控制在一個比虛擬節(jié)點數(shù)小的物理節(jié)點集合之內(nèi)，也就意味著可以充分發(fā)揮可重用特定而又不會導(dǎo)致群體無解的情況發(fā)生。以位置初始化算法initialposition( )為例，其偽代碼如下所示：

initialposition(VNR) {

//numofsnodes:物理網(wǎng)絡(luò)節(jié)點數(shù);

//numofvnodes:虛擬網(wǎng)絡(luò)節(jié)點數(shù)；

k=(rnd.nextInt(numofvnodes)+m)/m;

maph=rnd.nextInt(numofsnodes);

for(i=0; i

if(i%k==0){

maph=rnd.nextInt(numofsnodes);}

position.put(i, maph);}

}

位置更新函數(shù)updatePosition ( )與上述初始化函數(shù)類似，需要注意的是在位置更新時只更新那些對應(yīng)速度向量維度為0的位置，為它們隨機選取物理節(jié)點并通過強化機制發(fā)揮可重用優(yōu)勢。

4 實驗

實驗采用CloudSim 3.0.1[10]仿真軟件平臺，硬件平臺為IBM X3650服務(wù)器。在CloudSim中用Java為底層物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)編寫了一個隨機的拓撲生成器。映射算法中涉及到的參數(shù)設(shè)定為φ1=φ2=0.5，位置分配算法中m=2，虛擬網(wǎng)絡(luò)的生存周期在100～1 000時間單位中均勻分布，如果10輪沒有改變?nèi)肿顑?yōu)位置或者計算次數(shù)超過30輪則粒子群算法終止。實驗比較了本文提出的算法采用/不采用增強位置分配與文獻[8]中的VEN-R-PSO映射算法在底層物理網(wǎng)絡(luò)開銷及計算效率上的表現(xiàn)。在物理網(wǎng)絡(luò)開銷實驗中，底層物理網(wǎng)絡(luò)為100個節(jié)點，連通概率為0.2。虛擬網(wǎng)絡(luò)節(jié)點數(shù)為4，連通概率為0.4。實驗每次仿真2 000個虛擬網(wǎng)絡(luò)的映射，共運行10次,然后計算接受同樣節(jié)點數(shù)后物理網(wǎng)絡(luò)累積開銷的平均值，由于虛擬網(wǎng)絡(luò)不可能同時被接受，大部分網(wǎng)絡(luò)需要排隊等候，因此實驗?zāi)軌蚱鸬綑z驗作用。

由于虛擬網(wǎng)絡(luò)的連通概率大于底層物理網(wǎng)絡(luò)，對于不可重用的映射算法可能存在無解的虛擬網(wǎng)絡(luò)，即那些含有連通度大于物理網(wǎng)絡(luò)最大節(jié)點連通度的虛擬節(jié)點的虛擬網(wǎng)絡(luò)無法被接受，因此實驗只給出了1 500個虛擬網(wǎng)絡(luò)的映射結(jié)果。從圖1可以看出，本文提出的算法接受同樣的虛擬網(wǎng)絡(luò)時底層物理網(wǎng)絡(luò)開銷更小，主要原因是可重用技術(shù)的使用可以節(jié)省物理鏈路帶寬的分配，那些被映射到同一物理主機上的虛擬網(wǎng)絡(luò)沒有開銷產(chǎn)生。特別是加入位置強化機制后能夠節(jié)省很大的開銷，這主要是由于初始位置設(shè)定對于粒子群尋找最優(yōu)解有極大幫助，針對可重用特性的強化機制能夠盡量把同一虛擬網(wǎng)絡(luò)的節(jié)點放到相同的物理節(jié)點之上。

Figure 1 Cost of substrate network to accept same number of virtual networks圖1 接受相同數(shù)量虛擬網(wǎng)絡(luò)時的物理網(wǎng)絡(luò)開銷

第二個實驗將物理網(wǎng)絡(luò)的節(jié)點數(shù)分別設(shè)為60、80、100，測試了完成前1 000個虛擬網(wǎng)絡(luò)所需的時間。同樣每次實驗運行10次，共運行30次仿真。如圖2所示，物理網(wǎng)絡(luò)節(jié)點數(shù)越少，完成1 000個虛擬網(wǎng)絡(luò)的時間越多，使用位置分配強化機制的效果越明顯。原因在于m值對于群體求解效率具有影響，實驗中三種物理拓撲均采用m=2，對于規(guī)模大的物理網(wǎng)絡(luò)，由于搜索空間更大也就更不容易發(fā)揮可重用特性，此時應(yīng)該選擇大一些的m值。m值的選取除了考慮對可重用程度及求解效率有影響之外，還應(yīng)考慮搜索空間大小，即物理網(wǎng)絡(luò)節(jié)點的個數(shù)，因此m值的選取應(yīng)當參考實際情況進行合理選擇。

Figure 2 Completion time of 1 000 virtual networks on substrate networks with different node numbers圖2 不同節(jié)點數(shù)量物理網(wǎng)絡(luò)拓撲上1 000個虛擬網(wǎng)絡(luò)完成時間

5 結(jié)束語

本文針對網(wǎng)絡(luò)虛擬化應(yīng)用中的虛擬網(wǎng)絡(luò)映射問題，提出了一種物理節(jié)點可復(fù)用的虛擬網(wǎng)絡(luò)映射算法，該算法在盡可能縮小搜索空間的基礎(chǔ)上采用節(jié)點可復(fù)用方法，以內(nèi)存交換代替虛擬鏈路，從而減少了物理鏈路資源的開銷。針對粒子群初始位置及位置更新設(shè)計了強化機制，有助于算法求解效率的提高，對求解的優(yōu)化程度能夠起到良好促進作用。仿真實驗表明，本文提出的算法在支持相同數(shù)量及結(jié)構(gòu)的虛擬網(wǎng)絡(luò)時產(chǎn)生的開銷更小，特別是位置強化分配機制能夠?qū)崿F(xiàn)更小的開銷和更高的求解效率。

[1] Chowdhury N.M. M K,Boutaba R.A survey of network virtualization[J].Computer Networks,2010,54:862-876.

[2] Li Xiao-ling,Wang Huai-min,Ding Bo,et al.Research and development of virtual network mapping problem[J].Journal of Software,2012,23(11):3009-3028.(in Chinese)

[3] Cai Zhi-ping,Liu Qiang,Lu Pin,et al.Virtual network mapping model and optimization algorithms[J]. Journal of Software, 2012, 23(4):864-877. (in Chinese)

[4] Ines H,Wajdi L,Djamal Z. A distributed virtual network mapping algorithm[C]∥Proc of the IEEE International Conference on Communications (ICC’08), 2008:5634-5640.

[5] Jens L,Holger K.A virtual network mapping algorithm based on subgraph isomorphism detection[C]∥Proc of the 2009 ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures (VISA’ 09),2009:81-88.

[6] Minlan Y,Yung Y,Jennifer R,et al.Rethinking virtual network embedding:Substrate support for path splitting and migration[J]. ACM SIGCOMM CCR,2008,38(2):17-29.

[7] Yong Z,Mostafa A. Algorithms for assigning substrate network resources to virtual network components[C]∥Proc of the 25th IEEE International Conference on Computer Communications (INFOCOM’06), 2006:1-12.

[8] Cheng Xiang, Zhang Zhong-bao,Su Sen,et al.Virtual network embedding based on particle swarm optimization[J]. Acta Electronica Sinica,2011,39(10):2240-2244.(in Chinese)

[9] Jian W,Kwame-Lante W,Kartik G. XenLoop:A transparent high performance inter-VM network loopback[J].Cluster Computing,2009,12(2):141-152.

[10] CloudSim:A framework for modeling and simulation of cloud computing infrastructures and services[EB/OL].[2013-02-16].http://www.cloudbus.org/cloudsim/2013.

附中文參考文獻：

[2] 李小玲,王懷民,丁博,等.虛擬網(wǎng)絡(luò)映射問題研究及其進展[J].軟件學報,2012,23(11):3009-3028.

[3] 蔡志平,劉強,呂品,等.虛擬網(wǎng)絡(luò)映射模型及其優(yōu)化算法[J].軟件學報,2012,23(4):864-877.

[8] 程祥，張忠寶，蘇森，等.基于粒子群優(yōu)化的虛擬網(wǎng)絡(luò)映射算法[J].電子學報，2011,39(10):2240-2244.