基于k最短路徑算法優化與負載均衡的虛擬網絡映射機制

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

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

0 概述

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

1 相關工作

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

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

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

鑒于以上研究,本文利用MatLab平臺實現網絡拓撲的映射過程,通過鄰接矩陣反應網絡拓撲的結構性,它不同于虛擬映射研究平臺GM-ITM。此種映射方法可以轉化矩陣對應關系,找出適合算法的矩陣數據。

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

2 問題描述與網絡模型

如何更有效地實現多用戶復用同一個物理網絡,在映射均衡性的基礎上減少網絡出現的瓶頸問題,從而有效提高底層網絡的映射率。目前需要解決的問題主要有:

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

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

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

4)虛擬用戶是否可以降低數據帶寬要求,達到數據傳輸的暢通性,滿足基本的傳輸服務,而不影響服務的質量。

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

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

圖1 虛擬網絡映射

一個完整的底層物理網絡被抽象為一個無向圖:

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

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

(1)

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

表1 虛擬網絡映射符號

3 虛擬網絡映射機制

3.1 節點映射

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

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

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

圖2物理網絡拓撲簡易圖

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

(2)

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

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

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

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

設ti時刻,物理鏈路BC帶寬剩余率為F(Lα(ti,B,C)),設鏈路的起點為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時,說明帶寬未使用,鏈路帶寬處于最佳狀態。

影響節點處理能力的因素與節點的CPU帶寬和內存空間有關,這里僅考慮CPU的帶寬。

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

(4)

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

(5)

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

(6)

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

定義3節點CPU剩余帶寬比例。

設節點Nα的CPU剩余帶寬占整個網絡節點CPU剩余帶寬的比例,如式(7)所示。

(7)

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

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

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

0≤μ≤1, 0≤η≤1

(8)

同樣,虛擬網絡節點映射順序如式(9)所示。

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

η·RCPU(nβ(ti))

(9)

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

3.2 鏈路映射

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

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

(10)

虛擬網絡映射偽代碼如下:

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

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

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

2.For i=1:100

3.e<-Poissrn(i);

4.For j=1:e

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

6.計算虛擬節點指標Ω(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};%物理節點資源滿足虛擬節點;%

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

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

12.End If

13.A1->A2;%鄰接矩陣轉換;%

14.c=0;

15.For d=1:w

Pathα(a,b);

%生成物理節點對應的最短路徑;%

17.If

18.c++;

19.Continue;

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

20.Else Break;

21.End If

22.End for

23.If c

24.Refuse;

%虛擬網絡鏈路資源不完全匹配,拒絕請求;%

25.Else

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

26. End If

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

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

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

30.Else Refuse;

%超時,拒絕請求;%

31.End If

32.End For

33.End For

4 實驗模擬

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

圖3 基于節點度數大小的網絡拓撲單次案例

圖4 基于節點帶寬大小的網絡拓撲單次案例

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

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

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

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

(11)

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

圖5 負載壓力匹配度

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

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

圖6 物理網絡的最大節點壓力

圖7 物理網絡的最大鏈路壓力

算法負載壓力匹配度最大節點壓力最大鏈路壓力最大值最小值平均值最大值最小值平均值最大值最小值平均值本文算法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)收益

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

(12)

(13)

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

(14)

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

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

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

圖9 本文算法的總收益和收益成本的關系

4)虛擬網絡映射率(VMR)

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

(15)

從圖10可以看出,本文算法高于其他2種算法的虛擬網絡映射率。

圖10 3種算法的虛擬網絡映射率

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

表3 3種算法的虛擬網絡映射率比較

5)資源調整

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

圖11 調整k值的虛擬網絡映射率比較

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

圖12 最大介數節點和最大壓力節點比較

5 結束語

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

[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] 蔡志平,劉 強,呂 品,等.虛擬網絡映射模型及其優化算法[J].軟件學報,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] 龔水清,陳 靖,黃聰會.信任感知的安全虛擬網絡映射算法[J].通信學報,2015,36(11):180-189.

[5] 陳曉華,李春芝,陳良育,等.主動休眠節點鏈路的高效節能虛擬網絡映射[J].軟件學報,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] 黃彬彬,林榮恒,彭 凱.基于粒子群優化的負載均衡的虛擬網絡映射[J].電子與信息學報,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] 李小玲,郭長國,李小勇.一種基于約束優化的虛擬網絡映射方法[J].計算機研究與發展,2012,49(8):1601-1610.

[11] 徐冬冬,鄭淑麗,曹 敏.基于openflow網絡的虛擬網絡映射研究[J].合肥工業大學學報(自然科學版),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] 董永彬,呂光宏,李立龍.基于節點分割的兩階段虛擬網絡映射算法[J].四川大學學報(自然科學版),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] 張 翔.成本與能效優化的虛擬網絡映射算法研究[D].南京:南京郵電大學,2013.

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