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

蔣燕燕，楊龍祥，成聿倫

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

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

蔣燕燕，楊龍祥，成聿倫

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

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

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

0 引 言

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

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

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

(1)劃分虛擬網絡；

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

(3)初始化映射樹；

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

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

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

1.1 物理網絡模型

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

1.2 虛擬網絡模型

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

1.3 映射問題描述

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

圖1 虛擬網絡映射示意圖

2 評價指標

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

(1)網絡收益。

(1)

(2)映射成本。

(2)

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

(3)收益成本比值。

(3)

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

(4)請求接收率。

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

(4)

3 算法描述

3.1 選擇參數

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

(5)

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

(6)

3.2 VNE-RMT算法描述

(1)劃分虛擬網絡。

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

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

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

(7)

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

(3)初始化映射樹。

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

圖2 虛擬網絡樹形拓撲

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

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

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

(8)

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

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

(9)

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

(10)

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

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

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

(11)

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

4 仿真與分析

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

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

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

圖3 虛擬網絡請求接收率

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

圖4 資源平均利用率

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

圖5 平均收益

5 結束語

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

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

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

[8] 朱 強，王慧強，馮光升，等.VNE-ABC:基于人工蜂群的網絡虛擬化映射算法[J].北京工業大學學報，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”高技術發展計劃項目(2013CB329104)

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

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