劉 穎,王 聰,苑 迎,蔣國佳,劉珂禎,王翠榮
(東北大學(xué) 秦皇島分校 計算機與通信工程學(xué)院,河北 秦皇島 066004)
自20世紀(jì)60年代以來,互聯(lián)網(wǎng)得到飛速發(fā)展,已成為現(xiàn)代社會的重要基礎(chǔ)設(shè)施。目前中國網(wǎng)民數(shù)量已達(dá)到8.02億[1],用戶數(shù)量、接入網(wǎng)絡(luò)應(yīng)用軟件數(shù)量的激增,對互聯(lián)網(wǎng)性能提出更高的要求?,F(xiàn)有的互聯(lián)網(wǎng)架構(gòu)在服務(wù)質(zhì)量、響應(yīng)速度等方面很難滿足這些要求,在某種程度上呈現(xiàn)出“僵化”現(xiàn)象。為此,研究人員提出網(wǎng)絡(luò)虛擬化技術(shù),通過應(yīng)用現(xiàn)有的互聯(lián)網(wǎng)架構(gòu),將底層物理網(wǎng)絡(luò)的硬件和軟件資源進行整合,提高了網(wǎng)絡(luò)資源利用率。該技術(shù)在未來互聯(lián)網(wǎng)發(fā)展中極具應(yīng)用前景[2]。虛擬網(wǎng)絡(luò)映射是網(wǎng)絡(luò)虛擬化技術(shù)的一個重要部分,其可在滿足節(jié)點和鏈路資源約束的基礎(chǔ)上將虛擬網(wǎng)絡(luò)映射到物理網(wǎng)絡(luò),從而實現(xiàn)底層資源的高效利用[3]。
在虛擬網(wǎng)絡(luò)映射問題的求解過程中,元啟發(fā)式算法應(yīng)用廣泛[4]。文獻(xiàn)[4]采用一種從大粒子到大粒子、小粒子到小粒子的粒子位置初始化策略,以達(dá)到更好的算法收斂性和底層網(wǎng)絡(luò)負(fù)載平衡。文獻(xiàn)[5]采用多條路徑以提供更好的鏈路映射方案,并將粒子群優(yōu)化算法和遺傳算法相結(jié)合,在不斷迭代的基礎(chǔ)上尋找映射方案。文獻(xiàn)[6]針對網(wǎng)絡(luò)拓?fù)鋱D分解生成的環(huán)和樹結(jié)構(gòu),提出一種基于多元映射算法的改進蟻群算法。文獻(xiàn)[7]提出拓?fù)漕A(yù)配置機制,在映射前先修剪虛擬拓?fù)湟蕴岣哂成涞慕邮苈?。文獻(xiàn)[8]提出一種面向鏈路映射的蟻群系統(tǒng)算法,根據(jù)相連的鏈路資源屬性對節(jié)點進行排序,并在蟻群系統(tǒng)中引入具有連接感知能力的鏈路啟發(fā)式信息,有效地節(jié)省了帶寬。
近年來,隨著能源成本增長和人類生態(tài)意識的提高,網(wǎng)絡(luò)提供商、研究機構(gòu)和互聯(lián)網(wǎng)組件制造商等都試圖從各方面降低互聯(lián)網(wǎng)組件(如軟件)的能耗[9],這在求解虛擬網(wǎng)絡(luò)的映射方案上也有充分體現(xiàn)。文獻(xiàn)[10]針對底層網(wǎng)絡(luò)節(jié)點的異構(gòu)性,優(yōu)選具有最強資源能力的物理節(jié)點,將具有最低能耗的路徑用于鏈路映射。文獻(xiàn)[11]針對大規(guī)模云系統(tǒng)提出整體方案,其中多個數(shù)據(jù)中心通過骨干網(wǎng)絡(luò)互連提供云服務(wù),并提出虛擬機配置的混合整形線性規(guī)劃公式,最大限度地減少虛擬骨干網(wǎng)的功耗和數(shù)據(jù)中心資源使用。文獻(xiàn)[12]提出一種優(yōu)化模型研究數(shù)據(jù)中心的映射節(jié)能問題,同步考慮了與工作負(fù)載有關(guān)和無關(guān)的能耗,并引入用于虛擬網(wǎng)絡(luò)配置的啟發(fā)式方法,在遵守服務(wù)級別協(xié)議的同時降低了能耗。文獻(xiàn)[13]基于虛擬網(wǎng)絡(luò)的動態(tài)特性提出多反饋控制模型,通過關(guān)閉活動節(jié)點和活動鏈路,顯著降低了系統(tǒng)能耗。 文獻(xiàn)[14]優(yōu)先將相鄰虛擬節(jié)點映射到相鄰物理節(jié)點以保持拓?fù)湟恢滦?并減小映射范圍,從而有效地降低了映射成本和系統(tǒng)能耗。研究人員在用于虛擬網(wǎng)絡(luò)資源分配的基本映射方法及映射過程中的能量需求、拓?fù)浣Y(jié)構(gòu)等研究方面已取得一定成果[15],然而大部分研究都圍繞著網(wǎng)絡(luò)資源分配的單個目標(biāo)進行優(yōu)化,在虛擬網(wǎng)絡(luò)資源的實際分配中,通常需要同時考慮映射成本、收益、能耗、服務(wù)質(zhì)量(Quality of Service,QoS)等多目標(biāo)問題。
本文從多目標(biāo)優(yōu)化角度出發(fā),提出一種基于Pareto熵的虛擬網(wǎng)絡(luò)映射VEN-MOPSO算法。使用目標(biāo)空間變換方法[16]計算當(dāng)前最優(yōu)解集的Pareto熵,并以每次迭代后最優(yōu)解集的變化引發(fā)的差熵為依據(jù)評估種群的進化狀態(tài),進而設(shè)計動態(tài)自適應(yīng)的粒子運動參數(shù)策略,控制粒子群搜索的過程,以提高解的優(yōu)化程度。
底層網(wǎng)絡(luò)(Substrate Network,SN)用加權(quán)無向圖表示為:
(1)
虛擬網(wǎng)絡(luò)(Virtual Network,VN)用加權(quán)無向圖表示為:
(2)
虛擬網(wǎng)絡(luò)映射問題(Virtual Network Mapping Problem,VNMP)是將 VN 映射到 SN 的過程,可以形式化地定義為從GV到GS子集的映射[17]。映射過程包括節(jié)點映射過程和鏈路映射過程。
映射過程能耗包括以下兩方面:
1)節(jié)點能耗
網(wǎng)絡(luò)節(jié)點即服務(wù)器節(jié)點,網(wǎng)絡(luò)節(jié)點能耗與該節(jié)點承載的虛擬網(wǎng)絡(luò)節(jié)點總和成正比[13],第i個底層節(jié)點能耗定義為:
(3)
其中,Pb為底層物理節(jié)點能耗的基本值,Pm為底層物理節(jié)點能耗的最大值,u為處理器利用率。
2)鏈路能耗
在網(wǎng)絡(luò)虛擬化環(huán)境中具有減負(fù)引擎裝置,因而網(wǎng)絡(luò)設(shè)備對流量負(fù)荷的能耗不敏感[18]。物理鏈路能耗通常被視為常量[19],第j條鏈路能耗定義為:
(4)
其中,Pn為物理鏈路的能耗。
虛擬網(wǎng)絡(luò)映射優(yōu)化目標(biāo)為映射成本和能耗最小化。用戶的每個虛擬網(wǎng)絡(luò)請求映射模型為:
(5)
其中,f1為網(wǎng)絡(luò)資源開銷,cpu(nv)為虛擬節(jié)點nv所需的計算能力值,bw(lv)為虛擬鏈路lv所需的帶寬能力值,α為計算資源相對權(quán)重,β為帶寬資源相對權(quán)重,且α+β=1,φlv為用來判斷l(xiāng)v是否被映射到物理鏈路上的二進制變量,f2為映射能耗,ti為節(jié)點i開啟的時間,tj為鏈路j開啟的時間。
映射過程還需滿足CUP處理器資源和帶寬資源的約束條件,如式(6)所示:
s.t.?nv∈NV,?ni∈pS,nv→ni,
Ccpu(ni)-∑Ccpu(nv)≥Rcpu(nv)
?lv∈LV,?lj∈pS,lv→lj,
(6)
其中,pS為映射后物理節(jié)點和物理鏈路集合,ni為目標(biāo)物理節(jié)點,nv為映射的虛擬節(jié)點,ni的可用節(jié)點資源不能小于nv所請求的節(jié)點資源,lV為虛擬鏈路,pS為虛擬鏈路所映射的物理路徑,lj為虛擬鏈路所映射物理路徑的每條物理鏈路,lj的空閑帶寬不能小于lV所請求的帶寬。
由于上述優(yōu)化模型的最優(yōu)解不唯一,因此還需進一步設(shè)計映射方案選擇策略。在VNE-MOPSO算法中,每當(dāng)尋找到一個質(zhì)量更高的可行解時,外部最優(yōu)解集(Pareto最優(yōu)解集、外部檔案)就會進行更新。根據(jù)外部最優(yōu)解集的更新情況和差熵等信息,設(shè)計出自適應(yīng)的粒子參數(shù)策略,可促使算法尋找到更多高質(zhì)量的解。以下分別對Pareto最優(yōu)和Pareto熵的相關(guān)定義、外部最優(yōu)解集更新算法、自適應(yīng)粒子參數(shù)策略、VNE-PSO算法的整體流程進行介紹。
定義1對于任意兩個向量u,v∈Ω,稱u占優(yōu)v(或v被u占優(yōu),即Pareto占優(yōu)),記作u?v,當(dāng)且僅當(dāng)?i=1,2,…,m,ui≤vi∧ ?j=1,2,…,m,uj 定義2一個解x*∈Ω被稱為Pareto最優(yōu)解或非占優(yōu)解,當(dāng)且僅當(dāng)?x∈Ω:x?x*[16]。所有的Pareto最優(yōu)解的集合PS={x*|?x∈Ω:x?x*)}稱為Pareto最優(yōu)解集。 定義3所有Pareto最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值所形成的區(qū)域PF={F(x*)|x*)∈PS}稱為Pareto前端、Pareto前沿或Pareto均衡面[16]。 Pareto熵多目標(biāo)優(yōu)化模型以兩次迭代的Pareto差熵為優(yōu)化依據(jù)。首先將存儲在外部最優(yōu)解集中的多維Pareto解以目標(biāo)空間轉(zhuǎn)換方式映射到二維平面,然后求出每個Pareto解的平行格坐標(biāo)以及近似Pareto前端的Pareto熵。當(dāng)外部最優(yōu)解集更新時,會導(dǎo)致近似Pareto前端的Pareto熵發(fā)生變化,即產(chǎn)生差熵。差熵是控制優(yōu)化過程的有效信息。 將多維Pareto解按照平行坐標(biāo)方式轉(zhuǎn)化到二維平面中,其映射的整數(shù)值坐標(biāo)即為平行格坐標(biāo)[16],計算公式為: (7) 在第t次迭代過程中,外部最優(yōu)解集近似Pareto前端的Pareto熵Entropy(t)[16]的計算公式為: (8) 其中,Cellk,m(t)為Pareto解的格坐標(biāo)分量落在平行格坐標(biāo)系統(tǒng)第k行第m列方格的個數(shù)。 當(dāng)外部最優(yōu)解集容量已滿時,再次更新需評估解的個體密度。根據(jù)式(7),將外部最優(yōu)解集的成員映射到平行格坐標(biāo)系統(tǒng)后,任意解的個體密度[16]的計算公式為: (9) (10) 其中,Pi為任意解,Density(Pi)為任意解的個體密度,i,j=1,2,…,K(K為外部最優(yōu)解集中成員個數(shù)),Pj為外部最優(yōu)解集中除Pi之外的Pareto解,PCD(Pi,Pj)為Pi和Pj之間的平行格距離。 隨著粒子群不斷搜索到新解,外部最優(yōu)解集不斷更新。VNE-PSO算法在每次迭代中的進化狀態(tài)包括以下3種: 1)停滯狀態(tài):VNE-PSO算法得到的新解被外部最優(yōu)解集拒絕。 2)多樣化狀態(tài):VNE-PSO算法得到的新解取代外部最優(yōu)解集中質(zhì)量較差的舊解。 3)收斂狀態(tài):在目標(biāo)空間中VNE-PSO算法產(chǎn)生的Pareto前端向真實的Pareto前端靠近。 外部最優(yōu)解集的更新過程包括5種情形,各種情形對應(yīng)的進化狀態(tài)和差熵如表1所示,其中M為優(yōu)化目標(biāo)個數(shù),K為外部最優(yōu)解集最大容量。 表1 外部最優(yōu)解集更新過程分析Table 1 Updating process analysis of external optimal solution set 根據(jù)上述5種情形可得出外部最優(yōu)解集更新算法如下: 算法1外部最優(yōu)解集更新算法 輸入 待更新的外部最優(yōu)解集A 外部最優(yōu)解集的最大容量K 進化算法獲得的新解P 輸出 更新后的外部最優(yōu)解集A′ 進化狀態(tài)state(取值0,1,2.分別表示停滯狀態(tài),多樣化狀態(tài),收斂狀態(tài)) 差熵ΔEntropy 1.If (A=?){ A′={P};state=2;ΔEntropy=log M; ReturnA′,state,ΔEntropy;} /* 情形 I:外部最優(yōu)解集為空集,收斂狀態(tài)*/ 2.If (P被A中的任意一個成員ai∈A占優(yōu)) { state=0;ΔEntropy=0; ReturnA,state,ΔEntropy;} /* 情形 II:新解被舊解占優(yōu),停滯狀態(tài) */ 3.If (對任意ai∈A,ai被P占優(yōu)) { 被P占優(yōu)的舊解個數(shù)記為r,當(dāng)前A的成員個數(shù)記為|A|,首先令A(yù)=A/{ai}。 Else if (1 4.If (|A| A′=A∪{P};state=2; Return A′,state,ΔEntropy;} /* 情形 III:新解占優(yōu)舊解,收斂狀態(tài)*/ 5.Else if (|A|==K) { 6.令 B=A∪{P},對B中每一個成員bi∈B,評估bi的個體密度。 7.查找B中具有最大個體密度的成員 bmax。 8.If (P==bmax) { A′=A;state=0;ΔEntropy=0; Return A′,state,ΔEntropy;} /* 情形 IV:新解質(zhì)量最差,停滯狀態(tài)*/ 9.Else { Return A′,state,ΔEntropy;} /* 情形 V:新解替換質(zhì)量最差的舊解,多樣化狀態(tài) */ } Vi+1=ωVi+c1(pBesti-Xi)+c2(gBesti-Xi) (11) Xi+1=Xi+Vi+1 (12) 其中,ω為慣性權(quán)重,c1為學(xué)習(xí)權(quán)重,c2為群體權(quán)重,且ω、c1、c2均大于0,位置向量pBesti為個體最優(yōu)解,位置向量gBesti為整個群體的全局最優(yōu)解。 為了更好地控制進化過程,需要持續(xù)從進化環(huán)境中獲取實時反饋信息,可通過調(diào)整粒子運動參數(shù)ω、c1、c2調(diào)控搜索趨向。將進化狀態(tài)和差熵作為運動參數(shù)的因變量: (13) (14) (15) 其中,Lenω為ω的區(qū)間長度,Lenc1為c1的區(qū)間長度,Lenc2為c2的區(qū)間長度,按照文獻(xiàn)[20],ω、c1和c2的取值范圍分別為[0.4,0.9]、[0.5,2.5]和[0.5,2.5],即區(qū)間長度分別為0.5、2.0和2.0。 VNE-MOPSO算法的整體流程為:對于每一個虛擬網(wǎng)絡(luò)請求,首先隨機生成粒子的初始位置,每獲得一個新位置就判斷其是否可行,再更新外部最優(yōu)解集以獲得進化狀態(tài)和差熵,并由自適應(yīng)粒子運動參數(shù)策略更新粒子速度和位置,直到迭代結(jié)束。其中,通過式(11)位置減法進行同或運算,得到的速度向量Vi+1采用概率映射方式轉(zhuǎn)化為二進制數(shù)值,具體做法為:使用sigmoid函數(shù)將Vi+1映射到[0,1]區(qū)間作為概率,如果該概率大于或等于隨機生成的[0,1]區(qū)間的小數(shù),則下一步速度取值為1,否則取值為0,如式(16)所示: (16) 通過式(12) 更新粒子位置,將速度分量值為1的虛擬節(jié)點重新隨機映射到一個滿足節(jié)點約束條件的物理節(jié)點上。 VNE-MOPSO算法偽代碼算法如下: 算法2基于Pareto熵的虛擬網(wǎng)絡(luò)映射算法(VNE-MOPSO) 輸入虛擬網(wǎng)絡(luò)Gv,物理網(wǎng)絡(luò)Gs 輸出映射方案 solution 1.獲得Gs中實時空閑資源的節(jié)點隊列和鏈路隊列; 2.對于群體中的每個粒子,初始化其位置。 3.初始化令全局外部最優(yōu)解集gArchive=?,令個體外部最優(yōu)解集pArchive=?; 4.For (int i=0;i < MaxItCount;i++){ 5.If (當(dāng)前位置可行){ 6.用最短路徑方式得出映射方案,計算相應(yīng)的目標(biāo)函數(shù)值f1、f2; 7.對每個粒子調(diào)用算法1,更新gArchive,保存此時的進化狀態(tài)、差熵; 8.對每個粒子調(diào)用算法1,更新pArchive; 9.從gArchive中隨機地選取一個解,作為群體最優(yōu)解gBest; 10.從pArchive中選取距群體最優(yōu)解gBest最近的一個解,作為個體最優(yōu)解pBest; 11.根據(jù)式(11),由進化狀態(tài)、差熵,計算ω、c1、c2的值; 12.根據(jù)式(9)、式(10)、式(12),更新粒子的速度和位置;} 13.Else if (當(dāng)前位置不可行){ 隨機調(diào)整粒子位置;} 14.If (gArchive連續(xù)8輪不變){ 算法終止;} } 15.If (gArchive≠?){從gArchive中隨機選出一個解作為映射方案。} 本文分別采用VNE-MOPSO算法與文獻(xiàn)[4]中單目標(biāo)映射VNE-UEPSO算法通過CloudSim3.0.3軟件平臺進行2組仿實驗。第1組實驗將不同虛擬鏈路帶寬容量下由兩種算法得到的物理網(wǎng)絡(luò)映射成本和能耗進行對比;第2組實驗將虛擬鏈路帶寬容量為600~3 000時由兩種算法得到的物理網(wǎng)絡(luò)節(jié)點利用率和長期平均收益進行對比。2組實驗分別對2 000個虛擬網(wǎng)絡(luò)請求進行測試。為保證拓?fù)涠鄻有?使用節(jié)點數(shù)量范圍、節(jié)點連通度、資源范圍等為參數(shù)生成隨機拓?fù)渚W(wǎng)絡(luò)。計算資源和帶寬資源的相對權(quán)重比均為1∶1,運動參數(shù)ω、c1、c2初值分別為0.85、0.7、2.3,能耗參數(shù)Pm、Pb、Pn分別為300、150、15,外部最優(yōu)解集最大容量為5。物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)的具體實驗參數(shù)如表2所示。 表2 不同網(wǎng)絡(luò)的實驗參數(shù)Table 2 Experimental parameters of different networks 由圖1和圖2可以看出,采用VNE-MOPSO算法能減少物理網(wǎng)絡(luò)的映射成本和能耗。在底層網(wǎng)絡(luò)空閑較多時(虛擬網(wǎng)絡(luò)請求數(shù)量為0~800),采用兩種算法得到的物理網(wǎng)絡(luò)映射成本和能耗差異不大,這是因為前期物理網(wǎng)絡(luò)資源充足,粒子群算法搜索能力強,VNE-MOPSO算法的優(yōu)化效果不明顯。隨著虛擬網(wǎng)絡(luò)請求數(shù)量增多,VNE-MOPSO算法優(yōu)化效果不斷增強,最終在帶寬容量為200~1 000和600~3 000下比采用VNE-UEPSO算法分別減少了6.88%、3.63%的映射成本和4.64%、9.81%的能耗。 圖1 不同虛擬鏈路帶寬容量下采用兩種算法得到的物理網(wǎng)絡(luò)映射成本Fig.1 Physical network mapping cost under different virtual link bandwidth capacity using two algorithms 圖2 不同虛擬鏈路帶寬容量下采用兩種算法得到的物理網(wǎng)絡(luò)能耗Fig.2 Physical network energy consumption under different virtual link bandwidth capacity using two algorithms 此外,隨著虛擬鏈路帶寬容量的增大,采用兩種算法得到的物理網(wǎng)絡(luò)映射成本越高,VNE-MOPSO算法對映射成本的優(yōu)化效果越好。當(dāng)虛擬鏈路帶寬容量為200~1 000時,物理網(wǎng)絡(luò)的能耗比虛擬鏈路帶寬容量為600~3 000時要高,這是因為物理網(wǎng)絡(luò)能耗由已開啟的物理節(jié)點和鏈路數(shù)量、物理節(jié)點負(fù)載情況共同決定,能耗與虛擬鏈路的帶寬容量無關(guān)。 由圖3可以看出,在不同虛擬鏈路帶寬容量下,采用VNE-MOPSO算法的運行時間比采用VNE-UEPSO算法更少,映射效率也更高。這是因為VNE-MOPSO算法具有根據(jù)外部最優(yōu)解集反饋動態(tài)調(diào)整粒子群算法運動參數(shù)的機制,在迭代過程中不斷促進種群進行更加有效地搜索,從而能提高尋找最優(yōu)解的效率。 圖3 不同虛擬鏈路帶寬容量下采用兩種算法得到的運行時間Fig.3 Operation time under different virtual link bandwidth capacity using two algorithms 由圖4和圖5可以看出,隨著運行時間的增加,采用VNE-MOPSO算法得到的物理網(wǎng)絡(luò)節(jié)點利用率和長期平均收益比采用VNE-UEPSO算法得到的更高。這是因為VNE-MOPSO算法以減少物理網(wǎng)絡(luò)的映射成本和能耗為優(yōu)化目標(biāo),在進化過程中兼顧Pareto前端的多樣性和收斂性,節(jié)省物理網(wǎng)絡(luò)資源,并加快映射速度。由圖5還可以看出,在運行初期,隨著運行時間的增加,采用兩種算法得到的物理網(wǎng)絡(luò)長期平均收益均呈現(xiàn)下降趨勢。這是因為在運行初期底層物理網(wǎng)絡(luò)資源充足,映射效率較高,收益較高;隨著運行時間的增加,底層物理網(wǎng)絡(luò)資源逐漸減少,映射效率降低,收益下降;當(dāng)占用物理資源、釋放物理資源的過程逐漸達(dá)到平穩(wěn)時,長期平均收益趨于穩(wěn)定。 圖4 采用不同算法得到的物理網(wǎng)絡(luò)節(jié)點資源利用率隨運行時間變化曲線Fig.4 Resource utilization rate of physical network nodes vs running time curve using different algorithms 圖5 采用不同算法得到的物理網(wǎng)絡(luò)長期平均收益隨時間變化曲線Fig.5 Long term average income of physical network nodes vs running time curve using different algorithms 本文提出一種基于Pareto熵的多目標(biāo)粒子群優(yōu)化虛擬網(wǎng)絡(luò)映射算法。將Pareto熵多目標(biāo)優(yōu)化模型與粒子群算法相結(jié)合,在保證物理網(wǎng)絡(luò)資源租賃收益的同時兼顧能耗開銷,根據(jù)外部Pareto解集的更新狀況調(diào)整粒子運動參數(shù),控制搜索過程,最終降低映射成本和能耗,同時實現(xiàn)良好的長期平均收益。 仿真結(jié)果表明,該算法在收益、能耗和求解效率方面較單目標(biāo)優(yōu)化算法均有所提升。下一步將在本文算法的基礎(chǔ)上引入虛擬網(wǎng)絡(luò)服務(wù)質(zhì)量作為額外參數(shù),以實現(xiàn)更多目標(biāo)的同時優(yōu)化。2.2 Pareto熵多目標(biāo)優(yōu)化模型及進化狀態(tài)
2.3 外部最優(yōu)解集更新算法
2.4 粒子群優(yōu)化算法
2.5 自適應(yīng)粒子運動參數(shù)策略
2.6 VNE-MOPSO算法整體流程
3 仿真結(jié)果與分析
4 結(jié)束語