基于成本約束的虛擬網映射策略及競爭分析

余建軍，吳春明

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

研究與開發

基于成本約束的虛擬網映射策略及競爭分析

余建軍1，2，吳春明2

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

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

虛擬網映射；映射成本；凸二次規劃松弛；接入控制；競爭算法

1 引言

網絡虛擬化作為解決互聯網僵化問題的新技術，越來越引起學術界和產業界的關注，虛擬網映射問題［1］是虛擬化研究的核心內容，其任務是在物理網上為虛擬網節點和虛擬網鏈路分配滿足需求的節點和路徑，從而實現在物理網上多個相互隔離的虛擬網共存的目的，其求解目標主要是實現物理網提供商長期收益的最大化。

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

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

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

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

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

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

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

2 虛擬網映射問題

2.1 網絡模型

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

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

2.2 映射描述

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

2.3 映射目標

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

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

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

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

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

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

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

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

3.2 二次規劃模型

3.2.1 整數二次規劃模型

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

3.2.2 凸二次規劃松弛

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

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

3.3 近似算法VNM CQP設計

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

（1）構造CQP模型，然后用原始—對偶內點算法求解，得到最優解

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

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

3.4 算法近似比分析

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

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

4 在線虛擬網映射問題及其競爭算法VNM PDA設計

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

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

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

then｛拒絕VNi；退出；}

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

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

其中，γ（i）表示所求方案的成本（見第3.1節）。全局變量xm表示第m個物理資源的價格；Ai，m為所求方案需使用第m個物理資源的量，bm表示第m個物理節點（如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算法時間復雜度由原始—對偶內點算法決定，故VNM_PDA算法時間復雜度為O（|Ns|×|Nυ|）3×L），L指輸入長度［18］。

5.2 正確性和競爭比分析

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

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

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

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

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

記ak，m=Ak，m·β/bm，根據假設2和假設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，即算法不會違反鏈路和節點的容量約束條件。

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

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

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

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

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

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

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

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

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

5.3 算法平均性能實驗分析

5.3.1 實驗環境

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

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

5.3.2 實驗結果及分析

（1）VNM_PDA算法使物理網資源得到有效利用

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

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

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

表1 資源利用率及方差

圖1 虛擬網構建請求接受率

圖2 物理網提供商平均收益

6 結束語

以物理網提供商長期收益最大化為目標，通過采用物理節點可重復映射、影子價格的資源定價、以映射成本最小化為目標和基于成本收益比較的接入控制等策略，設計了在線虛擬網映射問題的競爭算法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］李文，吳春明，陳健，等.物理節點可重復映射的虛擬網映射算法［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］余建軍，吳春明.支持接入控制的虛擬網映射近似算法［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］李小玲，郭長國，李小勇，等.一種基于約束優化的虛擬網絡映射方法［J］.計算機研究與發展，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］.軟件學報，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］余恕蓮，吳革.企業成本理論與方法研究［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，FINKE 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）；國家高技術研究發展計劃（“863”計劃）基金資助項目（No.2015AA016103）

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

吳春明（1967-），男，博士，浙江大學教授、博士生導師，主要研究方向為互聯網體系結構、可重構網絡、軟件定義網絡、網絡虛擬化和網絡安全技術等。