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

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

基于拓撲預配置的公平虛擬網(wǎng)絡映射算法

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

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

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

網(wǎng)絡虛擬化；虛擬網(wǎng)絡映射；節(jié)點可重用；虛擬拓撲預配置；離散粒子群優(yōu)化算法

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

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

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

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

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

現(xiàn)有虛擬網(wǎng)絡映射算法研究成果大都以最大化資源利用率為目標[5]，當有空閑物理資源時就對在線排隊的虛擬網(wǎng)絡請求進行篩選，盡可能接受更多的虛擬網(wǎng)絡.在這樣的情況下，虛擬網(wǎng)絡拓撲的差異性將導致規(guī)模較大的虛擬網(wǎng)絡請求很難被接受.為此，本文提出了拓撲預配置機制，對虛擬網(wǎng)絡拓撲進行等價變換以減少虛擬拓撲間的差異性，并且結(jié)合可重用技術(shù)設計了一種以最大化物理網(wǎng)絡收益為目標并兼顧排隊公平性的虛擬網(wǎng)絡映射算法.

1 相關(guān)工作

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

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

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

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

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

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

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

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

Fig. 2 Virtual network pre-configuration (merging threshold is 6)圖2 虛擬拓撲預配置示意圖(該合并閾值為6)

虛擬網(wǎng)絡映射的目標是使用最少的物理網(wǎng)絡資源來支持盡可能多的虛擬網(wǎng)絡，即底層網(wǎng)絡所有者的成本最小化.對于主機資源如CPU、內(nèi)存、硬盤等資源來說需求和成本永遠相等，在構(gòu)建優(yōu)化模型時這部分的成本可以不予以考慮，僅需考慮資源是否能滿足約束條件；由于采用了可重用技術(shù)，可以用內(nèi)存交換替代網(wǎng)絡交換以節(jié)省物理帶寬資源，不同方案會存在網(wǎng)絡資源成本差異.因此對于每個虛擬網(wǎ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個約束條件是主機資源約束需滿足的條件，即目標物理節(jié)點的空閑資源要大于待映射虛擬節(jié)點請求的資源；第2個約束條件是物理帶寬約束，即虛擬邊映射到的每條物理鏈路的空閑帶寬必須大于虛擬鏈路所請求的帶寬.

3 虛擬拓撲預配置機制

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

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

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

預配置算法設計思路是：首先對等待隊列中的虛擬網(wǎng)絡請求進行篩選，對于節(jié)點數(shù)過大(大于給定的節(jié)點數(shù)限制)的虛擬網(wǎng)絡進行拓撲等價變換，以減少隊列中虛擬網(wǎng)絡請求的拓撲差異.拓撲的變換以盡量消除虛擬鏈路為目標，利用遞歸算法，首先定位虛擬拓撲中連通度最大的節(jié)點,對該節(jié)點的邊，根據(jù)帶寬資源降序排序；然后在不超過合并閾值的情況下對節(jié)點進行合并；再進行下一次遞歸，直至拓撲中所有節(jié)點無法再進行合并.預配置具體算法如算法1所示：

算法1. 虛擬網(wǎng)絡拓撲預配置算法.

輸入：虛擬網(wǎng)絡拓撲請求VNRi；

輸出：預配置后的拓撲RCVNRi.

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

② Ifn>nodes_thresholdthen

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

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

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

⑥ 如果新拓撲仍能被合并, 跳轉(zhuǎn)至步驟③；

⑦ End If

⑧ ReturnRCVNRi.

在算法1中，nodes_threshold是拓撲規(guī)模閾值，即節(jié)點數(shù)大于該值的虛擬拓撲需要被預配置；C_threshold和B_threshold分別是CPU合并閾值和帶寬合并閾值，即在預配置環(huán)節(jié)限定合并后的節(jié)點CPU和鏈路帶寬資源額度的上限.需要注意的是，閾值對于算法效率存在影響，閾值越小虛擬拓撲的合并程度越小；閾值越大虛擬拓撲合并程度越高，但是合并后的虛擬網(wǎng)絡各個節(jié)點的資源需求更高，這可能導致后續(xù)映射算法在搜索可行解上存在困難.

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

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

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

(3)

由于離散粒子群的特性，其位置和速度更新公式中的符號需要重新定義以切合實際問題的特點，為此還需給出下列運算符的定義：

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

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

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

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

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

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

輸出：映射方案solution.

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

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

③ For(inti=0;i

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

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

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

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

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

4.2 強化可重用的粒子位置分配機制

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

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

(4)

(5)

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

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

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

輸出：粒子位置position.

① 按照式(4)求k值；

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

③ For (i=0;i

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

⑤position.put(i,maph)；}

⑥ Returnposition.

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

5 實 驗

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

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

(6)

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

Table1 The Basic Experimental Parameter Settings

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

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

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

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

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

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

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

6 結(jié)束語

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

[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]. 計算機學報, 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)絡特征研究[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)絡映射問題研究綜述[J]. 通信學報, 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)絡映射問題研究及其進展[J]. 軟件學報, 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)絡虛擬化環(huán)境下基于預測的資源重配置算法[J]. 通信學報, 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]. 計算機研究與發(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

國家杰出青年科學基金項目(61225012，71325002)；國家自然科學基金項目(61300195，61379041)；河北省自然科學基金項目(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