何 源，侯韶華

(南京郵電大學(xué) 電子科學(xué)與工程學(xué)院，江蘇 南京 210003)

WDM光網(wǎng)絡(luò)虛擬映射協(xié)同RWA算法研究

何 源，侯韶華

(南京郵電大學(xué) 電子科學(xué)與工程學(xué)院，江蘇 南京 210003)

當(dāng)前，物聯(lián)網(wǎng)與云計(jì)算等產(chǎn)業(yè)的發(fā)展，使得波分復(fù)用(WDM)光網(wǎng)絡(luò)地位越來越重要。在WDM光網(wǎng)絡(luò)中的關(guān)鍵技術(shù)是網(wǎng)絡(luò)虛擬化及路由與波長分配(RWA)。然而，性能優(yōu)越的虛擬網(wǎng)絡(luò)(VN)映射和RWA算法有眾多約束條件，這使得目標(biāo)求解成為了一個(gè)NP-hard問題，因而更多的研究是將其分為VN映射、RWA子問題進(jìn)行研究?；诖耍芯苛藢⒐饩W(wǎng)絡(luò)虛擬化映射與RWA相結(jié)合的方案，并提出最小路由跳數(shù)以及最小波長平面的兩種啟發(fā)式算法。算法主要分析VN映射對路由及波長總數(shù)的需求。將這兩種算法與將VN映射、RWA作為子問題研究的Two-Step方案進(jìn)行對比，并進(jìn)行性能仿真。仿真結(jié)果表明，提出的方案比Two-Step方案性能優(yōu)越，同時(shí)自適應(yīng)虛擬網(wǎng)絡(luò)節(jié)點(diǎn)映射性能優(yōu)于固定節(jié)點(diǎn)映射的性能。

波分復(fù)用；網(wǎng)絡(luò)虛擬化；啟發(fā)式算法；映射算法；波長分配

0 引 言

隨著全球LTE網(wǎng)絡(luò)大規(guī)模部署，物聯(lián)網(wǎng)、云計(jì)算[1]等產(chǎn)業(yè)的不斷完善，越來越多的數(shù)據(jù)中心連接到物理網(wǎng)絡(luò)基礎(chǔ)設(shè)施，給當(dāng)前通信網(wǎng)絡(luò)的業(yè)務(wù)流量帶來指數(shù)級的增長，使得信息產(chǎn)業(yè)向?qū)拵Щ较虬l(fā)展。光網(wǎng)絡(luò)技術(shù)的發(fā)展，為高帶寬應(yīng)用提供了海量帶寬資源，然而現(xiàn)有光網(wǎng)絡(luò)可用波長資源有限[2]，故而其帶寬資源利用率低。而目前網(wǎng)絡(luò)僵化[3]越來越嚴(yán)重，導(dǎo)致現(xiàn)有網(wǎng)絡(luò)架構(gòu)已經(jīng)難以滿足互聯(lián)網(wǎng)業(yè)務(wù)的多樣性需求，給當(dāng)前光傳送網(wǎng)帶來了巨大壓力，網(wǎng)絡(luò)的可持續(xù)發(fā)展面臨嚴(yán)峻挑戰(zhàn)。光網(wǎng)絡(luò)虛擬化[4]可將虛擬網(wǎng)絡(luò)與底層物理光網(wǎng)絡(luò)有效隔離，使得網(wǎng)絡(luò)資源配置更加靈活，從而有效提升網(wǎng)絡(luò)的整體性能。因此光網(wǎng)絡(luò)虛擬化被認(rèn)為是打破這一僵局的關(guān)鍵技術(shù)之一。

當(dāng)前，在底層網(wǎng)絡(luò)上已有眾多基于分組交換網(wǎng)絡(luò)的虛擬網(wǎng)絡(luò)(VN)映射研究，但在WDM光網(wǎng)絡(luò)中，如何合理映射虛擬網(wǎng)絡(luò)是一個(gè)富有挑戰(zhàn)的問題，也是—個(gè)NP-hard問題[5-6]。為了降低WDM網(wǎng)絡(luò)虛擬化問題的復(fù)雜度，當(dāng)前最被認(rèn)同且應(yīng)用最廣泛的方法是將VN映射和RWA作為兩個(gè)獨(dú)立的子問題[7]來考慮。然而這種方法有鏈路映射失敗或者映射的物理路徑長度過大的缺點(diǎn)，從而浪費(fèi)物理鏈路帶寬資源，最終降低VN映射的接收率。

針對虛擬網(wǎng)絡(luò)映射問題，文中提出光網(wǎng)絡(luò)虛擬化映射協(xié)同路由波長分配(RWA)的方案。最近在控制平面上對軟件定義網(wǎng)絡(luò)(SDN)[8]的研究，顯示出這種方案是可行的。根據(jù)該方案提出了兩種啟發(fā)式算法[9-10]，為了盡量減少對網(wǎng)絡(luò)資源的需求，對算法中的候選節(jié)點(diǎn)的選擇加上一定的限制條件，并進(jìn)行仿真。仿真結(jié)果表明，該算法對VN映射的接收率有明顯的提升作用。

1 虛擬網(wǎng)絡(luò)映射啟發(fā)式算法

主要目標(biāo)是搜索每個(gè)虛擬節(jié)點(diǎn)的虛擬映射，尋找每條虛擬鏈路的路由并進(jìn)行波長分配，使WDM網(wǎng)絡(luò)中使用的總波長數(shù)盡可能小，同時(shí)盡量使每個(gè)物理節(jié)點(diǎn)的計(jì)算資源負(fù)載均衡[11]。在進(jìn)行算法研究之前，設(shè)定前提條件如下：

一個(gè)WDM網(wǎng)絡(luò)與一組光纖鏈路E，每條光纖鏈路有W個(gè)波長，一組物理節(jié)點(diǎn)N，每物理節(jié)點(diǎn)擁有一定的計(jì)算資源。用無向加權(quán)圖G=(N,E)對此網(wǎng)絡(luò)進(jìn)行建模。此外，給定一組VN請求，其中每個(gè)虛擬節(jié)點(diǎn)v需一定的計(jì)算資源，并且可以被映射到一組候選物理節(jié)點(diǎn)上，每條虛擬鏈路需一條光鏈路。

文中所討論的映射與路由分配算法所受約束如下：

(1)一個(gè)VN節(jié)點(diǎn)只能被映射到一個(gè)物理網(wǎng)絡(luò)(SN)節(jié)點(diǎn)；

(2)同一個(gè)VN中的兩個(gè)節(jié)點(diǎn)不能同時(shí)被映射到同一個(gè)SN的節(jié)點(diǎn)上；

(3)一條虛鏈路映射到一條物理光通道上，且受波長連續(xù)性影響；

(4)兩節(jié)點(diǎn)間的光路流量受光路的總?cè)萘考s束；

(5)同一個(gè)VN請求的節(jié)點(diǎn)資源需求不超過SN節(jié)點(diǎn)所具有的資源總和；

(6)同一根光纖中不同的光通道必須使用不同的波長，且同一條光纖鏈路的總光路不超過這條光纖鏈路的容量W。

為了提高映射成功率，在對一組VN請求進(jìn)行映射前，先將這組中的每一個(gè)VN請求以虛擬鏈路的總數(shù)進(jìn)行降序排序，然后以降序的順序?qū)@組VN依次映射。在對具體的一個(gè)VN請求進(jìn)行映射時(shí)，將這個(gè)VN請求中虛擬節(jié)點(diǎn)以節(jié)點(diǎn)度降序排序，然后依次映射。對于首個(gè)節(jié)點(diǎn)映射，利用貪婪算法[12]，將它映射到物理網(wǎng)絡(luò)中可用計(jì)算資源值最大的節(jié)點(diǎn)上，然后以此節(jié)點(diǎn)為中心節(jié)點(diǎn)，設(shè)為nv，給出其余候選節(jié)點(diǎn)到nv的距離dv，利用dv值來控制候選節(jié)點(diǎn)平均數(shù)量。

為了提高映射效率，在VN映射前對映射所需要的候選物理節(jié)點(diǎn)進(jìn)行篩選，將滿足條件的物理節(jié)點(diǎn)作為候選物理節(jié)點(diǎn)集，它能提供的可用計(jì)算資源需大于等于虛擬節(jié)點(diǎn)v的所需要求。接著在這些節(jié)點(diǎn)集中選出候選物理節(jié)點(diǎn)，映射之后，更新物理節(jié)點(diǎn)可用計(jì)算資源，如式(1)所示：

restNodeComputionn=preNodeComputionn-nodeComputionn

(1)

其中，restNodeComputionn為物理節(jié)點(diǎn)n剩余可用計(jì)算資源；preNodeComputionn為節(jié)點(diǎn)n映射前所具有的計(jì)算資源；nodeComputionn為當(dāng)前映射的節(jié)點(diǎn)所需計(jì)算資源。

提出的兩種啟發(fā)式算法為最小路由跳數(shù)(Min_Span)算法和最小波長平面(Min_W)算法。這兩種算法都基于分層圖法[13-14]，即在每個(gè)波長平面網(wǎng)絡(luò)中進(jìn)行搜索符合條件映射。

Min_Span算法：試圖找到最小路由跳數(shù)的VN映射。流程如下：

(1)對于每個(gè)VN請求，根據(jù)網(wǎng)絡(luò)拓?fù)湟?guī)模以及虛擬網(wǎng)絡(luò)請求設(shè)定路由跳數(shù)i的范圍。

(2)當(dāng)i=1時(shí)，在波長平面j=1上開始節(jié)點(diǎn)映射，搜索符合約束條件的路由，如果搜索到滿足條件的映射，算法停止，執(zhí)行步驟(4)。如果沒有滿足條件的映射，那么在j=2的平面上搜索，直到j(luò)達(dá)到最大值。

(3)當(dāng)i=1，j已到達(dá)波長平面最大值時(shí)，沒有找到符合條件的映射，那么在所有波長平面搜索i=2的映射，如果找到符合條件的映射，則執(zhí)行步驟(4)。當(dāng)i達(dá)到最大值時(shí)，依然沒找到滿足要求的映射，則請求阻塞，執(zhí)行步驟(4)。

(4)回到步驟(2)，進(jìn)行下一個(gè)VN映射請求。

該算法的缺點(diǎn)是，在所有波長平面中搜索最少路由跳數(shù)映射，可能無法使網(wǎng)絡(luò)效益最大化。

Min_W算法：試圖找到使波長平面以及波長跳數(shù)盡量小的一個(gè)VN映射。流程如下：

(1)動態(tài)設(shè)置每個(gè)VN映射所允許的最大路由跳數(shù)值i，以及最大波長平面數(shù)(maxLayer)的最小值j。

(2)依次執(zhí)行Min_Span方法的步驟(2)～(4)，并返回請求阻塞的VN映射。

(3)對于步驟(2)中阻塞的請求，在剩余的W-j波長平面范圍內(nèi)再次尋找這個(gè)映射。如果沒有找到一個(gè)映射滿足條件，那么請求阻塞，繼續(xù)搜索步驟(2)中返回的其他VN請求。

文中提出的算法對文獻(xiàn)[5]中的遞歸和窮舉算法的i跳路由映射步驟做了一個(gè)改進(jìn)：如圖1(c)所示有序的候選節(jié)點(diǎn)映射，虛擬節(jié)點(diǎn)11映射到物理節(jié)點(diǎn)B上。但是，連續(xù)虛擬節(jié)點(diǎn)映射(14，C)變得無效，因?yàn)樘摂M鏈接(11，14)上不存在單跳路徑。算法退回到上一步，重新選擇11的映射節(jié)點(diǎn)。若無論節(jié)點(diǎn)11如何映射，均無法滿足條件，那么繼續(xù)退回到上一步，直至找到滿足條件的點(diǎn)。

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

與文獻(xiàn)[5]的另一個(gè)區(qū)別是，針對每個(gè)虛擬節(jié)點(diǎn)v，算法對其候選物理節(jié)點(diǎn)n按照式(2)定義的節(jié)點(diǎn)資源量(mn)進(jìn)行降序排序，以減少WDM網(wǎng)絡(luò)資源的需求，并實(shí)現(xiàn)物理節(jié)點(diǎn)的計(jì)算資源負(fù)載均衡。

(2)

2 仿真與結(jié)果分析

將所提出的方案與將VN映射和RWA分步進(jìn)行的方案做了比較。對于VN映射方案，首先在基礎(chǔ)網(wǎng)絡(luò)中應(yīng)用文獻(xiàn)[6]中提供的方法進(jìn)行VN映射，然后在WDM網(wǎng)絡(luò)中應(yīng)用分層圖方案進(jìn)行波長分配。對于RWA的分步進(jìn)行，模擬了一個(gè)場景：一種是同時(shí)對鏈接和節(jié)點(diǎn)進(jìn)行負(fù)載均衡(Two_Step)，這與使WDM網(wǎng)絡(luò)中使用的波長數(shù)最少具有類似的目的。上述方案固定了任意兩個(gè)物理節(jié)點(diǎn)的最短路由。

使用如圖2所示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，此處假設(shè)每條鏈路擁有64個(gè)可用波長?，F(xiàn)在有一組VN請求，每個(gè)VN請求的虛擬節(jié)點(diǎn)的數(shù)量在[3,5]范圍上隨機(jī)生成。每個(gè)虛擬節(jié)點(diǎn)度范圍在[1,3]，也為隨機(jī)生成，dv為預(yù)先定值。每個(gè)實(shí)驗(yàn)重復(fù)20次，數(shù)據(jù)源為隨機(jī)生成，然后得出結(jié)果。可以通過調(diào)整dv的平均值大小來控制虛擬節(jié)點(diǎn)的候選節(jié)點(diǎn)數(shù)(cv)的取值范圍。

圖2 20節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)鋱D

圖3展示了在cv=8情況下，隨著VN請求數(shù)增加時(shí)的網(wǎng)絡(luò)資源需求情況。

圖3 cv=8的虛擬網(wǎng)絡(luò)映射性能對比

在圖3中，相對Two_Step而言，Min_W使得波長指數(shù)最大值(Wmax)更低、波長跨越更少。例如，當(dāng)VN請求的數(shù)目是100時(shí)，Min_W比Two_Step需要的波長平面數(shù)少30%，同時(shí)少約30%的波長跳數(shù)，且Two-Step需要的波長數(shù)已超過40個(gè)。從仿真結(jié)果可以看出，Min_W具有最低的Wmax，但路由跳數(shù)比Min_Span略多，因?yàn)镸in_Span主要是要求路由跳數(shù)最小，而Min_W側(cè)重于maxLayer最小。

圖4展示了虛擬節(jié)點(diǎn)映射的靈活性增加對網(wǎng)絡(luò)資源的影響。

圖4(a)和(b)展示了Wmax以及每個(gè)虛擬鏈路的平均波長跳數(shù)。例如，對于固定的節(jié)點(diǎn)映射(cv=1)，Wmax值在64，此時(shí)用盡了所有可用波長，每個(gè)虛擬鏈路平均路由跳數(shù)約為3.3。當(dāng)一個(gè)虛擬節(jié)點(diǎn)具有最大的彈性分配(cv=20時(shí)，所有節(jié)點(diǎn)將存在于網(wǎng)絡(luò)中)時(shí)，Min_W的Wmax為17，如果波長足夠多，其值比固定節(jié)點(diǎn)映射少了近78%，同時(shí)Min_W的每個(gè)虛擬鏈路的平均路由跳數(shù)約為1.2，比固定節(jié)點(diǎn)映射少60%。圖4(c)表明，cv值為1時(shí)，三種算法均會發(fā)生阻塞，因?yàn)闆]有足夠的波長資源，但是Two_Step的阻塞率更高些。在Two_Step為2時(shí)，雖然Min_Span還是使用了所有波長，但是并沒有發(fā)生阻塞現(xiàn)象。此時(shí)Min_Span盡可能增加路由跳數(shù)來滿足業(yè)務(wù)請求。當(dāng)cv值在[2,8]這一范圍時(shí)，Two_Step請求還是可能會被阻塞，即使網(wǎng)絡(luò)有足夠的網(wǎng)絡(luò)和計(jì)算資源，這是因?yàn)閮蓚€(gè)虛擬節(jié)點(diǎn)不能被映射到同一個(gè)物理節(jié)點(diǎn)上，而且Two_Step沒有回溯機(jī)制。

圖4 靈活虛擬網(wǎng)絡(luò)映射性能對比

3 結(jié)束語

提出的啟發(fā)式算法協(xié)同考慮WDM光網(wǎng)絡(luò)的虛擬網(wǎng)絡(luò)映射以及RWA問題。仿真結(jié)果表明，該方案比將VN映射與RWA分開進(jìn)行的方案要好，可以節(jié)約高達(dá)30%的光網(wǎng)絡(luò)資源。同時(shí)還證明，相對固定節(jié)點(diǎn)映射，利用靈活可變的自適應(yīng)虛擬節(jié)點(diǎn)映射，可以有效地利用光網(wǎng)絡(luò)資源，以及充分利用網(wǎng)絡(luò)虛擬化的優(yōu)點(diǎn)。

[1] 陳 全,鄧倩妮.云計(jì)算及其關(guān)鍵技術(shù)[J].計(jì)算機(jī)應(yīng)用,2009,29(9):2562-2567.

[2] 肖萍萍,吳健學(xué),周 芳,等.SDH原理與技術(shù)[M].北京:北京郵電大學(xué)出版社,2002:186-197.

[3]AndersonT,PetersonL,ShenkerS,etal.OvercomingtheInternetimpassethroughvirtualization[J].Computer,2005,38(4):34-41.

[4]ZhangS,ShiL,VadrevuCSK,etal.NetworkvirtualizationoverWDMnetworks[C]//IEEE5thinternationalconferenceonadvancednetworksandtelecommunicationsystems.[s.l.]:IEEE,2011:1-3.

[5]LischkaJ,KarlH.Avirtualnetworkmappingalgorithmbasedonsubgraphisomorphismdetection[C]//ACMSIGCOMMVISA.[s.l.]:ACM,2009.

[6]ZhuY,AmmarM.Algorithmsforassigningsubstratenetworkresourcestovirtualnetworkcomponents[C]//ProceedingsofINFOCOM.[s.l.]:IEEE,2006.

[7]YangH,ZhaoY,ZhangJ,etal.Crossstratumoptimizationofapplicationandnetworkresourcebasedongloballoadbalancingstrategyindynamicopticalnetworks[C]//OFC.[s.l.]:[s.n.],2012.

[8] 張 成.軟件定義網(wǎng)絡(luò)的研究及應(yīng)用[D].廣州:華南理工大學(xué),2014.

[9] 卿蘇德.網(wǎng)絡(luò)虛擬化映射算法研究[D].北京:北京郵電大學(xué),2013.

[10] 雷德明.多標(biāo)智能優(yōu)化算法及其應(yīng)用[M].北京:科學(xué)出版社,2009.

[11] 宋紹義.未來互聯(lián)網(wǎng)絡(luò)資源負(fù)載均衡研究[D].北京:北京郵電大學(xué),2014.

[12] 高 玲.光網(wǎng)絡(luò)虛擬化帶寬調(diào)度技術(shù)研究[D].南京:南京郵電大學(xué),2015.

[13] 徐世中,李樂民,王 晟.多光纖波分復(fù)用網(wǎng)動態(tài)路由和波長分配算法[J].電子學(xué)報(bào),2000,28(7):23-27.

[14] 王汝言,張普釗,隆克平,等.WDM網(wǎng)絡(luò)中一種基于分層圖模型的RWA算法[J].光通信技術(shù),2007,31(10):4-6.

Research on Virtual Network Mapping Combined with RWA inWDM Optical Network

HE Yuan，HOU Shao-hua

(College of Electronic Science and Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Recently,with the development of the Internet of Things and Cloud Computing,the optical Wavelength Division Multiplexing (WDM) network becomes more and more important.Virtualization Network (VN) and Routing Wavelength Assignment (RWA) are the key technologies of WDM optical network.However,the superior performance of the VN mapping and RWA,which contains many constraints,is a NP hard problem to the target solving.Therefore,in order to simplify the problem,more research is just based on the subproblem of VN mapping and RWA.Jointly considering problems of VN mapping and RWA in WDM networks,the Min_Span and Min_wavelength algorithm are proposed based on heuristic algorithms.The two algorithms mainly analyzes the total demand of VN mapping in routing spans and the wavelengths,which is simulated and compared with the Two_Step scheme algorithms.The simulation results show that the scheme proposed is better than Two_Step.It also shows that the network design with flexible virtual node mapping can efficiently utilize optical network resources compared to fixed node mapping.

WDM;network virtualization;heuristic algorithm;mapping algorithm;RWA

2016-04-16

2016-08-11

時(shí)間：2017-02-17

何 源(1988-)，男，碩士研究生，研究方向?yàn)楣饩W(wǎng)絡(luò)與光通信；侯韶華，副教授，碩士研究生導(dǎo)師，研究方向?yàn)楣馔ㄐ排c光波技術(shù)。

http://www.cnki.net/kcms/detail/61.1450.TP.20170217.1623.018.html

TP301.6

A

1673-629X(2017)03-0122-04

10.3969/j.issn.1673-629X.2017.03.025