何 源，侯韶華

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

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

何 源，侯韶華

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

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

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

0 引 言

隨著全球LTE網(wǎng)絡(luò)大規(guī)模部署，物聯(lián)網(wǎng)、云計算[1]等產(chǎn)業(yè)的不斷完善，越來越多的數(shù)據(jù)中心連接到物理網(wǎng)絡(luò)基礎(chǔ)設(shè)施，給當前通信網(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]越來越嚴重，導致現(xiàn)有網(wǎng)絡(luò)架構(gòu)已經(jīng)難以滿足互聯(lián)網(wǎng)業(yè)務(wù)的多樣性需求，給當前光傳送網(wǎng)帶來了巨大壓力，網(wǎng)絡(luò)的可持續(xù)發(fā)展面臨嚴峻挑戰(zhàn)。光網(wǎng)絡(luò)虛擬化[4]可將虛擬網(wǎng)絡(luò)與底層物理光網(wǎng)絡(luò)有效隔離，使得網(wǎng)絡(luò)資源配置更加靈活，從而有效提升網(wǎng)絡(luò)的整體性能。因此光網(wǎng)絡(luò)虛擬化被認為是打破這一僵局的關(guān)鍵技術(shù)之一。

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

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

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

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

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

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

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

(2)同一個VN中的兩個節(jié)點不能同時被映射到同一個SN的節(jié)點上；

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

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

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

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

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

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

restNodeComputionn=preNodeComputionn-nodeComputionn

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)

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

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

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

圖2 20節(jié)點網(wǎng)絡(luò)拓撲圖

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

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

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

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

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

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

3 結(jié)束語

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

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

[2] 肖萍萍,吳健學,周 芳,等.SDH原理與技術(shù)[M].北京:北京郵電大學出版社,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].廣州:華南理工大學,2014.

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

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

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

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

[13] 徐世中,李樂民,王 晟.多光纖波分復用網(wǎng)動態(tài)路由和波長分配算法[J].電子學報,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

時間：2017-02-17

何 源(1988-)，男，碩士研究生，研究方向為光網(wǎng)絡(luò)與光通信；侯韶華，副教授，碩士研究生導師，研究方向為光通信與光波技術(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