余建軍，吳春明

（1.衢州職業(yè)技術(shù)學院，浙江衢州324000；2.浙江大學計算機科學與技術(shù)學院，浙江杭州310027）

研究與開發(fā)

基于成本約束的虛擬網(wǎng)映射策略及競爭分析

余建軍1，2，吳春明2

（1.衢州職業(yè)技術(shù)學院，浙江衢州324000；2.浙江大學計算機科學與技術(shù)學院，浙江杭州310027）

為實現(xiàn)物理網(wǎng)提供商長期收益的最大化，單個虛擬網(wǎng)的映射成本和接入控制策略最為關(guān)鍵，但在之前的研究中，資源價格定義不能反映資源供求關(guān)系，不利于物理網(wǎng)資源的有效利用，且接入控制策略沒有綜合考慮成本和收益的關(guān)系。為此，首先基于凸二次規(guī)劃松弛方法，設(shè)計以映射成本最小化為目標的單虛擬網(wǎng)映射方案求解的近似算法；然后，針對動態(tài)到達的單虛擬網(wǎng)構(gòu)建請求，基于影子價格的物理網(wǎng)資源定價策略，用上述近似算法求出映射方案，并基于映射成本約束的虛擬網(wǎng)接入控制策略，完成競爭算法設(shè)計，并給出算法的競爭比分析。實驗表明，所提方法能使物理網(wǎng)資源得到有效利用，進而提高虛擬網(wǎng)構(gòu)建請求的接受率和物理網(wǎng)提供商的長期收益。

虛擬網(wǎng)映射；映射成本；凸二次規(guī)劃松弛；接入控制；競爭算法

1 引言

網(wǎng)絡(luò)虛擬化作為解決互聯(lián)網(wǎng)僵化問題的新技術(shù)，越來越引起學術(shù)界和產(chǎn)業(yè)界的關(guān)注，虛擬網(wǎng)映射問題［1］是虛擬化研究的核心內(nèi)容，其任務(wù)是在物理網(wǎng)上為虛擬網(wǎng)節(jié)點和虛擬網(wǎng)鏈路分配滿足需求的節(jié)點和路徑，從而實現(xiàn)在物理網(wǎng)上多個相互隔離的虛擬網(wǎng)共存的目的，其求解目標主要是實現(xiàn)物理網(wǎng)提供商長期收益的最大化。

虛擬網(wǎng)映射問題是NP難問題［2］，面臨在線請求、拓撲多樣和接入控制等挑戰(zhàn)，根據(jù)成本和收益等因素權(quán)衡是否接受虛擬網(wǎng)請求是接入控制的任務(wù)。當前提出的集中算法，要么假定虛擬節(jié)點映射已知［3］，將問題簡化為虛擬鏈路映射問題；要么將虛擬網(wǎng)映射分為節(jié)點映射和鏈路映射兩個階段［2，4-8］；要么將虛擬網(wǎng)作為一個整體，同時完成虛擬節(jié)點和虛擬鏈路映射［9-12］。

單虛擬網(wǎng)構(gòu)建的收益是確定的，為提高物理網(wǎng)提供商長期收益，單虛擬網(wǎng)映射的優(yōu)化目標是成本最小。目前研究中，成本的定義主要采用物理資源絕對消耗量［2，7］，物理鏈路映射基于最短路徑優(yōu)先原則，該方法易導致物理網(wǎng)關(guān)鍵節(jié)點和路徑上的負載過重，從而降低后續(xù)虛擬網(wǎng)構(gòu)建的成功概率，不利于長期收益提高；參考文獻［6］將資源絕對消耗量最小化和負載均衡兩個目標相結(jié)合，但也只能在一定程度上緩解物理網(wǎng)關(guān)鍵路徑和節(jié)點上的負載過重問題；上述方法僅考慮映射使用的資源要素，而沒有考慮資源的價格要素，參考文獻［5］和參考文獻［10］將映射成本定義為各物理資源需求量與物理資源價格乘積的累加和，但參考文獻［5］根據(jù)資源的即時負載定義其價格，沒能體現(xiàn)資源的供求關(guān)系，參考文獻［10］假設(shè)資源價格已知，都不是很合理。

對單虛擬網(wǎng)構(gòu)建提供接入控制是提高物理網(wǎng)提供商長期收益的有效手段，尤其在虛擬網(wǎng)數(shù)量很大的情況下。但目前提出的接入控制策略［3，5，7］存在以下問題：參考文獻［3］假設(shè)虛擬節(jié)點映射已知；參考文獻［5］通過過濾掉負載相對收益過重的物理鏈路和物理節(jié)點，間接實現(xiàn)接入控制；參考文獻［7］忽略虛擬網(wǎng)構(gòu)建的收益因素。

為提高長期收益或降低能源消耗，允許把同一虛擬網(wǎng)的虛擬節(jié)點映射到物理網(wǎng)的同一個物理節(jié)點上（即物理節(jié)點可重復映射）［4，8，11，12］，如在云計算數(shù)據(jù)中心的虛擬網(wǎng)構(gòu)建［8］中，可通過虛擬機整合［13］（即物理節(jié)點可重復映射）實現(xiàn)能耗的降低。

根據(jù)經(jīng)濟學原理，成本是使用資源的數(shù)量和資源價格乘積的累加和。根據(jù)經(jīng)濟學的成本理論［14］，虛擬網(wǎng)映射成本是機會成本，而影子價格與機會成本在本質(zhì)上是一致的，是一對以資源的有限性作為出發(fā)點，以資源的有效利用與合理配置為目的的成本和價格概念。

為提高物理網(wǎng)提供商的長期收益，基于以下策略構(gòu)建虛擬網(wǎng)映射方法：基于影子價格的定價策略動態(tài)定義物理網(wǎng)資源價格，物理網(wǎng)映射成本定義為各物理資源需求量與物理資源價格乘積的累加和；對動態(tài)到達的虛擬網(wǎng)構(gòu)建請求，以映射成本最小化為目標；基于成本約束，設(shè)計單個虛擬網(wǎng)映射的接入控制策略，拒絕掉對于收益來說成本過高的虛擬網(wǎng)構(gòu)建請求；允許物理節(jié)點可重復映射。

針對物理網(wǎng)不支持路徑分割［2］而且虛擬網(wǎng)數(shù)量很大的場景，本文基于上述策略設(shè)計在線虛擬網(wǎng)映射問題的競爭算法［3，5］。具體的，首先建立以最小成本為目標的單虛擬網(wǎng)映射方案求解問題的二次規(guī)劃模型，并設(shè)計基于凸二次規(guī)劃松弛方法的隨機近似算法求解該模型；然后針對動態(tài)到達的虛擬網(wǎng)構(gòu)建請求，首先使用上述隨機近似算法構(gòu)建該虛擬網(wǎng)的映射方案，然后基于接入控制策略，確定是否接受該虛擬網(wǎng)構(gòu)建請求，如接受則根據(jù)物理網(wǎng)資源的歷史負載情況重新定義物理資源價格，并完成該虛擬網(wǎng)映射；最后證明了在線虛擬網(wǎng)映射算法的競爭比，并通過仿真實驗對算法的有效性進行驗證。

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

2.1 網(wǎng)絡(luò)模型

物理網(wǎng)用無向圖Gs=（Ns，Es）［6］表示，Ns和Es是物理節(jié)點和物理鏈路集合。第i個物理節(jié)點nis有CPU容量c（nis）和位置loc（nis）兩個屬性，第i條物理鏈路eis有帶寬b（eis）屬性。

第j個動態(tài)到達的虛擬網(wǎng)VNj用無向圖Gjv=（Njv，Ejv）表示，Njv和Ejv是虛擬節(jié)點和虛擬鏈路集合。第i個虛擬節(jié)點nj，iv有CPU容量）和位置兩個屬性，第i條虛擬鏈路有帶寬屬性VNj有Djv、Tjs和Tjf3個屬性，虛擬節(jié)點與所映射物理節(jié)點間的距離必須小于或等于Djv，Tjs和Tjf表示虛擬網(wǎng)的開始和結(jié)束時間。

2.2 映射描述

虛擬網(wǎng)映射的任務(wù)是把虛擬節(jié)點和虛擬鏈路分別映射到物理節(jié)點和物理路徑上，并為其分配資源。針對VNj的映射須滿足以下約束條件：每個虛擬節(jié)點必須映射到唯一的物理節(jié)點上，而每個物理節(jié)點可被多個虛擬節(jié)點所映射；每條虛擬鏈路必須映射到物理網(wǎng)的唯一路徑上（即物理網(wǎng)不支持路徑分割），且物理路徑的兩個端點就是虛擬鏈路兩個端點所映射的物理節(jié)點，如虛擬鏈路的兩個端點映射到相同的物理節(jié)點，則虛擬鏈路不再映射，因同一物理節(jié)點內(nèi)部的通信帶寬遠高于虛擬鏈路的需求［4，12］；同時映射到eis上的虛擬鏈路的帶寬之和小于或等于b（eis）（鏈路容量約束條件）；同時映射到nis上的虛擬節(jié)點的CPU容量之和小于或等于c（nis）（節(jié)點容量約束條件）；虛擬節(jié)點與所映射的物理節(jié)點間的距離必須小于或等于Djv。

2.3 映射目標

映射目標是物理網(wǎng)提供商長期收益的最大化。同參考文獻［5］，當完成VNj映射后，物理網(wǎng)提供商所獲收益定義為ρj×（Tjf-Tjs），其中ρj=為單位時間收益。

定理1如物理網(wǎng)不支持路徑分割且物理節(jié)點可重復映射，則單虛擬網(wǎng)映射可行問題（指不考慮優(yōu)化目標的單個虛擬網(wǎng)映射問題）是NPC問題。

證明給定圖G=（N，E）以及圖G中k個頂點對（u1，υ1），…，（uk，υk）。邊不相交路徑問題是指找到圖G中分別連接這k對頂點的k條沒有公共邊的路徑，是NPC問題［15］，可將多項式歸約到特定單虛擬網(wǎng)映射可行問題，特定的單虛擬網(wǎng)映射可行問題構(gòu)造如下：物理網(wǎng)為G=（N，E），物理鏈路帶寬和物理節(jié)點CPU容量都為1，第i個物理節(jié)點ni的loc（ni）=（i，i）。虛擬網(wǎng)為Gv=（Nv，Ev），其中Nv=｛u1，υ1}∪…∪｛uk，υk}，記Nv=｛nm1，…，nmq}，當a＜b時，ma＜mb；Ev=｛（u1，υ1）}∪…∪｛（uk，υk）}，虛擬鏈路帶寬和虛擬節(jié)點CPU容量都為1；Dv=1，loc（nmc）=｛mc+0.1，mc+0.1}（通過位置約束使虛擬節(jié)點nmc只能映射到物理節(jié)點nmc）。

3 單虛擬網(wǎng)映射方案求解問題及其近似算法VNM CQP

3.1 不考慮容量約束的最小成本單虛擬網(wǎng)映射方案求解問題

物理節(jié)點nis增加價格屬性xi，物理鏈路eis增加價格屬性。不考慮容量約束的最小成本單虛擬網(wǎng)映射方案求解問題是指求出不考慮鏈路容量約束條件和節(jié)點容量約束條件的映射成本最小的映射方案（不完成資源分配）。針對VNj，某映射方案的映射成本γ（j）=，其中Aj，m表示該方案需分配第m個物理資源（m≤|Ns|，表示第m個物理節(jié)點；否則表示第m-|Ns|條物理鏈路）的量。

定理2不考慮容量約束的最小成本單虛擬網(wǎng)映射方案求解問題是NP難問題。

證明完全多部圖G（N，E）是指頂點集N可被劃分成k個不相交子集Ni（1≤i≤k），任何邊的兩個端點均在不同子集中，且每個頂點與不在同一頂點子集中的所有頂點均有邊相連。頂點ni有價格屬性ci，邊（ni，nj）有價格屬性dij。最小成本完全多部圖最大團問題是求出給定完全多部圖的最小成本（團頂點和邊的價格和）的最大團，是NP難問題，因為工藝方案選擇問題是NPC問題，且可歸約到最小成本完全多部圖最大團問題［16］。最小成本完全多部圖最大團問題可歸約到特定的不考慮容量約束的最小成本單虛擬網(wǎng)映射問題，特定映射問題構(gòu)造如下：物理網(wǎng)為完全多部圖G（N，E），第i個物理節(jié)點ni的價格為ci，如ni∈Nj，則loc（ni）=（j，j）；物理鏈路（ni，nj）的價格為dij。虛擬網(wǎng)是包含k個虛擬節(jié)點｛n1v，…，nkv}的完全圖，虛擬節(jié)點的CPU容量和虛擬鏈路的鏈路帶寬都為1，Dv=1，loc（niv）=（i+0.1，i+0.1）。

3.2 二次規(guī)劃模型

3.2.1 整數(shù)二次規(guī)劃模型

因無鏈路容量約束，則最小成本映射方案中虛擬鏈路映射一定采用最小價格路徑，故映射成本改寫成，其中表示所映射的物理節(jié)點，表示的價格，和是的端點，x（nis，njs）表示nis和njs間最小價格路徑上的鏈路價格之和。則最小成本單虛擬網(wǎng)映射方案求解問題的整數(shù)二次規(guī)劃模型如式（1）～式（4）所示。

3.2.2 凸二次規(guī)劃松弛

下面對模型QP的目標函數(shù)進行變換，得到新的二次規(guī)劃模型CQP，其中δ取任意小正實數(shù)。

Dˊ中yc，a所對應(yīng)行的主對角線元素值是，而yc，a所對應(yīng)行的非主對角線元素之和等于，根據(jù)主對角元全部大于零的嚴格對角占優(yōu)判別法［17］，可知Dˊ是正定矩陣，故CQP是嚴格凸二次規(guī)劃（有多項式時間算法［18］）。

3.3 近似算法VNM CQP設(shè)計

針對VNj，先用原始—對偶內(nèi)點算法［18］求解CQP模型，然后用隨機舍入法求IQP模型解，流程如下。

（1）構(gòu)造CQP模型，然后用原始—對偶內(nèi)點算法求解，得到最優(yōu)解

（2）for（i=1；i＜|Njv|；i++）｛對虛擬節(jié)點，按概率分布隨機選擇所映射的物理節(jié)點，如選擇的是第m個物理節(jié)點，則令ym，i=1，yh，i=0（h∈［1，|Ns|］Λh≠m）。}

（4）用Dijkstra算法，求出虛擬鏈路所映射的最小價格物理路徑，然后輸出虛擬鏈路映射方案。

3.4 算法近似比分析

定理3針對VNj，VNM_CQP算法所求方案的映射成本的數(shù)學期望，即算法近似比為Xj。其中是IQP的最優(yōu)值，bj，max和xmax表示最大虛擬鏈路帶寬和x（nis，njs）的最大值，wmin和cj，min分別表示最小物理節(jié)點價格和最小虛擬節(jié)點CPU容量。

證明：y*和y分別是QP和IQP的可行解。yk，i的數(shù)學期望當a＜b時，yc，a和yd，b相互獨立，故所以設(shè)QP最優(yōu)解是y-，則y-是CQP的可行解，故：

4 在線虛擬網(wǎng)映射問題及其競爭算法VNM PDA設(shè)計

當虛擬網(wǎng)請求獨立地動態(tài)到達后，僅知道現(xiàn)在和過去的虛擬網(wǎng)請求信息，為此不能精確計算物理資源的影子價格，而影子價格同資源的稀缺程度密切相關(guān)，體現(xiàn)了資源的供求關(guān)系［14］，由于物理網(wǎng)的資源量是確定的，故根據(jù)物理節(jié)點和物理鏈路的歷史相對負載（反映一段時期內(nèi)資源供求關(guān)系）定義其價格，具體見VNM_PDA算法的步驟3。針對動態(tài)到達的VNi，首先使用VNM_CQP構(gòu)建VNi的映射方案；然后基于接入控制策略，確定是否接受VNi，本文的接入控制策略是拒絕映射成本大于或等于Xi倍映射收益的虛擬網(wǎng)請求，Xi是針對VNi的VNM_CQP算法的近似比；如接受則重新計算物理網(wǎng)資源的價格，并完成該虛擬網(wǎng)映射。VNM_PDA算法具體流程如下：

（1）針對物理網(wǎng)Gs（附物理節(jié)點和鏈路的價格）和虛擬網(wǎng)VNi，采用VNM_CQP算法求出VNi的映射方案；

（2）if（γ（i）≥Xiρi）

then｛拒絕VNi；退出；}

else｛用所求映射方案完成映射；

（3）for（m=1；m≤|Ns|+|Es|；m++）

其中，γ（i）表示所求方案的成本（見第3.1節(jié)）。全局變量xm表示第m個物理資源的價格；Ai，m為所求方案需使用第m個物理資源的量，bm表示第m個物理節(jié)點（如m≤|Ns|）的CPU容量或第m-|Ns|條物理鏈路（如m＞|Ns|）的帶寬；全局變量xm初始化為，，其中最大近似比maxiXi=max｛X1，…，Xi}，maxiw（i）和最大收益maxiρi定義類似。

5 VNM PDA算法的時間復雜度和性能分析

5.1 時間復雜度分析

VNM_PDA算法時間復雜度由VNM_CQP算法時間復雜度決定。VNM_CQP算法時間復雜度由原始—對偶內(nèi)點算法決定，故VNM_PDA算法時間復雜度為O（|Ns|×|Nυ|）3×L），L指輸入長度［18］。

5.2 正確性和競爭比分析

先證明算法不會違反鏈路容量約束條件和節(jié)點容量約束條件；之后用競爭分析法［3，5］，研究算法在最壞情況下的性能。

假設(shè)1：VNi的任意虛擬鏈路的帶寬小于或等于最小物理鏈路帶寬的1/（β|Eiv|）。

假設(shè)2：VNi的任意虛擬節(jié)點的CPU容量小于或等于最小物理節(jié)點CPU容量的1/（β|Eiv|）。

假設(shè)3：任意虛擬鏈路的帶寬和虛擬節(jié)點的CPU容量大于或等于1。

通過假設(shè)對虛擬網(wǎng)的資源需求量進行限定［3，5］，否則任意確定在線算法的競爭比會趨向無窮大［5］。

記ak，m=Ak，m·β/bm，根據(jù)假設(shè)2和假設(shè)1可知，當1≤m≤|Ns|時，ak，m≤（bm/（β·|Nkv|）·|Nkv|·β）/bm=1；當|Ns|＜m≤|Es|+|Ns|時，ak，m≤（bm/（β·|Ekv|）·|Ekv|·β）/bm=1；因2x-1≤x（當0≤x≤1），故

定理4。其中xmi表示完成VNi處理后的xm；如算法接受VNa，則ha取1，否則取0。證明過程與參考文獻［3］類似，不再贅述。

定理5，即算法不會違反鏈路和節(jié)點的容量約束條件。

證明當i=1時，，故VN1會被映射。根據(jù)假設(shè)1和2，顯然成立。設(shè)當i=k-1成立。當i=k時，如拒絕VNk，則顯然成立；如接受VNk，則對VNk沒有使用的物理資源顯然成立。對VNk使用的第m個物理資源，根據(jù)假設(shè)3，，故；同時有xmk=；根據(jù)定理4，，即，得證。

定理6任意j≥1，針對請求序列｛VN1，…，VNj}，算法的競爭比小于或等于（1+2·maxjXi）·β。

證明先構(gòu)造針對該序列的離線虛擬網(wǎng)映射問題的數(shù)學模型，方法同參考文獻［3］。記VNi有效映射方案集為?i，第w個映射方案記為?i，w（設(shè)VNM_CQP算法所求為?i，1）。變量yi，w取1或0，表示VNi的映射采用或不采用?i，w，列向量；虛擬網(wǎng)映射收益列向量，其中ρi，w=ρi；物理節(jié)點CPU容量和物理鏈路帶寬向量B=；矩陣Aj共|Ns|+|Es|行，列，元素Ajm，（i，w）是?i，w方案需使用第m個物理資源的總量；矩陣Dj有j行，列，當a=b時矩陣元素取1，否則取0。

式（9）～式（12）給出離線虛擬網(wǎng)映射問題的0-1線性整數(shù)規(guī)劃模型ILP，優(yōu)化目標是收益最大化，式（10）是物理資源容量約束條件，式（11）確保對某個虛擬網(wǎng)，要么采用一種映射方案，要么拒絕。把式（12）中yi，w∈｛0，1}松弛為yi，w≥0，得到線性規(guī)劃模型LP，其對偶問題的線性規(guī)劃模型DLP見式（13）～式（15）。Xmj解釋為第m個物理資源的影子價格。

?i，w方案的映射成本記為γ（i，w），如VNM_PDA算法拒絕VNi，置zi=0，否則

（1）VNM_PDA算法完成VNj構(gòu)建處理后，所構(gòu)造的Zj向量和Xj向量，是針對｛VN1，…，VNj}的DLP模型的可行解。證明如下：當j=1時；因?qū)而言，xmj具有單調(diào)性，故對，有，得證。故設(shè)j=k-1時成立。當j=k時，對）的任意方案?b，w，滿足對VNk的任意映射方案?k，w，如接受VNk，則Zk+如拒絕VNk，則，得證。

證明如下：當j=1時，必接受VN1，（見定理5），故h1=1。因β≥2，則得證。故設(shè)j=k-1時成立。當j=k時，如拒絕VNk，則Zk=0，X取值不變，hk=0，則；如接受VNk，則hk=1，記，得證。

（3）算法的競爭比小于或等于（1+2·maxjXj）·β。證明如下：設(shè)離線問題的最大收益是ρoff，其LP模型的最優(yōu)解為Yj*；采用VNM_PDA算法所獲收益是ρin。根據(jù)對偶理論的弱對偶定理有：

定理7如考慮到虛擬網(wǎng)的Ts和Tf屬性，則針對｛VN1，…，VNj}序列，VNM_PDA算法的競爭比是lb（1+3（maxjXj）（maxjpj）（maxjw（j）Tmax）），其中Tmax是虛擬網(wǎng)最長持續(xù)時間。證明過程與參考文獻［3］類似，不再贅述。

5.3 算法平均性能實驗分析

5.3.1 實驗環(huán)境

通過實驗對算法的平均性能進行評估。支持物理節(jié)點可重復映射［4，8，11，12］的算法中，參考文獻［8，11］以降低能耗為目標，參考文獻［12］針對彈性光網(wǎng)絡(luò)，故把VNM_PDA算法同參考文獻［4］提出的NodeRep算法進行對比。具體使用MATLAB仿真，評估采用當前研究中的常用指標［2，4-6，9］，即用完成映射的虛擬網(wǎng)數(shù)量與虛擬網(wǎng)構(gòu)建請求總數(shù)之比表示的虛擬網(wǎng)請求接受率、單位時間物理網(wǎng)提供商的平均收益、物理節(jié)點利用率和物理鏈路利用率。

物理網(wǎng)和虛擬網(wǎng)請求的實際特征尚未清楚［6］，故用當前研究中常用方法［2，4-7，9，10］來構(gòu)建物理網(wǎng)和虛擬網(wǎng)。用GT-ITM［2］工具構(gòu)建含30個節(jié)點和40條鏈路的物理網(wǎng)，節(jié)點CPU容量和鏈路帶寬在［480，580］均勻分布，物理節(jié)點的x和y坐標在［1，100］均勻分布。虛擬網(wǎng)的連通度是50%，節(jié)點數(shù)在［2，5］均勻分布，節(jié)點CPU容量和鏈路帶寬在［1，6］均勻分布，虛擬節(jié)點的x和y坐標在［1，100］均勻分布，Dv=10；虛擬網(wǎng)的到達服從平均每單位時間有1.3個請求的泊松過程，其生存時間符合均值為1 000個單位時間的指數(shù)分布。NodeRep算法中參數(shù)取值同參考文獻［4］。

5.3.2 實驗結(jié)果及分析

（1）VNM_PDA算法使物理網(wǎng)資源得到有效利用

表1和圖1表明采用VNM_PDA算法的物理網(wǎng)資源的利用率更高，其原因是VNM_PDA算法的請求接受率更高；物理資源的利用率方差更小，即物理資源的使用更加均衡，其原因是VNM_PDA算法中物理資源的價格由其負載決定，故VNM_PDA算法將使用負載相對小的物理資源。

（2）VNM_PDA算法提高了請求接受率和長期收益

圖1和圖2表明，VNM_PDA和NodeRep算法都接受前800個虛擬網(wǎng)請求，但隨著虛擬網(wǎng)請求數(shù)的進一步增加，采用VNM_PDA算法的請求接受率和平均收益逐漸穩(wěn)定在0.828和17 992左右，比NodeRep算法提高11%左右。其主要原因是VNM_PDA算法能使負載更加均衡分布，從而使物理網(wǎng)資源得到更有效利用；VNM_PDA算法支持接入控制［5］，會主動拒絕映射比起收益來說成本過高的請求。

表1 資源利用率及方差

圖1 虛擬網(wǎng)構(gòu)建請求接受率

圖2 物理網(wǎng)提供商平均收益

6 結(jié)束語

以物理網(wǎng)提供商長期收益最大化為目標，通過采用物理節(jié)點可重復映射、影子價格的資源定價、以映射成本最小化為目標和基于成本收益比較的接入控制等策略，設(shè)計了在線虛擬網(wǎng)映射問題的競爭算法VNM_PDA。并對算法進行了競爭比分析和實驗驗證，以說明VNM_PDA算法的有效性和實用性。

［1］FISCHER A，BOTERO J F，BECK MT，et al.Virtual network embedding：a survey［J］.IEEE Communications Surveys and Tutorials，2013，15（4）：1888-1906.

［2］YU M，YI Y，REXFORD J，et al.Rethinking virtual network embedding：substrate support for path splitting and migration［J］.ACM SIGCOMM on Computer Communication Review，2008，38（2）：17-29.

［3］EVEN G，MEDINA M，SCHAFFRATH G，et al.Competitive and deterministic embeddings of virtual networks［J］.Theoretical Computer Science，2013（496）：184-194.

［4］李文，吳春明，陳健，等.物理節(jié)點可重復映射的虛擬網(wǎng)映射算法［J］.電子與信息學報，2011，33（4）：908-914.LI W，WU C M，CHEN J，et al.Virtual network mapping algorithm with repeatable mapping over substrate nodes［J］.Journal of Electronicsamp;Information Technology，2011，33（4）：908-914.

［5］余建軍，吳春明.支持接入控制的虛擬網(wǎng)映射近似算法［J］.電子與信息學報，2014，36（5）：1235-1241.YU J J，WU C M.Virtual network mapping approximation algorithm with admission control［J］.Journal of Electronicsamp;Information Technology，2014，36（5）：1235-1241.

［6］CHOWDHURY M，RAHMAN MR，BOUTABA R.ViNEYard：virtual network embedding algorithms with coordinated node and link mapping［J］.IEEE/ACM Transactions on Networking，2012，20（1）：206-219.

［7］李小玲，郭長國，李小勇，等.一種基于約束優(yōu)化的虛擬網(wǎng)絡(luò)映射方法［J］.計算機研究與發(fā)展，2012，48（9）：1601-1610.LI X L，GUO C G，LI X Y，et al.A constraint optimization based mapping method for virtual network［J］.Journal of Computer Research and Development，2012，48（9）：1601-1610.

［8］NONDE L，EL-GORASHI T E H，ELMIRGHANI J MH.Energy efficient virtual network embedding for cloud networks［J］.Journal of Lightwave Technology，2014，33（9）：1.

［9］JENS L，HOLGER K.A virtual network mapping algorithm based on subgraph isomorphism detection［C］//The 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures，August 17，2009，Barcelona，Spain.New York：ACM Press，2009：81-88.

［10］HU Q，WANG Y，CAO X.Resolve the virtual network embedding problem：a column generation approach［C］/The IEEE Conference on Computer Communications，April 14-19，2013，Turin，Italy.New Jersey：IEEE Press，2013：410-414.

［11］BOTERO J F，HESSELBACH X，DUELLI M，et al.Energy efficient virtual network embedding［J］.IEEE Communications Letters，2012，16（5）：756-759.

［12］ZHAO J Z，SUBRAMANIAM S，BRANDT-PEARCE M.Virtual topology mapping in elastic optical［C］/The IEEE International Conference on Communications（ICC），June 9-13，2013，Budapest，Hungary.New Jersey：IEEE Press，2013：3904-3908.

［13］李銘夫，畢經(jīng)平，李忠誠.資源調(diào)度等待開銷感知的虛擬機整合［J］.軟件學報，2014，25（7）：1388-1402.LI MF，BI J P，LI Z C.Resource-scheduling-waiting-aware virtual machine consolidation［J］.Journal of Software，2014，25（7）：1388-1401.

［14］余恕蓮，吳革.企業(yè)成本理論與方法研究［M］.北京：中國社會科學出版社，2010：32-44.YU S L，WU G.A Study on Enterprise Cost Theory and Its Methods［M］.Beijing：China Social Sciences Press，2010：32-44.

［15］KLEINBERG J M.Approximation Algorithms for Disjoint Paths Problems［M］.Cambridge：Massachusetts Institute of Technology，1996：11-12.

［16］KUSIAK A，F(xiàn)INKE G.Selection of process plans in automated manufacturing systems［J］.IEEE Journal of Robotics and Automation，1988，4（4）：397-402.

［17］岑燕斌，韋煜，羅會亮.快速判斷一類實對稱矩陣正定的極大極小元方法［J］.北京交通大學學報，2011，35（6）：140-143.CEN Y B，WEI Y，LUO H L.Max and mini-elements method：a rapid determination of one class rear symmetric positive definite matrices［J］.Journal of Beijing Jiaotong University，2011，35（6）：140-143.

［18］MONTEIRO R D C，ADLERIRO I.Interior path following primal-dual algorithms［J］.Mathematical Programming，1989，44（1）：43-66.

Virtual network mapping strategy and com petitive analysis based on cost constraint

YU Jianjun1，2，WU Chunming2
1.Quzhou College of Technology，Quzhou 324000，China 2.College of Computer Science and Technology，Zhejiang University，Hangzhou 310027，China

The approximation algorithm of single virtual network mapping solution aimed to minimize the mapping cost based on convex quadratic programming relaxation was designed.Then aiming for dynamic arrival construction request of the single virtual network，the mapping scheme was achieved based on physical network resource pricing strategy by shadow price，applying above-mentioned approximation algorithm.And then completed the competitive algorithm design based on virtual network admission control strategy by mapping cost constraint and provided the competitive analysis of this algorithm.Experiment results show that the proposed algorithm increases the effective utilization of physical network resources，hence it can improve the virtual network construction request acceptance ratio and the long-term profit of physical network service provider.

virtual network mapping，mapping cost，convex quadratic programming relaxation，admission control，competitive algorithm

s：Zhejiang Provincial Natural Science Foundation of China（No.LY14F020010），The National Natural Science Foundation of China（No.61379118），The National High Technology Research and Development Program of China（863 Program）（No.2015AA016103）

TP393

A

10.11959/j.issn.1000-0801.2016045

2015-09-02；

2015-12-30

浙江省自然科學基金資助項目（No.LY14F020010）；國家自然科學基金資助項目（No.61379118）；國家高技術(shù)研究發(fā)展計劃（“863”計劃）基金資助項目（No.2015AA016103）

余建軍（1969-），男，衢州職業(yè)技術(shù)學院信息工程學院院長、教授，主要研究方向為算法設(shè)計與分析、網(wǎng)絡(luò)虛擬化、光網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)等。

吳春明（1967-），男，博士，浙江大學教授、博士生導師，主要研究方向為互聯(lián)網(wǎng)體系結(jié)構(gòu)、可重構(gòu)網(wǎng)絡(luò)、軟件定義網(wǎng)絡(luò)、網(wǎng)絡(luò)虛擬化和網(wǎng)絡(luò)安全技術(shù)等。