基于拓?fù)漕A(yù)配置的公平虛擬網(wǎng)絡(luò)映射算法

王 聰 苑 迎 彭三城 王興偉 王翠榮 萬 聰

1(東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院 河北秦皇島 066004)2(廣東外語外貿(mào)大學(xué)思科信息學(xué)院 廣州 510420)3 (東北大學(xué)軟件學(xué)院 沈陽 110819)(congw@neuq.edu.cn)

基于拓?fù)漕A(yù)配置的公平虛擬網(wǎng)絡(luò)映射算法

王 聰1苑 迎1彭三城2王興偉3王翠榮1萬 聰1

1(東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院 河北秦皇島 066004)2(廣東外語外貿(mào)大學(xué)思科信息學(xué)院 廣州 510420)3(東北大學(xué)軟件學(xué)院 沈陽 110819)(congw@neuq.edu.cn)

虛擬網(wǎng)絡(luò)映射是實(shí)現(xiàn)云環(huán)境下資源多租賃運(yùn)營及彈性計(jì)算資源服務(wù)的關(guān)鍵基礎(chǔ)環(huán)節(jié)，其目的是在滿足虛擬網(wǎng)絡(luò)資源需求的前提下將虛擬網(wǎng)絡(luò)植入到合適的底層物理節(jié)點(diǎn)和鏈路.現(xiàn)有虛擬網(wǎng)絡(luò)映射算法的研究成果大多以極大化物理資源利用率為目標(biāo)，對(duì)虛擬網(wǎng)絡(luò)請(qǐng)求排隊(duì)中的公平性問題考慮較少.為此提出了一種基于虛擬拓?fù)漕A(yù)配置及可重用技術(shù)的虛擬網(wǎng)絡(luò)映射算法以提高映射公平性.將虛擬網(wǎng)路映射過程分為2步驟：拓?fù)漕A(yù)配置過程和映射過程.1)對(duì)在線隊(duì)列中較大的虛擬網(wǎng)絡(luò)拓?fù)溥M(jìn)行等價(jià)變換，將其變換為節(jié)點(diǎn)及鏈路數(shù)目更小的拓?fù)?，減少虛擬網(wǎng)絡(luò)請(qǐng)求在拓?fù)渖系牟町悘亩岣吖叫裕?)建立形式化的虛擬網(wǎng)絡(luò)映射模型，并利用離散粒子群算法對(duì)優(yōu)化模型進(jìn)行求解；為了充分利用可重用技術(shù)能在求解過程中節(jié)省帶寬資源的特性，引入粒子位置分配增強(qiáng)機(jī)制以提高物理網(wǎng)絡(luò)資源利用率.仿真實(shí)驗(yàn)結(jié)果表明：提出的算法在物理網(wǎng)絡(luò)資源利用率、收益成本比及虛擬網(wǎng)絡(luò)接受公平性等方面均優(yōu)于已有同類算法.

網(wǎng)絡(luò)虛擬化；虛擬網(wǎng)絡(luò)映射；節(jié)點(diǎn)可重用；虛擬拓?fù)漕A(yù)配置；離散粒子群優(yōu)化算法

云計(jì)算最大的特點(diǎn)是使得IT資源可以像水、電、天然氣一樣按需租賃并計(jì)費(fèi).從物理資源所有角度，云環(huán)境下的市場被分為2部分：基礎(chǔ)設(shè)施提供商和服務(wù)提供商[1].基礎(chǔ)設(shè)施提供商是資源所有者，其資源將被動(dòng)態(tài)、實(shí)時(shí)、按需地租賃給IT市場中的任意用戶；服務(wù)提供商根據(jù)實(shí)際需求按需租賃基礎(chǔ)設(shè)施提供商的硬件資源，從而構(gòu)建定制的虛擬網(wǎng)絡(luò)，向端用戶提供IT服務(wù).這種典型的云環(huán)境下的多租賃市場運(yùn)營機(jī)制，對(duì)于企業(yè)節(jié)省成本及提高資源利用率具有極大意義[2].

租賃的實(shí)現(xiàn)離不開虛擬化技術(shù)的支持，主要手段是通過虛擬化技術(shù)，包括軟件、操作系統(tǒng)、存儲(chǔ)、網(wǎng)絡(luò)和管理的虛擬化把物理資源集中在一起形成共享虛擬資源池[3]，進(jìn)而實(shí)現(xiàn)虛擬資源動(dòng)態(tài)分配的多租賃特性.目前基礎(chǔ)設(shè)施提供商僅能實(shí)現(xiàn)主機(jī)資源的動(dòng)態(tài)分配和計(jì)費(fèi)，如Amazon的EC2[4].然而，用戶的實(shí)際需求包含虛擬主機(jī)和虛擬鏈路組成的虛擬網(wǎng)絡(luò).隨著高帶寬業(yè)務(wù)的發(fā)展，以虛擬網(wǎng)絡(luò)為控制管理單位的資源租賃機(jī)制的需求變得愈加迫切.

Fig. 1 Diagram of virtual network embedding圖1 虛擬網(wǎng)絡(luò)映射示意圖

如圖1所示，網(wǎng)絡(luò)虛擬化技術(shù)允許在共享的底層物理網(wǎng)絡(luò)之上共存多重異構(gòu)的虛擬網(wǎng)絡(luò).以網(wǎng)絡(luò)虛擬化技術(shù)為基礎(chǔ)，為服務(wù)提供商的帶有節(jié)點(diǎn)(CPU、內(nèi)存、存儲(chǔ))和鏈路資源(帶寬)約束條件的虛擬網(wǎng)絡(luò)分配物理底層網(wǎng)絡(luò)資源的問題稱為虛擬網(wǎng)絡(luò)映射(嵌入)問題[5].虛擬網(wǎng)絡(luò)映射問題已經(jīng)被證明是NP難問題，即使在所有的虛擬節(jié)點(diǎn)已被映射后，映射具有帶寬資源約束的虛擬鏈路仍然是NP難的[6].因此，目前已有的研究成果大都采用智能算法來解決虛擬網(wǎng)絡(luò)映射問題.

在虛擬網(wǎng)絡(luò)映射的相關(guān)技術(shù)中，可重用技術(shù)的產(chǎn)生對(duì)于資源利用率的提高有較大意義.如圖1中虛擬網(wǎng)絡(luò)2的映射方案所示，可重用技術(shù)是指同一虛擬網(wǎng)絡(luò)的不同節(jié)點(diǎn)可以映射到同一物理節(jié)點(diǎn)上.這樣做的目的是可以將虛擬節(jié)點(diǎn)之間的鏈路直接映射到內(nèi)存中，用內(nèi)存數(shù)據(jù)交換來替代網(wǎng)絡(luò)交換，從而節(jié)省一部分帶寬資源.目前的主機(jī)虛擬化平臺(tái)軟件如VMware，Xen等均支持虛擬機(jī)間利用內(nèi)存通信的技術(shù)[7].

現(xiàn)有虛擬網(wǎng)絡(luò)映射算法研究成果大都以最大化資源利用率為目標(biāo)[5]，當(dāng)有空閑物理資源時(shí)就對(duì)在線排隊(duì)的虛擬網(wǎng)絡(luò)請(qǐng)求進(jìn)行篩選，盡可能接受更多的虛擬網(wǎng)絡(luò).在這樣的情況下，虛擬網(wǎng)絡(luò)拓?fù)涞牟町愋詫?dǎo)致規(guī)模較大的虛擬網(wǎng)絡(luò)請(qǐng)求很難被接受.為此，本文提出了拓?fù)漕A(yù)配置機(jī)制，對(duì)虛擬網(wǎng)絡(luò)拓?fù)溥M(jìn)行等價(jià)變換以減少虛擬拓?fù)溟g的差異性，并且結(jié)合可重用技術(shù)設(shè)計(jì)了一種以最大化物理網(wǎng)絡(luò)收益為目標(biāo)并兼顧排隊(duì)公平性的虛擬網(wǎng)絡(luò)映射算法.

1 相關(guān)工作

云環(huán)境下資源租賃的管理粒度正從物理主機(jī)、虛擬主機(jī)過渡到虛擬網(wǎng)絡(luò)，后者對(duì)資源租賃的抽象更加合理，兼具高效和靈活性.目前的研究成果可劃分為虛擬網(wǎng)絡(luò)映射和運(yùn)行時(shí)重配置兩大類，這兩類其實(shí)屬于資源租賃的2個(gè)不同階段.前者研究虛擬網(wǎng)絡(luò)在被映射到物理網(wǎng)絡(luò)上時(shí)的資源分配和收益優(yōu)化問題；后者通過調(diào)度物理網(wǎng)絡(luò)內(nèi)運(yùn)行的虛擬網(wǎng)絡(luò)，對(duì)虛擬鏈路和節(jié)點(diǎn)進(jìn)行遷移、調(diào)整，以減少資源“碎片”，提高資源利用率.本文主要針對(duì)虛擬網(wǎng)絡(luò)映射問題，但是借鑒了重配置對(duì)虛擬拓?fù)溥M(jìn)行調(diào)整的思路.下面對(duì)目前已有的研究成果做簡要論述.

在解決虛擬網(wǎng)絡(luò)映射問題時(shí)，往往通過簡化問題或增加假設(shè)來縮小搜索空間獲取優(yōu)化解.研究思路是首先給出映射模型及約束條件，然后出優(yōu)化目標(biāo)，最后利用智能算法進(jìn)行求解[6].因此，現(xiàn)有的解決方案可分為限制問題空間的映射算法[8-10]和不限制問題空間的映射算法[11-15].

由于同時(shí)存在節(jié)點(diǎn)和鏈路的資源限制，并且每個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求的到達(dá)時(shí)間、資源需求信息都是不可預(yù)知的，在不破壞底層資源約束的前提下實(shí)現(xiàn)多個(gè)不同拓?fù)涞奶摂M網(wǎng)絡(luò)的映射是一個(gè)巨大的挑戰(zhàn).文獻(xiàn)[8]在忽略節(jié)點(diǎn)資源限制、忽略準(zhǔn)入控制和假設(shè)已知所有虛擬網(wǎng)絡(luò)請(qǐng)求的前提下，將虛擬網(wǎng)絡(luò)請(qǐng)求的拓?fù)渚窒拊贗nternet骨干網(wǎng)絡(luò)拓?fù)?，使用線性規(guī)劃和混合整數(shù)2次規(guī)劃進(jìn)行問題求解.文獻(xiàn)[9]在忽略節(jié)點(diǎn)資源限制和忽略準(zhǔn)入控制的前提下，將小型網(wǎng)絡(luò)的通信矩陣建模成連續(xù)時(shí)間的Markov決定過程，通過模擬退火算法尋找最優(yōu)解.文獻(xiàn)[10]在忽略準(zhǔn)入控制和假設(shè)已知虛擬網(wǎng)絡(luò)請(qǐng)求信息的前提下，將虛擬網(wǎng)絡(luò)請(qǐng)求切割成多個(gè)星狀拓?fù)涞淖诱?qǐng)求之后，根據(jù)節(jié)點(diǎn)潛能使用自適應(yīng)的貪婪算法進(jìn)行求解.

文獻(xiàn)[11-15]在不限制問題空間的前提下，尋找映射虛擬網(wǎng)絡(luò)的解決方案.這類方法又可以細(xì)分為一階段映射算法和二階段映射算法.一階段映射算法是在映射過程中同時(shí)考慮節(jié)點(diǎn)和鏈路的資源限制，即映射一個(gè)虛擬節(jié)點(diǎn)，不但需要考慮節(jié)點(diǎn)資源需求，而且要考慮與已映射的虛擬節(jié)點(diǎn)之間的鏈路資源需求.在所有資源需求得到滿足之后，才能映射下一個(gè)虛擬節(jié)點(diǎn). 一階段算法往往使用回溯法進(jìn)行試探.文獻(xiàn)[11]在假定底層物理網(wǎng)絡(luò)資源無限的前提下，提出了一種分布式的虛擬網(wǎng)絡(luò)映射算法，通過多代理機(jī)制同時(shí)映射虛擬節(jié)點(diǎn)和鏈路.文獻(xiàn)[12]設(shè)計(jì)了基于子圖重構(gòu)的虛擬網(wǎng)絡(luò)映射算法，算法逐步映射節(jié)點(diǎn)和鏈路并引入回溯算法以擴(kuò)大搜索空間，當(dāng)下一步的映射方案無法滿足約束時(shí)則回溯到上一步，為虛擬節(jié)點(diǎn)重新選擇映射的物理節(jié)點(diǎn).

二階段算法將虛擬網(wǎng)絡(luò)的映射算法分為節(jié)點(diǎn)映射階段和鏈路映射階段.在節(jié)點(diǎn)映射階段，映射算法選出滿足各個(gè)虛擬節(jié)點(diǎn)資源需求的物理節(jié)點(diǎn)進(jìn)行節(jié)點(diǎn)映射；在鏈路映射階段，映射算法在已經(jīng)映射的物理節(jié)點(diǎn)之間尋找1條或多條無環(huán)路徑以映射相應(yīng)的虛擬鏈路.文獻(xiàn)[13]提出的二階段映射方案首先根據(jù)約束映射節(jié)點(diǎn)，然后將虛擬鏈路映射問題看成多商品流問題進(jìn)行求解.較傳統(tǒng)一階段算法，二階段算法提高了虛擬網(wǎng)絡(luò)的接受率和底層物理網(wǎng)絡(luò)的收益.文獻(xiàn)[14]使用貪心算法盡可能為虛擬節(jié)點(diǎn)選擇負(fù)載較輕的物理節(jié)點(diǎn)，然后通過最短路徑算法尋找2個(gè)物理節(jié)點(diǎn)間的鏈路以映射虛擬鏈路.文獻(xiàn)[15]提出了一種增強(qiáng)的虛擬網(wǎng)絡(luò)映射算法，首先利用離散粒子群算法映射節(jié)點(diǎn)，然后再根據(jù)最短路徑映射邊.在粒子初始化中設(shè)計(jì)了可行性檢驗(yàn)機(jī)制以過濾掉不可行的候選物理節(jié)點(diǎn)，以實(shí)現(xiàn)加速算法收斂的目的.該算法相較以前的算法可以獲得更好的收益和虛擬網(wǎng)絡(luò)接受率，但是沒有考慮公平性問題和可重用技術(shù)的應(yīng)用，群體初始位置的優(yōu)化也仍有提高空間.

虛擬網(wǎng)絡(luò)的重配置是指通過對(duì)運(yùn)行時(shí)的虛擬網(wǎng)絡(luò)進(jìn)行調(diào)度管理，合理地遷移虛擬機(jī)和虛擬鏈路從而優(yōu)化物理網(wǎng)絡(luò)的資源利用率.該問題考慮的是如何調(diào)度已出租的資源來滿足后續(xù)虛擬網(wǎng)絡(luò)接入的需求[16]，比虛擬網(wǎng)絡(luò)映射問題更加復(fù)雜.當(dāng)?shù)讓游锢砭W(wǎng)絡(luò)資源稀缺時(shí)，重配置算法通過周期性地改變運(yùn)行時(shí)虛擬網(wǎng)絡(luò)的映射方案來獲得更多的可用資源.文獻(xiàn)[16]針對(duì)虛擬網(wǎng)絡(luò)資源分配產(chǎn)生的底層物理網(wǎng)絡(luò)資源碎片問題，用已知信息預(yù)測資源重配置時(shí)間間隔，解決了傳統(tǒng)預(yù)配置周期固定的問題.文獻(xiàn)[17]進(jìn)一步細(xì)化檢測機(jī)制，定位需要調(diào)整的節(jié)點(diǎn)和鏈路，提高了虛擬網(wǎng)絡(luò)重配置的效率，并且提出了虛擬機(jī)的動(dòng)態(tài)遷移機(jī)制以保證服務(wù)的連續(xù)性.文獻(xiàn)[18]提出的重配置機(jī)制通過遷移代價(jià)最小節(jié)點(diǎn)來調(diào)整虛擬網(wǎng)絡(luò)拓?fù)?，減少了遷移開銷.上述虛擬網(wǎng)絡(luò)重配置算法通過對(duì)運(yùn)行虛擬網(wǎng)絡(luò)的映射方案進(jìn)行調(diào)整實(shí)現(xiàn)了提高資源利用率的目標(biāo)，本質(zhì)是對(duì)運(yùn)行時(shí)的虛擬網(wǎng)絡(luò)拓?fù)溥M(jìn)行變換，但是盡管設(shè)計(jì)了各種可行的機(jī)制，虛擬網(wǎng)絡(luò)的實(shí)時(shí)遷移仍然會(huì)存在一定的開銷.

綜上所述，已有的虛擬網(wǎng)絡(luò)映射方案沒有考慮接收公平性問題，這點(diǎn)在實(shí)際需求中是應(yīng)當(dāng)被關(guān)注的.另外，虛擬網(wǎng)絡(luò)重配置的研究成果對(duì)映射問題也有一定啟發(fā)：可以利用拓?fù)涞葍r(jià)變換的思路，對(duì)映射前的虛擬網(wǎng)絡(luò)進(jìn)行預(yù)配置來減少差異性，這樣不僅可以提高資源利用率，還可以解決排隊(duì)公平性問題.為此，區(qū)別于前人工作，本文針對(duì)虛擬網(wǎng)絡(luò)請(qǐng)求的排隊(duì)公平性問題，借鑒重配置的思路提出了一種虛擬拓?fù)漕A(yù)配置機(jī)制，即在虛擬網(wǎng)絡(luò)映射前就對(duì)其拓?fù)溥M(jìn)行變換從而提高虛擬網(wǎng)絡(luò)接受公平性及資源利用率.

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

Fig. 2 Virtual network pre-configuration (merging threshold is 6)圖2 虛擬拓?fù)漕A(yù)配置示意圖(該合并閾值為6)

虛擬網(wǎng)絡(luò)映射的目標(biāo)是使用最少的物理網(wǎng)絡(luò)資源來支持盡可能多的虛擬網(wǎng)絡(luò)，即底層網(wǎng)絡(luò)所有者的成本最小化.對(duì)于主機(jī)資源如CPU、內(nèi)存、硬盤等資源來說需求和成本永遠(yuǎn)相等，在構(gòu)建優(yōu)化模型時(shí)這部分的成本可以不予以考慮，僅需考慮資源是否能滿足約束條件；由于采用了可重用技術(shù)，可以用內(nèi)存交換替代網(wǎng)絡(luò)交換以節(jié)省物理帶寬資源，不同方案會(huì)存在網(wǎng)絡(luò)資源成本差異.因此對(duì)于每個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求，其映射優(yōu)化問題可以被描述為

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

?ew∈EV,?(i,j)∈pi j,ew→pi j,

(1)

?ew∈EV,ew→pi j,?i,j∈NS,

(2)

式(1)中第1個(gè)約束條件是主機(jī)資源約束需滿足的條件，即目標(biāo)物理節(jié)點(diǎn)的空閑資源要大于待映射虛擬節(jié)點(diǎn)請(qǐng)求的資源；第2個(gè)約束條件是物理帶寬約束，即虛擬邊映射到的每條物理鏈路的空閑帶寬必須大于虛擬鏈路所請(qǐng)求的帶寬.

3 虛擬拓?fù)漕A(yù)配置機(jī)制

現(xiàn)有的虛擬網(wǎng)絡(luò)映射方案沒有考慮虛擬網(wǎng)絡(luò)請(qǐng)求排隊(duì)的公平性問題.為了同時(shí)映射更多的虛擬網(wǎng)絡(luò)，算法需要在等待隊(duì)列中搜索盡可能多的虛擬網(wǎng)絡(luò)請(qǐng)求.而用戶對(duì)資源需求的不同會(huì)導(dǎo)致其請(qǐng)求的虛擬網(wǎng)絡(luò)在規(guī)模上存在差異，這將導(dǎo)致較小的虛擬網(wǎng)絡(luò)更容易被映射.虛擬拓?fù)洳町愡^大也會(huì)帶來底層物理資源“碎片”而降低資源利用率.現(xiàn)有的重配置方案為了獲得更多空閑物理資源，在大虛擬網(wǎng)絡(luò)無法映射時(shí)對(duì)已運(yùn)行的虛擬網(wǎng)絡(luò)進(jìn)行遷移，這部分開銷完全可以通過對(duì)待映射虛擬網(wǎng)絡(luò)拓?fù)溥M(jìn)行預(yù)配置來減輕或避免.

近幾年出現(xiàn)的虛擬機(jī)間內(nèi)存交換通道代替網(wǎng)絡(luò)鏈路的可重用技術(shù)，為虛擬網(wǎng)絡(luò)拓?fù)溥M(jìn)行節(jié)點(diǎn)合并提供了技術(shù)原理上的支持.預(yù)配置的主要目的是對(duì)虛擬網(wǎng)絡(luò)拓?fù)溥M(jìn)行修剪，以使得隊(duì)列中的虛擬網(wǎng)絡(luò)在節(jié)點(diǎn)數(shù)量上的差別盡可能縮小.預(yù)配置的手段是利用物理節(jié)點(diǎn)可重用的思想，將虛擬節(jié)點(diǎn)數(shù)過多的拓?fù)溥M(jìn)行節(jié)點(diǎn)合并，達(dá)到縮小拓?fù)湟?guī)模差異的目的.變換后的虛擬拓?fù)渑c原拓?fù)涞葍r(jià)，但節(jié)點(diǎn)數(shù)更少，從而能夠避免公平性問題，也可以減輕物理資源“碎片”的產(chǎn)生并提高利用率.

預(yù)配置的實(shí)例如圖2所示，在不超過給定的合并閾值(CPU、帶寬資源需求不得大于6)的情況下盡量合并虛擬拓?fù)渲羞B通度大的節(jié)點(diǎn)，將數(shù)個(gè)小節(jié)點(diǎn)合并成一個(gè)大節(jié)點(diǎn)以降低較大虛擬網(wǎng)絡(luò)拓?fù)涞囊?guī)模，從而縮小虛擬拓?fù)湓谝?guī)模上的差異.合并后的節(jié)點(diǎn)在物理上包含多個(gè)虛擬節(jié)點(diǎn)，但從資源需求角度考慮，邏輯上變成單個(gè)節(jié)點(diǎn)，在映射步驟中將作為單個(gè)節(jié)點(diǎn)被映射.除了能夠提高接受公平性，虛擬拓?fù)漕A(yù)配置的另一個(gè)好處就是帶寬資源的節(jié)省.在圖2中，利用虛擬機(jī)間的內(nèi)存交換技術(shù)，深色節(jié)點(diǎn)的合并令原本存在的部分虛擬鏈路消失，節(jié)點(diǎn)間轉(zhuǎn)為內(nèi)存直接交換數(shù)據(jù)，這就使得它們之間的鏈路對(duì)于物理網(wǎng)絡(luò)帶寬資源的需求可以被消除.通過圖2的3次拓?fù)渥儞Q，共節(jié)省了14單位的帶寬資源.

預(yù)配置算法設(shè)計(jì)思路是：首先對(duì)等待隊(duì)列中的虛擬網(wǎng)絡(luò)請(qǐng)求進(jìn)行篩選，對(duì)于節(jié)點(diǎn)數(shù)過大(大于給定的節(jié)點(diǎn)數(shù)限制)的虛擬網(wǎng)絡(luò)進(jìn)行拓?fù)涞葍r(jià)變換，以減少隊(duì)列中虛擬網(wǎng)絡(luò)請(qǐng)求的拓?fù)洳町?拓?fù)涞淖儞Q以盡量消除虛擬鏈路為目標(biāo)，利用遞歸算法，首先定位虛擬拓?fù)渲羞B通度最大的節(jié)點(diǎn),對(duì)該節(jié)點(diǎn)的邊，根據(jù)帶寬資源降序排序；然后在不超過合并閾值的情況下對(duì)節(jié)點(diǎn)進(jìn)行合并；再進(jìn)行下一次遞歸，直至拓?fù)渲兴泄?jié)點(diǎn)無法再進(jìn)行合并.預(yù)配置具體算法如算法1所示：

算法1. 虛擬網(wǎng)絡(luò)拓?fù)漕A(yù)配置算法.

輸入：虛擬網(wǎng)絡(luò)拓?fù)湔?qǐng)求VNRi；

輸出：預(yù)配置后的拓?fù)銻CVNRi.

① 計(jì)算VNRi中的節(jié)點(diǎn)數(shù)n；

② Ifn>nodes_thresholdthen

③ 找到具有最大連通度的節(jié)點(diǎn)vn′；

④ 對(duì)于vn′的虛擬邊，按照帶寬資源請(qǐng)求降序排序，將另外的端點(diǎn)加入待合并節(jié)點(diǎn)隊(duì)列sorted_nodes；

⑤ 依次合并sorted_nodes中節(jié)點(diǎn)，合并后的節(jié)點(diǎn)CPU資源不得超過C_threshold；由于節(jié)點(diǎn)合并而產(chǎn)生的虛擬鏈路帶寬資源不得超過B_threshold；

⑥ 如果新拓?fù)淙阅鼙缓喜? 跳轉(zhuǎn)至步驟③；

⑦ End If

⑧ ReturnRCVNRi.

在算法1中，nodes_threshold是拓?fù)湟?guī)模閾值，即節(jié)點(diǎn)數(shù)大于該值的虛擬拓?fù)湫枰活A(yù)配置；C_threshold和B_threshold分別是CPU合并閾值和帶寬合并閾值，即在預(yù)配置環(huán)節(jié)限定合并后的節(jié)點(diǎn)CPU和鏈路帶寬資源額度的上限.需要注意的是，閾值對(duì)于算法效率存在影響，閾值越小虛擬拓?fù)涞暮喜⒊潭仍叫?；閾值越大虛擬拓?fù)浜喜⒊潭仍礁?，但是合并后的虛擬網(wǎng)絡(luò)各個(gè)節(jié)點(diǎn)的資源需求更高，這可能導(dǎo)致后續(xù)映射算法在搜索可行解上存在困難.

4 基于DPSO的虛擬網(wǎng)絡(luò)映射算法

離散粒子群(discrete particle swarm optimization, DPSO)算法是基于群體智能的啟發(fā)式全局優(yōu)化技術(shù)，群體中的每一個(gè)粒子代表待解決問題的一個(gè)候選解，算法通過粒子間信息素的交互發(fā)現(xiàn)復(fù)雜搜索空間中的最優(yōu)區(qū)域，其具有收斂速度快、算法簡單、搜索效率高等特點(diǎn)[19].對(duì)于式(1)，本文采用離散粒子群算法對(duì)其進(jìn)行求解.本節(jié)首先描述映射優(yōu)化問題的離散粒子群求解算法，然后給出針對(duì)強(qiáng)化節(jié)點(diǎn)可重用的群體位置分配算法以形成整體算法.

4.1 虛擬網(wǎng)絡(luò)映射問題的離散粒子群求解算法

(3)

由于離散粒子群的特性，其位置和速度更新公式中的符號(hào)需要重新定義以切合實(shí)際問題的特點(diǎn)，為此還需給出下列運(yùn)算符的定義：

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

定義2. 位置的和φ1X′+φ2X″.結(jié)果是1個(gè)速度向量，其中φ1,φ2為權(quán)重.φ1X′+φ2X″的運(yùn)算定義為：如果X′和X″在相同維度上的值相同，則新速度在相應(yīng)維度上的值保持不變，否則，以φ1的概率保持X′，以φ2的概率保持X″.

定義3. 位置和速度的和Xk⊕Vk.結(jié)果是1個(gè)新的位置向量，即當(dāng)前映射方案Xk按照Vk調(diào)整虛擬節(jié)點(diǎn)的映射位置.對(duì)于Xk，與其對(duì)應(yīng)的Vk在相應(yīng)維度上的數(shù)值為1，意味著當(dāng)前虛擬節(jié)點(diǎn)的映射位置需要保留；為0時(shí)需要為當(dāng)前維度所代表的虛擬節(jié)點(diǎn)重新隨機(jī)選擇1個(gè)滿足主機(jī)資源約束條件的物理節(jié)點(diǎn).

根據(jù)上述定義及式(3)可以逐輪計(jì)算粒子的位置.在此還要給出粒子的適應(yīng)度計(jì)算方法以評(píng)判解是否為最優(yōu)：如果當(dāng)前粒子的位置代表的解不滿足式(1)中的約束條件，則其適應(yīng)度fitness將被置為+∞；如果當(dāng)前位置是1個(gè)可行解，那么開始進(jìn)行虛擬邊的映射.本文算法在該階段采用FloydWarshall最短路徑算法，同樣如果虛擬邊映射不成功則適應(yīng)度置為+∞；如果成功則按照式(3)計(jì)算適應(yīng)度fitness值，即計(jì)算虛擬網(wǎng)絡(luò)在物理網(wǎng)絡(luò)中占用的總帶寬.虛擬網(wǎng)絡(luò)映射算法如算法2所示：

算法2. 虛擬網(wǎng)絡(luò)映射算法.

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

輸出：映射方案solution.

① 對(duì)GS中實(shí)時(shí)空閑資源的節(jié)點(diǎn)隊(duì)列和鏈路隊(duì)列，移除其中空閑資源小于GV中最小節(jié)點(diǎn)CPU和鏈路帶寬需求的物理節(jié)點(diǎn)和物理鏈路；

② 對(duì)每個(gè)粒子，調(diào)用位置初始化函數(shù)initial-position()；

③ For(inti=0;i

④ 計(jì)算每個(gè)粒子的適應(yīng)度值，計(jì)算個(gè)體最優(yōu)位置，并調(diào)用函數(shù)updatePosition()更新粒子速度和位置；

⑤ 如果該粒子處在群體最優(yōu)位置，則更新群體最優(yōu)位置gBest和最優(yōu)適應(yīng)度值gfitness；

⑥ 如果群體最優(yōu)位置連續(xù)10輪不變則算法終止；}

⑦ 如果群體最優(yōu)位置存在則返回該位置作為映射方案.

在算法2中，移除空閑資源小于最小請(qǐng)求額度的物理節(jié)點(diǎn)和鏈路是為了盡量縮小算法搜索空間.算法結(jié)束的條件是群體最優(yōu)位置gBest在10輪內(nèi)不變或者迭代輪數(shù)超過給定的最大迭代次數(shù)MaxItCount.粒子種群大小的選取是關(guān)于求解效率及解優(yōu)化程度的折中問題，較大的群規(guī)模能充分探索解空間，但需要更多的計(jì)算時(shí)間.種群大小一般取20～50，對(duì)于大部分問題，20個(gè)粒子已經(jīng)能取得足夠好的結(jié)果[20].算法2中的2個(gè)粒子位置分配函數(shù)updatePosition()和initialposition()將在4.2節(jié)進(jìn)行詳細(xì)介紹.

4.2 強(qiáng)化可重用的粒子位置分配機(jī)制

位置的初始化及更新機(jī)制對(duì)于粒子群算法的收斂速度有著重要影響.在算法2中，與位置分配相關(guān)的函數(shù)是updatePosition()和initialposition().在傳統(tǒng)算法中，位置的分配只能隨機(jī)選取物理節(jié)點(diǎn)編號(hào)，為了充分發(fā)揮可重技術(shù)能夠節(jié)省物理帶寬消耗的優(yōu)勢，應(yīng)當(dāng)把盡量多的同一虛擬網(wǎng)絡(luò)的節(jié)點(diǎn)映射到同一物理節(jié)點(diǎn)上.因此有必要在算法的位置更新及初始化過程中加入可重用特性強(qiáng)化機(jī)制.

在粒子位置分配強(qiáng)化過程中，既要保證盡量發(fā)揮可重用的特性，又不能使得虛擬節(jié)點(diǎn)過度集中于某幾個(gè)物理節(jié)點(diǎn).因?yàn)槿绻谖恢贸跏蓟瘯r(shí)就令虛擬節(jié)點(diǎn)過度集中，那么很可能每個(gè)粒子都不會(huì)獲得可行解，即不滿足式(1)的約束條件.在沒有可行解的情況下無法獲得最優(yōu)適應(yīng)度值，也就無法獲得群體最優(yōu)位置，這將會(huì)導(dǎo)致映射算法無法返回可行的映射方案.另外還要考慮在虛擬網(wǎng)絡(luò)映射問題中，每個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求的節(jié)點(diǎn)數(shù)量都不相同，在每個(gè)維度上重復(fù)分配同1個(gè)物理節(jié)點(diǎn)的次數(shù)應(yīng)當(dāng)與虛擬節(jié)點(diǎn)的數(shù)量、資源請(qǐng)求額度及當(dāng)前物理節(jié)點(diǎn)的平均資源利用率建立動(dòng)態(tài)對(duì)應(yīng)關(guān)系.既要保證粒子多樣性，又要強(qiáng)化可重用機(jī)制，為此引入動(dòng)態(tài)強(qiáng)化因子：

(4)

(5)

其中,GS′是當(dāng)前虛擬網(wǎng)絡(luò)映射的搜索空間，即算法2步驟①中獲得的子圖.對(duì)于粒子位置向量的每個(gè)維度來說，如果其維度n模k等于0，則重新隨機(jī)選擇1個(gè)物理節(jié)點(diǎn)，否則保持前一維度所選擇的物理節(jié)點(diǎn).這樣既可以強(qiáng)化可重用特性，又不至于使得搜索空間被限制，令過大的虛擬網(wǎng)絡(luò)因?yàn)槭湛s到少數(shù)物理節(jié)點(diǎn)而找不到可行解.以位置初始化算法initialposition()為例，其偽代碼如算法3所示：

算法3. 粒子位置初始化函數(shù)initialposition().

輸入：物理網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)numofsnodes、虛擬網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)numofvnodes；

輸出：粒子位置position.

① 按照式(4)求k值；

② 隨機(jī)選取1個(gè)搜索空間內(nèi)的物理節(jié)點(diǎn)，將其編號(hào)賦值給maph；

③ For (i=0;i

④ If (i%k==0) then 重新選擇物理節(jié)點(diǎn)并賦值給maph;

⑤position.put(i,maph)；}

⑥ Returnposition.

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

5 實(shí) 驗(yàn)

實(shí)驗(yàn)采用CloudSim3.0.3[21]仿真平臺(tái)，硬件平臺(tái)為IBM X3650服務(wù)器.為了仿真拓?fù)涠鄻有?，在CloudSim中用Java語言為底層物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)編寫了1個(gè)拓?fù)渖善?，以連通概率、資源需求邊界、節(jié)點(diǎn)數(shù)量范圍作為輸入?yún)?shù)生成隨機(jī)拓?fù)?式(3)中涉及到的權(quán)重設(shè)定為φ1=0.1，φ2=0.2，φ3=0.7；離散粒子群算法的終止條件是10輪沒有改變?nèi)肿顑?yōu)位置或者總迭代次數(shù)超過30輪.當(dāng)有虛擬網(wǎng)絡(luò)生存周期結(jié)束釋放資源時(shí)，算法搜索等待隊(duì)列中前20個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求并嘗試尋找映射方案.

實(shí)驗(yàn)比較了本文提出的基于預(yù)配置的算法(PrC-DPSO)與文獻(xiàn)[15]中的VNE-UEPSO映射算法的性能表現(xiàn).比較的參數(shù)包含收益成本比、物理網(wǎng)絡(luò)資源利用率及虛擬網(wǎng)絡(luò)接受公平性.收益成本比(RC)的定義如式(6)所示：

(6)

其中,Revenue(GV)表示1個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求的CPU資源和帶寬資源之和；Co(GV)表示底層物理網(wǎng)絡(luò)分配給虛擬網(wǎng)絡(luò)請(qǐng)求的CPU資源和帶寬資源之和；T表示時(shí)間.實(shí)驗(yàn)中，物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)的基本參數(shù)如表1所示：

Table1 The Basic Experimental Parameter Settings

在表1中，形如100～500的參數(shù)設(shè)定表示的是虛擬網(wǎng)絡(luò)中鏈路的帶寬資源在100～500單位之間均勻分布.在本文實(shí)驗(yàn)中，每個(gè)實(shí)驗(yàn)測試1 000個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求的映射，每個(gè)實(shí)驗(yàn)運(yùn)行10輪映射，對(duì)最終結(jié)果求平均值，以保證實(shí)驗(yàn)結(jié)果的普遍性.

實(shí)驗(yàn)1. 比較了不同虛擬鏈路參數(shù)設(shè)置下的物理網(wǎng)絡(luò)收益成本比和資源利用率隨時(shí)間變化趨勢.其中時(shí)間的單位為CloudSim中的單位時(shí)間.從圖3可以看出，本文提出的算法可以顯著提高物理網(wǎng)絡(luò)的收益成本比.單就節(jié)點(diǎn)CPU資源來說其收益成本比恒為1，但從鏈路資源分配的角度考慮，由于可重用機(jī)制的應(yīng)用，在虛擬拓?fù)漕A(yù)配置及映射過程中都可以將不同節(jié)點(diǎn)映射到同一物理節(jié)點(diǎn)之上，從而抵消部分虛擬邊，因此能夠節(jié)省物理網(wǎng)絡(luò)資源的消耗.在2種虛擬網(wǎng)絡(luò)資源需求參數(shù)下，本文提出的PrC-DPSO算法均能夠獲得大于1的收益成本比.另外從圖3中可以看出，對(duì)于本文提出的算法，虛擬網(wǎng)絡(luò)對(duì)于帶寬的需求參數(shù)越高，收益成本比提高越大.1 500時(shí)間單位時(shí)，在100～200和200～100兩種帶寬需求參數(shù)下，算法的收益成本比分別提高約29%和57%.說明本文提出的預(yù)配置算法和可重用強(qiáng)化機(jī)制能夠起到節(jié)省物理網(wǎng)絡(luò)帶寬資源的作用.

Fig. 3 RC of substrate network under different virtual request parameters圖3 不同虛擬鏈路參數(shù)下物理網(wǎng)絡(luò)收益成本比

Fig. 4 Physical node utilization under different virtual link parameter圖4 不同虛擬鏈路參數(shù)下物理網(wǎng)絡(luò)節(jié)點(diǎn)資源利用率

實(shí)驗(yàn)2. 不同虛擬鏈路需求參數(shù)設(shè)定下物理網(wǎng)絡(luò)資源利用率的比較.從圖4可以看出本文提出的算法能夠提高物理節(jié)點(diǎn)資源利用率，這也可以說明結(jié)合預(yù)配置機(jī)制后，可以減少底層物理網(wǎng)絡(luò)的資源“碎片”問題，使得底層物理網(wǎng)絡(luò)可以同時(shí)接受更多的虛擬網(wǎng)絡(luò).另外，2個(gè)算法在虛擬鏈路帶寬需求較低時(shí)(100～500)可以獲得更好的資源利用率，主要原因是對(duì)于虛擬網(wǎng)絡(luò)映射問題來說，虛擬鏈路映射要比節(jié)點(diǎn)映射更難以找到最優(yōu)解，但本文算法由于加入了預(yù)配置機(jī)制，通過降低虛擬拓?fù)涞牟町悳p少了鏈路映射的難度，因此獲得了更好的節(jié)點(diǎn)利用率.

Fig. 5 Average nodes number of accepted virtual networks changing over time圖5 虛擬網(wǎng)絡(luò)平均節(jié)點(diǎn)數(shù)隨時(shí)間變化趨勢

實(shí)驗(yàn)3. 虛擬網(wǎng)絡(luò)排隊(duì)公平性方面的比較分析.為了突出預(yù)配置機(jī)制對(duì)公平性的提高，實(shí)驗(yàn)中虛擬網(wǎng)絡(luò)鏈路資源需求設(shè)定為250～2 500間均勻分布.實(shí)驗(yàn)運(yùn)行1 000個(gè)虛擬網(wǎng)絡(luò)的映射仿真，統(tǒng)計(jì)了每輪被接受的虛擬網(wǎng)絡(luò)的平均節(jié)點(diǎn)數(shù)隨時(shí)間變化的趨勢.結(jié)果如圖5所示，由于本實(shí)驗(yàn)設(shè)定的虛擬網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù)在2～10之間隨機(jī)均勻分布，因此2個(gè)算法的平均節(jié)點(diǎn)數(shù)圍繞6上下波動(dòng).VNE-UEPSO算法沒有考慮公平性問題，在映射過程中，較大的虛擬網(wǎng)絡(luò)很難被接受，只有在物理網(wǎng)絡(luò)空閑資源較大時(shí)才能夠被映射，所以平均節(jié)點(diǎn)數(shù)隨時(shí)間呈上升趨勢，說明較大虛擬網(wǎng)絡(luò)需要更多排隊(duì)時(shí)間.其后期平均節(jié)點(diǎn)數(shù)顯著上升，最后4輪接受的均是節(jié)點(diǎn)數(shù)為10的最大虛擬網(wǎng)絡(luò)，而此時(shí)物理網(wǎng)絡(luò)的利用率較低才有足夠空閑的資源來運(yùn)行較大虛擬網(wǎng)絡(luò).相對(duì)VNE-UEPSO算法來說，本文提出的PrC-DPSO算法因?yàn)榧尤肓祟A(yù)配置機(jī)制，可以減少虛擬網(wǎng)絡(luò)拓?fù)洳町愋裕@使得在映射方案搜索時(shí)不存在過于復(fù)雜的拓?fù)?，因此本文所提出算法的平均?jié)點(diǎn)曲線略平滑，且不會(huì)在后期顯著上升.另外，從圖5中還可以看出，得益于拓?fù)漕A(yù)配置機(jī)制的應(yīng)用，在同樣條件下本文提出的算法完成同樣數(shù)量的虛擬網(wǎng)絡(luò)請(qǐng)求所用時(shí)間更短(節(jié)省約11%的總運(yùn)行時(shí)間)，因此本文提出的虛擬網(wǎng)絡(luò)映射算法在提供接受公平性的同時(shí)也節(jié)省了物理網(wǎng)絡(luò)的總運(yùn)行時(shí)間.

6 結(jié)束語

本文從提高虛擬網(wǎng)絡(luò)接受公平性和物理網(wǎng)絡(luò)收益角度出發(fā)，提出了基于虛擬拓?fù)漕A(yù)配置及可重用技術(shù)的虛擬網(wǎng)絡(luò)映射算法.在虛擬網(wǎng)路映射前加入拓?fù)漕A(yù)配置機(jī)制以減少虛擬拓?fù)涞牟町愋?，避免了較大虛擬網(wǎng)絡(luò)難以求解映射方案的問題，從而提高了接受公平性.在預(yù)配置和映射階段均采用了可重用技術(shù)，提高了物理網(wǎng)絡(luò)的資源利用率.本文所提出的算法在支持相同數(shù)量及結(jié)構(gòu)的虛擬網(wǎng)絡(luò)時(shí)產(chǎn)生的開銷更小，并且能夠提供更好的公平性支持；另外，得益于預(yù)配置及粒子初始位置的強(qiáng)化機(jī)制，本文所提出的算法也有助于提高物理網(wǎng)絡(luò)資源利用率.

[1]Chowdhury N M M K, Boutaba R. Network virtualization: State of the art and research challenges[J]. IEEE Communications Magazine, 2009, 47(7): 20-26

[2]Shi Xuelin, Xu Ke. Utility maximization model of virtual machine scheduling in cloud environment[J]. Chinese Journal of Computers, 2013, 36(2): 252-262 (in Chinese)(師雪霖, 徐恪. 云虛擬機(jī)資源分配的效用最大化模型[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(2): 252-262)

[3]Deng Gang, Gong Zhenghu, Wang Hong. Characteristics research on modern data center network[J]. Journal of Computer Research and Development, 2014, 51(2): 395-407 (in Chinese)(鄧罡, 龔正虎, 王宏. 現(xiàn)代數(shù)據(jù)中心網(wǎng)絡(luò)特征研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(2): 395-407)

[4]Vidya K B, Ajit S M. Cloud resource provisioning for Amazon EC2[C]Proc of the 4th IEEE Conf on Computing Communications and Networking Technologies. Piscataway, NJ: IEEE, 2013: 1-7

[5]Cheng Xiang, Zhang Zhongbao, Su Sen, et al. Survey of virtual network embedding problem[J]. Journal on Communications, 2011, 32(10): 143-141 (in Chinese)(程祥, 張忠寶, 蘇森, 等. 虛擬網(wǎng)絡(luò)映射問題研究綜述[J]. 通信學(xué)報(bào), 2011, 32(10): 143-141)

[6]Li Xiaoling, Wang Huaimin, Ding Bo, et al. Research and development of virtual network mapping problem[J]. Journal of Software, 2012, 23(11): 3009-3028 (in Chinese)(李小玲, 王懷民, 丁博, 等. 虛擬網(wǎng)絡(luò)映射問題研究及其進(jìn)展[J]. 軟件學(xué)報(bào), 2012, 23(11): 3009-3028)

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

[8]Lu Jing, Turner J. Efficient mapping of virtual networks onto a shared substrate, WUCSE-2006-35[R]. Washington: Department of Computer Science and Engineering, Washington University, 2006

[9]Fan J, Ammar M. Dynamic topology configuration in service overlay networks: A study of reconfiguration policies[C]Proc of the 25th IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2006: 1-12

[10]Zhu Y, Ammar M. Algorithms for assigning substrate network resources to virtual network components[C]Proc of the 25th IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2006: 21-32

[11]Ines H, Wajdi L, Djamal Z. A distributed virtual network mapping algorithm[C]Proc of the IEEE Int Conf on Communications. Piscataway, NJ: IEEE, 2008: 5634-5640

[12]Jens L, Holger K. A virtual network mapping algorithm based on subgraph isomorphism detection[C]Proc of the ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures. New York: ACM, 2009: 81-88

[13]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

[14]Yong Z, Mostafa A. Algorithms for assigning substrate network resources to virtual network components[C]Proc of the 25th IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2006: 1-12

[15]Zhang Zhongbao, Cheng Xiang, Su Sen, et al. A unified enhanced particle swarm optimization-based virtual network embedding algorithm[J]. Internet Journal of Communication Systems, 2013, 26(8): 1054-1073

[16]Zhang Shunli, Qiu Xuesong,Pan Yalian, et al. Forecast-based resource reconfiguration algorithm for network virtualization[J]. Journal on Communications, 2011, 32(7): 57-70 (in Chinese)(張順利, 邱雪松, 潘亞蓮, 等. 網(wǎng)絡(luò)虛擬化環(huán)境下基于預(yù)測的資源重配置算法[J]. 通信學(xué)報(bào), 2011, 32(7): 57-70)

[17]Bassem W, Nancy S, Ahmed K. Substrate network house cleaning via live virtual vetwork migration[C]Proc of 2013 IEEE Int Conf on Communications. Piscataway, NJ: IEEE, 2013: 2256-2261

[18]Samantha L, Mostafa A, Ellen Z. Design and analysis of schedules for virtual network migration[C]Proc of the International Federation for Information Processing Networking Conf. Piscataway, NJ: IEEE, 2013: 1-9

[19]Ma Xuan, Liu Qing. Particle swarm optimization for multiple multicast routing problem[J]. Journal of Computer Research and Development, 2013, 50(2): 260-268 (in Chinese)(馬炫, 劉慶. 多組播路由問題的粒子群優(yōu)化算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(2): 260-268)

[20]Wang Weibo, Lin Chuan, Zheng Yongkang. The experiment and analysis of parameters in particle swarm optimization algorithm[J]. Journal of Xihua University: Natural Science Edition, 2008, 27(1): 76-80

[21]Rodrigo N C, Rajiv R, Anton B, et al. CloudSim: A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software: Practice and Experience, 2011, 41(1): 23-50

Wang Cong, born in 1981. PhD and lecturer in Northeastern University at Qinhuangdao. Member of CCF. His main research interests include virtual network embedding, resource allocation in data center.

Yuan Ying, born in 1981. PhD and lecturer in Northeastern University at Qinhuangdao. Member of CCF. Her main research interests include virtual network embedding, virtual resource allocation in cloud computing (yuanying1121@163.com).

Peng Sancheng, born in 1974. PhD and professor in Guangdong University of Foreign Studies. Senior member of CCF. His main research interests include network and information security, trusted computing, and mobile computing (psc346@aliyun.com).

Wang Xingwei, born in 1968. PhD, professor and PhD supervisor in Northeastern University. Senior member of CCF. His main research interests include future Internet, cloud computing, network security and information security.

Wang Cuirong, born in 1963. PhD and professor in Northeastern University at Qinhuangdao. Member of CCF. Her main research interests include routing protocol, network security and sensor networks (wcr@mail.neuq.edu.cn).

Wan Cong, born in 1983. PhD and lecturer in Northeastern University at Qinhuangdao. Member of CCF. His main research interests include cloud computing, parallel algorithm design (wancong@neuq.edu.cn).

Fair Virtual Network Embedding Algorithm with Topology Pre-Configuration

Wang Cong1, Yuan Ying1, Peng Sancheng2, Wang Xingwei3, Wang Cuirong1, and Wan Cong1

1(CollegeofComputerandCommunicationEngineering,NortheasternUniversityatQinhuangdao,Qinhuangdao,Hebei066004)2(CiscoSchoolofInformatics,GuangdongUniversityofForeignStudies,Guangzhou510420)3(SoftwareCollege,NortheasternUniversity,Shenyang110819)

Virtual network embedding (VNE) is critical fundamental technology to archive multi resource tenancy in cloud environment. It aims to embed virtual networks into appropriate underlying physical substrate network under the premise of satisfying the resource demand of virtual networks. Most research achievements of the existing VNE algorithms aim at maximizing the physical resource utilization, but consider less about the fairness problem in virtual network request reception. This paper puts forward a pre-configured virtual network mapping algorithm to improve the mapping of fairness, in which the mapping process are divided into two steps: topology pre-configuration phase and embedding phase. In pre-configuration phase, larger virtual network topologies are transformed to equivalent but smaller ones with less number of nodes and links. Such mechanism can reduce differences between virtual network requests so as to improve reception fairness. In mapping phase, we establish a formal VNE model, and use the discrete particle swarm optimization algorithm to solve the model. In order to improve the physical network resource utilization, a particle position enhancement mechanism is introduced leveraging node repeatable technology to save bandwidth resource. Simulation results show that the proposed algorithm is superior to the existing similar algorithms in physical network resource utilization, revenuecost ratio and reception fairness.

network virtualization; virtual network embedding; node reusable; virtual topology pre-configuration; discrete particle swarm optimization algorithm

2015-09-01；

2016-06-02

國家杰出青年科學(xué)基金項(xiàng)目(61225012，71325002)；國家自然科學(xué)基金項(xiàng)目(61300195，61379041)；河北省自然科學(xué)基金項(xiàng)目(F2014501078，F(xiàn)2016501079) This work was supported by the National Natural Science Fund for Distinguished Young Scholars of China (61225012, 71325002)，the National Natural Science Foundation of China (61300195, 61379041), and the Natural Science Foundation of Hebei Province of China (F2014501078, F2016501079).

王興偉(wangxw@mail.neu.edu.cn)

TP393.02