陳曉華,李春芝,陳良育,曾振柄
(1.湖州師范學院信息工程學院 湖州313000;2.華東師范大學軟件學院 上海200062;3.上海大學數(shù)學系 上海200444)
網(wǎng)絡虛擬化[1],是未來互聯(lián)網(wǎng)、云計算和軟件定義網(wǎng)絡的重要技術[2~6]。多個虛擬網(wǎng)絡能夠共享同一底層物理網(wǎng)絡資源。虛擬化技術分割、整合網(wǎng)絡基礎設施資源,使得在不影響現(xiàn)有網(wǎng)絡情況下部署新的網(wǎng)絡架構、協(xié)議以及應用成為可能。
隨著網(wǎng)絡虛擬化技術的發(fā)展,多路徑虛擬鏈路映射成為網(wǎng)絡虛擬化的重要技術[7]?;诙嗌唐妨鞯奶摂M網(wǎng)絡鏈路映射[8]以底層網(wǎng)絡總體資源消耗最低的方式映射虛擬鏈路,取得較好的系統(tǒng)收益。然而基于多商品流的多路徑鏈路映射算法時間復雜度受虛擬網(wǎng)絡以及底層網(wǎng)絡規(guī)模影響較大,難以滿足在線虛擬網(wǎng)絡映射的實時性要求;且虛擬網(wǎng)絡請求是一個動態(tài)變化的過程。因此研究虛擬網(wǎng)絡映射動態(tài)過程,設計有效的虛擬網(wǎng)絡多路徑鏈路映射算法對于保證在線虛擬網(wǎng)絡映射的實時性具有重要意義。
虛擬網(wǎng)絡多路徑鏈路映射主要研究有:
[8]在底層網(wǎng)絡支持路徑分裂基礎上,首次提出了基于多商品流的虛擬網(wǎng)絡多路徑鏈路映射,與單路徑鏈路映射相比取得了更好的底層網(wǎng)絡資源利用率和系統(tǒng)收益;
·參考文獻[9]提出基于最短路徑疊加的虛擬網(wǎng)絡多路徑鏈路映射,降低了虛擬網(wǎng)絡多路徑映射的時間復雜度,但犧牲了底層資源利用率及系統(tǒng)收益。
圖1中,同時到來4個虛擬網(wǎng)絡請求,如圖1(a)~圖1(d)所示。方案一如圖1(e)所示,選擇基于多商品流的映射方案,底層網(wǎng)絡成功映射VN1,導致物理資源耗盡而無法映射VN2、VN3和VN4。而方案二選擇了另外一種方法,如圖1(f)所示,因為無法找到足夠的物理資源而拒絕了VN1,從而保留了足夠的資源,成功映射VN2、VN3和VN4。從靜態(tài)角度看,方案一能夠映射較大資源請求的VN1,比方案二優(yōu)越;但虛擬網(wǎng)絡映射是動態(tài)過程,方案二能夠提高較小規(guī)模虛擬網(wǎng)絡映射成功率,影響了底層網(wǎng)絡的整體收益,而且方案一的多商品流算法計算復雜度高,并不適合大規(guī)模虛擬網(wǎng)絡及底層網(wǎng)絡環(huán)境。
網(wǎng)絡虛擬化動態(tài)特征包括虛擬網(wǎng)絡、底層網(wǎng)絡和映射算法的動態(tài)特征,具體如下。
·虛擬網(wǎng)絡動態(tài)特征:虛擬網(wǎng)絡請求的到來時間、存在時間、虛擬網(wǎng)絡節(jié)點個數(shù)、虛擬鏈路條數(shù)、節(jié)點CPU、鏈路帶寬等。
·底層網(wǎng)絡動態(tài)特征:隨著虛擬網(wǎng)絡請求的到來和離開,底層網(wǎng)絡剩余CPU、鏈路剩余帶寬資源量和分布將會動態(tài)變化。
·映射算法動態(tài)特征:隨著虛擬網(wǎng)絡請求資源量的變化,在不同映射算法下,底層網(wǎng)絡資源利用率、虛擬網(wǎng)絡接收率、底層網(wǎng)絡鏈路資源利用率和虛擬網(wǎng)絡拓撲大小是不同的。
從圖1可以看出由于虛擬網(wǎng)絡映射的動態(tài)特征,使得虛擬網(wǎng)絡映射存在代價收益動態(tài)倒置現(xiàn)象,定義如下:假設有A和B兩種不同虛擬網(wǎng)絡映射算法,從單個虛擬網(wǎng)絡映射的靜態(tài)角度看,A能夠映射較小虛擬網(wǎng)絡,B能夠映射較大虛擬網(wǎng)絡,A映射花費的代價要高于B;由于底層網(wǎng)絡資源有限,雖然A花費的代價要高于B,但是A能夠映射較多的較小虛擬網(wǎng)絡,使得系統(tǒng)收益高于B,本文稱之為虛擬網(wǎng)絡映射代價收益動態(tài)倒置現(xiàn)象。
虛擬網(wǎng)絡映射是網(wǎng)絡虛擬化主要問題之一,以下介紹底層網(wǎng)絡、虛擬網(wǎng)絡以及虛擬網(wǎng)絡映射模型。
·底層網(wǎng)絡:本文通過無向圖Gs=(Ns,Ls,,對底層網(wǎng)絡建模,其中,Ns為節(jié)點集合,Ls為鏈路集合,為節(jié)點屬性集合,為鏈路屬性集合。本文設置節(jié)點屬性為CPU處理器資源,鏈路屬性為帶寬資源。
·虛擬網(wǎng)絡:與底層網(wǎng)絡相同,本文通過無向圖Gv=(Nv,Lv,,對虛擬網(wǎng)絡建模,其中,Nv為節(jié)點集合,Lv為鏈路集合,為節(jié)點屬性集合(CPU處理器資源),為鏈路屬性集合(帶寬資源)。
·虛擬網(wǎng)絡映射:把虛擬節(jié)點和鏈路映射到滿足虛擬資源需求的底層節(jié)點和路徑,可分為節(jié)點映射和鏈路映射。節(jié)點映射分為:一個虛擬網(wǎng)絡的不同節(jié)點不允許映射到同一節(jié)點、一個虛擬網(wǎng)絡的不同節(jié)點可映射到一個節(jié)點。鏈路映射分為單路徑映射以及多路徑映射。本文在一個虛擬網(wǎng)絡的不同節(jié)點不允許映射到同一節(jié)點以及多路徑鏈路映射情況下,研究虛擬網(wǎng)絡映射。
由于多商品流的多路徑映射時間復雜度高,不適合大規(guī)模虛擬網(wǎng)絡及底層網(wǎng)絡的虛擬網(wǎng)絡映射。為了滿足大規(guī)模虛擬網(wǎng)絡映射在線請求的實時性要求,本文設計了基于最小費用流的多路徑鏈路映射算法。
無向網(wǎng)絡:無向網(wǎng)絡NG=(V,A,C),其中V是節(jié)點集合,A是無向邊集合,C是邊容量集合,對于每條邊(i,j)∈A,對應有一個c(i,j)≥0(或簡寫為cij)為邊的容量。
無向網(wǎng)絡流及流量:在NG中,指定一點為源點(記為s),另一點為匯點(記為t),其余的點叫做中間點,坌(i,j)∈A,f={f(i,j)},滿 足 下 述 條 件 的f稱 為s到t的無向網(wǎng)絡流。
·容量限制條件:坌(i,j)∈A,0≤fij≤cij。
·方向條件:坌i,j∈V,fij=-fji,可行流具有方向性。
·平衡條件:對于中間點,流出量等于流入量,即每個
v(f)稱為f的流量。
最小費用流模型:給定NG,每一條邊(i,j)∈A,給定一個單位流量的費用b(i,j)≥0(簡記為)bij。最小費用流問題就是給定s、t和流量m,求出從s到t的流f滿足流量v(f)=m,并使得流的總輸送費用b(f)=取最小值,即
步驟1調用最小費用流算法找到一條虛擬鏈路的最小費用流映射,直到完成所有虛擬鏈路映射。
步驟2找到一條未映射的虛擬鏈路lv,取出鏈路兩端點v1、v2以及鏈路流量vbw。
步驟3找出lv映射的兩底層結點s1和s2。
步驟4創(chuàng)建無向網(wǎng)絡NG=(V,A,C),設置每條邊的單位流量費用。
步驟5調用最小費用流算法,如果找到s1到s2帶寬流量為vbw的最小費用流f,則將f分配給lv。
其中,步驟4中不同的NG參數(shù)及單位流量費用,會產(chǎn)生不同的映射算法,分別為UNMCF-S和UMMCF-L。bw(i,j)表示底層鏈 路l(i,j)剩余的 帶寬總量,bwl(i,j)表示底層鏈路l(i,j)已經(jīng)映射的帶寬總量。UNMCF-S設置NG及單位流量費用如下:容量c(i,j)=bw(i,j),如果c(i,j)==0,表示節(jié)點i與j不存在鏈路;如果bw(i,j)>0,單位流量費用b(i,j)=1;如果bw(i,j)==0,單 位流量費 用b(i,j)=0。UMMCF-L設置NG及單位流量費用如下:容量c(i,j)=bw(i,j),如果c(i,j)==0,表示節(jié)點i與j不存在鏈路;b(i,j)=bwl(i,j)。
算法1的時間復雜度為O(e·n2),其中n為物理網(wǎng)絡的節(jié)點數(shù),e為虛擬網(wǎng)絡的邊數(shù)。
算法1基于最小費用流的虛擬鏈路映射算法
輸入:虛擬網(wǎng)絡VN,底層網(wǎng)絡SN;
輸出:虛擬網(wǎng)絡多路徑映射結果;
(1)while(VN存在鏈路未分配)do
(2)取一條未分配虛擬鏈路1v:(v1,v2,vbw);
(3)找到虛擬節(jié)點(v1,v2)對應底層節(jié)點(s1,s2);
(4)創(chuàng)建NG,設置每條邊的單位流量費用;
(5)if(調用最小費用流算法找到了s1到s2及帶寬流量vbw的最小費用流f)
(6)映射虛擬鏈路1v到底層網(wǎng)絡最小費用流f;
(7)else return null;
(8)end if
(9)end while
(10)return虛擬鏈路多路徑映射結果
本節(jié)評估虛擬網(wǎng)絡多路徑映射,首先介紹性能評價指標及仿真環(huán)境,然后對仿真結果進行說明和評估。
與參考文獻[8]一致,本文定義收益成本比、系統(tǒng)收益、虛擬網(wǎng)絡接收率以及映射時間作為性能指標。
(1)收益成本比
定義R(Gv(t))為系統(tǒng)收益:R(Gv(t))CPU(nv),其中,為接收的虛擬網(wǎng)絡鏈路帶寬總和,為接收的虛擬網(wǎng)絡節(jié)點CPU總和。定義C(Gv(t))為虛擬網(wǎng)絡映射代價:C(Gv(t))為接收的虛擬鏈路lv對應底層網(wǎng)絡路徑的帶寬總和,fp為接收的虛擬鏈路lv對應底層網(wǎng)絡路徑上的鏈路;定義平均收益成本比為
(2)系統(tǒng)收益
(3)虛擬網(wǎng)絡接收率
(4)映射時間
定義在T個時間窗內完成虛擬網(wǎng)絡請求映射所花費的時間。
因為多商品流算法受虛擬網(wǎng)絡以及底層網(wǎng)絡規(guī)模影響較大,本文采用GT-ITM工具隨機生成一個由50個節(jié)點、約140條鏈路組成的較小底層網(wǎng)絡拓撲。底層網(wǎng)絡節(jié)點CPU資源和鏈路帶寬資源服從50~100的均勻分布。每個時間窗為100個時間單元。虛擬網(wǎng)絡請求過程模擬泊松過程,在每個時間窗內虛擬網(wǎng)絡請求到達個數(shù)服從均值為20的泊松分布,每個虛擬網(wǎng)絡的生存時間服從均值為5個時間窗的指數(shù)分布,每個虛擬網(wǎng)絡請求節(jié)點個數(shù)服從2~8的均勻分布,每對虛擬網(wǎng)絡節(jié)點以0.5的概率相連;設置虛擬網(wǎng)絡節(jié)點CPU資源與鏈路帶寬資源需求服從0~40的均勻分布,虛擬網(wǎng)絡映射等待時間為1個時間窗。每次模擬試驗運行約25 000個時間單元,包含5 000個虛擬網(wǎng)絡請求。實驗在10個不同實例運行,取平均值作為結果。為了評價虛擬網(wǎng)絡多路徑鏈路映射結果,本文設置節(jié)點映射為貪心算法,多路徑鏈路映射分別采用本文提出的UNMCF-S、UNMCF-L以及多商品流鏈路映射算法MCF[8]。因為最短路徑疊加算法[9]較MCF算法系統(tǒng)收益小,本文不與之比較。
(1)基于最小費用流的虛擬網(wǎng)絡映射算法提高了系統(tǒng)收益及虛擬網(wǎng)絡接收率
圖2、圖3表明UNMCF-S、UNMCF-L與MCF比較,本文所提算法的系統(tǒng)收益及虛擬網(wǎng)絡接收率得到提高。例如在映射1 000個虛擬網(wǎng)絡時,MCF算法的系統(tǒng)收益為10.739 51,而UNMCF-S算法提高到11.691 41。同時MCF算法的虛擬網(wǎng)絡接收率為0.305 31,而UNMCF-S及UNMCF-L算法的虛擬網(wǎng)絡接收率為0.40,較MCF提高了10%。這是由于虛擬網(wǎng)絡映射具有動態(tài)性,本文所提算法能夠映射更多的較小規(guī)模虛擬網(wǎng)絡,即提高虛擬網(wǎng)絡接收率,從而提高了系統(tǒng)收益。圖2、圖3也驗證了虛擬網(wǎng)絡映射代價收益動態(tài)倒置現(xiàn)象的存在。
(2)基于最小費用流的虛擬網(wǎng)絡映射算法極大地降低了映射時間
基于最小費用流映射算法的時間復雜度低于基于多商品流映射算法,其更適合在線虛擬網(wǎng)絡映射。以圖4可以看出,基于多商品流映射算法需要首先找到是否有解,然后找到最優(yōu)解,雖然收益成本比值較基于最小費用流映射算法高(如圖5所示),但是映射時間遠遠超過基于最小費用流的映射算法。
本文分析了虛擬網(wǎng)絡映射動態(tài)過程,發(fā)現(xiàn)了虛擬網(wǎng)絡映射代價收益動態(tài)倒置現(xiàn)象?;诖耍岢鎏摂M網(wǎng)絡多路徑鏈路映射的最小費用流模型,設置單位流量映射費用單價,進而設計基于最小費用流的最小代價、最小負載虛擬網(wǎng)絡多路徑鏈路映射算法,提高了虛擬網(wǎng)絡接收率及系統(tǒng)收益,有效降低了算法時間復雜度,保證了在線虛擬網(wǎng)絡映射的實時性要求,適用于在大規(guī)模底層網(wǎng)絡上創(chuàng)建虛擬網(wǎng)絡。
致謝本文仿真實驗在C3S2服務器完成,感謝湖州師范學院C3S2計算中心的大力支持。
參考文獻
1 Chowdhury N M M K,Boutaba R.Network virtualization:state of the art and research challenges.IEEE Communications Magazine,2009,47(7):20~26
2 Anderson T,Peterson L,Shenker S,et al.Overcoming the internet impass through virtualization.IEEE Computer Magazine,2005,38(4):34~41
3 Sun G,Anand V,Yu H F,et al.Optimal provisioning for elastic service oriented virtual network request in cloud computing.Proceedings of Global Communications Conference(GLOBECOM),Anaheim,CA,2012:2541~46
4 Drutskoy D,Keller E,Rexford J.Scalable network virtualization in software-defined networks.IEEE Internet Computing,2013,17(2):21~27
5 Sharkh M A,Jammal M,Shami A,et al.Resource allocation in a network-based cloud computing environment:design challenges.IEEE Communications Magazine,2013,51(11):46~52
6 Wei X L,Chen M,Fan J H,et al.Architecture of the data center network.Journal of Software,2013,24(2):295~316
7 Fischer A,Botero J,Beck M,et al.Virtual network embedding:a survey.IEEE Communications Surveys and Tutorials,2013,15(4):1888~1906
8 Yu M,Yi Y,Rexford J,et al.Rethinking virtual network embedding:substrate support for path splitting and migration.Proceedings of Computer Communication Review,2008,38(2):17~27
9 Zhang Z,Cheng X,Su S,et al.A unified enhanced particle swarm optimization-based virtual network embedding algorithm.International Journal of Communication Systems,2013,26(8):1054~1073