基于拓撲預配置的公平虛擬網絡映射算法

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

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

基于拓撲預配置的公平虛擬網絡映射算法

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

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

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

網絡虛擬化；虛擬網絡映射；節點可重用；虛擬拓撲預配置；離散粒子群優化算法

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

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

Fig. 1 Diagram of virtual network embedding圖1 虛擬網絡映射示意圖

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

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

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

1 相關工作

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

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

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

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

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

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

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

2 虛擬網絡映射問題描述

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

虛擬網絡映射的目標是使用最少的物理網絡資源來支持盡可能多的虛擬網絡，即底層網絡所有者的成本最小化.對于主機資源如CPU、內存、硬盤等資源來說需求和成本永遠相等，在構建優化模型時這部分的成本可以不予以考慮，僅需考慮資源是否能滿足約束條件；由于采用了可重用技術，可以用內存交換替代網絡交換以節省物理帶寬資源，不同方案會存在網絡資源成本差異.因此對于每個虛擬網絡請求，其映射優化問題可以被描述為

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個約束條件是主機資源約束需滿足的條件，即目標物理節點的空閑資源要大于待映射虛擬節點請求的資源；第2個約束條件是物理帶寬約束，即虛擬邊映射到的每條物理鏈路的空閑帶寬必須大于虛擬鏈路所請求的帶寬.

3 虛擬拓撲預配置機制

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

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

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

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

算法1. 虛擬網絡拓撲預配置算法.

輸入：虛擬網絡拓撲請求VNRi；

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

① 計算VNRi中的節點數n；

② Ifn>nodes_thresholdthen

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

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

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

⑥ 如果新拓撲仍能被合并, 跳轉至步驟③；

⑦ End If

⑧ ReturnRCVNRi.

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

4 基于DPSO的虛擬網絡映射算法

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

4.1 虛擬網絡映射問題的離散粒子群求解算法

(3)

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

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

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

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

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

算法2. 虛擬網絡映射算法.

輸入：虛擬網絡GV；物理網絡GS；

輸出：映射方案solution.

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

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

③ For(inti=0;i

④ 計算每個粒子的適應度值，計算個體最優位置，并調用函數updatePosition()更新粒子速度和位置；

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

⑥ 如果群體最優位置連續10輪不變則算法終止；}

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

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

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

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

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

(4)

(5)

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

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

輸入：物理網絡節點數numofsnodes、虛擬網絡節點數numofvnodes；

輸出：粒子位置position.

① 按照式(4)求k值；

② 隨機選取1個搜索空間內的物理節點，將其編號賦值給maph；

③ For (i=0;i

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

⑤position.put(i,maph)；}

⑥ Returnposition.

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

5 實 驗

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

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

(6)

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

Table1 The Basic Experimental Parameter Settings

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

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

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

Fig. 4 Physical node utilization under different virtual link parameter圖4 不同虛擬鏈路參數下物理網絡節點資源利用率

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

Fig. 5 Average nodes number of accepted virtual networks changing over time圖5 虛擬網絡平均節點數隨時間變化趨勢

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

6 結束語

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

[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)(鄧罡, 龔正虎, 王宏. 現代數據中心網絡特征研究[J]. 計算機研究與發展, 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)(程祥, 張忠寶, 蘇森, 等. 虛擬網絡映射問題研究綜述[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)(李小玲, 王懷民, 丁博, 等. 虛擬網絡映射問題研究及其進展[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)(張順利, 邱雪松, 潘亞蓮, 等. 網絡虛擬化環境下基于預測的資源重配置算法[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)(馬炫, 劉慶. 多組播路由問題的粒子群優化算法[J]. 計算機研究與發展, 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，F2016501079) 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