許建平
(海軍裝備研究院 北京 100073)
針對日益豐富的網(wǎng)絡(luò)應(yīng)用,傳統(tǒng)網(wǎng)絡(luò)體系結(jié)構(gòu)在靈活性、實時性、便捷性等方面越來越難以適應(yīng)[1]。為解決該問題,一部分學(xué)者對虛擬網(wǎng)絡(luò)技術(shù)進行了研究,為該問題的解決開辟了新的途徑[2]。虛擬網(wǎng)絡(luò)是指通過抽象、分配、隔離機制,在一個公共物理網(wǎng)絡(luò)上支持多個虛擬互連架構(gòu),各個虛擬互連架構(gòu)之間協(xié)議體系相互獨立的邏輯分成網(wǎng)絡(luò)。具有鏈路和節(jié)點資源約束的虛擬網(wǎng)絡(luò)到物理網(wǎng)絡(luò)的映射問題被稱為虛擬網(wǎng)絡(luò)映射問題。
針對虛擬網(wǎng)絡(luò)映射問題,Wang等[3]所提出了一種自適應(yīng)虛擬網(wǎng)構(gòu)建算法(BACA)鏈路負載均衡性和節(jié)點負載均衡性都進行了考慮。但BACA算法假定節(jié)點映射是已知的,因而只從邊映射的角度來分析虛擬網(wǎng)絡(luò)映射問題;Cheng等[4]提出了一種拓撲感知的虛擬網(wǎng)絡(luò)映射算法,提高了虛擬網(wǎng)絡(luò)請求成功率,但是沒有考慮中間節(jié)點的資源消耗;Lischka等[5]考慮了節(jié)點及鏈路的映射開銷,但鏈路開銷出現(xiàn)偏差時方法的成功率較低;蔡志平等[6]提出在滿足虛擬網(wǎng)絡(luò)資源需求的前提下,將虛擬網(wǎng)絡(luò)植入到合適的底層物理節(jié)點和鏈路,但該方法的計算復(fù)雜度較高;陳曉華等[7]根據(jù)底層網(wǎng)絡(luò)資源利用率的訓(xùn)練方法以及主動休眠底層節(jié)點和鏈路算法,提高休眠節(jié)點和鏈路數(shù)量,實現(xiàn)高效節(jié)能虛擬網(wǎng)絡(luò)映射,但該方法沒有考慮虛擬網(wǎng)絡(luò)請求成功率的優(yōu)化。上述方法均在不同程度上存在網(wǎng)絡(luò)負載失衡問題,為此,本文提出了一種負載感知的虛擬網(wǎng)絡(luò)映射算法(a workload-aware virtual network map?ping algorithm,WAVNM),同時考慮了基礎(chǔ)網(wǎng)絡(luò)的鏈路負載和節(jié)點負載,以均衡映射后的虛擬網(wǎng)絡(luò)的流量。
映射成本是虛擬網(wǎng)絡(luò)映射需要解決的核心問題,因此通常以映射成本最小作為優(yōu)化目標,即物理網(wǎng)絡(luò)使用最少的帶寬資源和計算資源來滿足虛擬網(wǎng)絡(luò)的需求。在分析虛擬網(wǎng)絡(luò)映射問題時,物理網(wǎng)絡(luò)可以被看作是一個無向圖GS,其被定義為
其中,為物理網(wǎng)絡(luò)的剩余計算資源;為物理網(wǎng)絡(luò)的剩余帶寬資源;NS為物理網(wǎng)絡(luò)的節(jié)點集;LS為物理網(wǎng)絡(luò)的鏈路集。
虛擬網(wǎng)絡(luò)請求也可以被看作是一個無向圖GV:
其中,為虛擬網(wǎng)絡(luò)所需的計算資源;為虛擬網(wǎng)絡(luò)所需的鏈路資源。
如果把虛擬網(wǎng)絡(luò)映射過程看作是一個映射操作M,其是GV映射成GS的一個子集,并且該子集是GV在GS中的象,即該子集滿足兩個條件,一個是它的計算和鏈路資源不小于,另一個是它的計算和鏈路資源不大于。因此,可表示為
式(3)可以進一步分解成節(jié)點映射和鏈路映射:
其中,PS為一組物理鏈路LS的集合,即一條虛擬鏈路可由多條物理鏈路來實現(xiàn)。
設(shè)物理網(wǎng)絡(luò)為加權(quán)無向圖GS(NS,ES),其中(M為物理節(jié)點個數(shù))是物理網(wǎng)絡(luò)節(jié)點集合,ES是物理網(wǎng)絡(luò)鏈路集合。和分別是總的CPU資源與可用CPU資源,之間的物理鏈路,而分別為的總帶寬與可用帶寬(i,j=1,2,…,M)。由于虛擬映射網(wǎng)絡(luò)是物理網(wǎng)絡(luò)的子圖,因此,虛擬映射網(wǎng)絡(luò)也可以用加權(quán)無向圖GV(NV,EV)來表示,其中(N為虛擬映射網(wǎng)絡(luò)中的節(jié)點個數(shù))是虛擬映射網(wǎng)絡(luò)節(jié)點集合,EV是虛擬映射網(wǎng)絡(luò)鏈路集合。所需的計算資源,而表示虛擬鏈路所需的帶寬。那么,虛擬網(wǎng)絡(luò)映射到物理網(wǎng)絡(luò)的數(shù)學(xué)模型為
在實際應(yīng)用中,虛擬鏈路所對應(yīng)的物理路徑上的中間節(jié)點需要消耗部分CPU資源才能實現(xiàn)數(shù)據(jù)包的轉(zhuǎn)發(fā)。在本章中,所對應(yīng)物理路徑上的每個中間節(jié)點消耗的CPU資源。令Γ=100CPUunits,Φ=100BWunits,數(shù)據(jù)包大小為Pn byte,中間節(jié)點轉(zhuǎn)發(fā)該數(shù)據(jù)包需要花費的CPU周期為ω,那么的計算公式為
同時式(7)滿足下列條件:
其中,表示虛擬鏈路所對應(yīng)的物理路徑上的最小剩余帶寬。式(8)表明物理網(wǎng)絡(luò)節(jié)點的處理能力能夠滿足自身需求和作為中間節(jié)點的需求。式(9)表明虛擬鏈路所對應(yīng)的物理路徑上的最小剩余帶寬大于鏈路所需的帶寬
為了衡量鏈路負載和節(jié)點負載的均衡性,下面對鏈路負載和節(jié)點負載進行數(shù)據(jù)建模。對于物理網(wǎng)絡(luò)節(jié)點而言,其除了可以作為工作節(jié)點來進行計算以外,還可以作為中間節(jié)點來進行數(shù)據(jù)包的轉(zhuǎn)發(fā),因此,的負載為
那么,整個物理網(wǎng)絡(luò)節(jié)點的平均負載Navg為
而整個物理網(wǎng)絡(luò)節(jié)點的負載方差Nσ:
同理,物理鏈路的負載為
其中:所對應(yīng)的物量鏈包括其它
那么,整個物理網(wǎng)絡(luò)鏈路的平均負載Lavg為
而整個物理網(wǎng)絡(luò)鏈路的負載方差Lσ為
為了實現(xiàn)鏈路負載和節(jié)點負載的雙均衡,本文所定義的目標函數(shù)為
其中,α和β分別為節(jié)點負載調(diào)節(jié)因子和鏈路負載調(diào)節(jié)因子,并且0<α,β<1,α+β=1。α(或β)的取值根據(jù)Nσ(或Lσ)動態(tài)地進行調(diào)整。當Nσ(或Lσ)較大時,減少α(或β)的取值,改變虛擬網(wǎng)絡(luò)映射,從而實現(xiàn)鏈路負載和節(jié)點負載的雙均衡。
根據(jù)上述分析可知,虛擬網(wǎng)絡(luò)映射問題是一個多目標優(yōu)化問題,并且其已被證明是一個NP-hard問題[8]。對于多目標優(yōu)化問題,粒子群優(yōu)化算法是一種常用的求解方法[9]。針對標準粒子群優(yōu)化算法存在過早收斂[10]和局部最優(yōu)[11]的問題,因此本文使用改進的粒子群優(yōu)化算法來進行虛擬網(wǎng)絡(luò)映射問題的求解,算法包括初始化和迭代兩個階段。
首先,我們引入能力衡量參數(shù),該參數(shù)的定義為
在初始化階段,WAVNM算法通過以下四個步驟生成初始種群。
1)為GV中的每個虛擬鏈路選擇相對應(yīng)的GS中的起始節(jié)點ns和結(jié)束節(jié)點ne;起始節(jié)點選擇原則:(1)ns未被虛擬鏈路使用;(2)ns的值不小于所有未被虛擬鏈路所使用的節(jié)點的能力衡量參數(shù);結(jié)束節(jié)點選擇原則:(1)ne與ns的最小跳數(shù)不大于Nhop;(2)在Nhop范圍內(nèi),ns的值最大,并且ns的可用CPU資源能夠滿足需求;(3)在ne與ns之間的所有最短路徑中,選擇一條鏈路負載最小并且滿足式(8)和式(9)的路徑。
2)如果根據(jù)步驟1)起始節(jié)點選擇原則未找到ns,那么根據(jù)步驟1)結(jié)束節(jié)點選擇原則來選取ns。
3)當ne和ns選擇好后,在ne與ns之間的所有最短路徑中,選擇鏈路負載最小并且滿足式(8)和式(9)的路徑作為兩者的通信路徑。
4)重復(fù)步驟1~3),產(chǎn)生規(guī)模為Nscale的初始種群。
由于在生成初始種群的時候,并未從整個物理網(wǎng)絡(luò)的角度來考慮節(jié)點負載和鏈路負載的均衡度,因此需要在迭代階段對映射方案進行調(diào)整,改善請求接收成功率、整體資源負載均衡度、長期運營收益[12]等。
在WAVNM算法,每個粒子分別根據(jù)式(17)~(18)來進行速度與位置的更新。
其中,Vi為粒子的速度向量;Xi為粒子的位置向量;為第次迭代時,粒子的局部負載均衡值;為第i次迭代時,粒子的局部最優(yōu)負載均衡值;為第i次迭代時,粒子的全局最優(yōu)負載均衡值。
結(jié)合4.1和4.2節(jié),WAVNM算法的流程如下:
1)根據(jù)式(16),計算每個粒子的
2)根據(jù)式(19),計算c1、c2和c3;
3)根據(jù)式(17),計算每個粒子的Vi+1;
4)根據(jù)式(18),計算每個粒子的Xi+1,即隨機選取的物理節(jié)點nt∈Ns以概率Vi+1替代原ne和nt,選取nt的原則為參照初始化階段的步驟(3);
5)調(diào)整α和β,更新
6)如果達到最大迭代次數(shù),迭代結(jié)束,輸出最優(yōu)的VNM方案;否則,跳到步驟1)開始下一輪迭代。
為了能夠全面評估本文所提出的負載感知的虛擬網(wǎng)絡(luò)映射算法性能,本文所使用的評價指標有:請求接收成功率、整體資源負載均衡度和長期運營收益。
請求接收成功率定義為
其中,Rqss為虛擬網(wǎng)絡(luò)映射請求成功數(shù);Rqtl為虛擬網(wǎng)絡(luò)請求數(shù)。
在t時刻,物理網(wǎng)絡(luò)的運營收益定義為虛擬網(wǎng)絡(luò)占用的帶寬資源和CPU資源,即
那么,長期運營收益為
為了驗證WAVNM算法性能,本文所使用的部分仿真參數(shù)如表1所示。同時,假設(shè)物理網(wǎng)絡(luò)兩節(jié)點相連的概率為0.02,在100個單位時間內(nèi)虛擬網(wǎng)絡(luò)請求的到達率服從λ=5的泊松分布,虛擬網(wǎng)絡(luò)的生存時間服從λ=400的負指數(shù)分布,虛擬網(wǎng)絡(luò)兩節(jié)點相連的概率為0.5。
圖1給出了請求接收成功率隨虛擬網(wǎng)絡(luò)請求數(shù)的變化情況。圖2給出了整體資源負載均衡度隨虛擬網(wǎng)絡(luò)請求數(shù)的變化情況。圖3給出了長期運營收益隨時間的變化情況。
從圖1中可以看出,當虛擬網(wǎng)絡(luò)請求數(shù)比較少時,兩種算法的請求接收成功率都在90%以上。因為在虛擬網(wǎng)絡(luò)請求數(shù)比較少的情況下,物理網(wǎng)絡(luò)中節(jié)點的可用CPU資源和鏈路的可用帶寬都比較多,所以兩種算法的請求接收成功率都比較高。隨著虛擬網(wǎng)絡(luò)請求數(shù)的增加,兩種算法的請求接收成功率逐漸減少,但是WAVNM算法的性能一直優(yōu)于BACA,這是因為WAVNM算法對節(jié)點負載和鏈路負載的優(yōu)化有效消除了中間節(jié)點資源不足所造成的網(wǎng)絡(luò)瓶頸,實現(xiàn)了更高的求接收成功率。
圖2 整體資源負載均衡度
從圖2中可以看出,WAVNM算法的負載均衡度到要低于BACA。這是因為,每當收到虛擬網(wǎng)絡(luò)映射請求后,WAVNM算法會根據(jù)當前物理網(wǎng)絡(luò)的負載情況自適應(yīng)地調(diào)整節(jié)點負載調(diào)節(jié)因子和鏈路負載調(diào)節(jié)因子,使得物理網(wǎng)絡(luò)中節(jié)點負載和鏈路負載更加的均衡,從而提高了整體資源負載均衡度。
從圖3中可以看出,WAVNM算法的長期運營收益遠大于BACA,這是因為與BACA相比,WAVNM算法擁有更高的請求接收成功率,在相同的時間內(nèi),WAVNM算法能夠成功地構(gòu)建更多的虛擬網(wǎng)絡(luò),獲得比BACA算法更高的長期運營收益。
圖3 長期運營收益
傳統(tǒng)網(wǎng)絡(luò)基礎(chǔ)架構(gòu)面對不斷涌現(xiàn)的新應(yīng)用需求越來越力不從心,針對當前虛擬網(wǎng)絡(luò)映射算法的不足,本文提出來一種流量感知的虛擬網(wǎng)絡(luò)映射算法,該算法同時考慮節(jié)點均衡和鏈路均衡兩個問題,并基于多目標優(yōu)化方法有效實現(xiàn)了問題的綜合求解,仿真實驗證明所提出的算法具備有效性。
參考文獻
[1]王聰,王翠榮,王興偉等.面向云計算的數(shù)據(jù)中心網(wǎng)絡(luò)體系結(jié)構(gòu)設(shè)計[J]. 計算機研究與發(fā)展,2012,49(2):286-293.
[2]梅丹,王公寶,胡偉文,張建軍.艦船通信網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜性實證分析[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]蔡志平,劉強,呂品等.虛擬網(wǎng)絡(luò)映射模型及其優(yōu)化算法[J].軟件學(xué)報,2012,23(4):864-877.
[7]陳曉華,李春芝,陳良育等.主動休眠節(jié)點鏈路的高效節(jié) 能 虛 擬 網(wǎng) 絡(luò) 映 射[J].軟 件 學(xué) 報 ,2014(7):1416-1431.
[8]李偉東,李建平.具有數(shù)目約束的負載均衡問題[J].計算機科學(xué),2015,42(7):74-77.
[9]申元霞,王國胤,曾傳華.相關(guān)性粒子群優(yōu)化模型[J].軟件學(xué)報,2011,22(4):696-708.
[10]王皓,高立群,歐陽海濱.多種群隨機差分粒子群優(yōu)化算法及其應(yīng)用[J].哈爾濱工程大學(xué)學(xué)報,2017,38(4):652-660.
[11]呂振肅,侯志榮.自適應(yīng)變異的粒子群優(yōu)化算法[J].電子學(xué)報,2004,32(3):416-420.
[12]張建勛,古志民,鄭超.云計算研究進展綜述[J].電子學(xué)報,2010,27(2):429-433.