劉光遠(yuǎn),蘇 森

(1.石家莊鐵道大學(xué)信息科學(xué)與技術(shù)學(xué)院,河北石家莊050043; 2.北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室,北京100876)

?

可靠的虛擬網(wǎng)絡(luò)映射算法研究

劉光遠(yuǎn)1,蘇 森2

(1.石家莊鐵道大學(xué)信息科學(xué)與技術(shù)學(xué)院,河北石家莊050043; 2.北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室,北京100876)

網(wǎng)絡(luò)虛擬化技術(shù)允許多個異構(gòu)的虛擬網(wǎng)絡(luò)共享一個底層物理網(wǎng)絡(luò)資源,為目前的網(wǎng)絡(luò)架構(gòu)提供了一種有效的擴展手段.近年來,底層網(wǎng)絡(luò)基礎(chǔ)設(shè)施失效事件頻發(fā),因此如何提高虛擬網(wǎng)絡(luò)的可靠性成為目前該領(lǐng)域一個研究熱點.本文針對底層節(jié)點失效后虛擬拓?fù)淙绾巫畲蠡B通問題進行研究,設(shè)計了一種基于割集和擁塞感知的虛擬網(wǎng)絡(luò)映射機制.實驗表明,該方法在不預(yù)留保護資源的情況下,可獲得更好的底層網(wǎng)絡(luò)長期運行平均收益.

網(wǎng)絡(luò)虛擬化；虛擬網(wǎng)絡(luò)映射；最大化虛擬拓?fù)溥B通；割集和擁塞感知

電子學(xué)報URL:http://www.ejournal.org.cn DOI:10.3969/j.issn.0372-2112.2016.08.007

1 引言

網(wǎng)絡(luò)虛擬化技術(shù)可以有效解決互聯(lián)網(wǎng)的“僵化”問題.在網(wǎng)絡(luò)虛擬化環(huán)境下,傳統(tǒng)的Internet 服務(wù)運營商被分為兩個角色,即底層網(wǎng)絡(luò)運營商和服務(wù)提供商.底層網(wǎng)絡(luò)運營商負(fù)責(zé)管理和維護底層網(wǎng)絡(luò)資源；服務(wù)提供商向底層基礎(chǔ)設(shè)施運營商租用底層網(wǎng)絡(luò)資源創(chuàng)建虛擬網(wǎng)絡(luò),并向用戶提供端到端的網(wǎng)絡(luò)服務(wù)[1].虛擬網(wǎng)絡(luò)映射是網(wǎng)絡(luò)虛擬化研究的關(guān)鍵問題之一,受到了國內(nèi)外學(xué)者的廣泛關(guān)注.每個虛擬網(wǎng)絡(luò)可看作底層物理網(wǎng)絡(luò)的一份資源切片,包含虛擬節(jié)點和虛擬鏈路.為服務(wù)提供商的帶有節(jié)點和鏈路資源約束條件的虛擬網(wǎng)絡(luò)請求分配基礎(chǔ)設(shè)施提供商的底層網(wǎng)絡(luò)資源的問題稱為虛擬網(wǎng)絡(luò)映射(嵌入、指派)問題[2].該問題已被證明為NP-Hard問題.為了提高底層網(wǎng)絡(luò)運營商的收益,早期研究主要集中于如何提高虛擬網(wǎng)絡(luò)映射的成功率和底層網(wǎng)絡(luò)資源利用率[3～5].

由于黑客攻擊或硬軟件錯誤,底層物理網(wǎng)絡(luò)的部分節(jié)點和鏈路可能會失效.然而,在網(wǎng)絡(luò)虛擬化環(huán)境中大量的虛擬網(wǎng)絡(luò)共存于同一底層網(wǎng)絡(luò)之上,即使單個底層節(jié)點或單條底層鏈路失效就會導(dǎo)致大量的虛擬網(wǎng)絡(luò)不可用.如果基礎(chǔ)設(shè)施提供商不采取措施應(yīng)對底層節(jié)點或鏈路故障,將會使租用虛擬網(wǎng)絡(luò)的網(wǎng)絡(luò)服務(wù)提供商蒙受巨大經(jīng)濟損失,并對基礎(chǔ)設(shè)施提供商所提供的虛擬網(wǎng)絡(luò)服務(wù)喪失信心.為了解決上述問題,近年來對虛擬網(wǎng)絡(luò)可靠性問題的研究逐漸增多,文獻[6,7]主要基于先驗式恢復(fù)機制,在底層節(jié)點和鏈路失效時將其替換為預(yù)留保護資源,該類方法實現(xiàn)簡單,但需要消耗額外的底層物理計算資源和網(wǎng)絡(luò)帶寬資源,底層資源利用效用不高,同時會增加用戶的使用成本.對于輕量級可靠的虛擬網(wǎng)絡(luò)服務(wù)映射請求(在底層節(jié)點或鏈路失效時,需維持除失效節(jié)點或鏈路外的虛擬網(wǎng)絡(luò)拓?fù)溥B通),目前研究還很少.文獻[8]在未分配底層網(wǎng)絡(luò)保護資源的情況下,對底層單鏈路失效后如何保持虛擬網(wǎng)拓?fù)溥B通的映射方法進行了研究,但該方法無法解決底層單節(jié)點失效問題.

本研究的目的在于設(shè)計一種新的面向底層單節(jié)點失效的輕量級可靠虛擬網(wǎng)絡(luò)映射算法,該算法可不預(yù)留底層保護資源,在底層物理單節(jié)點失效后,虛擬網(wǎng)絡(luò)拓?fù)涑Ч?jié)點外仍保持連通,從而盡可能降低服務(wù)運營商的損失.

本文首先對面向節(jié)點失效的虛擬網(wǎng)絡(luò)映射問題進行描述,然后建立該問題的整數(shù)線性規(guī)劃模型,最后提出一種基于割集和擁塞感知的虛擬網(wǎng)絡(luò)映射算法對該問題進行求解.

2 面向節(jié)點失效的虛擬網(wǎng)絡(luò)映射問題的形式化描述

2.1 虛擬網(wǎng)絡(luò)請求

2.2 底層網(wǎng)絡(luò)

2.3 面向節(jié)點失效的虛擬網(wǎng)絡(luò)映射問題描述

虛擬網(wǎng)絡(luò)映射問題被定義為映射:M:Gv(Nv,Ev)→Gs(Ns,Es),包括節(jié)點和鏈路映射兩個方面.圖1(b)給出了虛擬網(wǎng)絡(luò)請求的一種映射方案.如圖所示,節(jié)點映射方案為{a→A,b→B,c→F},鏈路映射方案為{(a,b)→(A,B),(a,c)→(A,F),(b,c)→(B,A,F)}.

因為每個底層鏈路的帶寬資源可被多條虛擬鏈路所共享,所以兩個或更多的虛擬鏈路可能被映射到同一條底層鏈路上.當(dāng)一個底層單節(jié)點失效時,其周圍相連的鏈路也隨即失效,這會導(dǎo)致映射到這些底層鏈路上的虛擬網(wǎng)絡(luò)中的多條虛擬鏈路同時失效,進而導(dǎo)致已經(jīng)映射的虛擬網(wǎng)絡(luò)不再連通、虛擬網(wǎng)絡(luò)服務(wù)不可用.如圖1所示,底層節(jié)點A失效,與其相連的底層鏈路(A,B)和(A,F)隨即失效,則映射在其上的虛擬鏈路(a,b),(a,c),(b,c)均失效,導(dǎo)致虛擬網(wǎng)絡(luò)拓?fù)洳辉龠B通.因此,我們提出面向節(jié)點失效的虛擬網(wǎng)絡(luò)映射問題,即當(dāng)?shù)讓泳W(wǎng)絡(luò)中發(fā)生單一節(jié)點故障時,受到影響的虛擬網(wǎng)絡(luò)仍能夠最大限度保持拓?fù)溥B通性.如圖2所示,將虛擬網(wǎng)鏈路(b,c)映射到(B,C,F)上,此時底層節(jié)點A失效,虛擬拓?fù)渲械?b,c)部分仍保持聯(lián)通.

本文的工作的內(nèi)容就是要設(shè)計高效的映射算法以解決面向節(jié)點失效的虛擬網(wǎng)絡(luò)映射問題.我們首先對該問題進行數(shù)學(xué)建模,然后提出一種基于割集和擁塞感知的虛擬網(wǎng)絡(luò)映射算法對該問題進行求解.

3 面向節(jié)點失效的虛擬網(wǎng)絡(luò)映射問題的整數(shù)線性規(guī)劃模型

本文以降低虛擬網(wǎng)絡(luò)映射開銷為目標(biāo),建立面向節(jié)點失效的虛擬網(wǎng)絡(luò)映射問題的整數(shù)線性規(guī)劃模型.

變量:

目標(biāo)函數(shù):Minimize

(1)

資源約束:

(2)

(3)

連接性約束:

(4)

節(jié)點可靠性約束:

?(i,j)∈Ls,?Mv?Nv,

(5)

變量約束:

(6)

(7)

說明:

式(1)為虛擬網(wǎng)絡(luò)映射的整數(shù)規(guī)劃模型的目標(biāo)函數(shù),該目標(biāo)函數(shù)只包含了底層鏈路的帶寬資源開銷.這是因為不同映射方案的底層節(jié)點計算資源開銷是恒定的,而底層鏈路帶寬資源開銷是不同的.

式(2)和(3)給出了節(jié)點和鏈路的資源約束條件.在節(jié)點資源約束方面,底層網(wǎng)絡(luò)節(jié)點的CPU能力必須能夠滿足虛擬網(wǎng)絡(luò)節(jié)點的CPU能力需求.在鏈路資源約束方面,底層鏈路的帶寬能力必須滿足虛擬鏈路的帶寬能力需求.

式(6)表示對于同一個虛擬網(wǎng)絡(luò)請求,一個底層節(jié)點只能承載一個虛擬節(jié)點,一個虛擬節(jié)點也只能映射到一個底層節(jié)點上.

4 基于割集和擁塞感知的虛擬網(wǎng)絡(luò)映射算法描述

由于解決整數(shù)線性規(guī)劃問題的復(fù)雜性是NP難的,因此獲得最優(yōu)的虛擬網(wǎng)絡(luò)映射方案也是NP難的.目前解決該問題的方法從大的方面分為兩類:精確算法和啟發(fā)式算法,分支限界或割平面等傳統(tǒng)解決整數(shù)規(guī)劃的方法在解決小規(guī)模問題時可得到最優(yōu)的性能.但當(dāng)求解問題規(guī)模較大時,計算量巨大,無法在合理的時間給出解.所以本本設(shè)計了一種啟發(fā)式算法CCA-RVNM來解決較大規(guī)模虛擬網(wǎng)絡(luò)映射的整數(shù)線性規(guī)劃問題.算法的目標(biāo)如下:給定一個虛擬網(wǎng)絡(luò)請求和底層網(wǎng)絡(luò)資源,虛擬網(wǎng)絡(luò)映射方案首先應(yīng)該滿足虛擬網(wǎng)絡(luò)輕量級可靠需求(在底層節(jié)點失效時,需維持除失效節(jié)點外的虛擬網(wǎng)絡(luò)拓?fù)溥B通),其次虛擬網(wǎng)絡(luò)映射消耗的底層網(wǎng)絡(luò)資源應(yīng)該盡可能小.

CCA-RVNM算法為一階段算法,即映射節(jié)點和映射鏈路在同一階段進行.在進行虛擬節(jié)點映射時,CCA-RVNM基于廣度優(yōu)先搜索方式映射虛擬節(jié)點,目的是方便節(jié)點映射回溯處理.算法首先計算所有底層節(jié)點可提供的計算能力和虛擬節(jié)點的需求能力值,然后基于虛擬網(wǎng)絡(luò)拓?fù)錁?gòu)建廣度優(yōu)先搜索樹,且樹中每一層節(jié)點按照其需求能力值降序排列.虛擬節(jié)點的需求值越大,則其被映射的優(yōu)先級越高.每當(dāng)一個虛擬網(wǎng)絡(luò)節(jié)點映射成功后,便映射與其相連接的虛擬鏈路.這樣可以盡可能地避免虛擬網(wǎng)絡(luò)鏈路被映射到一條底層長路徑上,從而降低虛擬網(wǎng)絡(luò)映射引入的底層網(wǎng)絡(luò)資源開銷.所以我們在算法實現(xiàn)上引入了節(jié)點之間的距離參數(shù)K,可以理解為兩個節(jié)點之間的跳數(shù),根據(jù)設(shè)置上限值,如果超過了該值就停止該次映射并進行回溯,重新映射上一節(jié)點.在虛擬鏈路映射時,為了滿足在底層節(jié)點失效后維持虛擬拓?fù)渥畲蠡B通,我們提出了一種割集和擁塞感知的虛擬鏈路映射策略.割集感知的設(shè)計思想是基于前節(jié)整數(shù)線性規(guī)劃模型中公式(5)的約束條件,目的是保證虛擬網(wǎng)絡(luò)拓?fù)湓诘讓庸?jié)點失效后最大化連通.擁塞是指當(dāng)前物理鏈路負(fù)載的大小,因為負(fù)載大的物理鏈路承載的虛擬鏈路可能多,一旦失效,受影響的范圍相對較大,因此擁塞感知的思想就是在滿足割集約束的前提下盡量平衡底層鏈路負(fù)載,降低鏈路失效所帶來的風(fēng)險.具體地來講,在映射每一條虛擬鏈路前,我們首先檢查是否存在一個包含此條虛擬鏈路的割集,在該割集中,其他的虛擬鏈路是否已經(jīng)被映射到同一個底層物理節(jié)點直接相連的路徑上.這是對公式(5)的直接應(yīng)用.如果存在這樣的一個割集,那么在該割集中已經(jīng)被映射的虛擬鏈路所共享的與底層同一節(jié)點相連的鏈路將被標(biāo)記,在使用最小擁塞算法映射當(dāng)前的虛擬鏈路時,有標(biāo)記的底層網(wǎng)絡(luò)鏈路將不會被考慮；如果不存在這樣一個割集,那么直接使用最小擁塞算法映射虛擬鏈路.算法1和算法2分別給出了基于廣度優(yōu)先搜索的虛擬節(jié)點映射策略與基于割集和擁塞感知的虛擬鏈路映射策略的細(xì)節(jié).CCA-RVNM算法以底層網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)請求的拓?fù)浣Y(jié)構(gòu)和資源能力情況作為輸入,以滿足虛擬網(wǎng)絡(luò)輕量級可靠需求的虛擬網(wǎng)絡(luò)映射方案為輸出結(jié)果.圖3給出了CCA-RVNM算法的整體流程.

5 實驗評估與分析

我們在先前工作成果[10～12]的虛擬網(wǎng)絡(luò)映射模擬平臺上進行了CCA-RVNM算法的實現(xiàn)和結(jié)果驗證.實驗結(jié)果表明,該算法在滿足虛擬網(wǎng)絡(luò)輕量級可靠需求的同時,節(jié)省了底層網(wǎng)絡(luò)資源,提高了底層網(wǎng)絡(luò)的長期平均運營收益.

我們首先將CCA-RVNM算法與用GLPK工具解的該問題的ILP結(jié)果進行了比較,對于小規(guī)模問題,ILP能在合理的時間給出最優(yōu)解,是最佳的解決方法.但對于中等規(guī)模虛擬網(wǎng)絡(luò)映射問題,其計算時間無法滿足在線虛擬網(wǎng)絡(luò)映射的需求,如表1所示.而我們提出的算法在計算結(jié)果上接近最優(yōu)算法,更重要的是隨著問題規(guī)模的擴大,我們的計算時間是能夠滿足虛擬網(wǎng)絡(luò)在線映射需求的.

表1 ILP vs CCA-RVNM

為了更好地說明CCA-RVNM的優(yōu)點,本文還將CCA-RVNM與其它兩個在線虛擬網(wǎng)絡(luò)映射算法(如表2所示),從底層網(wǎng)絡(luò)長期平均運營收益(一段時間內(nèi)底層網(wǎng)絡(luò)承載虛擬網(wǎng)絡(luò)所獲收益的平均值)、虛擬網(wǎng)絡(luò)請求接受率(成功映射的虛擬網(wǎng)絡(luò)個數(shù)/所有虛擬網(wǎng)絡(luò)請求個數(shù))、底層網(wǎng)絡(luò)長期平均收益開銷比(一段時間內(nèi)底層網(wǎng)絡(luò)承載虛擬網(wǎng)絡(luò)所獲收益/承載虛擬網(wǎng)絡(luò)資源開銷)三個方面進行了比較.

表2 比較算法

實驗的設(shè)置如下:底層物理網(wǎng)絡(luò)拓?fù)溆蒅T-ITM工具隨機產(chǎn)生[9],其中包含120個節(jié)點和600條鏈路,與一個中型規(guī)模的ISP運營商類似.物理網(wǎng)絡(luò)節(jié)點計算資源與鏈路帶寬資源服從30-80的均勻分布.虛擬網(wǎng)絡(luò)節(jié)點的度為2-5,節(jié)點個數(shù)隨機產(chǎn)生且服從3-10的均勻分布,每一對虛擬網(wǎng)絡(luò)節(jié)點以0.5的概率相連.虛擬網(wǎng)絡(luò)節(jié)點計算資源需求服從0-15的均勻分布,鏈路帶寬資源需求服從0-30的均勻分布.我們假設(shè)在每100個時間單元內(nèi)虛擬網(wǎng)絡(luò)請求的到達服從均值為5的泊松分布,每一個虛擬網(wǎng)絡(luò)的生存時間服從指數(shù)分布,其平均生存時間為600個時間單元.實驗中設(shè)置節(jié)點失效的間隔時間為20000個時間單位,并假設(shè)在下一次失效到來前上一次的失效節(jié)點已被修復(fù).每次模擬實驗運行50000個時間單元,大約包含2500個虛擬網(wǎng)絡(luò)請求.算法1中使用的距離約束k,我們將其設(shè)置為3.

下面是通過模擬實驗得出的結(jié)果:

(1)CCA-RVNM算法的長期運行平均收益和虛擬網(wǎng)絡(luò)請求接受率高于Hybrid-SVNE和DP-VNE算法.

如圖4和圖5所示,算法CCA-RVNM的底層網(wǎng)絡(luò)長期運行平均收益相比于Hybrid-SVN平均高出6.9%,相比于DP-VNE平均高出13.8%.這是因為CCA-RVNM的節(jié)點映射策略在虛擬網(wǎng)絡(luò)映射成功率方面優(yōu)于Hybrid-SVNE中采用的映射策略,且CCA-RVNM不用預(yù)留底層保護資源,使底層網(wǎng)絡(luò)資源能用來映射更多的虛擬網(wǎng)絡(luò),提高了虛擬網(wǎng)絡(luò)的接受率,從而獲得了較高的收益.而DP-VNE算法在鏈路映射階段很難為所有的虛擬網(wǎng)絡(luò)鏈路找到底層不相交的路徑,從而導(dǎo)致較低的虛擬網(wǎng)絡(luò)接受率和長期平均收益.

(2) CCA-RVNM算法的長期收益開銷比高于 Hybrid-SVNE 和 DP-VNE算法.

如圖6所示,從長期收益開銷比來看,CCA-RVNM高于其它兩種算法,主要是因為Hybrid-SVNE預(yù)先分配了保護資源,使底層可用于映射虛擬鏈路的資源減少,從而降低了資源利用率.而DP-VNE算法為了找到不相交的兩條路徑,不得不映射到較長的底層物理鏈路上,從而增加了映射開銷.

6 結(jié)論

本文針對虛擬網(wǎng)可靠性問題提出了一種基于割集和擁塞感知的虛擬網(wǎng)絡(luò)映射算法,實驗表明該算法在滿足虛擬網(wǎng)絡(luò)輕量級可靠需求的前提下,能最大限度提高底層網(wǎng)絡(luò)的資源利用效用.該成果可應(yīng)用于支持網(wǎng)絡(luò)虛擬化技術(shù)的骨干網(wǎng)絡(luò)或數(shù)據(jù)中心網(wǎng)絡(luò)環(huán)境中,為網(wǎng)絡(luò)服務(wù)的提供商獲取更多的運營收益.

[1]Feamster N,Gao L,Rexford J.How to lease the Internet inyour spare time[J].ACM SIGCOMM Computer Communication Review,2007,37(1):61-64.

[2]程祥,張忠寶,蘇森,楊放春.虛擬網(wǎng)絡(luò)映射問題研究綜述[J].通信學(xué)報,2011,32(10):143-151.

Cheng X ,Zhang Z,Su S,et al.Survey of virtual network embedding problem[J].Journal on Communications,2011,32(10):143-151.(in Chinese)

[3]Yu M,Yi Y,Rexford J,et al..Rethinking virtual network embedding:substrate support for path splitting and migration[J].ACM SIGCOMM Computer Communication Review,2008,38(2):17-29.

[4]Chowdhury N,Rahman M,Boutaba R.ViNEYard:virtual network embedding algorithms with coordinated node and link mapping[J].IEEE/ACM Transactions on Networking,2012,20(1):206-219.

[5]Lischka J,Karl H.A virtual network mapping algorithm based on subgraph isomorphism detection[A].Proc the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures[C].ACM,2009.81-88.

[6]Rahman M,Aib I,Boutaba R.SVNE:Survivable virtual network embedding algorithms for network virtualization[J].IEEE Transactions on Network and Service Management.2013,10 (2):105-118.

[7]Yeow W L,Westphal C,Kozat U.Designing and embedding reliable virtual infrastructures[J].ACM SIGCOMM Computer Communication Review,2012,41(2):51-64.

[8]Su S,Cheng X,Zhang Z,et al.Virtual network embedding with survivable routing[J].Journal of Internet Technology,2013,14(5):741-750.

[9]Zegura E W,Calvert K L,Bhattacharjee S.How to model an Internetwork[A].Proc IEEE INFOCOM[C].San Francisco,1996.594-602.

[10]Cheng X,Su S,Zhang Z,et al.Virtual network embedding through topology-aware node ranking[J].ACM SIGCOMM Computer Communication Review,2011,41(2):39-47.

[11]Cheng X,Su S,Zhang Z,et al.Virtual network embedding through topology awareness and optimization[J].Computer Networks,2012,56(6):1797-1813.

[12]程祥,張忠寶,蘇森,楊放春.基于粒子群優(yōu)化的虛擬網(wǎng)絡(luò)映射算法[J].電子學(xué)報,2011,10:2240-2244.

Cheng X ,Zhang Z,Su S,et al.Virtual network embedding based on particle swarm optimization[J].Acta Electronica Sinica,2011,39(10):2240-2244.(in Chinese)

劉光遠(yuǎn) 男,1981年出生.北京郵電大學(xué)網(wǎng)絡(luò)技術(shù)研究院博士.現(xiàn)為石家莊鐵道大學(xué)信息學(xué)院教師.研究方向為云計算、網(wǎng)絡(luò)虛擬化.

E-mail:gyuanliu@163.com

蘇 森 男,1971年出生.北京郵電大學(xué)網(wǎng)絡(luò)技術(shù)研究院教授,博士生導(dǎo)師.研究方向為下一代網(wǎng)絡(luò)、服務(wù)計算.

The Research of Reliable Virtual Network Mapping Algorithm

LIU Guang-yuan1,SU Sen2

(1.SchoolofInformationScienceandTechnology,ShijiazhuangTiedaoUniversity,Shijiazhuang,Hebei050043,China;2.StateKeyLaboratoryofNetworkingandSwitchingTechnology,BeijingUniversityofPostsandTelecommunications,Beijing100876,China)

Network virtualization has been proposed as a promising way for running multiple customized virtual networks (VNs) on a shared infrastructure.However,how to provide reliable VN against substrate infrastructure failures has become an increasingly important issue.In this paper,we present a novel VN mapping scheme based on cutset and congestion awareness for the VN topology remain maximizing connected in the event of single substrate node failure.Simulation results show that algorithm can gain more optimal substrate long-term average revenue compared to the previous algorithms without reserving protection resource.

network virtualization; virtual network mapping; maximizing VN topology connected; cutset and congestion awareness

2015-01-17;

2016-05-26；責(zé)任編輯:藍紅杰

國家自然科學(xué)基金(No.61170274 ); 河北省教育廳科研基金(No.QN2016270)

TP393

A

0372-2112 (2016)08-1820-06