徐冬冬,鄭淑麗,曹 敏,樊玉琦

(合肥工業(yè)大學(xué) 計算機與信息學(xué)院,安徽 合肥 230009)

?

基于openflow網(wǎng)絡(luò)的虛擬網(wǎng)絡(luò)映射研究

徐冬冬,鄭淑麗,曹 敏,樊玉琦

(合肥工業(yè)大學(xué) 計算機與信息學(xué)院,安徽 合肥 230009)

基于多個openflow網(wǎng)絡(luò)自治域提出各域共同合作完成虛擬網(wǎng)絡(luò)映射,由于各域公開的信息有限,傳統(tǒng)的單域映射方法不適用于虛擬網(wǎng)絡(luò)跨域映射,文章提出一種競價機制的跨域虛擬網(wǎng)絡(luò)映射框架(bidding multi-domain virtual network mapping,B-MDVNM),在框架內(nèi)針對虛擬節(jié)點映射采用啟發(fā)式均衡算法(balancing heuristic algorithm,BHA),并通過仿真實驗和現(xiàn)有的虛擬節(jié)點映射算法從效率、開銷、性能等方面進(jìn)行對比來驗證BHA的有效性。

虛擬網(wǎng)絡(luò);跨域映射;openflow網(wǎng)絡(luò)域;B-MDVNM框架;BHA算法;有效性

網(wǎng)絡(luò)虛擬化技術(shù)支持多個虛擬網(wǎng)絡(luò)(virtual network,VN)共享物理網(wǎng)絡(luò)資源[1],VN映射作為網(wǎng)絡(luò)虛擬化的關(guān)鍵,其目標(biāo)是為每個VN中的虛擬節(jié)點和虛擬鏈路在底層網(wǎng)絡(luò)中尋找滿足映射約束的物理節(jié)點和物理鏈路。軟件定義網(wǎng)絡(luò)(software defined network,SDN)是一種新興的控制與轉(zhuǎn)發(fā)分離并直接可編程的網(wǎng)絡(luò)架構(gòu),openflow網(wǎng)絡(luò)作為SDN的原型被提出主要由openflow交換機和控制器2個部分組成[2]。單個openflow自治域由1個控制器、1個或多個openflow交換機和若干主機組成?？刂破鞒休d本域內(nèi)的控制資源,并且根據(jù)VN請求和域內(nèi)所有的相關(guān)資源,設(shè)計映射算法提供VN映射結(jié)果。openflow交換機承載轉(zhuǎn)發(fā)資源,通過運行openflow協(xié)議和控制器進(jìn)行通信。VN請求共享底層網(wǎng)絡(luò)資源,openflow網(wǎng)絡(luò)可以對不同的VN請求設(shè)計不同的映射算法。由于openflow網(wǎng)絡(luò)具有強大的可編程能力,VN可以在被映射到的openflow網(wǎng)絡(luò)域中運行自定義協(xié)議(IP或非IP協(xié)議)[3]。openflow網(wǎng)絡(luò)基礎(chǔ)設(shè)施提供商(infrastructure provider,InP)為VN請求提供所需的資源。目前,對于單一自治域,文獻(xiàn)[4-9]對其有研究,上述單域VN映射方案都是需要知道整個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以及資源、帶寬等信息,然而在實際中,由于客觀因素的限制(單一InP無法完成的)需要多個InP共同合作才能滿足VN映射需求,所以單域VN映射無法適用于跨域映射部署。

目前已有的跨域VN映射方法分為兩類：① 分布式。分布式跨域VN映射方法通過VN請求與InP、InP與InP之間的資源協(xié)商來實現(xiàn),需要獲取全局網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。優(yōu)點是滿足InP的資源協(xié)調(diào),具有良好擴展性。缺點是在協(xié)商過程中會引起額外的傳輸代價和資源消耗,缺乏全局網(wǎng)絡(luò)信息的掌握,難以得到跨域VN映射最優(yōu)解。② 集中式。集中式方法[10-13]在VN請求和InP之間引入虛擬網(wǎng)絡(luò)提供商(virtual network provider,VNP)或者映射管理器作為協(xié)調(diào)VN請求和InP匹配映射過程,以最小化映射開銷為目標(biāo)求解跨域VN映射。綜上所述,集中式方法相對于分布式方法對全局信息掌握相對容易,簡化了VN請求和InP之間資源匹配的過程，集中式方法較容易實現(xiàn)。

本文針對跨域映射提出一種集中式的基于競價機制跨域VN映射框架(B-MDVNM),針對虛擬節(jié)點映射提出啟發(fā)式均衡算法(balancing heuristic algorithmy,BHA),根據(jù)算法設(shè)計相應(yīng)的模擬仿真實驗，與現(xiàn)有的虛擬節(jié)點映射算法從效率、開銷、負(fù)載等方面進(jìn)行對比來驗證BHA的有效性。

1 基于openflow網(wǎng)絡(luò)跨域映射模型

VN請求用有權(quán)無向圖為Gv=(Nv,Lv),Nv表示虛擬節(jié)點集合,Lv表示虛擬鏈路集合。底層openflow網(wǎng)絡(luò)基礎(chǔ)設(shè)施由m個openflow網(wǎng)絡(luò)InP(簡稱OFInP)提供。圖1所示為一個實例,VN請求中,V1,V2,V3∈Nv表示虛擬節(jié)點類型,而矩形中的數(shù)字表示該虛擬節(jié)點所需的資源量,連接兩節(jié)點的線段為虛擬鏈路。而底層網(wǎng)絡(luò)由3個OFInP組成,每個OFInP都有一個控制器(controller),該控制器中記錄本域可提供的虛擬節(jié)點資源、域內(nèi)網(wǎng)絡(luò)拓?fù)湫畔⒌?。比如OFInP1中為V1、V2、V3提供的資源量為20、5、5。

根據(jù)圖1可知，單個OFInP域內(nèi)虛擬節(jié)點資源不足，無法滿足VN請求,此時需要多個InP共同提供虛擬資源來為VN請求提供服務(wù)。3個域共同參與了VN映射,其中V1映射至OFInP1域內(nèi),而V2映射至OFInP2域內(nèi),V3映射至OFInP3域內(nèi)。節(jié)點U、V、W、X、Y是每個域的邊界節(jié)點(border nodes),邊界節(jié)點屬于OFInP的物理節(jié)點集合,負(fù)責(zé)域之間的連接。虛擬網(wǎng)絡(luò)請求跨域映射過程分為虛擬節(jié)點映射和跨域鏈路映射2個步驟,即兩階段映射[14-15]。當(dāng)虛擬節(jié)點映射完成后,根據(jù)鏈路資源約束進(jìn)行跨域路徑映射,選擇合適的跨域路徑。由圖1可以看出,VN請求鏈路映射至跨域路徑V、X、Y相連的鏈路。本文主要研究虛擬節(jié)點映射過程。

圖1 基于openflow網(wǎng)絡(luò)跨域映射模型

2 基于競價的跨域VN映射框架

在保護(hù)OFInP的內(nèi)部網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)隱私安全的前提上,考慮到?jīng)Q策者需要一定程度的全局視角,在OFInP與VN請求之間加入管理中心(supervisor),B-MDVNM框架如圖2所示。

圖2 B-MDVNM框架

圖2中具體步驟如下:

(1) VN請求發(fā)送至信息處理中心,處理中心記錄VN請求的節(jié)點以及鏈路信息。

(2) 各個OFInP中的控制器(controller)將本域所能提供的節(jié)點資源信息和節(jié)點資源單價發(fā)送給信息處理中心。例如OFInP1向管理中心遞交內(nèi)容為:可提供虛擬節(jié)點V1、V2、V3,資源量分別為20、5、5,資源單價為12。

(3) 處理中心對各OFInP發(fā)送的信息和VN請求進(jìn)行分析制定競價結(jié)果表(bidding results table)。

(4) 管理中心根據(jù)算法計算最優(yōu)虛擬節(jié)點映射結(jié)果。從圖2中可知最優(yōu)映射結(jié)果由3個最優(yōu)的局部映射結(jié)果組成，分別為:V1映射至OFInP1;V2映射至OFInP2;V3映射至OFInP3;而映射的總價格為415。

(5) 將映射結(jié)果發(fā)送至OFInP,再根據(jù)映射結(jié)果各OFInP接受VN請求中虛擬節(jié)點的映射。

3 啟發(fā)式均衡算法

3.1 算法步驟

BHA得到的結(jié)果是I滿足R的最優(yōu)映射結(jié)果(optimal mapping results,MR)。MR由若干個最優(yōu)的局部映射結(jié)果(part of the mapping results,PMR)組成。

輸入:I、R。

輸出:PMR集合(即MR)。

算法具體步驟如下:

(1) 判斷R能否映射至I,判斷公式如下:

(1)

若無法滿足判斷公式則說明當(dāng)前I中的節(jié)點資源無法滿足R的節(jié)點需求,算法結(jié)束；若滿足，則R一定可以映射,轉(zhuǎn)步驟(2)。

(2) 設(shè)Vf表示已完成映射節(jié)點集,Va表示待映射節(jié)點集,初始Va=VR,Vf=?。設(shè)k為PMR集合長度,初始k=0。

(3) fori=1 to m，根據(jù)R、Ii計算V(Ii,R)，計算公式如下:

(2)

同時記錄L(V(Ii,R))并選擇該值最大的V(Ii,R)作為本次循環(huán)的最優(yōu)局部映射結(jié)果,該公式的策略在于虛擬節(jié)點映射至最少的OFInP內(nèi),目的是盡可能減少跨域開銷,即優(yōu)先選取可以提供最多類型虛擬節(jié)點的OFInP域作為VN請求的映射域。若出現(xiàn)多組L(V(Ii,R))的值相同,則需要比較Ii的均衡系數(shù)δ,δ的計算公式為:

(3)

再優(yōu)先選取δ較大的Ii,k=k+1,并更新PMR集,公式如下:

(4)

(5) 由于R有部分節(jié)點被映射需要更新R的節(jié)點信息,移除已經(jīng)被映射的節(jié)點。同時更新Ii的資源信息,公式如下:

(5)

(6) 若Vf=VR,Va=?,則表示R的節(jié)點全部完成映射,跳出該循環(huán)。若Va≠?,說明R的節(jié)點并未全部映射,回到步驟(3),計算下一個PMRk。

(7) 算法結(jié)束,記錄映射結(jié)果PMR集合,映射工作完成時間為T,I集合中各OFInP的剩余資源以及PMR的長度u=k。

3.2 評價指標(biāo)

為了提高底層OFInP的資源使用率,盡可能降低映射開銷,并且保證各個OFInP的負(fù)載均衡,參照文獻(xiàn)[1]引入4個性能指標(biāo)作為參照。

(1) 完成VN請求集的映射的總時間T。

(2) 完成VN請求集的映射的總開銷,本文以總的開銷報價的形式表示,公式如下:

其中,Bp為跨域開銷報價;α、β分別為OFInP的節(jié)點資源開銷權(quán)重和跨域開銷權(quán)重。

(3) 在相同底層網(wǎng)絡(luò)資源狀況下,高效的映射算法能夠接受更多的VN請求,VN請求接受率η定義如下:

(4) 用I的剩余資源和的極差來反映當(dāng)前底層網(wǎng)絡(luò)的負(fù)載情況,極差τ定義如下:

4 算法仿真

4.1 仿真環(huán)境

仿真實驗使用配置為3 GB內(nèi)存,32位Win7操作系統(tǒng),Intel core2 T9550處理器的計算機進(jìn)行上述評估,實驗代碼用C++語言編寫,使用Visual Studio 2010進(jìn)行編程,實驗中物理網(wǎng)絡(luò)及虛擬網(wǎng)絡(luò)拓?fù)涠疾捎肎T-ITM工具隨機生成。

實驗的預(yù)設(shè)變量信息如下:預(yù)設(shè)整個底層網(wǎng)絡(luò)由5個不同的OFInP組成,虛擬節(jié)點種類設(shè)置為s=8,VN請求數(shù)設(shè)為n=1 000。每個OFInP對于每種虛擬結(jié)點提供的資源r服從均勻分布[0,max],資源單價p服從[10,20]的均勻分布,每個OFInP的控制資源信息集中于管理中心形成統(tǒng)一的資源表。VN請求虛擬節(jié)點數(shù)服從[1,s]上的均勻分布,其中每個節(jié)點需求資源r服從[0,20]的均勻分布。節(jié)點資源開銷權(quán)重α和跨域開銷權(quán)重β均設(shè)置為1,跨域開銷Bp設(shè)置為300。

通過改變max的值,將本文提出的BHA和不加入均衡系數(shù)比較的BHA(簡稱NOBC-BHA)以及二元整數(shù)規(guī)劃求最小節(jié)點映射開銷算法(binary integer programming minimize node mapping cost,BIP)[12]分別進(jìn)行節(jié)點映射仿真實驗,記錄評價指標(biāo)。

4.2 仿真結(jié)果及分析

仿真結(jié)果如圖3～圖7所示。

(1) 從圖3得到BHA的平均映射時間比BIP低9.3%,比NOBC-BHA低3.7%。由圖4可以看出，當(dāng)max≥7 000時,由于底層網(wǎng)絡(luò)資源充裕,VN請求映射成功率為100%,而max<7 000時,底層網(wǎng)絡(luò)資源有限,BHA的映射成功率稍高于NOBC-BHA和BIP?？梢钥闯鯞HA算法效率明顯要高于BIP,稍高于NOBC-BHA。

圖3 VN請求平均映射時間

圖4 VN請求映射成功率

圖5 VN請求總映射價格

圖6 OFInP集剩余資源極差

(2) 從圖5可以看出BHA的平均映射總價比BIO算法低18.5%,比NOBC-BHA低5.5%。因為BHA要求VN請求映射至最少的OFInP內(nèi),可使跨域開銷最低,并且引入均衡系數(shù)的比較使VN請求映射至價格較低的OFInP內(nèi)。由圖6可以看出，VN請求映射完成后，BHA的底層網(wǎng)絡(luò)資源極差最低,而BIP會優(yōu)先使VN請求映射至報價較低的OFInP中,造成低價的OFInP資源消耗較大,負(fù)載較高,而報價較高的OFInP會長時間處在空閑狀態(tài),產(chǎn)生局部負(fù)載偏高的現(xiàn)象。

圖7 一個VN請求平均處理時間

(3) 從圖7可以看出BHA的算法執(zhí)行時間低于NOBC-BHA和BIP。這是因為BIP采用了優(yōu)先選取最低報價的OFInP作為映射目標(biāo)的策略,所以計算報價的時間開銷較大,BIP的一個VN請求平均處理時間為3.74 ms。雖然NOBC-BHA比BHA缺少計算均衡系數(shù)這一步驟,但是當(dāng)?shù)讓泳W(wǎng)絡(luò)資源不足時需要多次循環(huán)計算局部最優(yōu)映射子集,而BHA只需比較均衡系數(shù)即可得到局部最優(yōu)映射子集。NOBC-BHA的一個VN請求平均處理時間為3.32 ms,而BHA只有3.03 ms。比BIP降低了23.4%,比NOBC-BHA降低了9.6%。

5 結(jié) 論

本文對基于openflow網(wǎng)絡(luò)跨域的虛擬網(wǎng)絡(luò)映射進(jìn)行了研究。由于多域環(huán)境下各域不公開網(wǎng)絡(luò)拓?fù)涞仍敿?xì)信息且各域的資源處于動態(tài)變化的情況下,針對VN請求跨域映射問題提出一種競價機制的跨域虛擬網(wǎng)絡(luò)映射框架,并且在虛擬節(jié)點映射問題上提出一種啟發(fā)式均衡算法。模擬實驗結(jié)果表明，本文提出的算法在高效快速地滿足多域下VN請求可靠需求的同時,仍能達(dá)到較低的映射開銷和底層網(wǎng)絡(luò)各域之間的負(fù)載均衡。

在完成虛擬節(jié)點映射工作后,需在跨域鏈路上進(jìn)行跨域鏈路映射,今后應(yīng)在現(xiàn)有的工作基礎(chǔ)上進(jìn)一步研究跨域鏈路映射的問題。

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

[2] MCKEOWN N,ANDERSON T,BALAKRISHNAN H,et al.Openflow:enabling innovation in campus networks[J].ACM SIGCOMM Computer Communication Review,2008,38(2):69-74.

[3] BAVIER A,FEAMSTER N,HUANG M,et al.In VINI veritas:realistic and controlled network experimentation [C]//Proceedings of the ACM SIGCOMM.Pisa,Italy,2006:3-14.

[4] 李文,吳春明,陳健,等.物理節(jié)點可重復(fù)映射的虛擬網(wǎng)映射算法[J].電子與信息學(xué)報,2011,33(4):908-914.

[5] CHENG X,SU S,ZHANG Z B,et al.Virtual network embedding through topology-aware node ranking[J].ACM SIGCOMM Computer Communication Review,2011,41(2):39-47.

[6] YU M L,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.

[7] CHOWDHURY N M MK,RAHMAN M R,BOUTABA R.Virtual networkembedding with coordinated node and link mapping[C]//2009 IEEE INFOCOM.28th International Conference on Computer Conmunicoations,Rio de Janeiro:IEEE,2009:783-791.

[8] 姜明,王保進(jìn),吳春明,等.網(wǎng)絡(luò)虛擬化與虛擬網(wǎng)映射算法研究[J].電子學(xué)報,2011,39(6):1315-1320.

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

[10] HOUIDI I,LOUATI W,ZEGHLACHE D,et al.Virtual resource description and clustering for virtual network discovery[C]//2009 IEEE International Conference on Commupications Workshops.D resden:IEEE,2009:1-6.

[11] HOUIDI I,LOUATI W,AMEUR W B,et al.Virtual network provisioning across multiple substrate networks[J].Computer Networks,2011,55(4):1011-1023.

[12] DIETRICH D,RIZK A,PAPADIMITRIOU P.Multi-domain virtual network embedding with limited information disclosure[C]//Prceedings of the 2013 IFIP Networking Conference.Brooklyn:IEEE,2013:1-9.

[13] 肖藹玲,王穎,孟洛明,等.基于知識描述和遺傳算法的跨域虛擬網(wǎng)絡(luò)映射[J].軟件學(xué)報,2014,25(10):2189-2205.

[14] 徐鵬,李勇,金德鵬.改進(jìn)的兩階段虛擬網(wǎng)映射算法[J].計算機工程,2012,38(5):79-82.

[15] YU M,YI Y,REXFORD J,et al.Rethinking virtual network embedding:substrate support for path splitti-ng and migration[J].Computer Communication Review,2008,38(2):17-29.

(責(zé)任編輯 張 镅)

Multi-domain virtual network mapping based on openflow network

XU Dongdong,ZHENG Shuli,CAO Min,FAN Yuqi

(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

In this paper, the multi-domain cooperation to complete the virtual network mapping is put forward based on the multiple openflow network autonomous domain. Because of the limited disclosed information, the traditional single domain mapping method is not applicable to multi-domain virtual network mapping. Therefore, the bidding multi-domain virtual network mapping(B-MDVNM) framework is proposed in which the balancing heuristic algorithm(BHA) is applied for the virtual nodes mapping. Finally, the simulation and the comparison between BHA and the existing virtual nodes mapping algorithm in view of the efficiency, overhead and performance are conducted to verify the effectiveness of the BHA.

virtual network; multi-domain mapping; openflow domain; bidding multi-domain virtual network mapping(B-MDVNM) framework; balancing heuristic algorithm(BHA); effectiveness

2015-05-20；

2015-08-18

安徽省自然科學(xué)基金資助項目(1508085MF115)

徐冬冬(1991-),男,安徽合肥人,合肥工業(yè)大學(xué)碩士生;

鄭淑麗(1974-),女,安徽蚌埠人,博士,合肥工業(yè)大學(xué)副教授,碩士生導(dǎo)師.

10.3969/j.issn.1003-5060.2016.10.011

TP393

A

1003-5060(2016)10-1352-05