余建軍，吳春明

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

研究與開發(fā)

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

余建軍1，2，吳春明2

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

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

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

1 引言

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

虛擬網(wǎng)映射問題是NP難問題［2］，面臨在線請(qǐng)求、拓?fù)涠鄻雍徒尤肟刂频忍魬?zhàn)，根據(jù)成本和收益等因素權(quán)衡是否接受虛擬網(wǎng)請(qǐng)求是接入控制的任務(wù)。當(dāng)前提出的集中算法，要么假定虛擬節(jié)點(diǎn)映射已知［3］，將問題簡(jiǎn)化為虛擬鏈路映射問題；要么將虛擬網(wǎng)映射分為節(jié)點(diǎn)映射和鏈路映射兩個(gè)階段［2，4-8］；要么將虛擬網(wǎng)作為一個(gè)整體，同時(shí)完成虛擬節(jié)點(diǎn)和虛擬鏈路映射［9-12］。

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

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

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

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

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

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

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

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

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

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

2.2 映射描述

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

2.3 映射目標(biāo)

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

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

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

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

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

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

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

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

3.2 二次規(guī)劃模型

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

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

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

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

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

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

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

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

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

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

3.4 算法近似比分析

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

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

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

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

（1）針對(duì)物理網(wǎng)Gs（附物理節(jié)點(diǎn)和鏈路的價(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個(gè)物理資源的價(jià)格；Ai，m為所求方案需使用第m個(gè)物理資源的量，bm表示第m個(gè)物理節(jié)點(diǎn)（如m≤|Ns|）的CPU容量或第m-|Ns|條物理鏈路（如m＞|Ns|）的帶寬；全局變量xm初始化為，，其中最大近似比maxiXi=max｛X1，…，Xi}，maxiw（i）和最大收益maxiρi定義類似。

5 VNM PDA算法的時(shí)間復(fù)雜度和性能分析

5.1 時(shí)間復(fù)雜度分析

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

5.2 正確性和競(jìng)爭(zhēng)比分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.3 算法平均性能實(shí)驗(yàn)分析

5.3.1 實(shí)驗(yàn)環(huán)境

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

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

5.3.2 實(shí)驗(yàn)結(jié)果及分析

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

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

（2）VNM_PDA算法提高了請(qǐng)求接受率和長期收益

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

表1 資源利用率及方差

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

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

6 結(jié)束語

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

［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é)點(diǎn)可重復(fù)映射的虛擬網(wǎng)映射算法［J］.電子與信息學(xué)報(bào)，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］.電子與信息學(xué)報(bào)，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］.計(jì)算機(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ī)整合［J］.軟件學(xué)報(bào)，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］.北京：中國社會(huì)科學(xué)出版社，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］岑燕斌，韋煜，羅會(huì)亮.快速判斷一類實(shí)對(duì)稱矩陣正定的極大極小元方法［J］.北京交通大學(xué)學(xué)報(bào)，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

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

余建軍（1969-），男，衢州職業(yè)技術(shù)學(xué)院信息工程學(xué)院院長、教授，主要研究方向?yàn)樗惴ㄔO(shè)計(jì)與分析、網(wǎng)絡(luò)虛擬化、光網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)等。

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