余建軍 吳春明

1(衢州職業(yè)技術(shù)學(xué)院信息工程學(xué)院 浙江 衢州 324000) 2(浙江大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 浙江 杭州310027)

0 引 言

網(wǎng)絡(luò)虛擬化技術(shù)作為解決互聯(lián)網(wǎng)僵化問題的關(guān)鍵技術(shù)，正成為云計(jì)算范式的核心技術(shù)。虛擬網(wǎng)映射[1]是網(wǎng)絡(luò)虛擬化技術(shù)的核心問題，其任務(wù)是當(dāng)單個(gè)虛擬網(wǎng)絡(luò)構(gòu)建請(qǐng)求動(dòng)態(tài)到達(dá)后，構(gòu)建該虛擬網(wǎng)絡(luò)的映射方案并完成映射。單個(gè)虛擬網(wǎng)映射問題是NP難問題[2-3]，求解該問題的精確算法具有非多項(xiàng)式時(shí)間復(fù)雜度，故當(dāng)前提出的單個(gè)虛擬網(wǎng)映射算法主要集中在啟發(fā)式算法[2,4-7]，當(dāng)然也有少數(shù)單個(gè)虛擬網(wǎng)映射問題的精確算法被提出，因?yàn)榫_算法設(shè)計(jì)對(duì)啟發(fā)式算法設(shè)計(jì)具有啟發(fā)意義，且精確算法可用于中小規(guī)模問題求解以及啟發(fā)式算法的性能評(píng)估。精確算法可以分為兩階段映射精確算法和一階段映射精確算法兩類[8]。

兩階段映射精確算法采用迭代技術(shù)，每次迭代都是在完成虛擬節(jié)點(diǎn)映射后進(jìn)行虛擬鏈路映射，迭代的依據(jù)是虛擬網(wǎng)映射方案的目標(biāo)函數(shù)。文獻(xiàn)[9]以映射代價(jià)最小化為目標(biāo)，建立了基于路徑的單個(gè)虛擬網(wǎng)映射問題的混合整數(shù)規(guī)劃模型P-VNE；在分析P-VNE模型的對(duì)偶規(guī)劃模型的基礎(chǔ)上，提出了求解單個(gè)虛擬網(wǎng)映射問題最優(yōu)解的嵌入于分支限界搜索框架下的列生成算法。文獻(xiàn)[10]以最小化物理網(wǎng)絡(luò)資源消耗為目標(biāo)，通過增強(qiáng)文獻(xiàn)[9]的P-VNE模型，建立了基于路徑的單個(gè)虛擬網(wǎng)映射問題的混合整數(shù)規(guī)劃模型，并基于該模型設(shè)計(jì)了兩階段映射精確算法。該算法的主要流程如下：① 首先假設(shè)部分物理節(jié)點(diǎn)已經(jīng)被虛擬節(jié)點(diǎn)所映射；② 基于虛擬網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行虛擬鏈路映射，從而形成MILP模型新的約束條件，并得到該虛擬網(wǎng)映射問題的上屆；③ 假設(shè)虛擬鏈路已經(jīng)完成映射，然后完成虛擬節(jié)點(diǎn)映射，從而形成MILP模型新的約束條件，并得到該虛擬網(wǎng)映射問題的下屆；④ 重復(fù)步驟①、②和③，直到虛擬網(wǎng)映射問題的下屆等于或接近等于上屆。

一階段映射精確算法是指虛擬節(jié)點(diǎn)映射和虛擬鏈路映射同時(shí)進(jìn)行的精確算法。一階段映射精確算法是通過建立單個(gè)虛擬網(wǎng)映射問題的數(shù)學(xué)規(guī)劃模型，然后通過分枝定界法、整數(shù)規(guī)劃算法等常用方法求解。文獻(xiàn)[11]以最小化物理網(wǎng)絡(luò)資源消耗和負(fù)載均衡為目標(biāo)，建立了基于節(jié)點(diǎn)-鏈路的單個(gè)虛擬網(wǎng)映射問題的整數(shù)線性規(guī)劃模型，并采用優(yōu)化軟件CPLEX求解該模型，該模型的約束條件包括了鏈路延遲約束和虛擬節(jié)點(diǎn)最大距離約束。文獻(xiàn)[12]針對(duì)小規(guī)模的單個(gè)虛擬網(wǎng)映射問題，以映射代價(jià)最小化為目標(biāo)建立數(shù)學(xué)規(guī)劃模型，并用優(yōu)化軟件LINGO來(lái)求解。

虛擬網(wǎng)映射問題精確算法設(shè)計(jì)的關(guān)鍵是提高其求解效率，目前所提出的一階段映射精確算法是基于求解數(shù)學(xué)規(guī)劃模型的優(yōu)化軟件來(lái)實(shí)現(xiàn)的，其求解效率有待進(jìn)一步提高，以進(jìn)一步增強(qiáng)其實(shí)用性。鑒于可滿足性模理論在線性邏輯約束公式優(yōu)化問題求解領(lǐng)域有突出優(yōu)勢(shì)[13]，本文基于可滿足性模理論，設(shè)計(jì)了虛擬網(wǎng)映射問題一階段映射精確算法，并通過實(shí)驗(yàn)對(duì)比和分析，驗(yàn)證本文方法的有效性。具體而言，針對(duì)物理網(wǎng)絡(luò)不支持路徑分割且物理節(jié)點(diǎn)不支持重復(fù)映射的虛擬網(wǎng)映射問題[2]，首先建立以物理網(wǎng)絡(luò)資源消耗量最小化為目標(biāo)的單個(gè)虛擬網(wǎng)映射問題的整數(shù)線性規(guī)劃模型；然后，基于可滿足性模理論[13]提出了一種解決物理網(wǎng)絡(luò)不支持路徑分割且物理節(jié)點(diǎn)不支持重復(fù)映射的虛擬網(wǎng)映射問題的精確求解方法。

1 問題描述和數(shù)學(xué)模型

1.1 問題描述

1.2 虛擬網(wǎng)映射收益及目標(biāo)

虛擬網(wǎng)映射問題是在線優(yōu)化問題，其求解目標(biāo)往往是多樣化的[2]，如從物理網(wǎng)絡(luò)提供商的角度，其目標(biāo)是最大化長(zhǎng)期收益；從服務(wù)提供商的角度，其目標(biāo)是最小化從物理網(wǎng)絡(luò)提供商租用的資源量；其他還有節(jié)能、安全、容錯(cuò)等[14]，本文以最大化物理網(wǎng)絡(luò)提供商長(zhǎng)期收益為其映射目標(biāo)。在單個(gè)虛擬網(wǎng)映射時(shí)，因其收益是常數(shù)，為達(dá)到長(zhǎng)期映射目標(biāo)，最小化映射成本是單個(gè)虛擬網(wǎng)映射問題的主要目標(biāo)[2]，本文將物理網(wǎng)絡(luò)資源(CPU容量和物理鏈路帶寬)消耗量定義為映射成本[10,12]。

1.3 整數(shù)線性規(guī)劃模型

(1)

(3) 約束條件為：

(2)

(3)

(4)

(5)

(6)

式中：si和ti是第i條虛擬鏈路的兩個(gè)端點(diǎn)對(duì)應(yīng)的源節(jié)點(diǎn)，式(4)、式(5)和式(6)表示流守恒，即除了源節(jié)點(diǎn)si和目標(biāo)節(jié)點(diǎn)ti外其他節(jié)點(diǎn)的網(wǎng)絡(luò)凈流量為0。

(7)

(8)

(9)

式(9)確保每個(gè)物理節(jié)點(diǎn)最多只能被一個(gè)虛擬節(jié)點(diǎn)所映射。

2 基于可滿足性模理論求解器的虛擬網(wǎng)映射問題求解

2.1 虛擬網(wǎng)映射問題的SMT公式

命題邏輯可滿足性問題(SATISFIABILITY，SAT)[13]是NPC問題，SAT技術(shù)被廣泛應(yīng)用于自動(dòng)電子設(shè)計(jì)、靜態(tài)程序分析、測(cè)試用例生成等領(lǐng)域。針對(duì)SAT存在只面向命題邏輯公式、表達(dá)能力有限等問題，人們將SAT擴(kuò)展為可滿足性模理論(satisfiability module theories，SMT)[13]。SMT是判定一階邏輯公式在組合背景理論下的可滿足性問題，SMT技術(shù)在測(cè)試用例自動(dòng)生成、線性邏輯約束公式優(yōu)化問題求解等領(lǐng)域有突出優(yōu)勢(shì)。

通過構(gòu)建虛擬網(wǎng)映射問題的SMT公式VNM_SMT，從而將虛擬網(wǎng)映射問題建模為線性邏輯約束求解優(yōu)化問題。虛擬網(wǎng)映射問題的SMT公式由式(10)-式(19)組成。

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

蘊(yùn)涵詞用?表示，A?B等價(jià)于A∨B。式(10)確保物理節(jié)點(diǎn)剩余CPU容量大于等于映射到該物理節(jié)點(diǎn)的虛擬節(jié)點(diǎn)的CPU容量需求。式(11)確保任意物理鏈路上所映射的所有虛擬鏈路帶寬之和小于等于該物理鏈路的剩余帶寬。式(12)確保源節(jié)點(diǎn)不能成為流的中間節(jié)點(diǎn)。式(13)、式(14)和式(15)表示流守恒，除了si對(duì)應(yīng)的源節(jié)點(diǎn)和ti對(duì)應(yīng)的目標(biāo)節(jié)點(diǎn)外其他節(jié)點(diǎn)的網(wǎng)絡(luò)凈流量為0。式(16)確保每個(gè)源節(jié)點(diǎn)(對(duì)應(yīng)虛擬節(jié)點(diǎn))只能映射到唯一的一個(gè)物理節(jié)點(diǎn)上。式(17)確保每個(gè)物理節(jié)點(diǎn)最多只能被一個(gè)虛擬節(jié)點(diǎn)所映射。式(18)表示優(yōu)化目標(biāo)是最小化物理鏈路帶寬消耗量。

2.2 基于SMT求解器的虛擬網(wǎng)映射問題求解

2.2.1SMT求解器

用以求解SMT問題的自動(dòng)化工具稱為SMT求解器。SMT求解器的算法實(shí)現(xiàn)分為兩類，第一類是積極類算法，它將SMT公式轉(zhuǎn)化為SAT公式，然后用SAT求解器求解；第二類是惰性算法，它將SMT公式層次化為布爾公式與理論公式，然后采用SAT求解器與理論求解器互動(dòng)求解[13]。

積極類算法將SMT公式轉(zhuǎn)化為SAT公式時(shí)，SAT公式長(zhǎng)度隨問題規(guī)模呈指數(shù)型增長(zhǎng)，故不適用于大規(guī)模問題求解。而惰性算法通過SAT求解器與理論求解器互相配合，提高了問題求解效率，成為大多數(shù)SMT求解器的選擇。

目前，主流SMT求解器支持的背景理論有整數(shù)集上的線性算數(shù)理論(quantifier free_linear integer arithmetic，QF_LIA)、實(shí)數(shù)集上的線性算數(shù)理論(quantifier free_linear real arithmetic，QF_LRA)、數(shù)組理論、未解釋函數(shù)理論等[13]。

2.2.2 虛擬網(wǎng)映射問題求解

(|Ns|-1)]進(jìn)行二分搜索，該區(qū)間的下界是虛擬網(wǎng)絡(luò)所有鏈路的帶寬之和，表示每條虛擬鏈路所映射的物理路徑的長(zhǎng)度至少為1；上界是虛擬網(wǎng)絡(luò)所有鏈路的帶寬之和與物理節(jié)點(diǎn)數(shù)減1之乘積，表示每條虛擬鏈路所映射的物理路徑的長(zhǎng)度至多為物理節(jié)點(diǎn)數(shù)減1。OPT-MathSA[15]、Z3[16]和SYMBA[17]等SMT求解器均能滿足問題求解需要。

3 平均性能實(shí)驗(yàn)評(píng)估

基于SMT求解器的虛擬網(wǎng)映射問題精確求解方法屬于一階段映射精確算法。目前提出的求解虛擬網(wǎng)映射問題的精確算法，其本質(zhì)是求解混合整數(shù)線性規(guī)劃模型的不同方法，主要包括列生成算法(Column Generation Algorithm，CGA)[9]、最優(yōu)分解法(optimal decomposition approach，ODA)[10]和采用優(yōu)化軟件的分枝定界法等[11-12]。

下面采用實(shí)驗(yàn)的方法評(píng)估基于SMT求解器的虛擬網(wǎng)映射問題精確求解方法的平均性能，具體把所提出的基于SMT求解器的方法同列生成算法[9]、最優(yōu)分解算法[10]和基于優(yōu)化軟件方法[12]進(jìn)行比較，虛擬網(wǎng)映射問題的線性整數(shù)規(guī)劃數(shù)學(xué)模型采用VNM_IP。

3.1 實(shí)驗(yàn)環(huán)境及性能評(píng)估指標(biāo)

基于Mininet和FlowVisor[18]構(gòu)建仿真環(huán)境，SMT求解器采用Z3 4.4.4，優(yōu)化軟件CPLEX采用CPLEX11.0，優(yōu)化軟件LINGO采用LINGO 11.0。本實(shí)驗(yàn)在配置Intel(R) Core(TM) i5- 480M@ 2.67 GHz CPU，4 GB內(nèi)存的電腦上進(jìn)行。對(duì)基于Z3求解虛擬網(wǎng)映射問題的性能分析，主要使用虛擬網(wǎng)請(qǐng)求接受率、單位時(shí)間物理網(wǎng)絡(luò)提供商的平均收益和求得虛擬網(wǎng)映射問題最優(yōu)解所用平均時(shí)間等三個(gè)評(píng)估指標(biāo)。

3.2 實(shí)驗(yàn)數(shù)據(jù)的設(shè)定

物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)構(gòu)建采用當(dāng)前研究常用的方法[2]，即采用GT-ITM[2]工具構(gòu)建物理節(jié)點(diǎn)CPU容量和物理鏈路帶寬均在[480,580]內(nèi)均勻分布的包含30個(gè)物理節(jié)點(diǎn)和40條物理鏈路的物理網(wǎng)絡(luò)。虛擬網(wǎng)絡(luò)的到達(dá)是平均每5分鐘有1.3個(gè)請(qǐng)求的泊松過程，每個(gè)虛擬網(wǎng)絡(luò)的生存時(shí)間符合均值為5 000分鐘的指數(shù)分布；虛擬網(wǎng)絡(luò)的虛擬節(jié)點(diǎn)數(shù)在[2,5]間均勻分布，虛擬網(wǎng)絡(luò)的連通度是50%，虛擬節(jié)點(diǎn)CPU容量和虛擬鏈路帶寬均在[1,6]內(nèi)均勻分布。另外，求解每個(gè)虛擬網(wǎng)映射問題的時(shí)間限定在4分鐘之內(nèi)。

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

實(shí)驗(yàn)發(fā)現(xiàn)采用優(yōu)化軟件CPLEX和LINGO求解性能相差很小，故下面針對(duì)采用優(yōu)化軟件CPLEX的結(jié)果進(jìn)行分析。

(1) 基于SMT求解器的求解法提高了請(qǐng)求接受率和長(zhǎng)期收益。圖1和圖2表明前750個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求到達(dá)后所有算法都能夠完成構(gòu)建，但隨著時(shí)間的推移和請(qǐng)求數(shù)的不斷增加，所有算法的請(qǐng)求接受率和平均收益就相對(duì)穩(wěn)定。基于SMT求解器的求解方法的請(qǐng)求接受率穩(wěn)定在0.809左右，比列生成算法CGA、最優(yōu)分解算法ODA和基于優(yōu)化軟件CPLEX的方法分別提高19.2%、15.5%和9.6%；物理網(wǎng)絡(luò)提供商單位時(shí)間(設(shè)為5分鐘)平均收益穩(wěn)定在17 283左右，比列生成算法CGA、最優(yōu)分解算法ODA和基于優(yōu)化軟件CPLEX的方法分別提高20.1%、16.6%和10.9%。因虛擬網(wǎng)請(qǐng)求接受率等同于求得虛擬網(wǎng)映射問題最優(yōu)解比例，故基于SMT求解器的求解方法求得虛擬網(wǎng)映射問題最優(yōu)解比例穩(wěn)定在0.809左右，比其他三種算法至少提高9.6%。

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

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

(2) 基于SMT求解器的求解法的最優(yōu)解平均求解時(shí)間更短。從圖3可觀察到基于SMT求解器的求解方法，求得虛擬網(wǎng)映射問題最優(yōu)解所用平均時(shí)間在3.43分鐘左右，比列生成算法CGA、最優(yōu)分解算法ODA和基于優(yōu)化軟件CPLEX的方法分別減少2.9%、8.1%和9.4%。從圖1和圖2可知，相比于列生成算法CGA、最優(yōu)分解算法ODA和基于優(yōu)化軟件CPLEX的方法，基于SMT求解器的求解方法的物理網(wǎng)提供商單位時(shí)間平均收益提高幅度高于虛擬網(wǎng)請(qǐng)求接受率提高幅度至少0.9%，說明在限定時(shí)間內(nèi)基于SMT求解器的求解方法能夠求解出更加復(fù)雜的虛擬網(wǎng)映射請(qǐng)求，可以得出基于SMT求解器的實(shí)際求解方法的求解效率比圖3所示結(jié)果更優(yōu)。

圖3 最優(yōu)解平均求解時(shí)間

4 結(jié) 語(yǔ)

針對(duì)物理網(wǎng)不支持路徑分割且物理節(jié)點(diǎn)不支持重復(fù)映射的虛擬網(wǎng)映射問題，基于可滿足性模理論，構(gòu)建解決虛擬網(wǎng)映射問題的SMT公式，并采用SMT求解器求解最優(yōu)解。實(shí)驗(yàn)表明，與目前基于求解混合整數(shù)線性規(guī)劃模型的精確算法相比，基于可滿足性模理論的虛擬網(wǎng)映射問題求解精確方法，具有更高的有效性和實(shí)用性。后期，將對(duì)如何進(jìn)一步優(yōu)化虛擬網(wǎng)映射問題的SMT公式繼續(xù)開展研究，以進(jìn)一步提高求解效率。