一種負載感知的虛擬網絡映射算法?

許建平

（海軍裝備研究院 北京 100073）

1 引言

針對日益豐富的網絡應用，傳統網絡體系結構在靈活性、實時性、便捷性等方面越來越難以適應［1］。為解決該問題，一部分學者對虛擬網絡技術進行了研究，為該問題的解決開辟了新的途徑［2］。虛擬網絡是指通過抽象、分配、隔離機制，在一個公共物理網絡上支持多個虛擬互連架構，各個虛擬互連架構之間協議體系相互獨立的邏輯分成網絡。具有鏈路和節點資源約束的虛擬網絡到物理網絡的映射問題被稱為虛擬網絡映射問題。

針對虛擬網絡映射問題，Wang等［3］所提出了一種自適應虛擬網構建算法（BACA）鏈路負載均衡性和節點負載均衡性都進行了考慮。但BACA算法假定節點映射是已知的，因而只從邊映射的角度來分析虛擬網絡映射問題；Cheng等［4］提出了一種拓撲感知的虛擬網絡映射算法，提高了虛擬網絡請求成功率，但是沒有考慮中間節點的資源消耗；Lischka等［5］考慮了節點及鏈路的映射開銷，但鏈路開銷出現偏差時方法的成功率較低；蔡志平等［6］提出在滿足虛擬網絡資源需求的前提下，將虛擬網絡植入到合適的底層物理節點和鏈路，但該方法的計算復雜度較高；陳曉華等［7］根據底層網絡資源利用率的訓練方法以及主動休眠底層節點和鏈路算法，提高休眠節點和鏈路數量，實現高效節能虛擬網絡映射，但該方法沒有考慮虛擬網絡請求成功率的優化。上述方法均在不同程度上存在網絡負載失衡問題，為此，本文提出了一種負載感知的虛擬網絡映射算法（a workload-aware virtual network map?ping algorithm，WAVNM），同時考慮了基礎網絡的鏈路負載和節點負載，以均衡映射后的虛擬網絡的流量。

2 虛擬網絡映射分析

映射成本是虛擬網絡映射需要解決的核心問題，因此通常以映射成本最小作為優化目標，即物理網絡使用最少的帶寬資源和計算資源來滿足虛擬網絡的需求。在分析虛擬網絡映射問題時，物理網絡可以被看作是一個無向圖GS，其被定義為

其中，為物理網絡的剩余計算資源；為物理網絡的剩余帶寬資源；NS為物理網絡的節點集；LS為物理網絡的鏈路集。

虛擬網絡請求也可以被看作是一個無向圖GV：

其中，為虛擬網絡所需的計算資源；為虛擬網絡所需的鏈路資源。

如果把虛擬網絡映射過程看作是一個映射操作M，其是GV映射成GS的一個子集，并且該子集是GV在GS中的象，即該子集滿足兩個條件，一個是它的計算和鏈路資源不小于，另一個是它的計算和鏈路資源不大于。因此，可表示為

式（3）可以進一步分解成節點映射和鏈路映射：

其中，PS為一組物理鏈路LS的集合，即一條虛擬鏈路可由多條物理鏈路來實現。

3 問題建模

設物理網絡為加權無向圖GS(NS,ES)，其中（M為物理節點個數）是物理網絡節點集合，ES是物理網絡鏈路集合。和分別是總的CPU資源與可用CPU資源，之間的物理鏈路，而分別為的總帶寬與可用帶寬(i,j=1,2,…,M)。由于虛擬映射網絡是物理網絡的子圖，因此，虛擬映射網絡也可以用加權無向圖GV(NV,EV)來表示，其中（N為虛擬映射網絡中的節點個數）是虛擬映射網絡節點集合，EV是虛擬映射網絡鏈路集合。所需的計算資源，而表示虛擬鏈路所需的帶寬。那么，虛擬網絡映射到物理網絡的數學模型為

在實際應用中，虛擬鏈路所對應的物理路徑上的中間節點需要消耗部分CPU資源才能實現數據包的轉發。在本章中，所對應物理路徑上的每個中間節點消耗的CPU資源。令Γ=100CPUunits，Φ=100BWunits，數據包大小為Pn byte，中間節點轉發該數據包需要花費的CPU周期為ω，那么的計算公式為

同時式（7）滿足下列條件：

其中，表示虛擬鏈路所對應的物理路徑上的最小剩余帶寬。式（8）表明物理網絡節點的處理能力能夠滿足自身需求和作為中間節點的需求。式（9）表明虛擬鏈路所對應的物理路徑上的最小剩余帶寬大于鏈路所需的帶寬

為了衡量鏈路負載和節點負載的均衡性，下面對鏈路負載和節點負載進行數據建模。對于物理網絡節點而言，其除了可以作為工作節點來進行計算以外，還可以作為中間節點來進行數據包的轉發，因此，的負載為

那么，整個物理網絡節點的平均負載Navg為

而整個物理網絡節點的負載方差Nσ：

同理，物理鏈路的負載為

其中：所對應的物量鏈包括其它

那么，整個物理網絡鏈路的平均負載Lavg為

而整個物理網絡鏈路的負載方差Lσ為

為了實現鏈路負載和節點負載的雙均衡，本文所定義的目標函數為

其中，α和β分別為節點負載調節因子和鏈路負載調節因子，并且0＜α，β＜1，α+β=1。α（或β）的取值根據Nσ（或Lσ）動態地進行調整。當Nσ（或Lσ）較大時，減少α（或β）的取值，改變虛擬網絡映射，從而實現鏈路負載和節點負載的雙均衡。

4 負載感知虛擬網絡映射算法WAVNM

根據上述分析可知，虛擬網絡映射問題是一個多目標優化問題，并且其已被證明是一個NP-hard問題［8］。對于多目標優化問題，粒子群優化算法是一種常用的求解方法［9］。針對標準粒子群優化算法存在過早收斂［10］和局部最優［11］的問題，因此本文使用改進的粒子群優化算法來進行虛擬網絡映射問題的求解，算法包括初始化和迭代兩個階段。

4.1 初始化階段

首先，我們引入能力衡量參數，該參數的定義為

在初始化階段，WAVNM算法通過以下四個步驟生成初始種群。

1）為GV中的每個虛擬鏈路選擇相對應的GS中的起始節點ns和結束節點ne；起始節點選擇原則：（1）ns未被虛擬鏈路使用；（2）ns的值不小于所有未被虛擬鏈路所使用的節點的能力衡量參數；結束節點選擇原則：（1）ne與ns的最小跳數不大于Nhop；（2）在Nhop范圍內，ns的值最大，并且ns的可用CPU資源能夠滿足需求；（3）在ne與ns之間的所有最短路徑中，選擇一條鏈路負載最小并且滿足式（8）和式（9）的路徑。

2）如果根據步驟1）起始節點選擇原則未找到ns，那么根據步驟1）結束節點選擇原則來選取ns。

3）當ne和ns選擇好后，在ne與ns之間的所有最短路徑中，選擇鏈路負載最小并且滿足式（8）和式（9）的路徑作為兩者的通信路徑。

4）重復步驟1～3），產生規模為Nscale的初始種群。

4.2 迭代求解階段

由于在生成初始種群的時候，并未從整個物理網絡的角度來考慮節點負載和鏈路負載的均衡度，因此需要在迭代階段對映射方案進行調整，改善請求接收成功率、整體資源負載均衡度、長期運營收益［12］等。

在WAVNM算法，每個粒子分別根據式（17）～（18）來進行速度與位置的更新。

其中，Vi為粒子的速度向量；Xi為粒子的位置向量；為第次迭代時，粒子的局部負載均衡值；為第i次迭代時，粒子的局部最優負載均衡值；為第i次迭代時，粒子的全局最優負載均衡值。

4.3 WAVNM算法流程

結合4.1和4.2節，WAVNM算法的流程如下：

1）根據式（16），計算每個粒子的

2）根據式（19），計算c1、c2和c3；

3）根據式（17），計算每個粒子的Vi+1；

4）根據式（18），計算每個粒子的Xi+1，即隨機選取的物理節點nt∈Ns以概率Vi+1替代原ne和nt，選取nt的原則為參照初始化階段的步驟（3）；

5）調整α和β，更新

6）如果達到最大迭代次數，迭代結束，輸出最優的VNM方案；否則，跳到步驟1）開始下一輪迭代。

5 評價指標

為了能夠全面評估本文所提出的負載感知的虛擬網絡映射算法性能，本文所使用的評價指標有：請求接收成功率、整體資源負載均衡度和長期運營收益。

請求接收成功率定義為

其中，Rqss為虛擬網絡映射請求成功數；Rqtl為虛擬網絡請求數。

在t時刻，物理網絡的運營收益定義為虛擬網絡占用的帶寬資源和CPU資源，即

那么，長期運營收益為

6 實驗與分析

為了驗證WAVNM算法性能，本文所使用的部分仿真參數如表1所示。同時，假設物理網絡兩節點相連的概率為0.02，在100個單位時間內虛擬網絡請求的到達率服從λ=5的泊松分布，虛擬網絡的生存時間服從λ=400的負指數分布，虛擬網絡兩節點相連的概率為0.5。

圖1給出了請求接收成功率隨虛擬網絡請求數的變化情況。圖2給出了整體資源負載均衡度隨虛擬網絡請求數的變化情況。圖3給出了長期運營收益隨時間的變化情況。

從圖1中可以看出，當虛擬網絡請求數比較少時，兩種算法的請求接收成功率都在90%以上。因為在虛擬網絡請求數比較少的情況下，物理網絡中節點的可用CPU資源和鏈路的可用帶寬都比較多，所以兩種算法的請求接收成功率都比較高。隨著虛擬網絡請求數的增加，兩種算法的請求接收成功率逐漸減少，但是WAVNM算法的性能一直優于BACA，這是因為WAVNM算法對節點負載和鏈路負載的優化有效消除了中間節點資源不足所造成的網絡瓶頸，實現了更高的求接收成功率。

圖2 整體資源負載均衡度

從圖2中可以看出，WAVNM算法的負載均衡度到要低于BACA。這是因為，每當收到虛擬網絡映射請求后，WAVNM算法會根據當前物理網絡的負載情況自適應地調整節點負載調節因子和鏈路負載調節因子，使得物理網絡中節點負載和鏈路負載更加的均衡，從而提高了整體資源負載均衡度。

從圖3中可以看出，WAVNM算法的長期運營收益遠大于BACA，這是因為與BACA相比，WAVNM算法擁有更高的請求接收成功率，在相同的時間內，WAVNM算法能夠成功地構建更多的虛擬網絡，獲得比BACA算法更高的長期運營收益。

圖3 長期運營收益

7 結語

傳統網絡基礎架構面對不斷涌現的新應用需求越來越力不從心，針對當前虛擬網絡映射算法的不足，本文提出來一種流量感知的虛擬網絡映射算法，該算法同時考慮節點均衡和鏈路均衡兩個問題，并基于多目標優化方法有效實現了問題的綜合求解，仿真實驗證明所提出的算法具備有效性。

參考文獻

［1］王聰，王翠榮，王興偉等.面向云計算的數據中心網絡體系結構設計［J］. 計算機研究與發展，2012，49（2）：286-293.

［2］梅丹，王公寶，胡偉文，張建軍.艦船通信網絡結構復雜性實證分析［J］.艦船電子工程，2014，34（8）：53-55.

［3］Wang Z，WU J，Wang Y，et al.Survivable Virtual Net?work Mapping Using Optimal Backup Topology in Virtual?ized SDN［J］.Communications，China，2014，11（2）：26-37.

［4］Cheng X，Su S，Zhang Z，et al.Virtual Network Embed?ding through Topology-aware Node Ranking［J］.Acm Sig?comm Computer Communication Review，2011，41（2）：38-47.

［5］Lischka J，Karl H.A Virtual Network Mapping Algorithm Based on Subgraph Isomorphism Detection［C］//Proceed?ings of the 1st ACM workshop on Virtualized infrastruc?ture systems and architectures.ACM，2009：81-88.

［6］蔡志平，劉強，呂品等.虛擬網絡映射模型及其優化算法［J］.軟件學報，2012，23（4）：864-877.

［7］陳曉華，李春芝，陳良育等.主動休眠節點鏈路的高效節 能 虛 擬 網 絡 映 射［J］.軟 件 學 報 ，2014（7）：1416-1431.

［8］李偉東，李建平.具有數目約束的負載均衡問題［J］.計算機科學，2015，42（7）：74-77.

［9］申元霞，王國胤，曾傳華.相關性粒子群優化模型［J］.軟件學報，2011，22（4）：696-708.

［10］王皓，高立群，歐陽海濱.多種群隨機差分粒子群優化算法及其應用［J］.哈爾濱工程大學學報，2017，38（4）：652-660.

［11］呂振肅，侯志榮.自適應變異的粒子群優化算法［J］.電子學報，2004，32（3）：416-420.

［12］張建勛，古志民，鄭超.云計算研究進展綜述［J］.電子學報，2010，27（2）：429-433.