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

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

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

1 引言

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

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

2 網絡建模及虛擬網絡映射問題描述

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

2.1 底層網絡描述

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

圖1 虛擬網絡請求的映射方案

2.2 虛擬網絡請求描述

2.3 虛擬網絡映射問題描述

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

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

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

3 虛擬網絡映射評價指標

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

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

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

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

底層網絡鏈路資源的平均利用率為

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

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

4 虛擬網絡映射問題的二進制組合優化模型

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

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

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

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

4.1 節點及約束條件

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

4.2 鏈路及約束條件

4.3 目標函數

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

5 VNE-AFS算法

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

5.1 解的表達、生成與適應度函數

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

步驟1 依據虛擬節點對底層節點的位置約束，為每個虛擬節點niV

建立可映射節點的集合。

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

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

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

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

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方向進行一次移動：隨機產生整數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方向移動；否則，執行覓食行為，聚群行為結束。

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

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

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

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

步驟1 設定有限次循環次數limit，變化量閾值ε；

5) 人工魚Xi的行為選擇

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

5.4 VNE-AFS算法流程

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

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

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

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

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

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

6 仿真實現與性能評價

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

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

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

表1 參與對比的算法

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

圖2 虛擬網絡請求映射成功率

圖3 虛擬網絡請求映射的平均收益

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

圖4 底層網絡鏈路資源的平均利用率

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

圖5 虛擬網絡請求映射的平均花費

圖6 虛擬網絡映射算法運行時間對比

7 結束語

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

[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]. 電子學報,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] 李曉磊.一種新型的智能優化方法—人工魚群算法[D]. 杭州: 浙江大學, 2003.LI X L. A New Intelligent Optimization Method-Artificial Fish School Algorithm[D]. Hangzhou: Zhejiang University, 2003.