一種改進(jìn)的高可靠性虛擬網(wǎng)絡(luò)映射算法研究

童緒軍，鐘 梁

(1. 安徽醫(yī)學(xué)高等專科學(xué)校 基礎(chǔ)部，中國 合肥 230601； 2. 武漢大學(xué) 計算機(jī)學(xué)院，中國 武漢 430072)

虛擬技術(shù)在云計算環(huán)境下扮演重要角色[1-3]，多個服務(wù)商(Service Providers, SPs)只需從一個或多個基礎(chǔ)設(shè)施供應(yīng)商(Infrastructure Providers, InPS)處租借共享資源即可創(chuàng)建異構(gòu)虛擬網(wǎng)絡(luò)(Virtual Networks, VNs)，進(jìn)而向終端用戶提供個性化端到端服務(wù)[4]。其中，虛擬網(wǎng)絡(luò)映射主要負(fù)責(zé)將虛擬網(wǎng)絡(luò)請求(虛擬節(jié)點的計算請求(虛擬機(jī))和虛擬鏈路的帶寬請求)映射到數(shù)據(jù)中心所位于的具體的物理節(jié)點以及具有有限資源的底層網(wǎng)絡(luò)的路徑上。如果數(shù)據(jù)中心或者底層物理網(wǎng)絡(luò)鏈路發(fā)生物理故障，則受影響的虛擬網(wǎng)絡(luò)無法為終端用戶提供服務(wù)，導(dǎo)致服務(wù)提供商遭受重大經(jīng)濟(jì)損失。因此，我們希望將虛擬網(wǎng)絡(luò)映射到可靠性最高的底層物理網(wǎng)絡(luò)上，該問題稱為高可靠性虛擬網(wǎng)絡(luò)映射問題(Reliable Virtual Network Mapping, RVNM)[6]。

人們先前對RVNM問題的研究可分為3類：第1類，分布式云資源的分配。文獻(xiàn)[7]將CPU和帶寬等資源看成底層網(wǎng)絡(luò)上的節(jié)點和鏈路的容量，資源分配過程負(fù)責(zé)通過多物品流通理論將各種請求映射到底層網(wǎng)絡(luò)上的節(jié)點和路徑上。文獻(xiàn)[8]將分布式數(shù)據(jù)中心虛擬機(jī)的分配問題轉(zhuǎn)化為分團(tuán)問題，提出一種比率為2的近似算法，并可實現(xiàn)最大延時最小化。然而其算法對于虛擬器分配時的可靠性問題欠缺考慮。第2類，對虛擬星型網(wǎng)絡(luò)的可靠性/可生存性資源分析問題進(jìn)行研究。文獻(xiàn)[9,10]的作者向不同的數(shù)據(jù)中心分配不同數(shù)量的虛擬機(jī)，以盡量提升可靠性。他們首先確定一個中央數(shù)據(jù)中心，然后增加更多數(shù)據(jù)中心以提供足夠多的高可靠性虛擬機(jī)。文獻(xiàn)[11]的作者首先通過提供超過請求數(shù)量的數(shù)據(jù)中心實現(xiàn)K度生存性。然后，根據(jù)不同參數(shù)(包括風(fēng)險和延時)提出兩種啟發(fā)式算法，使虛擬星型網(wǎng)絡(luò)的總體延時最小化。然而其算法只適用于星型拓?fù)浣Y(jié)構(gòu)，且只考慮了計算容量約束，局限性較大。第3類，利用雙階段博弈理論研究虛擬網(wǎng)絡(luò)嵌入算法[12]。第1階段的博弈將虛擬節(jié)點映射到物理節(jié)點上；第2階段將虛擬鏈路映射到網(wǎng)絡(luò)中的物理路徑上。為了利用博弈理論獲得近似解，他們的算法需要考察所有可能的虛擬節(jié)點映射，但忽略了鏈路容量約束。針對以上3類算法的不足，文中提出了一種改進(jìn)的虛擬網(wǎng)絡(luò)映射算法，可在滿足計算容量和帶寬容量約束的同時，提高虛擬網(wǎng)絡(luò)映射的可靠性。

1 高可靠性虛擬網(wǎng)絡(luò)映射

在本文研究中，采用如下的場景：(1)每次只考慮一個虛擬網(wǎng)絡(luò)的映射請求；(2)每個虛擬節(jié)點請求的虛擬機(jī)數(shù)量不會多于一個或多個物理節(jié)點提供的可用虛擬機(jī)數(shù)量；(3)虛擬網(wǎng)絡(luò)是連通型網(wǎng)絡(luò)；(4)因為將一個虛擬節(jié)點映射到多個物理節(jié)點的能量消耗和網(wǎng)絡(luò)成本可能更高，所以我們將一個虛擬節(jié)點只映射到一個物理節(jié)點上；(5)利用目前典型的虛擬機(jī)動態(tài)分配算法[13]來確定虛擬機(jī)的布局和建立物理路徑；(6)因為發(fā)生故障時云服務(wù)的延時較高，所以重點是實現(xiàn)可靠性的最大化，而不是延時的最小化。

1.1 圖模型和虛擬網(wǎng)絡(luò)映射

圖1 RVNM問題的圖形示例：(a)GS；(b)GT

(1)服務(wù)圖形：圖1(a)給出了云計算場景下的虛擬網(wǎng)絡(luò)示例。文中將虛擬網(wǎng)絡(luò)表示為服務(wù)圖形GS(V,E)，其中V表示負(fù)責(zé)處理計算任務(wù)的虛擬節(jié)點集合；E表示將虛擬節(jié)點連接起來的虛擬鏈路集合。每個頂點u的數(shù)值(mu)表示執(zhí)行計算任務(wù)而請求的虛擬機(jī)數(shù)量；每條虛擬邊e=(u,v)的數(shù)值(bu,v)表示兩個虛擬節(jié)點之間的帶寬請求。

(2)網(wǎng)絡(luò)拓?fù)洌簣D1(b)給出了將物理節(jié)點所在地的多個分布式數(shù)據(jù)中心連接起來的物理網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)示例。文中將物理網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)表示為圖形GT(N,L)，其中N表示數(shù)據(jù)中心所在地的節(jié)點集合；L表示將這些節(jié)點連接起來的物理鏈路集合。對每個節(jié)點p∈N，括號中的首個數(shù)值(mp)表示數(shù)據(jù)中心內(nèi)可用虛擬機(jī)的數(shù)量；第2個數(shù)值(fp)表示數(shù)據(jù)中心的可靠性。對每條鏈路l=(p,q)∈L，括號中的首個數(shù)值(bp,q)表示鏈路的可用帶寬；第2個數(shù)值(fp,q)表示鏈路的可靠性。

(3)虛擬網(wǎng)絡(luò)映射：虛擬網(wǎng)絡(luò)映射問題是指將服務(wù)圖形中的虛擬節(jié)點映射到網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的物理節(jié)點(用h1:V→N′?N表示)，并將虛擬鏈路映射到網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中相應(yīng)物理節(jié)點之間的路徑上(用h2:E→L′?L表示)。圖1(a)和圖1(b)中的虛線表示虛擬節(jié)點映射(h1)，圖1(b)中的實線(計算鏈路和節(jié)點可靠性)表示虛擬鏈路映射(h2)。

1.2 可靠性函數(shù)

根據(jù)圖1所示，對于虛擬網(wǎng)絡(luò)映射(h1,h2)而言，其可靠性可表示為

Pr(h1,h2)=∏u∈V,p=h1(u)fp×∏(p,q)∈U(u,v)∈Eh2(u,v)fp,q。

(1)

可靠性主要包括兩個方面：(1)數(shù)據(jù)中心所在地物理節(jié)點的可靠性；(2)將被選物理節(jié)點連接起來的鏈路的可靠性。對于任意給定的一個實數(shù)a(0

R(h1,h2)=∑u∈V,p=h1(u)logafp+∑(p,q)∈U(u,v)∈Eh2(u,v)logafp,q=

∑u∈V,p=h1(u)rp+∑(p,q)∈U(u,v)∈Eh2(u,v)rp,q，

(2)

其中，rp=logafp表示物理節(jié)點p的可靠性；rp,q=logafp,q表示鏈路(p,q)的可靠性。因為a<1，為了實現(xiàn)最大可靠性(Pr)，需要找到可使可靠性函數(shù)R(h1,h2)最小化的映射(h1,h2)。

1.3 問題定義

定義1高可靠性虛擬網(wǎng)絡(luò)映射問題(RVNM)可表述如下：

已知：服務(wù)圖形GS(V,E)，每個節(jié)點u∈V請求(mu)個虛擬機(jī)，每條邊e=(u,v)∈E請求帶寬(bu,v)，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)GT(N,L)，每個節(jié)點p∈N的可靠性為(rp)，可用虛擬機(jī)數(shù)量為(mp)，每條鏈路l=(p,q)∈L的可靠性為(rp,q)，可用帶寬為(bu,v)。

目標(biāo)：尋找到映射(h1,h2)使可靠性函數(shù)R(h1,h2)最小。其中h1:V→N′?N將虛擬節(jié)點映射到數(shù)據(jù)中心所在地的物理節(jié)點，h2:E→L′?L將虛擬鏈路映射到網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的路徑上。在映射過程中滿足如下約束：(1)計算容量約束：請求的虛擬機(jī)數(shù)量不得多于可用虛擬機(jī)數(shù)量(即對?u∈V有mu≤mh1(u))；(2)帶寬容量約束：對各條鏈路請求的總體帶寬不得大于可用帶寬(即對?(p,q)∈L有∑(p,q)∈h2(u,v)bu,v≤bp,q)。

2 ILP模型

依據(jù)第1節(jié)給出的場景，當(dāng)物理網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)為連通圖且各條物理鏈路可靠性較高，可用/被請求的虛擬機(jī)的可靠性為1，可用/被請求的帶寬的可靠性為1時，RVNM問題可以看作旅行推銷員問題(TSP)，所以，RVNM問題是NP難題[14]。為此，本節(jié)首先給出基于整數(shù)線性規(guī)劃(ILP)的RVNM問題描述和求解方法，然后在第3節(jié)對RVNM問題進(jìn)行擴(kuò)展求解。為了便于闡述，下面給出了基于ILP的RVNM問題描述中的各種參數(shù)定義：

(1) ILP的輸入E:=[eu,v]|V|×|V|：GS的鄰接矩陣；MS:=[mu]|V|：每個虛擬節(jié)點u請求的虛擬機(jī)；BS:=[bu,v]|V|×|V|：每條虛擬鏈路(u,v)要求的帶寬；L:=[lp,q]|N|×|N|：GT的鄰接矩陣；MT:=[mp]|N|：每個物理節(jié)點p的可用虛擬機(jī)；BT:=[bp,q]|N|×|N|：每條鏈路(p,q)的可用帶寬；RN:=[rp]|N|：每個物理節(jié)點的可靠性p；RL:=[rp,q]|N|×|N|：每條鏈路(p,q)的可靠性；VL：大數(shù)。

從定義1可以看出，我們的目標(biāo)是使下面的函數(shù)最小化。

(3)

本文采用匈牙利算法[15]獲得基于ILP的RVNM問題的解。

3 基于雙階段博弈的啟發(fā)式算法

由于RVNM問題是NP難題，以上的ILP模型只能解決小規(guī)模問題，應(yīng)用局限性較大。為此，本節(jié)提出一種基于雙階段博弈的啟發(fā)式算法來解決大規(guī)模RVNM問題。該算法涉及到兩種映射：(1)虛擬鏈路映射(h2)；(2)虛擬節(jié)點映射(h1)。由于本文算法首先映射虛擬鏈路，所以將算法稱為鏈路映射優(yōu)先算法(LMF)。在描述博弈算法內(nèi)容之前，首先給出另外4種符號標(biāo)記。設(shè)I(u)={p∈N|mp≥mu}表示可滿足虛擬節(jié)點u虛擬機(jī)請求數(shù)量的物理節(jié)點構(gòu)成的集合；設(shè)J(u,p)={e∈E|u為e的端點&u映射到p}表示虛擬路徑集合，集合中的各條路徑均映射到物理節(jié)點p的虛擬節(jié)點u。因此，J(u)=∪p∈NJ(u,p)={e∈E|u為e的端點}。設(shè)K(l)={e∈E|l包含于e映射的物理路徑上}表示各條物理路徑l=(p,q)共有的路徑。

3.1 第1階段的博弈：虛擬鏈路映射

在第1階段的博弈，我們松弛虛擬節(jié)點映射的約束，允許1個虛擬節(jié)點映射到1或多個物理節(jié)點。具體來說，式(4)松弛為：

(13)

第1階段博弈表示為博弈方：各條虛擬鏈路e=(u,v)構(gòu)成博弈方。策略/行動：對各個博弈方e=(u,v)，p1≠p2時從p1到p2的所有物理路徑；因此，所有的行動集合可表示為∏e∈EAe。效用/成本函數(shù)：當(dāng)博弈方從其行動集合ae∈Ae中選擇從p1到p2的路徑(表示為Pp1,p2)時，將成本函數(shù)計算為

C(e)=C(p1)+C(p2)+C(Pp1,p2),

(14)

其中

(15)

(16)

VL表示大數(shù)。與終端節(jié)點成本類似，如果滿足帶寬容量約束式(10)，則鼓勵物理路徑通過共享鏈路來提升可靠性。

綜上所述，第1階段博弈的算法內(nèi)容如下所示。該算法的核心思路是最優(yōu)響應(yīng)。開始時，所有博弈方隨機(jī)選擇一條路徑；然后，博弈方e根據(jù)其他博弈方的行動改選最短路徑(C(e)方面)。當(dāng)所有博弈方均滿足各自選擇的路徑，本文算法終止。

算法1：虛擬鏈路映射算法

輸入：虛擬機(jī)請求數(shù)量為(MS)、帶寬請求數(shù)量為(BS)的GS(V,E)；可用虛擬機(jī)為(MT)、可用帶寬為(BT)的GT(N,L)；節(jié)點可靠性(RN)，鏈路可靠性(RL)；

輸出：每條虛擬鏈路映射到1條物理鏈路，否則駁回請求；

//初始階段

1：for 各個博弈方e，隨機(jī)選擇1條物理路徑，根據(jù)式(14-16)計算成本函數(shù)C(e)；

//博弈方可改變它們的選擇

2：Done ← false //表明博弈方有沒有更改其選擇；

3：while (!Done)

4：Done ←true

5：for 從1至|E|的各條虛擬路徑e

6： 刪除被e映射的路徑；

7： 如果虛擬鏈路e的某個終端節(jié)點映射到物理節(jié)點p上且物理路徑遍歷鏈路l，則創(chuàng)建虛擬鏈路e的圖形G′，并根據(jù)式(15-16)計算出節(jié)點成本和鏈路成本；

8： 尋找出圖G′中所有最短路徑對，選擇成本最低的成本對，將其存儲為C′(e)；

9：ifC′(e)

10：End for

11：End while

12：if 存在虛擬鏈路e使C(e)=VL

13： return 請求被駁回；

14： else return 鏈路e∈E的物理路徑及其成本C(e)；

3.2 第2階段博弈：虛擬節(jié)點映射

在第2階段，我們要求被相同虛擬節(jié)點映射的物理節(jié)點融合為1個物理節(jié)點，以便滿足式(4)的約束。

第2階段的博弈可表述為博弈方：映射到2個或2個以上物理節(jié)點的各個虛擬節(jié)點u構(gòu)成1個博弈方。策略/行動：所有物理節(jié)點。效用/成本函數(shù)：當(dāng)博弈方u選擇節(jié)點p1時，計算p1∈I(u)的成本函數(shù)C(u)：

(17)

其中，C(e)根據(jù)式(14—16)計算而得。如果p1?I(u)，則C(u)=VL。第1階段的博弈結(jié)果作為第2階段博弈的初始狀態(tài)。根據(jù)對其他博弈做的最優(yōu)響應(yīng)，博弈方融合為1個物理節(jié)點。第2階段博弈的算法內(nèi)容如下所示。

算法2：虛擬節(jié)點的映射

輸入：虛擬鏈路映射

輸出：虛擬網(wǎng)絡(luò)映射滿足所有約束(式(12))

0：if 沒有虛擬節(jié)點映射到多個物理節(jié)點；

Return虛擬網(wǎng)絡(luò)的映射//完成虛擬網(wǎng)絡(luò)的映射

1：對映射到多個物理節(jié)點的各個虛擬節(jié)點u，根據(jù)式(17)計算C(u)；

2：Done ← false //表明博弈方有沒有改變行動；

3：while (!Done)

4：Done ← true

5：for 映射到多個節(jié)點的各個虛擬節(jié)點u

6：尋找I(u)中C′(u)最小的物理節(jié)點；

7：ifC′(u)

8： End for

9：End while

10：if 存在使C(u)=VL的虛擬節(jié)點u

11：return 駁回請求

12：else return 虛擬網(wǎng)絡(luò)的映射

3.3 收斂性分析

定理1第1階段的博弈具有收斂性。

證明本文博弈過程的勢函數(shù)定義為

Φ=∑e∈EC(e)=∑e∈E1?EC(e)+VL·|E2|，

(18)

其中，E1表示成功映射到物理路徑的所有虛擬鏈路集合，根據(jù)式(14-16)計算C(e)。剩余未成功映射的虛擬鏈路為E2=E-E1?，F(xiàn)在證明，當(dāng)博弈方e′更改想法映射到另一條物理路徑時，勢函數(shù)的變化量(ΔΦ)等價于ΔC(e′)的變化量。此時需要討論兩種情況：

情況1：開始時e′∈E2，改變主意后e′∈E1。有：

ΔΦ=[∑e∈E1∪{e′}?EC(e)+VL·(|E2|-1)]-[∑e∈E1?EC(e)+VL·|E2|]

=C(e′)-VL=ΔC(e′)。

情況2：改變物理路徑之前和之后均有e′∈E1。通過考察受此變化影響的所有物理路徑及終端節(jié)點，我們有ΔΦ=ΔC(e′)。如果虛擬節(jié)點u從映射p1變化到映射p2，則：

映射發(fā)生變化時ΔC(e′)也會變化，且

如果|J(u,p1)-1|或|J(u,p2)-1|等于0，則將該項刪除后便可獲得同樣結(jié)論。類似地，鏈路變化時證明過程同上。所以，采用式(14-16)的成本函數(shù)時，本文第1階段的博弈是具有收斂性的潛在博弈。得證。

當(dāng)勢函數(shù)為Φ=∑u∈VC(u)并根據(jù)式(17)計算C(u)時，同樣可證明第2階段的博弈具有收斂性。因此，可以得出結(jié)論：整個博弈過程具有收斂性。

4 仿真實驗

本節(jié)給出定量結(jié)果，證明LMF在小規(guī)模和大規(guī)模場景下均具有優(yōu)異性能。首先定義兩個仿真參數(shù)：通信請求率和計算請求率。通信請求率α定義為

α=(‖BS·E‖/‖E‖)/(‖BT·L‖/‖L‖)，

其中，‖BS·E‖=∑(u,v)∈Ebu,v·eu,v，‖BT·L‖=∑(p,q)∈Lbp,q·lp,q。參數(shù)α的范圍為0-1，用于衡量物理鏈路的共享概率。若α較大，則物理鏈路成為性能瓶頸，不利于鏈路映射時的路徑共享，虛擬網(wǎng)絡(luò)映射用到的物理鏈路數(shù)量上升，可靠性下降。

計算請求率β定義為β=(‖MS‖/|N|)/(‖MT‖/|V|)，其中，‖MS‖=∑u∈Vmu且‖MT‖=∑p∈Nmp>0。參數(shù)β范圍0-1，用于衡量數(shù)據(jù)中心滿足計算請求的程度。當(dāng)其數(shù)值接近于0時，每個虛擬節(jié)點均可映射到任意物理節(jié)點上。當(dāng)數(shù)值接近于1時，每個虛擬節(jié)點請求大量虛擬機(jī)，且只可映射到少量物理節(jié)點上。因此，參數(shù)β可間接衡量可被虛擬節(jié)點映射的物理節(jié)點的數(shù)量。

所有的仿真結(jié)果取算法1 000次運(yùn)行后的均值。為便于比較，我們對文獻(xiàn)[12]中的博弈算法進(jìn)行修改，并增加了容量約束。修改后的博弈算法首先對虛擬節(jié)點進(jìn)行映射，然后對虛擬鏈路進(jìn)行映射，因此將該算法稱為節(jié)點映射優(yōu)先算法(NMF)。對于NMF，每個虛擬節(jié)點均是博弈方，并映射到某一物理節(jié)點上。所有虛擬節(jié)點映射到物理節(jié)點上時，NMF算法進(jìn)行第2階段的博弈，找到被虛擬節(jié)點映射的物理節(jié)點之間的路徑，實現(xiàn)虛擬鏈路映射。博弈方為了降低成本可更換到其他物理節(jié)點。所有博弈方均不改變其映射策略時，博弈終止。

4.1 小規(guī)模條件下高可靠性虛擬網(wǎng)絡(luò)映射

物理網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1(b)所示。隨機(jī)生成物理拓?fù)浣Y(jié)構(gòu)中各條鏈路和各個節(jié)點的可靠性，范圍在0.99～1.00之間。同時隨機(jī)確定范圍在50～150之間的可用虛擬機(jī)數(shù)量，及范圍在2～10 Gbps之間的可用帶寬。另外，我們還生成具有3～4個虛擬節(jié)點的服務(wù)圖，虛擬節(jié)點之間的虛擬鏈路隨機(jī)確定并保證服務(wù)圖連通。隨機(jī)確定范圍在10～100之間的請求虛擬機(jī)數(shù)量，使β=40%；隨機(jī)確定范圍在1～3 Gbps之間的各條虛擬鏈路的請求帶寬，滿足不同α值的需要。表1給出了基于雙階段博弈的啟發(fā)式算法的運(yùn)行結(jié)果。

表1 ILP， IMF和NMF的性能比較

從表1可以看出，可靠性隨著α值的下降而上升。原因在于：(1)有更多條虛擬鏈路共享高可靠性物理鏈路；(2)共享程度上升，使虛擬網(wǎng)絡(luò)在映射后的物理鏈路總量下降。另外，虛擬節(jié)點和虛擬鏈路數(shù)量上升時，分配的虛擬鏈路和節(jié)點數(shù)量也在上升，滿足了虛擬網(wǎng)絡(luò)的需求，因此可靠性下降。當(dāng)虛擬節(jié)點數(shù)量上升時，如果α值較大(α=0.5)，則鏈路共享的概率較低，導(dǎo)致可靠性從83.80%下降到69.04%。另一方面，α值較小時(當(dāng)α≤0.3或|V|=3時差值低于9%)，鏈路共享的概率較高，所以可靠性只下降了6%左右。因此，通信請求率較低時有助于提升可靠性。最后，我們發(fā)現(xiàn)LMF可獲得接近于最優(yōu)解的結(jié)果，當(dāng)α較小時尤其如此(當(dāng)α≤0.3或|V|=3時差值低于9%)。同時，發(fā)現(xiàn)無論在哪種情況下，LMF的性能總是優(yōu)于NMF。這是因為LMF在第1階段博弈時通過松弛虛擬節(jié)點映射約束(式(4))來擴(kuò)大解空間。于是，在高效分配網(wǎng)絡(luò)帶寬時，LMF將每條虛擬鏈路均看作獨立的博弈方，從而獲得了更好的性能。

4.2 大規(guī)模條件下高可靠性虛擬網(wǎng)絡(luò)映射

從圖2可以看出，當(dāng)|V|增加時，由于虛擬網(wǎng)絡(luò)具有更多個物理節(jié)點和鏈路，所以可靠性下降。其次，α=0.1時的可靠性下降速度要快于α=0.05時，原因是可以共享物理鏈路的虛擬鏈路數(shù)量下降。例如，當(dāng)|V|=10時，|E|=27條虛擬鏈路需要映射。然而，每條物理鏈路平均來說只能與1/α=10條虛擬鏈路共享，導(dǎo)致虛擬網(wǎng)絡(luò)對物理鏈路的需求量變大，可靠性下降，請求駁回概率上升。圖3中結(jié)果也印證了上述結(jié)論。另外，LMF在可靠性和請求駁回概率方面的性能均優(yōu)于NMF。原因在于：(1)LMF在第1階段博弈時放松了虛擬節(jié)點映射約束(式(4))，增大了解空間，降低了請求駁回概率；(2) LMF在第2階段的博弈采用第1階段的博弈結(jié)果作為輸入，而不是像NMF那樣將虛擬節(jié)點隨機(jī)映射到物理節(jié)點上，因此提升了可靠性。

此外，根據(jù)圖2和3的仿真結(jié)果分析可知，通過如下方式可提升RVNM的可靠性，降低請求駁回概率：(1)將虛擬網(wǎng)絡(luò)限定于少量分布式數(shù)據(jù)中心中，從虛擬鏈路數(shù)量方面減少數(shù)據(jù)中心間的通信；(2)增加可用網(wǎng)絡(luò)帶寬，使更多虛擬鏈路共享物理鏈路；(3)降低虛擬鏈路的帶寬請求。

圖2 可靠性 vs虛擬節(jié)點的數(shù)量

圖3 請求駁回概率vs虛擬節(jié)點的數(shù)量

4.2.2 計算容量約束和帶寬容量約束對高可靠性虛擬網(wǎng)絡(luò)映射的影響 對于物理網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，所有參數(shù)的生成方法與4.2節(jié)相同。對于服務(wù)圖，隨機(jī)生成虛擬網(wǎng)絡(luò)的虛擬鏈路且|V|=6，|E|=10。隨機(jī)生成虛擬機(jī)請求數(shù)量，滿足不同β值的需要；隨機(jī)生成各條虛擬鏈路的帶寬請求，滿足不同α值的需要。圖4～5比較了兩種約束對虛擬網(wǎng)絡(luò)映射的影響。從圖4可以看出，當(dāng)計算請求率(β)低于 0.8時可靠性較為穩(wěn)定。原因在于：(1)每個虛擬節(jié)點映射到至少1個既滿足計算容量約束且未被分配給其他虛擬節(jié)點的物理節(jié)點上；(2)網(wǎng)絡(luò)帶寬容容量約束在虛擬網(wǎng)絡(luò)映射結(jié)果中占據(jù)主導(dǎo)地位。另一方面，如果β≥0.8，無論帶寬容量約束如何，由于難以找到足夠多的滿足計算容量約束的物理節(jié)點，導(dǎo)致可靠性嚴(yán)重下降。最后，圖5表明只有β≥0.8時計算容量約束才對請求駁回概率具有重大影響。因此，當(dāng)β<0.8時，虛擬節(jié)點映射到物理節(jié)點的概率很大。

圖4 可靠性vs計算請求率(β)

圖5 請求駁回概率vs計算請求率(β)

5 結(jié)束語

本文在計算容量約束和帶寬容量約束兩種條件下研究了云請求的高可靠性虛擬網(wǎng)絡(luò)映射(RVNM)問題。該問題被證明是NP難題，并提出ILP模型來獲得小型網(wǎng)絡(luò)的近似最優(yōu)解。對于大型網(wǎng)絡(luò)，進(jìn)一步提出基于雙階段博弈的鏈路映射優(yōu)先(LMF)算法來求解RVNM問題。定量結(jié)果表明，通過松弛第1階段博弈過程的虛擬節(jié)點映射約束，LMF可在更大解空間搜索可行解，因此無論是對小型網(wǎng)絡(luò)還是大型網(wǎng)絡(luò)，LMF的可靠性和請于駁回概率性能均優(yōu)于已有算法。在下一步工作中，除了可靠性之外，我們將繼續(xù)研究具體底層網(wǎng)絡(luò)(比如光纖網(wǎng)絡(luò))的各種故障類型，以及虛擬網(wǎng)絡(luò)映射的生存性。