朱強(qiáng)，王慧強(qiáng)，呂宏武，王振東

（哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001）

1 引言

云計(jì)算環(huán)境追求以較低的成本提供可伸縮的多樣性服務(wù)，而網(wǎng)絡(luò)虛擬化是目前實(shí)現(xiàn)該目標(biāo)最有效的技術(shù)手段[1～3]。網(wǎng)絡(luò)虛擬化允許在共享底層網(wǎng)絡(luò)資源的基礎(chǔ)之上建立多個(gè)獨(dú)立、異構(gòu)的虛擬網(wǎng)絡(luò)，使服務(wù)提供商（SP, service provider）能夠依據(jù)用戶需求提供可定制的個(gè)性化服務(wù)。虛擬網(wǎng)絡(luò)請(qǐng)求中節(jié)點(diǎn)和鏈路通常帶有約束條件。依據(jù)基礎(chǔ)設(shè)施提供商（InP, infrastructure provider）當(dāng)前資源情況，通過(guò)映射算法在虛擬網(wǎng)絡(luò)構(gòu)建需求與底層網(wǎng)絡(luò)資源之間進(jìn)行匹配，為虛擬網(wǎng)絡(luò)請(qǐng)求分配合理的底層節(jié)點(diǎn)和鏈路資源被稱為虛擬網(wǎng)絡(luò)映射，它是一個(gè)NP-hard問(wèn)題[4]。虛擬網(wǎng)絡(luò)映射問(wèn)題通常采用基于啟發(fā)式算法的方法求解，然而為了降低映射的難度和提高啟發(fā)式算法的效率，已有的成果通常對(duì)映射問(wèn)題的空間進(jìn)行諸多限制：1）假設(shè)底層節(jié)點(diǎn)資源和鏈路資源是無(wú)限的[5,6]；2）底層網(wǎng)絡(luò)需要支持路徑分割[7]；3）映射算法評(píng)估指標(biāo)不完善[8]；4）忽略虛擬網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)位置的需求[9,10]等。同時(shí)映射求解過(guò)程還存在過(guò)于復(fù)雜和開銷大的問(wèn)題。

針對(duì)上述問(wèn)題，本文在底層網(wǎng)絡(luò)資源有限和不支持路徑分割的前提下，提出了一種基于人工魚群的網(wǎng)絡(luò)虛擬化映射算法，利用虛擬網(wǎng)絡(luò)請(qǐng)求對(duì)底層網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路的約束關(guān)系建立二進(jìn)制組合優(yōu)化模型，并通過(guò)人工魚群算法對(duì)底層網(wǎng)絡(luò)資源進(jìn)行近似最優(yōu)化映射，有效地降低底層網(wǎng)絡(luò)開銷和求解時(shí)間，提高虛擬網(wǎng)絡(luò)映射的成功率、平均收益和資源平均利用率。

2 網(wǎng)絡(luò)建模及虛擬網(wǎng)絡(luò)映射問(wèn)題描述

影響虛擬網(wǎng)絡(luò)映射的節(jié)點(diǎn)和鏈路因素有很多,為了簡(jiǎn)化映射問(wèn)題并清晰地描述映射過(guò)程，節(jié)點(diǎn)一般考慮CPU、內(nèi)存和位置因素，而鏈路一般考慮帶寬因素[3]。本節(jié)基于上述因素對(duì)底層網(wǎng)絡(luò)、虛擬網(wǎng)絡(luò)請(qǐng)求以及兩者之間的映射問(wèn)題進(jìn)行描述。

2.1 底層網(wǎng)絡(luò)描述

虛擬網(wǎng)絡(luò)映射問(wèn)題可抽象為一個(gè)圖論問(wèn)題。底層網(wǎng)絡(luò)使用帶權(quán)無(wú)向圖描述，其中，NS和ES分別代表底層網(wǎng)絡(luò)節(jié)點(diǎn)集和鏈路集。每個(gè)底層節(jié)點(diǎn)nS∈NS的屬性集合用ASN表示。節(jié)點(diǎn)的屬性分別為可用CPU資源占用比cpu(nS)、可用內(nèi)存占用比memory(nS)和位置loc(nS)。節(jié)點(diǎn)i和j之間鏈路eS(i,j)∈ES的屬性集為ASE，鏈路的屬性為可用帶寬占用比b(eS)。使用PS表示底層網(wǎng)絡(luò)所有無(wú)環(huán)路徑的集合，節(jié)點(diǎn)i和j之間的無(wú)環(huán)路徑集為PS(i,j)。圖1為一虛擬網(wǎng)絡(luò)請(qǐng)求到底層網(wǎng)絡(luò)的映射方案。其中，圖1(b)是底層網(wǎng)絡(luò)，鏈路上的數(shù)字代表鏈路可用帶寬，節(jié)點(diǎn)周圍長(zhǎng)方形內(nèi)的數(shù)字分別代表可用CPU和內(nèi)存資源占用比。

圖1 虛擬網(wǎng)絡(luò)請(qǐng)求的映射方案

2.2 虛擬網(wǎng)絡(luò)請(qǐng)求描述

2.3 虛擬網(wǎng)絡(luò)映射問(wèn)題描述

虛擬請(qǐng)求的映射表示為從VG到SG′的一個(gè)映射f，SG′為SG的一個(gè)子集，并且能夠滿足VG的約束條件。

其中，NS′?NS，PS′?PS，RN和RE分別為分配給虛網(wǎng)請(qǐng)求的節(jié)點(diǎn)和鏈路資源。虛擬映射可以分為節(jié)點(diǎn)映射Nf和鏈路映射Ef2部分。

如圖1(b)所示，虛擬網(wǎng)絡(luò)請(qǐng)求VN1和VN2的節(jié)點(diǎn)映射方案分別為{a→C,b→B,c→G}和{d→H, e→D,f→F}。鏈路映射方案分別為{(a,b)→{(C,A),(A,B)},(a,c)→{(C,D),(D,G)}}和{(d,e)→{(H,G),(G,D)},(d,f)→{(H,F)},(e,f)→{(D,E),(E,F)}}。節(jié)點(diǎn)和鏈路的分配同時(shí)滿足虛擬網(wǎng)絡(luò)請(qǐng)求的約束條件。

3 虛擬網(wǎng)絡(luò)映射評(píng)價(jià)指標(biāo)

從InP的角度看，虛擬網(wǎng)絡(luò)映射算法需要提高平均收益和資源利用率，并降低映射的平均花費(fèi)。與文獻(xiàn)[5,7,9]相似，定義為InP接受第i個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求所獲得的收益，由虛擬網(wǎng)絡(luò)的CPU、內(nèi)存資源和可用帶寬需求組成。

假設(shè)0到T時(shí)間段內(nèi)接受的虛擬網(wǎng)絡(luò)請(qǐng)求集合為I。底層網(wǎng)絡(luò)的平均運(yùn)營(yíng)收益為

InP接受一個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求的花費(fèi)為分配給該請(qǐng)求的所有相關(guān)底層資源花費(fèi)的總和為

0到T時(shí)間段內(nèi)底層網(wǎng)絡(luò)對(duì)虛擬網(wǎng)絡(luò)請(qǐng)求映射的平均花費(fèi)為

底層網(wǎng)絡(luò)鏈路資源的平均利用率為

從SP的角度來(lái)看，映射算法需要滿足更多的虛擬網(wǎng)絡(luò)映射需求。虛擬網(wǎng)絡(luò)的映射成功率表示為

其中，VN(t)和VN′(t)分別為0到t時(shí)刻虛擬網(wǎng)絡(luò)請(qǐng)求總數(shù)和接受的虛擬網(wǎng)絡(luò)請(qǐng)求數(shù)。

4 虛擬網(wǎng)絡(luò)映射問(wèn)題的二進(jìn)制組合優(yōu)化模型

與文獻(xiàn)[5～8]不同，本文在底層網(wǎng)絡(luò)資源有限和不支持路徑分割的前提下，以降低底層網(wǎng)絡(luò)映射開銷為目的，建立虛擬網(wǎng)絡(luò)映射問(wèn)題的二進(jìn)制組合優(yōu)化模型。

首先，定義底層節(jié)點(diǎn)nS∈NS的剩余可用CPU、內(nèi)存資源分別為cpu′(nS)和memory′(nS)，底層鏈路eS∈ES的剩余可用帶寬資源為b′(eS)。

其中，nV⊥nS定義為虛擬節(jié)點(diǎn)nV被分配到底層節(jié)點(diǎn)nS，eV⊥eS定義為虛擬鏈路nV被分配到底層鏈路eS。

任意路徑P∈PS的可用帶寬表示為2個(gè)底層節(jié)點(diǎn)之間沿著該路徑的最小剩余帶寬。

4.1 節(jié)點(diǎn)及約束條件

令MN為二進(jìn)制m×n矩陣，代表節(jié)點(diǎn)的映射關(guān)系。每個(gè)行向量和列向量分別代表一個(gè)虛擬節(jié)點(diǎn)和底層節(jié)點(diǎn)，當(dāng)虛擬節(jié)點(diǎn)被分配到底層節(jié)點(diǎn)nSj上時(shí)，MN(i,j)值為1，否則為0。對(duì)于同一個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求，每個(gè)虛擬節(jié)點(diǎn)只能夠被分配到一個(gè)底層節(jié)點(diǎn)，并且2個(gè)虛擬節(jié)點(diǎn)不能夠同時(shí)分配到同一個(gè)底層節(jié)點(diǎn)，約束條件形式化為

4.2 鏈路及約束條件

4.3 目標(biāo)函數(shù)

對(duì)于虛擬網(wǎng)絡(luò)請(qǐng)求，映射虛擬節(jié)點(diǎn)所分配的資源（CPU和內(nèi)存）是相同的，而虛擬鏈路分配的底層鏈路長(zhǎng)度會(huì)因方案不同而存在差異，因此使用底層鏈路的總使用帶寬來(lái)衡量映射成本。目標(biāo)函數(shù)為最小化鏈路映射成本。

5 VNE-AFS算法

虛擬網(wǎng)絡(luò)映射問(wèn)題的二進(jìn)制組合優(yōu)化本質(zhì)上是NP-hard問(wèn)題[11]，直接進(jìn)行全局最優(yōu)解的求取十分困難。因此，本文通過(guò)使用人工魚群智能啟發(fā)式算法求取近似最優(yōu)解。人工魚群是一種模擬魚群行為的群體智能算法，通過(guò)模擬魚的覓食、聚群、追尾等行為實(shí)現(xiàn)全局尋優(yōu)[12]。本文基于人工魚群的虛擬網(wǎng)絡(luò)映射算法主要由解的表達(dá)、生成與適應(yīng)度函數(shù)的確定，人工魚距離與感知距離的定義，人工魚的行為及其選擇方式3部分組成。

5.1 解的表達(dá)、生成與適應(yīng)度函數(shù)

人工魚個(gè)體的狀態(tài)對(duì)應(yīng)映射問(wèn)題的解。其當(dāng)前狀態(tài)Xi=（xi1,xi2,…,xid）表示映射問(wèn)題的第i個(gè)解，維數(shù)d表示虛擬網(wǎng)絡(luò)請(qǐng)求中節(jié)點(diǎn)的個(gè)數(shù)。xij表示虛擬節(jié)點(diǎn)j分配到底層節(jié)點(diǎn)的編號(hào)。采用如下方法進(jìn)行節(jié)點(diǎn)選取并采用隨機(jī)路徑方法生成初始解。

步驟1 依據(jù)虛擬節(jié)點(diǎn)對(duì)底層節(jié)點(diǎn)的位置約束，為每個(gè)虛擬節(jié)點(diǎn)niV

建立可映射節(jié)點(diǎn)的集合。

步驟2 若集合Ω(i)=θ(niV)∩{nS∈NS|MN(i,j)=1}為空集，表明底層網(wǎng)絡(luò)已經(jīng)沒有符合該虛擬節(jié)點(diǎn)映射需求的節(jié)點(diǎn)，虛網(wǎng)請(qǐng)求被拒絕，轉(zhuǎn)到步驟5；否則，轉(zhuǎn)到步驟3。

其中，Pbk為與相鄰節(jié)點(diǎn)之間的路徑。ω1和ω2分別為節(jié)點(diǎn)剩余CPU、內(nèi)存的權(quán)值。

式(11)～式(15)對(duì)節(jié)點(diǎn)的約束條件，分配成功；否則，映射失敗。

人工魚Xi的適應(yīng)度函數(shù)與虛擬網(wǎng)絡(luò)映射的d(i,j)目標(biāo)函數(shù)有關(guān)，定義為

fit(Xi)值越大，表明鏈路映射成本越低，對(duì)應(yīng)的映射方案越好。

5.2 人工魚距離與感知距離

2條人工魚iX和jX的距離如下

式(21)表示向量Xi與向量Xj有對(duì)不同的分量，本文將Xj中這樣的分量即路徑的集合記為wj(i,j)。

定義vd(i)為人工魚Xi的感知距離，所有滿足d(i,j)＜vd(i)的人工魚Xj構(gòu)成Xi的鄰域。

5.3 人工魚的行為及選擇

人工魚的行為主要有覓食、追尾、聚群和雜交行為。人工魚對(duì)行為的選擇會(huì)導(dǎo)致其位置的調(diào)整，同時(shí)對(duì)應(yīng)著映射方案的調(diào)整。人工魚的具體行為描述如下。

1) 人工魚Xi的覓食行為描述如下。

步驟1 設(shè)定TN，tn=0。

步驟2 設(shè)定人工魚移動(dòng)的步長(zhǎng)step，擁擠度因子δ。

步驟3 對(duì)于人工魚Xi，在其鄰域內(nèi)任意選擇人工魚Xj。

步驟4 如果fit(Xj)≤fit(Xi)，轉(zhuǎn)到步驟5；否則，Xi向Xj方向進(jìn)行一次移動(dòng)：隨機(jī)產(chǎn)生整數(shù)k(1≤k≤step)。如果k≥d(i,j)，則k=d(i,j)；在wj(i,j)中任選k條路徑進(jìn)行隨機(jī)變換，路徑需滿足式（10）和式（16）的約束條件，覓食行為結(jié)束。

步驟5 tn=tn+1。如果tn＜TN，轉(zhuǎn)步驟3；否則，人工魚Xi隨機(jī)移動(dòng)一步：在wj(i,j)中任選k條邊進(jìn)行隨機(jī)變換，覓食行為結(jié)束。

2) 人工魚Xi的聚群行為描述如下。

步驟1 將人工魚Xi鄰域范圍內(nèi)所有人工魚組成集合Ri。

步驟2 對(duì)Ri的中心位置進(jìn)行確定。其中，是Ri中人工魚在第x個(gè)分量上使用最多的邊。

i覓食行為步驟4相同的方法向Xc方向移動(dòng)；否則，執(zhí)行覓食行為，聚群行為結(jié)束。

3) 人工魚Xi的追尾行為描述如下。

步驟1 從Ri中選取適應(yīng)度值最大的Xu，

步驟2 確定與bestX相對(duì)應(yīng)的bestR。如果，則iX用與覓食行為步驟4相同的方法向bestX方向移動(dòng)；否則，執(zhí)行覓食行為，追尾行為結(jié)束。

4) 人工魚iX的雜交行為描述如下。

步驟1 設(shè)定有限次循環(huán)次數(shù)limit，變化量閾值ε；

5) 人工魚Xi的行為選擇

采用常用的試探法選擇人工魚的行為。對(duì)人工魚Xi分別模擬執(zhí)行覓食、聚群和追尾行為。分別得到Xi在執(zhí)行相應(yīng)行為后的適應(yīng)度函數(shù)值fit(Xi)p、fit(Xi)s和fit(Xi)f。執(zhí)行與fit(Xi)p、fit(Xi)s和fit(Xi)f中最大值對(duì)應(yīng)的行為，如果有多個(gè)值相同的行為，則隨機(jī)選取一個(gè)行為。

5.4 VNE-AFS算法流程

本文設(shè)計(jì)的基于人工魚群的網(wǎng)絡(luò)虛擬化映射算法流程描述如下。

步驟1 初始化人工魚種群規(guī)模SN、總迭代次數(shù)NI，NI=1，人工魚移動(dòng)的步長(zhǎng)step，擁擠度因子δ。依據(jù)5.1節(jié)生成SN個(gè)解構(gòu)成初始人工魚集合

步驟2 計(jì)算每條人工魚Xi的適應(yīng)度f(wàn)it(Xi)，記錄當(dāng)前適應(yīng)度值最大的人工魚Xi為Xbest。

步驟3 對(duì)于每條人工魚，按照5.3節(jié)進(jìn)行行為選擇，并執(zhí)行選定的行為。若Xj的適應(yīng)度值更高fit(Xj)＞fit(Xi)，表明新的映射方案要優(yōu)于原方案，則有Xbest=Xj。

步驟4 假定某些解連續(xù)經(jīng)過(guò)limit次循環(huán)之后沒有得到明顯改善，即變化量低于ε時(shí)，對(duì)其進(jìn)行雜交操作。

步驟5 記錄下當(dāng)前最優(yōu)的人工魚位置。若當(dāng)前的迭代次數(shù)Ni小于NI，Ni=Ni+1，跳轉(zhuǎn)至步驟3；否則，算法結(jié)束。

6 仿真實(shí)現(xiàn)與性能評(píng)價(jià)

在驗(yàn)證算法有效性的過(guò)程中，為了降低求解的復(fù)雜性，本文使用GT-ITM(georgia tech internet work topology models)拓?fù)渖善鲗?duì)VNE-AFS算法進(jìn)行輔助求解。

為了方便實(shí)驗(yàn)對(duì)比，參照文獻(xiàn)[5～8]，底層網(wǎng)絡(luò)設(shè)置為一具有100個(gè)節(jié)點(diǎn)和約500條鏈路的拓?fù)浣Y(jié)構(gòu)，與一個(gè)中等規(guī)模InP的能力相當(dāng)，節(jié)點(diǎn)之間的連接概率為0.5。底層節(jié)點(diǎn)的CPU和內(nèi)存資源符合[40,100]的均勻分布，底層鏈路資源符合[50,100]的均勻分布。虛擬網(wǎng)絡(luò)請(qǐng)求的拓?fù)涫请S機(jī)的，每個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求的節(jié)點(diǎn)數(shù)符合[2,10]的均勻分布，每個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求的生存時(shí)間符合指數(shù)分布，平均生存時(shí)間為1 000個(gè)時(shí)間單元。假設(shè)虛擬網(wǎng)絡(luò)請(qǐng)求符合每100個(gè)時(shí)間單元平均到達(dá)4個(gè)的泊松分布。對(duì)底層節(jié)點(diǎn)CPU和內(nèi)存資源的需求符合[0,20]的均勻分布，對(duì)底層鏈路的需求符合[50,100]的均勻分布。人工魚群的種群規(guī)模SN取20，迭代次數(shù)NI為500，控制參數(shù)limit取值20，適應(yīng)度函數(shù)變化的閾值ε取0.02，預(yù)選取可行節(jié)點(diǎn)權(quán)值1ω、2ω和3ω分別為0.2、0.2和0.6。

本文分別從底層網(wǎng)絡(luò)的虛擬網(wǎng)絡(luò)的映射成功率、平均運(yùn)營(yíng)收益、底層網(wǎng)絡(luò)鏈路資源的平均利用率和虛擬網(wǎng)絡(luò)請(qǐng)求映射的平均花費(fèi)4個(gè)方面，將VNE-AFS算法與經(jīng)典的G-MCF[5]、G-SP[7]、R-VINE[8]和D-VNMA[6]算法進(jìn)行比較。4種對(duì)比算法的描述如表1所示。仿真結(jié)果如圖2～圖6所示。

表1 參與對(duì)比的算法

由于預(yù)先篩選性能較高的節(jié)點(diǎn)，能夠最大限度避免如G-MCF算法和G-SP算法產(chǎn)生節(jié)點(diǎn)過(guò)載；同時(shí)人工魚群算法具有較強(qiáng)的尋優(yōu)能力，隨著時(shí)間的推移和虛擬網(wǎng)絡(luò)請(qǐng)求的增多， VNE-AFS算法在虛網(wǎng)映射成功率和底層網(wǎng)絡(luò)的平均收益上明顯高于4種對(duì)比算法，如圖2和圖3的實(shí)驗(yàn)結(jié)果所示，分別穩(wěn)定在0.82和29左右。與對(duì)比算法中性能最好的D-VNMA相比，映射成功率和平均收益分別提升了9.2%和14.6%。

圖2 虛擬網(wǎng)絡(luò)請(qǐng)求映射成功率

圖3 虛擬網(wǎng)絡(luò)請(qǐng)求映射的平均收益

圖4描述底層鏈路的平均使用率情況。VNE-AFS能夠使底層網(wǎng)絡(luò)利用率維持在0.35～0.5之間，僅在個(gè)別時(shí)間點(diǎn)略低于D-VNMA算法，其余時(shí)刻均高于或等于D-VNMA算法。從圖4實(shí)驗(yàn)結(jié)果可以看出，與4種對(duì)比算法相比，VNE-AFS能夠使底層網(wǎng)絡(luò)資源具有較高的平均使用率和映射成功率。

圖4 底層網(wǎng)絡(luò)鏈路資源的平均利用率

通過(guò)圖5和圖6實(shí)驗(yàn)結(jié)果可知，VNE-AFS算法降低虛擬網(wǎng)絡(luò)請(qǐng)求映射的平均花費(fèi)最高為47.8%（與G-SP算法相比），最低為24.2%（與D-VNMA算法相比），較好地控制了資源的平均花費(fèi)；在運(yùn)行時(shí)間方面，與4種映射算法相比，VNE-AFS最高降低了76.7%（與G-SP算法相比），最低降低了32.7%（與D-VNMA算法相比）。主要原因是4種對(duì)比算法求取的不一定是最優(yōu)解，而人工魚群算法有較強(qiáng)的尋優(yōu)能力，并可以獲得近似全局最優(yōu)解，能夠在確保底層網(wǎng)絡(luò)對(duì)虛擬網(wǎng)絡(luò)請(qǐng)求映射保持較低的資源開銷的同時(shí)降低算法的運(yùn)行時(shí)間。

圖5 虛擬網(wǎng)絡(luò)請(qǐng)求映射的平均花費(fèi)

圖6 虛擬網(wǎng)絡(luò)映射算法運(yùn)行時(shí)間對(duì)比

7 結(jié)束語(yǔ)

傳統(tǒng)的網(wǎng)絡(luò)虛擬化映射算法存在資源開銷大、效率低和對(duì)映射問(wèn)題空間進(jìn)行限制等問(wèn)題。本文在底層網(wǎng)絡(luò)資源有限和不支持路徑分割的前提下，結(jié)合人工魚群仿生智能算法，提出一種新的映射算法VNE-AFS。算法以二進(jìn)制組合優(yōu)化問(wèn)題為基礎(chǔ)，利用人工魚群算法較強(qiáng)的尋優(yōu)能力對(duì)虛擬網(wǎng)絡(luò)映射進(jìn)行近似最優(yōu)的分配。實(shí)驗(yàn)結(jié)果表明，隨著時(shí)間的增長(zhǎng)和虛擬網(wǎng)絡(luò)請(qǐng)求的增多，該算法在映射成功率、資源利用率和平均收益上較傳統(tǒng)的G-MCF、G-SP、R-VINE和D-VNMA算法有較為明顯的提升，并且有效地降低了底層網(wǎng)絡(luò)的平均花費(fèi)和求解時(shí)間。下一步的工作將對(duì)節(jié)點(diǎn)選取過(guò)程中的權(quán)值1ω和2ω進(jìn)行最優(yōu)確定，并針對(duì)底層網(wǎng)絡(luò)支持路徑分割的情況展開。

[1] ARMBRUS M, FOX A, GRIFFITH R, etal. A view of cloud computing[J]. Communications of the ACM, 2010, 53(4): 50-58.

[2] ZHANG Q, LU C, RAOUF B. Cloud computing: state-of-the-art and research challenges[J]. Journal of Internet Services and Applications,2010, 1(1): 7-18.

[3] CHOWDHURY N M M K, BOUTABA R. A survey of network virtualization[J]. Computer Networks, 2010, 54(5): 862-876.

[4] ANDERSEN D G. Theoretical approaches to node assignment[EB/OL].http://www.cs.cmu.edu/～ dga/papers/index.html,2002.

[5] YU M, YI Y, REXFORD J, etal. Rethinking virtual network embedding substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 17-29.

[6] HOUIDI, LOUATI W, DJAMAL Z, etal. A distributed virtual network mapping algorithm[A]. IEEE International Conference on Communications(ICC’09)[C]. Beijing: Chinese Academy of Science, China,2009. 5634-5640.

[7] CHOWDHURY N M M K, RAHMAN M R, BOUTABA B. ViNEYard: virtual network embedding algorithms with coordinated node and link mapping[J]. IEEE/ACM Transactions on Networking, 2012,20(1): 206-219.

[8] ZHU Y, AMMAR M. Algorithms for assigning substrate network resources to virtual network components[A]. Proceedings of 25th IEEE International Conference on Computer Communications (INFOCOM2006)[C].Barcelona, Spain, 2006.1-12.

[9] CHENG X, SU S, ZHANG Z. Virtual network embedding through topology-aware node ranking[J]. ACM SIGCOMM Computer Communication Review, 2011, 41(2): 39-47.

[10] 姜明，王保進(jìn)，吳春明等.網(wǎng)絡(luò)虛擬化與網(wǎng)映射算法研究[J]. 電子學(xué)報(bào),2011, 39(6): 1315-1320.JIANG M, WANG B J, WU C M, etal. Research on network virtualization and virtual network mapping algorithm[J]. Chinese Journal of Electronics, 2011, 39(6): 1315-1320.

[11] KOLLIOPOULOS S G, STEIN C. Improved approximation algorithms for unsplittable flow problems[A]. The 38th Annual Symposium on foundations of Computer Science[C]. Miami Beach, 1997.426-436.

[12] 李曉磊.一種新型的智能優(yōu)化方法—人工魚群算法[D]. 杭州: 浙江大學(xué), 2003.LI X L. A New Intelligent Optimization Method-Artificial Fish School Algorithm[D]. Hangzhou: Zhejiang University, 2003.