基于k最短路徑算法優(yōu)化與負載均衡的虛擬網(wǎng)絡(luò)映射機制

高 斐,陳德禮,洪家軍,于 智,田 甜

(1.莆田學(xué)院 信息工程學(xué)院,福建 莆田 351100; 2.浙江大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,杭州 310027; 3.審計署駐上海特派員辦事處,上海 200051)

0 概述

隨著網(wǎng)絡(luò)技術(shù)的快速發(fā)展,互聯(lián)網(wǎng)已經(jīng)成為現(xiàn)代社會的重要基礎(chǔ)設(shè)施,越來越多的行業(yè)需要借助互聯(lián)網(wǎng)傳遞信息實現(xiàn)數(shù)據(jù)交換和資源共享,而互連網(wǎng)在區(qū)域擴大或資源使用方面出現(xiàn)了瓶頸,物理網(wǎng)絡(luò)資源的稀缺問題慢慢浮現(xiàn)出來。為了提高物理網(wǎng)絡(luò)資源的使用率,一些研究機構(gòu)開始利用虛擬網(wǎng)絡(luò)映射技術(shù)提升底層物理網(wǎng)絡(luò)的資源利用率。虛擬網(wǎng)絡(luò)映射技術(shù)即將物理資源按照節(jié)點和鏈路資源分配給不同的虛擬用戶,滿足不同用戶的服務(wù)需求,使得底層物理網(wǎng)絡(luò)能夠最大化地將資源分配給網(wǎng)絡(luò)用戶。虛擬網(wǎng)絡(luò)技術(shù)既減少了底層物理資源的浪費,又減少了重新構(gòu)建物理網(wǎng)絡(luò)而投入的新成本,有效解決了互聯(lián)網(wǎng)發(fā)展過程中遇到的僵化問題。目前,國外的研究機構(gòu)GENI[1]對全球網(wǎng)絡(luò)環(huán)境進行創(chuàng)新性改革,一個大規(guī)模的分布式的虛擬網(wǎng)絡(luò)環(huán)境正在逐步完善。本文從全網(wǎng)的節(jié)點和鏈路負載均衡性展開研究,提出一種基于k最短路徑算法優(yōu)化和負載均衡的虛擬網(wǎng)絡(luò)映射機制。

1 相關(guān)工作

由于物理網(wǎng)絡(luò)本身存在節(jié)點和鏈路映射的地理位置限制,資源大小限制,用戶對服務(wù)質(zhì)量要求限制,以及NP難等問題[2-3],虛擬網(wǎng)絡(luò)映射技術(shù)一直是科研人員長期攻克的研究課題。文獻[4]將信任關(guān)系和信任度引入到虛擬網(wǎng)絡(luò)資源分配中,分析網(wǎng)絡(luò)虛擬化環(huán)境中的安全問題,提出基于信任感知的虛擬網(wǎng)絡(luò)映射算法,該方法從用戶的服務(wù)安全性來考慮。文獻[5]針對網(wǎng)絡(luò)設(shè)備出現(xiàn)能耗浪費,資源利用率不足等問題,提出通過將流量負載不敏感的節(jié)點進行資源整合,利用休眠技術(shù)實現(xiàn)網(wǎng)絡(luò)節(jié)能,該方法從滿足網(wǎng)絡(luò)資源節(jié)能和提升資源使用率的角度來考慮。除此之外,還有從提高物理網(wǎng)絡(luò)總收益的角度[6],從網(wǎng)絡(luò)拓撲特性,從降低映射成本[7]為目標來展開研究。它們都是從不同角度對虛擬映射進行了研究。虛擬網(wǎng)絡(luò)映射過程大致分為2種,一種是基于最優(yōu)化的啟發(fā)式算法[8-10],它通過滿足某個條件使模型參數(shù)達到最優(yōu),通?？稍诤侠淼臅r間找出問題的最優(yōu)解。從數(shù)學(xué)意義上來說,它是研究如何選出最合適的變量取值,使得目標函數(shù)實現(xiàn)最大化或最小化的問題[11]。另一種是根據(jù)不同的環(huán)境建立模型,從而滿足虛擬用戶的服務(wù)質(zhì)量需求,該方法既可以實現(xiàn)局部最優(yōu)解,也可以實現(xiàn)全局最優(yōu)解。本課題研究的內(nèi)容鑒于后者。

在虛擬映射過程中,按照節(jié)點和鏈路映射的順序來劃分可以分為一步映射和兩步映射。一步映射主要指虛擬節(jié)點和鏈路同時映射,一步映射是進行節(jié)點和鏈路的同時映射,但此種算法的時間和空間復(fù)雜度較高。而兩步映射算法在算法復(fù)雜度和映射效果方面有著較好的平衡,因此,本文選用兩步映射策略。為了提高虛擬用戶的成功映射率,很多文獻運用貪婪思想優(yōu)先考慮資源最大的節(jié)點資源進行映射,或者節(jié)點和相鄰鏈路資源總和最大的局部區(qū)域進行映射[12-13],但此方法沒有考慮全網(wǎng)節(jié)點和鏈路負載的均衡性。

如果依賴貪婪思想獲得最大資源的節(jié)點或鏈路進行映射,在映射過程中,可能會在固定節(jié)點或固定區(qū)域進行多次映射,不僅造成其他未映射區(qū)域資源的浪費,而且還會使得在該區(qū)域周邊的鏈路由于多次映射,使得周圍鏈路帶寬快速陷入極小值,本文采用最短路徑優(yōu)先映射算法時,在每次尋找路徑時,都要尋找最小鏈路的那條路徑,使得某一條或幾條鏈路帶寬無法滿足虛擬用戶的帶寬要求,導(dǎo)致虛擬用戶后期映射拒絕率逐漸增高。因此,在考慮節(jié)點映射負載能力的同時,還要考慮周邊鏈路映射的負載能力。關(guān)于鏈路映射,很多文獻采用窮舉法[12-13],找出兩點間的所有無環(huán)路徑,將映射路徑中跳數(shù)(Hop)引入到映射成本中,由于該方法必須搜索出所有的無環(huán)路徑,將每條路徑所有鏈路帶寬總和除以對應(yīng)路徑跳數(shù),選出比值最小的路徑進行映射。此種算法雖然考慮了路徑節(jié)點的轉(zhuǎn)發(fā)成本,但隨著網(wǎng)絡(luò)規(guī)模增大,服務(wù)對用戶的響應(yīng)時間無法滿足用戶對服務(wù)的時間要求,即NP難問題中提到的無法在合理時間內(nèi)找到有效解。另外,在虛擬網(wǎng)絡(luò)映射過程中還會存在一個忽略性的問題是當節(jié)點和相鄰鏈路間的帶寬差異較大時,存在節(jié)點和相鄰鏈路資源的浪費以及報文在它們間傳輸過程中產(chǎn)生的抖動現(xiàn)象。

鑒于以上研究,本文利用MatLab平臺實現(xiàn)網(wǎng)絡(luò)拓撲的映射過程,通過鄰接矩陣反應(yīng)網(wǎng)絡(luò)拓撲的結(jié)構(gòu)性,它不同于虛擬映射研究平臺GM-ITM。此種映射方法可以轉(zhuǎn)化矩陣對應(yīng)關(guān)系,找出適合算法的矩陣數(shù)據(jù)。

節(jié)點基于以下規(guī)則進行映射:1)基于節(jié)點和相鄰鏈路間的帶寬資源差異性,差異越小,該節(jié)點越優(yōu)先映射;2)節(jié)點的CPU帶寬剩余率和相鄰鏈路帶寬剩余率總和越大,說明這個區(qū)域的節(jié)點和鏈路負載壓力越小,該節(jié)點越優(yōu)先選擇;3)節(jié)點CPU剩于帶寬占所有節(jié)點CPU剩余帶寬的比例,比例越大表明剩余帶寬越大,映射成功率越高,越優(yōu)先選擇。鏈路映射算法采用k最短路徑算法(k-shortest)[9,14-15],將該算法映射的鄰接矩陣轉(zhuǎn)換成反應(yīng)鏈路負載均衡的映射矩陣,減少鏈路映射負載的差異性,有效平衡網(wǎng)絡(luò)節(jié)點和鏈路的負載壓力。

2 問題描述與網(wǎng)絡(luò)模型

如何更有效地實現(xiàn)多用戶復(fù)用同一個物理網(wǎng)絡(luò),在映射均衡性的基礎(chǔ)上減少網(wǎng)絡(luò)出現(xiàn)的瓶頸問題,從而有效提高底層網(wǎng)絡(luò)的映射率。目前需要解決的問題主要有:

1)虛擬網(wǎng)絡(luò)在使用k最短路徑算法映射鏈路過程中容易出現(xiàn)映射范圍局部化,局部鏈路帶寬陷入極小值,使得無法保證一條完整路徑中每條鏈路帶寬都能滿足虛擬用戶對鏈路的帶寬資源要求。

2)當節(jié)點和相鄰鏈路帶寬比例較大時,節(jié)點和鏈路間傳輸報文時,容易產(chǎn)生報文抖動,報文丟失和資源浪費等現(xiàn)象,即使足夠的緩存可以減少報文抖動性,當網(wǎng)絡(luò)流快速占滿路由器整個緩沖區(qū)時,造成數(shù)據(jù)報文丟失,產(chǎn)生報文重傳,使得報文無法持續(xù)傳輸,將會產(chǎn)生報文抖動現(xiàn)象,后者往往被人們忽視。

3)當用戶請求的節(jié)點或鏈路帶寬資源高于物理節(jié)點或鏈路已有帶寬時,無法請求到底層資源,是否可以使一些節(jié)點或鏈路的資源進行釋放,等到虛擬用戶資源釋放后,新到的用戶得到資源再映射,而具備什么樣特性的節(jié)點和鏈路的資源需要調(diào)整是待解決的問題。

4)虛擬用戶是否可以降低數(shù)據(jù)帶寬要求,達到數(shù)據(jù)傳輸?shù)臅惩ㄐ?滿足基本的傳輸服務(wù),而不影響服務(wù)的質(zhì)量。

綜上所述,以上是目前需要進一步思考和解決的問題。

為了對虛擬網(wǎng)絡(luò)映射有更深入的了解,首先需要建立虛擬網(wǎng)絡(luò)模型,對各個參數(shù)進行定義和描述。虛擬網(wǎng)絡(luò)模型如圖1所示。

圖1 虛擬網(wǎng)絡(luò)映射

一個完整的底層物理網(wǎng)絡(luò)被抽象為一個無向圖:

Gα=(Nα,Lα)。將虛擬網(wǎng)絡(luò)映射到物理網(wǎng)絡(luò)設(shè)置為M(Vβ):(Vβ,nβ,Iβ)→(Gα,Nα,Lα)∈(Vβ≤Gα)∩(nβ≤Nα)∩(Iβ≤Lα)即虛擬網(wǎng)絡(luò)映射的最基本要求如式(1)所示。

Vβ≤Gα,nβ≤Nα,lβ≤Lα

(1)

其中,Vβ≤Gα表示虛擬網(wǎng)絡(luò)映射的物理節(jié)點是底層物理網(wǎng)絡(luò)擁有節(jié)點集合的子集,nβ≤Nα表示映射的物理節(jié)點資源必須滿足虛擬用戶請求的節(jié)點資源大小,lβ≤Lα表示映射的物理鏈路資源必須滿足虛擬用戶請求的鏈路資源大小。本文要求同一虛擬用戶映射的物理節(jié)點是不同的網(wǎng)絡(luò)節(jié)點,同一個虛擬用戶映射的鏈路可以映射到相同或不同的物理鏈路上,每次映射的虛擬鏈路可以用某一條路徑上的各條鏈路共同分擔(dān)。具體的符號對照信息如表1所示。

表1 虛擬網(wǎng)絡(luò)映射符號

3 虛擬網(wǎng)絡(luò)映射機制

3.1 節(jié)點映射

隨著虛擬網(wǎng)絡(luò)請求數(shù)目增多,物理節(jié)點和物理鏈路上的負載分布將趨于不平衡,尤其采用k最短路徑算法時,會快速陷入局部鏈路極小值,使后續(xù)用戶無法繼續(xù)映射。為此,本文提出一種基于節(jié)點和鏈路負載均衡以及k最短路徑算法映射矩陣轉(zhuǎn)換的虛擬網(wǎng)絡(luò)映射算法。

定義1節(jié)點和相鄰鏈路帶寬差異性。

當節(jié)點的處理能力超過了相鄰鏈路的傳輸能力,節(jié)點會出現(xiàn)存儲空間浪費,CPU利用率下降等現(xiàn)象。同樣,當相鄰鏈路的傳輸能力超過了節(jié)點的處理能力,會使鏈路帶寬浪費,鏈路上的報文快速到達節(jié)點,當節(jié)點緩沖區(qū)不足,造成報文丟失和抖動等現(xiàn)象。為此,本文提出第一個指標是選擇節(jié)點和相鄰鏈路帶寬相近的區(qū)域進行映射。物理網(wǎng)絡(luò)拓撲簡易圖如圖2所示。

圖2物理網(wǎng)絡(luò)拓撲簡易圖

如圖2所示,設(shè)m表示鏈路AB和節(jié)點B的處理能力的比值,n表示節(jié)點B和鏈路的BC處理能力比值。m和n如式(2)所示。

(2)

當m=n=1時,節(jié)點B、鏈路AB及BC處于最佳狀態(tài),帶寬差異為0。這里設(shè)ti時刻,節(jié)點B和相鄰鏈路的帶寬差異為Ω(NB(ti)),Ω(NB(ti))與節(jié)點剩余帶寬和相鄰鏈路AB和BC的剩余帶寬有關(guān)。

1)當m>n>1時,Ω(NB(ti))=m+n。m或n越大,說明節(jié)點B越容易出現(xiàn)報文排隊滯留及數(shù)據(jù)報文丟失,處理能力取決于鏈路BC的帶寬。

通過以上分析,節(jié)點和相鄰鏈路帶寬差異接近的區(qū)域傳輸效果最好。在選擇物理節(jié)點進行映射時,盡量選擇物理網(wǎng)絡(luò)節(jié)點和相鄰鏈路帶寬接近的拓撲區(qū)域進行映射,減少節(jié)點和相鄰鏈路帶寬差異性引起的資源浪費和報文抖動。

定義2節(jié)點和相鄰鏈路的處理能力差異。

設(shè)ti時刻,物理鏈路BC帶寬剩余率為F(Lα(ti,B,C)),設(shè)鏈路的起點為B,終點為C。Lα(ti,B,C)為ti時刻鏈路剩余帶寬,Lα(t0,B,C)為t0時刻鏈路初始帶寬。

第ti時刻物理鏈路BC的帶寬剩余率如式(3)所示。

(3)

其中,F(Lα(ti))∈[0,1],當F(Lα(ti))=0時,說明帶寬已耗盡,無法映射。當F(Lα(ti))=1時,說明帶寬未使用,鏈路帶寬處于最佳狀態(tài)。

影響節(jié)點處理能力的因素與節(jié)點的CPU帶寬和內(nèi)存空間有關(guān),這里僅考慮CPU的帶寬。

設(shè)第ti時刻物理節(jié)點Nα的CPU帶寬剩余率,如式(4)所示。

(4)

其中,CPU(Nα(ti))為ti時刻物理節(jié)點Nα的CPU剩余帶寬,CPU(Lα(t0))為t0時刻物理節(jié)點Nα的CPU初始帶寬。設(shè)節(jié)點Nα的相鄰鏈路共有q條。節(jié)點Nα的相鄰鏈路帶寬剩余率平均值為RF(Lα(ti)),如式(5)所示。

(5)

W(Nα(ti))=θ1F(Nα(ti))+θ2RF(Lα(ti))

(6)

如式(6)所示,W(Nα(ti))為節(jié)點剩余率和它的相鄰鏈路平均剩余率分別乘以相應(yīng)的系數(shù)得到的總和。θ1和θ2表示節(jié)點和相鄰鏈路處理能力的權(quán)重關(guān)系。

定義3節(jié)點CPU剩余帶寬比例。

設(shè)節(jié)點Nα的CPU剩余帶寬占整個網(wǎng)絡(luò)節(jié)點CPU剩余帶寬的比例,如式(7)所示。

(7)

通過以上3個指標作為物理節(jié)點的選取依據(jù),即物理節(jié)點映射的評估模型如式(8)所示,按照SNode_Rank(Nα(ti))從大到小進行排序。其中,μ表示節(jié)點和相鄰鏈路帶寬差異指標的權(quán)重系數(shù),η表示節(jié)點剩余帶寬指標的權(quán)重系數(shù),Ω(Nα(ti))′表示Ω(Nα(ti))歸一化后的數(shù)值。

SNode_Rank(Nα(ti))=W(Nα(ti))+

μ·(1-Ω(Nα(ti))′)+η·RCPU(Nα(ti))

0≤μ≤1, 0≤η≤1

(8)

同樣,虛擬網(wǎng)絡(luò)節(jié)點映射順序如式(9)所示。

VNode_Rank(nβ(ti))=μ·(1-Ω(nβ(ti))′)+

η·RCPU(nβ(ti))

(9)

由于虛擬網(wǎng)絡(luò)節(jié)點不存在剩余率,因此θ1=θ2=0。其中,Ω(nβ(ti))′是Ω(nβ(ti))歸一化后的數(shù)值。虛擬網(wǎng)絡(luò)節(jié)點映射順序按照VNode_Rank(nβ(ti))排序從大到小選取。

3.2 鏈路映射

常用的鏈路映射算法是最短路徑算法中的基于k最短路徑映射算法。算法可以按照用戶的要求選擇合適的k值,依次選擇第k條最短路徑。本文設(shè)定映射路徑經(jīng)過的節(jié)點個數(shù),即跳數(shù)(Hop),跳數(shù)越多,成本越高。本文將該算法映射的拓撲圖鄰接對稱矩陣進行變換,將鄰接對稱矩陣轉(zhuǎn)換成反應(yīng)鏈路負載均衡的映射矩陣。轉(zhuǎn)換后,可以解決k最短路徑算法對原始鄰接對稱矩陣尋找最短路徑時出現(xiàn)的快速陷入極小值的問題,該問題會造成路徑中的某些鏈路剩余帶寬太低,造成后續(xù)的虛擬用戶映射率下降。如果將鄰接對稱矩陣進行變換,使得鄰接對稱矩陣中的鏈路帶寬數(shù)據(jù)轉(zhuǎn)換成本文設(shè)定的反應(yīng)鏈路負載均衡的映射矩陣,無論是虛擬映射率還是鏈路負載均衡性都具有很好的映射效果。

如式(10)所示,矩陣A1代表無向圖的鄰接對稱矩陣,矩陣A2代表轉(zhuǎn)換后的反應(yīng)鏈路負載均衡的鏈路映射矩陣。n表示節(jié)點個數(shù),axy(ti)表示在ti時刻無向拓撲圖鄰接矩陣元素,其中,x≥1且x≤n,y≥1且y≤n。當x≠y且axy(ti)=ayx(ti)時,axy表示起點為x,終點為y的鏈路帶寬;當x=y時,axy(ti)表示對角線上的元素,即節(jié)點CPU的帶寬。在每次搜索第k條最短路徑時,使算法映射到經(jīng)過轉(zhuǎn)換的矩陣A2上。在矩陣A2中,設(shè)F(axy(ti))表示鏈路axy(ti)在ti時刻的帶寬剩余率,則1-F(axy(ti))表示鏈路axy在ti時刻的帶寬使用率,對它進行歸一化后的數(shù)值表示為f(axy(ti))。f(axy(ti))越小,說明鏈路負載壓力越小,越容易選擇作為映射的對象。另一個指標是鏈路使用帶寬占所有鏈路使用帶寬的比例,設(shè)為R(axy(ti)),比例越小,說明鏈路剩余帶寬越大,映射成功率越高,越容易作為優(yōu)先選擇映射的對象。將2個指標結(jié)合在一起作為k最短路徑算法的映射矩陣元素。反之,如果單選鏈路壓力大小作為選擇對象,則映射次數(shù)較少且?guī)捿^小的鏈路就會被選中作為映射的對象,會造成虛擬映射率下降。如果僅考慮鏈路剩余帶寬大小作為一個指標,它與前面提到的節(jié)點映射采用最大資源節(jié)點映射的貪婪思想是一樣的,雖然暫時可以完成虛擬用戶的映射,但沒有考慮鏈路負載壓力的均衡性,隨著時間推移,鏈路映射率陷入局部極小值,映射率逐漸下降。因此,在執(zhí)行k最短路徑算法之前需要做如下矩陣變換:

(10)

虛擬網(wǎng)絡(luò)映射偽代碼如下:

輸入底層網(wǎng)絡(luò)為Gα(Nα,Lα),底層網(wǎng)絡(luò)有r1個節(jié)點;虛擬網(wǎng)絡(luò)請求為V(nβ,Iβ),虛擬網(wǎng)絡(luò)有r2個節(jié)點,r2

1.%記錄每個時段用戶到達時間;%

t1,t2,…,ti-1,ti;

2.For i=1:100

3.e<-Poissrn(i);

4.For j=1:e

5.計算物理節(jié)點指標Ω(Nα(ti))、W(Nα(ti))和RCPU(Nα(ti)),得出SNode_Rank(Nα(ti));

6.計算虛擬節(jié)點指標Ω(Nβ(ti))和RCPU(Nβ(ti)),得出VNode_Rank(nβ(ti));

7.S1←Descend(VNode_Rank(nβ(ti)));

8.S2←Descend(SNode_Rank(nβ(ti)));

9.If {nβ≤Nα|nβ∈S1,Nα∈S2};%物理節(jié)點資源滿足虛擬節(jié)點;%

10.Lα(a,b)←S2;%保存相鄰節(jié)點對的鏈路,S2(a)和S2(b)是相鄰的節(jié)點;%

11.Else Continue %否則,進行下一個虛擬用戶的請求;%

12.End If

13.A1->A2;%鄰接矩陣轉(zhuǎn)換;%

14.c=0;

15.For d=1:w

Pathα(a,b);

%生成物理節(jié)點對應(yīng)的最短路徑;%

17.If

18.c++;

19.Continue;

%鏈路資源匹配,繼續(xù)檢測下一條鏈路;%

20.Else Break;

21.End If

22.End for

23.If c

24.Refuse;

%虛擬網(wǎng)絡(luò)鏈路資源不完全匹配,拒絕請求;%

25.Else

%記錄用戶服務(wù)的結(jié)束時間;f(t1),f(t2),…f(ti);%

26. End If

27.If f(ti)-ti<=T

28.Embed(CPU(nβ)→CPU(Nα|));%虛擬網(wǎng)絡(luò)請求成功,物理節(jié)點映射完成;%

29.BW(Lα)←BW(Lα)-BW(1β);%虛擬網(wǎng)絡(luò)請求成功,更新鏈路帶寬資源;%

30.Else Refuse;

%超時,拒絕請求;%

31.End If

32.End For

33.End For

4 實驗?zāi)M

網(wǎng)絡(luò)拓撲結(jié)構(gòu)的鄰接矩陣采用Matlab工具生成。物理網(wǎng)絡(luò)節(jié)點個數(shù)隨機生成30個～50個。虛擬網(wǎng)絡(luò)請求的節(jié)點CPU和鏈路帶寬服從2～5的均勻分配。VN拓撲結(jié)構(gòu)中包含的節(jié)點個數(shù)為3個～7個,VN中節(jié)點的度數(shù)服從0～5。圖3是基于節(jié)點度數(shù)的網(wǎng)絡(luò)拓撲單次案例圖,圖中有30個物理節(jié)點,圓點的大小反映物理節(jié)點度數(shù)的多少?；诠?jié)點帶寬大小的網(wǎng)絡(luò)拓撲如圖4所示。

圖3 基于節(jié)點度數(shù)大小的網(wǎng)絡(luò)拓撲單次案例

圖4 基于節(jié)點帶寬大小的網(wǎng)絡(luò)拓撲單次案例

方形點的大小反映節(jié)點帶寬資源的多少,這兩個圖是同一時刻基于不同角度的拓撲案例圖,通過兩個圖的對比可以提供網(wǎng)絡(luò)不同區(qū)域的節(jié)點剩余的帶寬分布情況。本文把實驗完成的過程劃分成1個～100個時段,每個時段記錄一次實驗數(shù)據(jù)。采用間隔抽樣法,從100個時段中抽取20個采樣點,每隔5個時段抽取1次作為樣本數(shù)據(jù)。設(shè)生存時間窗口足夠大。對參數(shù)進行賦值:η=1,μ=1,θ1=1,θ2=1。將本文算法與其他兩種算法進行比較,一種是隨機算法,它對節(jié)點映射采用隨機抽取方法,鏈路映射采用k最短路徑算法;另一種算法是文獻[9,13]基于貪婪思想的局部節(jié)點和相鄰鏈路帶寬最大化的節(jié)點映射算法與k最短路徑映射算法相結(jié)合的虛擬鏈路映射算法。

為了更好地說明本文算法在映射過程優(yōu)于其他映射算法,使用以下指標進行衡量。

1)節(jié)點和鏈路負載壓力匹配度

為了體現(xiàn)節(jié)點和鏈路負載均衡性,引入負載壓力匹配度C,計算公式如下:

(11)

其中,m1為鏈路個數(shù),n1為節(jié)點個數(shù)。負載壓力匹配度C越大,說明節(jié)點與節(jié)點間,鏈路與鏈路間負載均衡效果越好,節(jié)點和鏈路映射負載差異越小,網(wǎng)絡(luò)平衡性越好,映射率越高。如圖5所示,從曲線變化趨勢看,本文算法使得物理網(wǎng)絡(luò)整體負載差異變化最穩(wěn)定,差異最小。

圖5 負載壓力匹配度

2)最大節(jié)點負載壓力和最大鏈路負載壓力

最大節(jié)點壓力和最大鏈路壓力反映網(wǎng)絡(luò)哪些節(jié)點和鏈路遇到瓶頸問題。最大節(jié)點壓力和最大鏈路壓力的變化反映整個網(wǎng)絡(luò)是否處于資源短缺狀態(tài)。圖6是3種算法在映射過程中最大節(jié)點壓力變化曲線。圖7是3種算法在映射過程中最大鏈路壓力變化曲線?？梢钥闯?本文映射算法中的最大節(jié)點和最大鏈路壓力比較穩(wěn)定,一直小于其他算法,可見本文算法的負載均衡性較好。而其他2種算法由于沒有考慮節(jié)點負載的均衡性,以及對鏈路映射矩陣未進行更好的優(yōu)化,使它們的節(jié)點和鏈路很快出現(xiàn)壓力過大,在后期映射中,全網(wǎng)負載壓力不均衡,虛擬映射率下降。表2反映3種算法負載參數(shù)對應(yīng)的數(shù)據(jù),從平均負載壓力匹配度和節(jié)點鏈路的負載壓力上看,本文算法都優(yōu)于其他2種算法,雖然隨機算法最大壓力節(jié)點的最大值和最小值小于本文算法,但整體執(zhí)行過程的平均壓力不如本文算法,而本文對基于最短路徑算法的鄰接矩陣優(yōu)化,鏈路的負載均衡性都優(yōu)于其他2種算法。

圖6 物理網(wǎng)絡(luò)的最大節(jié)點壓力

圖7 物理網(wǎng)絡(luò)的最大鏈路壓力

算法負載壓力匹配度最大節(jié)點壓力最大鏈路壓力最大值最小值平均值最大值最小值平均值最大值最小值平均值本文算法0.305 50.146 90.278 20.889 70.058 80.504 70.365 90.122 00.278 3隨機算法+k-shortest0.880 70.145 40.614 80.808 30.049 40.592 51.000 00.129 00.835 0貪婪算法+k-shortest0.811 30.159 30.694 30.866 70.084 00.729 71.000 00.216 20.892 5

3)收益

網(wǎng)絡(luò)映射的主要目標是物理網(wǎng)絡(luò)在消耗相對較小資源成本和滿足用戶服務(wù)質(zhì)量的前提下,映射盡量多的虛擬網(wǎng)絡(luò)用戶。本文分2種情況來考慮映射收益[16]:一個指標只考慮虛擬用戶映射總收益,它包括虛擬用戶節(jié)點和鏈路的帶寬資源的請求大小;另一個指標將成本引入到映射收益中,即映射成本收益。映射成本反映虛擬映射在實際網(wǎng)絡(luò)條件的情況下,映射收益和成本間的關(guān)系。映射成本主要體現(xiàn)在鏈路映射的路徑長度,路徑越長,占用的鏈路帶寬越多。

(12)

(13)

其中,RC(V(t))是總收益和成本的比例關(guān)系。物理網(wǎng)絡(luò)接受虛擬請求所消耗的成本如式(14)所示。

(14)

式(14)中的length(ev(t),Hop)表示分配給虛擬鏈路的物理路徑中經(jīng)過節(jié)點的個數(shù)。W(ev(t))表示分配給該鏈路的路徑上的占用鏈路總帶寬。C(Vv(t))表示底層網(wǎng)絡(luò)節(jié)點為虛擬節(jié)點分配的CPU帶寬。當虛擬鏈路映射物理鏈路時,分配的路徑中經(jīng)過的節(jié)點個數(shù)越多,映射成本越大。圖8表示本文算法分別與隨機算法和貪婪算法在總收益上的比較。

圖8 2種情況下的總收益比較

點在對角線下面說明本文算法總收益更大,在對角線上面說明其他2種算法總收益更大,對角線上的點表示本文算法與其他算法總收益相同。圖7本文算法總收益總體上要高于其他2種算法。圖9是本文算法總收益與收益成本間的關(guān)系。黑色線條是RC(V(t)),白色線條是R(V(t))。這里設(shè)初始參數(shù)為α1=0.1,α2=α3=1。

圖9 本文算法的總收益和收益成本的關(guān)系

4)虛擬網(wǎng)絡(luò)映射率(VMR)

設(shè)虛擬用戶成功映射個數(shù)為Receive(num(V(t))) 與虛擬用戶請求個數(shù)Request(num(V(t)))的比值關(guān)系如式(15)所示。

(15)

從圖10可以看出,本文算法高于其他2種算法的虛擬網(wǎng)絡(luò)映射率。

圖10 3種算法的虛擬網(wǎng)絡(luò)映射率

表3給出了3種算法虛擬映射率的對比數(shù)據(jù),它通過分析100個時段3種算法對等量和等結(jié)構(gòu)的虛擬用戶進行映射,本文算法的虛擬用戶映射率相比隨機算法提高了0.48,相比貪婪算法提高了0.61。隨機算法比貪婪算法效果更好,因為每次映射物理節(jié)點時,節(jié)點的選取是隨機的,負載平衡性比貪婪算法好,而貪婪算法中的節(jié)點映射會選取節(jié)點和相鄰鏈路帶寬資源最大的區(qū)域進行映射,可能存在一個帶寬較大的區(qū)域被映射多次,使得周圍區(qū)域中的鏈路資源基本耗盡。而隨機算法的節(jié)點選擇的區(qū)域隨機性較強,因此,隨機算法的節(jié)點映射的區(qū)域變化性比基于貪婪算法的節(jié)點映射區(qū)域變化性大。但隨機算法每次隨機選取的節(jié)點資源不一定保證滿足虛擬用戶資源要求,同時鏈路映射沒有考慮負載均衡性,造成后期虛擬網(wǎng)絡(luò)映射率下降。

表3 3種算法的虛擬網(wǎng)絡(luò)映射率比較

5)資源調(diào)整

當鏈路資源不足時,如果將虛擬節(jié)點遷移到其他節(jié)點上,隨著網(wǎng)絡(luò)規(guī)模增加會出現(xiàn)以下問題,遷移距離越大,遷移成本越高。如果把虛擬節(jié)點只遷移到相鄰節(jié)點,由于節(jié)點周邊鏈路資源可能稀缺,改變的差異較小,映射率提高的效果較輕微。因此,本文滿足路徑跳數(shù)限制的基礎(chǔ)上調(diào)整k值,使路徑重新規(guī)劃。如圖11所示,白色線條表示k為1時的虛擬映射率。黑色線條是k為8時的虛擬映射率。當虛擬鏈路不滿足要求時,k值增加到8。從第4次到第7次抽樣時,即第20到第35個時刻,可以看出,通過調(diào)整k值提高了虛擬網(wǎng)絡(luò)映射率。

圖11 調(diào)整k值的虛擬網(wǎng)絡(luò)映射率比較

當節(jié)點資源不足時,本文采用節(jié)點資源的動態(tài)調(diào)整。首先找出瓶頸節(jié)點,然后對其進行資源釋放。瓶頸節(jié)點主要指最大壓力節(jié)點和最大介數(shù)節(jié)點。通過實驗結(jié)論得出釋放最大介數(shù)節(jié)點上的資源,效果更好。介數(shù)[17]很高的節(jié)點或鏈路對于網(wǎng)絡(luò)起著重要的支撐作用。節(jié)點介數(shù)定義為拓撲中經(jīng)過該節(jié)點最短路徑數(shù)目占所有節(jié)點最短路徑總數(shù)的比例。如果該節(jié)點介數(shù)很高并且出現(xiàn)帶寬資源短缺,則鏈接它的子網(wǎng)將無法交換數(shù)據(jù),造成經(jīng)過該節(jié)點的鏈路映射失敗。在沒有釋放資源之前始終處于僵持狀態(tài)。如圖12所示,圖12中用2種算法進行比較。黑色線條表示最大介數(shù)節(jié)點資源釋放的虛擬映射率,白色線條表示最大壓力節(jié)點資源釋放的虛擬映射率。假設(shè)2種節(jié)點釋放的資源大小相同。在大多數(shù)時段,通過釋放最大介數(shù)節(jié)點資源的虛擬映射率比釋放最大壓力節(jié)點資源的虛擬映射率效果更好,虛擬網(wǎng)絡(luò)映射率提升的更快。

圖12 最大介數(shù)節(jié)點和最大壓力節(jié)點比較

5 結(jié)束語

本文提出一種結(jié)合節(jié)點和鏈路資源負載均衡的高效映射方案。通過對鄰接矩陣進行變換,將原來的鄰接矩陣轉(zhuǎn)換成反映鏈路負載均衡的映射矩陣,有效提高虛擬映射率。對網(wǎng)絡(luò)出現(xiàn)的資源不足采取了對應(yīng)的資源調(diào)整措施,即最大介數(shù)節(jié)點的資源釋放和基于k值調(diào)整的鏈路重規(guī)劃。下一步將研究節(jié)點和鏈路資源的動態(tài)調(diào)整,針對不同的虛擬用戶進行定義,考慮哪些虛擬用戶在降低數(shù)據(jù)帶寬要求的前提下,可以實現(xiàn)數(shù)據(jù)的基本傳輸,滿足基本的服務(wù)質(zhì)量,從而進一步提高虛擬網(wǎng)絡(luò)映射率。

[1] MARK B,JEFFREY S C,LAWRENCE L,et al.GENI:a federated testbed for innovative network experiments[J].Computer Networks,2014,61(14):5-23.

[2] 蔡志平,劉 強,呂 品,等.虛擬網(wǎng)絡(luò)映射模型及其優(yōu)化算法[J].軟件學(xué)報,2012,23(4):864-877.

[3] LEONARDO R B,RODRIGO R O,LUCIANA S B,et al.Security-aware optimal resource allocation for virtual network embedding[C]//Proceedings of the 8th International Conference on Network and Service Management.Washington D.C.,USA:IEEE Press,2012:378-384.

[4] 龔水清,陳 靖,黃聰會.信任感知的安全虛擬網(wǎng)絡(luò)映射算法[J].通信學(xué)報,2015,36(11):180-189.

[5] 陳曉華,李春芝,陳良育,等.主動休眠節(jié)點鏈路的高效節(jié)能虛擬網(wǎng)絡(luò)映射[J].軟件學(xué)報,2014,25(7):1416-1431.

[6] HSU W H,SHIEH Y P.Virtual network mapping algorithm in the cloud infrastructure[J].Journal of Network and Computer Applications,2013,36(6):1724-1734.

[7] FAJJARI I,AITSAADI N,PIORO M,et al.A new virtual network static embedding strategy within the cloud’s private backbone network[J].Computer Network,2014,62:69-88.

[8] 黃彬彬,林榮恒,彭 凱.基于粒子群優(yōu)化的負載均衡的虛擬網(wǎng)絡(luò)映射[J].電子與信息學(xué)報,2013,35(7):1753-1759.

[9] ZHANG Min,TANG Xi Jie.Hop-limit path mapping algorithm for virtual network embedding[J].Wireless Personal Communications,2016,95(3):1-16.

[10] 李小玲,郭長國,李小勇.一種基于約束優(yōu)化的虛擬網(wǎng)絡(luò)映射方法[J].計算機研究與發(fā)展,2012,49(8):1601-1610.

[11] 徐冬冬,鄭淑麗,曹 敏.基于openflow網(wǎng)絡(luò)的虛擬網(wǎng)絡(luò)映射研究[J].合肥工業(yè)大學(xué)學(xué)報(自然科學(xué)版),2016,39(10):1352-1356.

[12] JIANG Liu,TAO Huang,CHEN Jianya,et al.A new algorithm based on the proximity principle for the virtual network embedding problem[J].Journal of Zhejiang University-SCIENCE C,2011,12(11):910-918.

[13] 董永彬,呂光宏,李立龍.基于節(jié)點分割的兩階段虛擬網(wǎng)絡(luò)映射算法[J].四川大學(xué)學(xué)報(自然科學(xué)版),2005,52(2):287-292.

[14] EPPSTEIN D.Finding the k shortest paths[J].SIAM Journal on Computing,1994,28(2):652-673.

[15] YU M,YI Y,REXFORD J,et al.Rethinking virtual network embedding:substrate support for path splitting and migration[J].Computer Communication REVIEW,2008,38(2):17-29.

[16] 張 翔.成本與能效優(yōu)化的虛擬網(wǎng)絡(luò)映射算法研究[D].南京:南京郵電大學(xué),2013.

[17] FREEMAN L C.A set of measures of centrality based upon betweenness[J].Sociometry,1977,40(1):35-41.