蔣燕燕，楊龍祥，成聿倫

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

一種基于健壯型映射樹的虛擬網絡映射算法

蔣燕燕，楊龍祥，成聿倫

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

針對虛擬網絡映射存在的資源開銷大、虛擬網絡請求接收率低等問題，文中提出了一種基于健壯型映射樹的虛擬網絡映射算法。該算法通過劃分虛擬網絡、估算物理節(jié)點資源、初始化映射樹和比較啟發(fā)式函數，實現(xiàn)對虛擬網絡請求的映射。該算法的主要目的在于盡可能大地提高請求接收率，優(yōu)化資源利用，同時增加映射收益。文中將該算法與傳統(tǒng)的虛擬網絡映射算法進行仿真相比，結果表明，該算法在虛擬網絡映射接收率和平均收益方面優(yōu)于傳統(tǒng)虛擬網絡映射算法，以及在映射較多的虛擬網絡請求的同時減少了物理資源的使用。

網絡虛擬化；映射樹；接收率；資源利用率

0 引 言

近年來，網絡虛擬化技術受到普遍關注,被視為構建未來網絡的重要技術之一。利用網絡虛擬化技術將未來網絡劃分為多個虛擬網絡，這些虛擬網絡共享同一個物理網絡，從而完成虛擬網絡請求。網絡虛擬化主要問題是如何將虛擬網絡映射到物理網絡上，該過程稱為VNE(Virtual Network Embedding)問題。由于應用場景、資源條件約束和動態(tài)在線請求等因素，使得虛擬網絡映射問題變得難以解決，所以VNE問題是一個NP-hard問題[1]。

針對虛擬網絡映射問題，VNE算法已有一些研究。這些算法根據映射過程大致可以分為兩類：節(jié)點和鏈路同時映射、節(jié)點和鏈路分兩步單獨映射。文獻[2]中提出了VNE-Least算法，使用貪婪算法進行節(jié)點映射，最短路徑算法進行鏈路映射，由于假設物理資源是無限的，所以控制條件不足，無法用于實際場景中。文獻[3]中提出給予分布式協(xié)作虛擬網絡映射算法，將虛擬網絡劃分為若干個星型拓撲網絡，采用基于多代理系統(tǒng)同時完成節(jié)點和鏈路映射，為保證算法性能，假設物理資源是無限的。文獻[4]中提出支持對物理網絡路徑分割，但求解復雜，開銷很大。文獻[5]中采用蟻群算法VNE-AC，旨在減少虛擬網絡請求的拒絕率，算法派出工蜂尋找最優(yōu)路徑，雖然減少了鏈路的利用率，但會引起部分鏈路發(fā)生擁塞現(xiàn)象。文獻[6]中采用貪婪算法進行節(jié)點映射，路徑分割進行鏈路映射，該方法容易造成部分節(jié)點過載。

通過以上分析，在實際應用場景中，物理網絡資源不為無限可用，除了考慮算法效率外，還需考慮網絡負載均衡，不能造成局部網絡擁塞[7]。文中主要研究基于映射樹拓撲同時完成節(jié)點和鏈路映射的虛擬網絡映射算法VNE-RMT(Robust Mapping Tree)，算法主要分為四步：

(1)劃分虛擬網絡；

(2)選出候選物理節(jié)點；

(3)初始化映射樹；

(4)選出最佳映射方案。

該研究的目的在于盡可能提高虛擬網絡請求的接收率和減少物理資源的開銷。

1 網絡模型及映射問題描述

1.1 物理網絡模型

物理網絡用加權無向圖GS=(NS,LS)表示，NS表示物理節(jié)點，LS表示物理鏈路。每個物理節(jié)點nS∈NS，C(nS)表示物理節(jié)點可用的CPU資源，memory(nS)表示物理節(jié)點的可用內存。每條物理鏈路lS(i,j)∈LS,lS(i,j)表示物理節(jié)點i和j之間的物理鏈路,B(lS(i,j))表示物理鏈路的可用帶寬資源，u(lS(i,j))表示物理鏈路的成本、時延的均值。

1.2 虛擬網絡模型

虛擬網絡用加權無向圖GV=(NV,LV)表示，NV表示虛擬節(jié)點，LV表示虛擬鏈路。每個虛擬節(jié)點nV∈NV，C(nV)表示網絡請求對節(jié)點的CPU資源的約束,memory(nV)表示請求對節(jié)點的內存約束。每條虛擬鏈路lV(i,j)∈LV，lV(i,j)表示虛擬節(jié)點i和j之間的虛擬鏈路，B(lV(i,j))表示虛擬網絡請求對鏈路的帶寬約束，u(lV(i,j))表示請求對鏈路的成本、時延的均值約束。

1.3 映射問題描述

圖1給出了虛擬網絡映射到物理網絡上的過程，包括節(jié)點映射和鏈路映射。

圖1 虛擬網絡映射示意圖

2 評價指標

虛擬網絡映射算法的目標是用盡可能少的物理資源獲得最大的收益，而且為了保證服務質量，請求接收率也是網絡映射的重要指標之一。因此，這里考慮的評價指標有：網絡收益、映射成本、收益成本、收益成本比和請求接收率[8]。

(1)網絡收益。

(1)

(2)映射成本。

(2)

式中，β表示CPU和帶寬之間的均衡權值。

(3)收益成本比值。

(3)

式中，R/C的比值表示物理網絡的資源利用率，可以直接反映基礎設施提供商的利潤。

(4)請求接收率。

虛擬網絡的映射接收率表示為成功映射的虛擬網絡請求數VNR-S(t)與該時間段內到達的虛擬網絡請求總數VNR-A(t)的比值，即

(4)

3 算法描述

3.1 選擇參數

物理網絡節(jié)點nS的綜合資源可以表示為：

(5)

同樣，虛擬節(jié)點nV的綜合資源可以表示為：

(6)

3.2 VNE-RMT算法描述

(1)劃分虛擬網絡。

把虛擬網絡劃分為多個小型虛擬網絡[9]，計算每個小型虛擬網絡中的每個虛擬節(jié)點的IR(nV)值，把具有最大綜合資源的虛擬節(jié)點作為根節(jié)點root，與之相鄰的虛擬節(jié)點按照IR(nV)值降序排列。

(2)選出候選物理節(jié)點。

計算物理網絡中每個物理節(jié)點的綜合資源IR(nS)。先估算物理網絡承載虛擬網絡請求的能力[10]。用矩陣Mat(i,j)表示每個虛擬節(jié)點的映射候選物理節(jié)點，i表示物理節(jié)點的數目，j表示虛擬節(jié)點的數目。

(7)

因此，這個步驟是處理物理節(jié)點能承載的虛擬節(jié)點。通過比較可用節(jié)點和請求節(jié)點的綜合資源參數，選出每個虛擬節(jié)點的候選映射物理節(jié)點。如果虛擬節(jié)點j的Mat(i,j)<0，算法將把負值返回給請求的虛擬網絡，將不為該節(jié)點進行映射分配物理節(jié)點。只要虛擬節(jié)點有一個候選物理節(jié)點，算法將保留該虛擬節(jié)點。

(3)初始化映射樹。

如圖2所示，在劃分好的小型虛擬網絡中，建立映射樹TM。每個映射樹的等級代表第j級虛擬節(jié)點分配，節(jié)點和樹枝分別代表候選物理節(jié)點和節(jié)點間的鏈路[11-13]。虛擬網絡中從源節(jié)點到目的節(jié)點的路徑中的節(jié)點和鏈路的分配方式取決于啟發(fā)式函數。啟發(fā)式函數是一個有真實數值的函數，決定哪個節(jié)點作為最佳節(jié)點去生成映射樹，直到所有節(jié)點完成分配。該映射樹有n級，n為每個小型虛擬網絡總虛擬節(jié)點的數目，每個虛擬節(jié)點的映射方案對應搜索樹的每一級。映射樹的節(jié)點表示候選物理節(jié)點，節(jié)點之間的樹枝表示兩節(jié)點間鏈路的映射方案。通過啟發(fā)式函數實現(xiàn)從root節(jié)點到節(jié)點映射，該過程同時考慮了節(jié)點和鏈路的映射分配方案。在映射分配時，如果下一級節(jié)點沒有可映射的物理節(jié)點，算法將回到上一級分配節(jié)點，從候選物理節(jié)點選出最佳節(jié)點。

圖2 虛擬網絡樹形拓撲

(4)選擇最佳映射方案。

通過估算資源能力，啟發(fā)式函數為每個物理節(jié)點選出映射樹的節(jié)點，物理節(jié)點nS啟發(fā)式函數表示如下：

f(nS)=g(nS)+h(nS)

(8)

假設最小的f值表示構建方案的最佳節(jié)點。當發(fā)生回溯現(xiàn)象時，選擇發(fā)生不能映射的最近一級的節(jié)點[14]。啟發(fā)式函數的第一部分是：

g(nS)=(n-i)*2n-i，n=NV，i是當前虛擬節(jié)點

(9)

h(nS)=1/Mat(i,j)+1

(10)

其中，函數g表示現(xiàn)在節(jié)點和最末節(jié)點樹葉之間的距離。最末節(jié)點樹葉定義為最后一個被映射的虛擬節(jié)點，該節(jié)點下面不再有分支節(jié)點。啟發(fā)式函數f可以用最快的速度完成搜索過程，完成所有節(jié)點和鏈路的映射，允許映射過程發(fā)生無法再映射情況時回溯到上一級節(jié)點。函數h是為現(xiàn)在的虛擬節(jié)點估算候選物理節(jié)點的能力。Mat(i,j)是一個整數值，表示每個虛擬節(jié)點的物理候選節(jié)點，假設沒有約束條件的節(jié)點優(yōu)于有約束條件的節(jié)點。

從式(9)和式(10)得到：

f(nS)=(n-i)*2n-i+1/Mat(i,j)+1

(11)

對當前虛擬節(jié)點，選擇啟發(fā)式函數f值最小的候選物理節(jié)點為映射樹每一級的最佳候選節(jié)點。必須確認從一個物理節(jié)點到另一個物理節(jié)點間的路徑鏈路滿足請求所需的帶寬。如果這樣的路徑存在，就進行下一個虛擬節(jié)點分配，否則算法將回溯到上一級節(jié)點，直到找到最佳分配方案。一旦路徑找到，物理網絡資源將被分配一段時間，用完后釋放資源。當分配或釋放資源發(fā)生時，將更新物理資源。

4 仿真與分析

文中使用GT-ITM拓撲生成器生成物理網絡和虛擬網絡請求[6]。物理網絡是一個具有100個節(jié)點和約500條鏈路的初始拓撲，每對節(jié)點連接的概率是0.5，物理節(jié)點的CPU資源、內存資源和鏈路帶寬資源都符合[50,100]的均勻分布，虛擬網絡請求的到達強度符合100個時間單元平均到達4個的泊松分布。假定有10個虛擬網絡請求的節(jié)點個數符合[2,10]的均勻分布。

把VNE-RMT算法與VNE-Least[2]、G-MCF[6]進行比較。對虛擬網絡請求接收率、物理網絡節(jié)點和鏈路資源的平均利用率和虛擬網絡映射平均收益進行分析比較。仿真過程假設式(1)和(2)中的CPU與帶寬影響相同，即設α=β=1。

圖3的實驗結果表明，VNE-RMT算法的虛擬網絡請求接收率比其他兩種算法高，隨著時間的推移，穩(wěn)定在0.74，這得益于預先對虛擬請求節(jié)點進行綜合資源估算，避免了局部擁塞。

圖3 虛擬網絡請求接收率

圖4的實驗結果表明，與其他兩種算法比較，VNE-RMT算法在映射較多的虛擬網絡請求的同時使用較少的物理網絡節(jié)點和鏈路資源。

圖4 資源平均利用率

圖5的實驗結果表明，VNE-RMT算法在物理網絡上的平均收益比其他兩種算法有明顯優(yōu)勢，隨著時間的推移穩(wěn)定在30左右。

圖5 平均收益

5 結束語

網絡虛擬化問題主要是有效的資源分配問題。文中使用基于健壯型映射樹算法來同時完成節(jié)點和鏈路映射。該算法的主要目標是提高虛擬網絡請求接收率和映射平均收益，且更高效地利用物理網絡節(jié)點和鏈路資源。該算法將虛擬網絡簡化為映射樹拓撲結構，使用啟發(fā)式函數來確定資源分配方案，達到網絡負載均衡。

隨著網絡規(guī)模的不斷擴大，中心結構使得計算緩慢，造成嚴重時延。下一步研究工作將圍繞應用多代理系統(tǒng)的虛擬網絡映射算法展開。

[1]FischerA,BoteroJF,TillBH,etal.Virtualnetworkembedding:asurvey[J].IEEECommunicationsSurveys&Tutorials,2013,15(4):1888-1906.

[2]ZhuY,AmmarM.Algorithmsforassigningsubstratenetworkresourcestovirtualnetworkcomponents[C]//ProcofIEEEINFOCOM.[s.l.]:IEEE,2006:1-12.

[3]LouatiHW,ZeghlacheD.Adistributedvirtualnetworkmappingalgorithm[C]//ProcofICC’08.[s.l.]:IEEE,2008:5634-5640.

[4]ChowdhuryM,RahmanMR,BoutabaR.ViNEYard:virtualnetworkembeddingalgorithmswithcoordinatednodeandlinkmapping[J].IEEE/ACMTransactionsonNetworking,2012,20(1):206-219.

[5]FajjariI,SaadiNA,PujolleG,etal.VNE-AC:virtualnetworkembeddingalgorithmbasedonantcolonymetaheuristic[C]//ProcofICC.[s.l.]:IEEE,2011:1-6.

[6]YuM,YiY,RexfordJ,etal.Rethinkingvirtualnetworkembedding:substratesupportforpathsplittingandmigration[J].SIGCOMMComputCommunRev,2008,38(2):17-29.

[7] 朱 軍，許 倩，易輝躍，等.節(jié)點刪除法的虛擬網絡映射算法[J]．安徽大學學報:自然科學版，2014,38(5):37-43.

[8] 朱 強，王慧強，馮光升，等.VNE-ABC:基于人工蜂群的網絡虛擬化映射算法[J].北京工業(yè)大學學報，2014,40(1):68-73.

[9]DongZ.Astudyonvirtualnetworkdecomposingmappingalgorithmbasedonnetworkbalance[C]//Procoffourthinternationalconferenceoncomputationalandinformationsciences.[s.l.]:[s.n.],2012:880-883.

[10]DiH,YuH,AnandV,etal.Efficientonlinevirtualnetworkmappingusingresourceevaluation[J].JournalofNetworkandSystemsManagement,2012,20(4):468-488.

[11]HuangTao,LiuJiang,ChenJiangya,etal.Atopology-cognitivealgorithmframeworkforvirtualnetworkembeddingproblem[J].ChinaCommunications,2014(4):73-84.

[12]CuiHongyan,TangShaohua,HuangXu,etal.Anovelmethodofvirtualnetworkembeddingbasedontopologyconvergence-degree[C]//ProcofIEEEinternationalconferenceoncommunicationsworkshops.[s.l.]:IEEE,2013:246-250.

[13]ButtNF,ChowdhuryM,BoutabaR.Topologyawarenessandreoptimizationmechanismforvirtualnetworkembedding[J].Networking,2010,6091:27-39.

[14]LiWen,WuChunming,ChenJian,etal.Virtualnetworkmappingalgorithmwithrepeatablemappingoversubstratenodes[J].JournalofElectronicsandInformationTechnology,2011,33(4):908-914.

A Virtual Network Embedding Algorithm Based on Robust Mapping Tree

JIANG Yan-yan,YANG Long-xiang,CHENG Yu-lun

(College of Communication and Information Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

To overcome the high cost and low accepted rate faced by virtual network embedding,a virtual network embedding algorithm based on robust mapping tree is proposed.This algorithm realizes virtual network embedding through dividing the virtual network,estimation of substrate node resource,initialization of mapping tree and comparison of heuristic function.The objective of this algorithm is to maximize the accepted rate,optimize resource utilization and increase the average revenue.In this paper,the algorithm is compared with the traditional virtual network embedding algorithms.Simulation results show that the accepted rate and average revenue of virtual networks requests are increased,and the usage of substrate network resources is reduced as realizations of virtual network request are increased compared with the traditional virtual network embedding algorithms.

network virtualization;mapping tree;accepted rate;usage of resources

2015-05-11

2015-08-14

時間：2016-01-26

國家自然科學基金資助項目(61271237，61372124);國家“863”高技術發(fā)展計劃項目(2013CB329104)

蔣燕燕(1991-)，女，碩士，研究方向為移動通信與無線技術;楊龍祥，教授,博士生導師，研究方向為移動無線通信系統(tǒng)和物聯(lián)網。

http://www.cnki.net/kcms/detail/61.1450.TP.20160126.1520.036.html

TP301.6

A

1673-629X(2016)02-0069-04

10.3969/j.issn.1673-629X.2016.02.016