VNE-AFS：基于人工魚群的網(wǎng)絡虛擬化映射算法

朱強，王慧強，呂宏武，王振東

（哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱 150001）

1 引言

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

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

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

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

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

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

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

2.2 虛擬網(wǎng)絡請求描述

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

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

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

如圖1(b)所示，虛擬網(wǎng)絡請求VN1和VN2的節(jié)點映射方案分別為{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é)點和鏈路的分配同時滿足虛擬網(wǎng)絡請求的約束條件。

3 虛擬網(wǎng)絡映射評價指標

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

假設0到T時間段內接受的虛擬網(wǎng)絡請求集合為I。底層網(wǎng)絡的平均運營收益為

InP接受一個虛擬網(wǎng)絡請求的花費為分配給該請求的所有相關底層資源花費的總和為

0到T時間段內底層網(wǎng)絡對虛擬網(wǎng)絡請求映射的平均花費為

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

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

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

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

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

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

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

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

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

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

4.2 鏈路及約束條件

4.3 目標函數(shù)

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

5 VNE-AFS算法

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

5.1 解的表達、生成與適應度函數(shù)

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

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

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

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

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

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

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

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

5.2 人工魚距離與感知距離

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

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

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

5.3 人工魚的行為及選擇

人工魚的行為主要有覓食、追尾、聚群和雜交行為。人工魚對行為的選擇會導致其位置的調整，同時對應著映射方案的調整。人工魚的具體行為描述如下。

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

步驟1 設定TN，tn=0。

步驟2 設定人工魚移動的步長step，擁擠度因子δ。

步驟3 對于人工魚Xi，在其鄰域內任意選擇人工魚Xj。

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

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

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

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

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

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

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

步驟1 從Ri中選取適應度值最大的Xu，

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

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

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

5) 人工魚Xi的行為選擇

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

5.4 VNE-AFS算法流程

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

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

步驟2 計算每條人工魚Xi的適應度fit(Xi)，記錄當前適應度值最大的人工魚Xi為Xbest。

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

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

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

6 仿真實現(xiàn)與性能評價

在驗證算法有效性的過程中，為了降低求解的復雜性，本文使用GT-ITM(georgia tech internet work topology models)拓撲生成器對VNE-AFS算法進行輔助求解。

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

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

表1 參與對比的算法

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

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

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

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

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

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

圖5 虛擬網(wǎng)絡請求映射的平均花費

圖6 虛擬網(wǎng)絡映射算法運行時間對比

7 結束語

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

[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] 姜明，王保進，吳春明等.網(wǎng)絡虛擬化與網(wǎng)映射算法研究[J]. 電子學報,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]. 杭州: 浙江大學, 2003.LI X L. A New Intelligent Optimization Method-Artificial Fish School Algorithm[D]. Hangzhou: Zhejiang University, 2003.