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

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

0 概述

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

綜上所述,以上是目前需要進(jìn)一步思考和解決的問(wèn)題。

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

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

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

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é)點(diǎn)是底層物理網(wǎng)絡(luò)擁有節(jié)點(diǎn)集合的子集,nβ≤Nα表示映射的物理節(jié)點(diǎn)資源必須滿(mǎn)足虛擬用戶(hù)請(qǐng)求的節(jié)點(diǎn)資源大小,lβ≤Lα表示映射的物理鏈路資源必須滿(mǎn)足虛擬用戶(hù)請(qǐng)求的鏈路資源大小。本文要求同一虛擬用戶(hù)映射的物理節(jié)點(diǎn)是不同的網(wǎng)絡(luò)節(jié)點(diǎn),同一個(gè)虛擬用戶(hù)映射的鏈路可以映射到相同或不同的物理鏈路上,每次映射的虛擬鏈路可以用某一條路徑上的各條鏈路共同分擔(dān)。具體的符號(hào)對(duì)照信息如表1所示。

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

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

3.1 節(jié)點(diǎn)映射

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

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

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

圖2物理網(wǎng)絡(luò)拓?fù)浜?jiǎn)易圖

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

(2)

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

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

通過(guò)以上分析,節(jié)點(diǎn)和相鄰鏈路帶寬差異接近的區(qū)域傳輸效果最好。在選擇物理節(jié)點(diǎn)進(jìn)行映射時(shí),盡量選擇物理網(wǎng)絡(luò)節(jié)點(diǎn)和相鄰鏈路帶寬接近的拓?fù)鋮^(qū)域進(jìn)行映射,減少節(jié)點(diǎn)和相鄰鏈路帶寬差異性引起的資源浪費(fèi)和報(bào)文抖動(dòng)。

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

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

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

(3)

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

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

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

(4)

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

(5)

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

(6)

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

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

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

(7)

通過(guò)以上3個(gè)指標(biāo)作為物理節(jié)點(diǎn)的選取依據(jù),即物理節(jié)點(diǎn)映射的評(píng)估模型如式(8)所示,按照SNode_Rank(Nα(ti))從大到小進(jìn)行排序。其中,μ表示節(jié)點(diǎn)和相鄰鏈路帶寬差異指標(biāo)的權(quán)重系數(shù),η表示節(jié)點(diǎn)剩余帶寬指標(biāo)的權(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é)點(diǎn)映射順序如式(9)所示。

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

η·RCPU(nβ(ti))

(9)

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

3.2 鏈路映射

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

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

(10)

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

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

1.%記錄每個(gè)時(shí)段用戶(hù)到達(dá)時(shí)間;%

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

2.For i=1:100

3.e<-Poissrn(i);

4.For j=1:e

5.計(jì)算物理節(jié)點(diǎn)指標(biāo)Ω(Nα(ti))、W(Nα(ti))和RCPU(Nα(ti)),得出SNode_Rank(Nα(ti));

6.計(jì)算虛擬節(jié)點(diǎn)指標(biāo)Ω(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é)點(diǎn)資源滿(mǎn)足虛擬節(jié)點(diǎn);%

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

11.Else Continue %否則,進(jìn)行下一個(gè)虛擬用戶(hù)的請(qǐng)求;%

12.End If

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

14.c=0;

15.For d=1:w

Pathα(a,b);

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

17.If

18.c++;

19.Continue;

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

20.Else Break;

21.End If

22.End for

23.If c

24.Refuse;

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

25.Else

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

26. End If

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

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

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

30.Else Refuse;

%超時(shí),拒絕請(qǐng)求;%

31.End If

32.End For

33.End For

4 實(shí)驗(yàn)?zāi)M

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的鄰接矩陣采用Matlab工具生成。物理網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)隨機(jī)生成30個(gè)～50個(gè)。虛擬網(wǎng)絡(luò)請(qǐng)求的節(jié)點(diǎn)CPU和鏈路帶寬服從2～5的均勻分配。VN拓?fù)浣Y(jié)構(gòu)中包含的節(jié)點(diǎn)個(gè)數(shù)為3個(gè)～7個(gè),VN中節(jié)點(diǎn)的度數(shù)服從0～5。圖3是基于節(jié)點(diǎn)度數(shù)的網(wǎng)絡(luò)拓?fù)鋯未伟咐龍D,圖中有30個(gè)物理節(jié)點(diǎn),圓點(diǎn)的大小反映物理節(jié)點(diǎn)度數(shù)的多少?；诠?jié)點(diǎn)帶寬大小的網(wǎng)絡(luò)拓?fù)淙鐖D4所示。

圖3 基于節(jié)點(diǎn)度數(shù)大小的網(wǎng)絡(luò)拓?fù)鋯未伟咐?/p>

圖4 基于節(jié)點(diǎn)帶寬大小的網(wǎng)絡(luò)拓?fù)鋯未伟咐?/p>

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

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

1)節(jié)點(diǎn)和鏈路負(fù)載壓力匹配度

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

(11)

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

圖5 負(fù)載壓力匹配度

2)最大節(jié)點(diǎn)負(fù)載壓力和最大鏈路負(fù)載壓力

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

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

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

算法負(fù)載壓力匹配度最大節(jié)點(diǎn)壓力最大鏈路壓力最大值最小值平均值最大值最小值平均值最大值最小值平均值本文算法0.305 50.146 90.278 20.889 70.058 80.504 70.365 90.122 00.278 3隨機(jī)算法+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ò)映射的主要目標(biāo)是物理網(wǎng)絡(luò)在消耗相對(duì)較小資源成本和滿(mǎn)足用戶(hù)服務(wù)質(zhì)量的前提下,映射盡量多的虛擬網(wǎng)絡(luò)用戶(hù)。本文分2種情況來(lái)考慮映射收益[16]:一個(gè)指標(biāo)只考慮虛擬用戶(hù)映射總收益,它包括虛擬用戶(hù)節(jié)點(diǎn)和鏈路的帶寬資源的請(qǐng)求大小;另一個(gè)指標(biāo)將成本引入到映射收益中,即映射成本收益。映射成本反映虛擬映射在實(shí)際網(wǎng)絡(luò)條件的情況下,映射收益和成本間的關(guān)系。映射成本主要體現(xiàn)在鏈路映射的路徑長(zhǎng)度,路徑越長(zhǎng),占用的鏈路帶寬越多。

(12)

(13)

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

(14)

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

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

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

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

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

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

(15)

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

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

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

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

5)資源調(diào)整

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

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

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

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

5 結(jié)束語(yǔ)

本文提出一種結(jié)合節(jié)點(diǎn)和鏈路資源負(fù)載均衡的高效映射方案。通過(guò)對(duì)鄰接矩陣進(jìn)行變換,將原來(lái)的鄰接矩陣轉(zhuǎn)換成反映鏈路負(fù)載均衡的映射矩陣,有效提高虛擬映射率。對(duì)網(wǎng)絡(luò)出現(xiàn)的資源不足采取了對(duì)應(yīng)的資源調(diào)整措施,即最大介數(shù)節(jié)點(diǎn)的資源釋放和基于k值調(diào)整的鏈路重規(guī)劃。下一步將研究節(jié)點(diǎn)和鏈路資源的動(dòng)態(tài)調(diào)整,針對(duì)不同的虛擬用戶(hù)進(jìn)行定義,考慮哪些虛擬用戶(hù)在降低數(shù)據(jù)帶寬要求的前提下,可以實(shí)現(xiàn)數(shù)據(jù)的基本傳輸,滿(mǎn)足基本的服務(wù)質(zhì)量,從而進(jìn)一步提高虛擬網(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] 蔡志平,劉 強(qiáng),呂 品,等.虛擬網(wǎng)絡(luò)映射模型及其優(yōu)化算法[J].軟件學(xué)報(bào),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] 龔水清,陳 靖,黃聰會(huì).信任感知的安全虛擬網(wǎng)絡(luò)映射算法[J].通信學(xué)報(bào),2015,36(11):180-189.

[5] 陳曉華,李春芝,陳良育,等.主動(dòng)休眠節(jié)點(diǎn)鏈路的高效節(jié)能虛擬網(wǎng)絡(luò)映射[J].軟件學(xué)報(bào),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)化的負(fù)載均衡的虛擬網(wǎng)絡(luò)映射[J].電子與信息學(xué)報(bào),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] 李小玲,郭長(zhǎng)國(guó),李小勇.一種基于約束優(yōu)化的虛擬網(wǎng)絡(luò)映射方法[J].計(jì)算機(jī)研究與發(fā)展,2012,49(8):1601-1610.

[11] 徐冬冬,鄭淑麗,曹 敏.基于openflow網(wǎng)絡(luò)的虛擬網(wǎng)絡(luò)映射研究[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(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é)點(diǎn)分割的兩階段虛擬網(wǎng)絡(luò)映射算法[J].四川大學(xué)學(xué)報(bào)(自然科學(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.