基于openflow網絡的虛擬網絡映射研究

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

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

?

基于openflow網絡的虛擬網絡映射研究

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

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

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

虛擬網絡;跨域映射;openflow網絡域;B-MDVNM框架;BHA算法;有效性

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

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

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

1 基于openflow網絡跨域映射模型

VN請求用有權無向圖為Gv=(Nv,Lv),Nv表示虛擬節點集合,Lv表示虛擬鏈路集合。底層openflow網絡基礎設施由m個openflow網絡InP(簡稱OFInP)提供。圖1所示為一個實例,VN請求中,V1,V2,V3∈Nv表示虛擬節點類型,而矩形中的數字表示該虛擬節點所需的資源量,連接兩節點的線段為虛擬鏈路。而底層網絡由3個OFInP組成,每個OFInP都有一個控制器(controller),該控制器中記錄本域可提供的虛擬節點資源、域內網絡拓撲信息等。比如OFInP1中為V1、V2、V3提供的資源量為20、5、5。

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

圖1 基于openflow網絡跨域映射模型

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

在保護OFInP的內部網絡拓撲結構隱私安全的前提上,考慮到決策者需要一定程度的全局視角,在OFInP與VN請求之間加入管理中心(supervisor),B-MDVNM框架如圖2所示。

圖2 B-MDVNM框架

圖2中具體步驟如下:

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

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

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

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

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

3 啟發式均衡算法

3.1 算法步驟

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

輸入:I、R。

輸出:PMR集合(即MR)。

算法具體步驟如下:

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

(1)

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

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

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

(2)

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

(3)

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

(4)

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

(5)

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

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

3.2 評價指標

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

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

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

其中,Bp為跨域開銷報價;α、β分別為OFInP的節點資源開銷權重和跨域開銷權重。

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

(4) 用I的剩余資源和的極差來反映當前底層網絡的負載情況,極差τ定義如下:

4 算法仿真

4.1 仿真環境

仿真實驗使用配置為3 GB內存,32位Win7操作系統,Intel core2 T9550處理器的計算機進行上述評估,實驗代碼用C++語言編寫,使用Visual Studio 2010進行編程,實驗中物理網絡及虛擬網絡拓撲都采用GT-ITM工具隨機生成。

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

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

4.2 仿真結果及分析

仿真結果如圖3～圖7所示。

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

圖3 VN請求平均映射時間

圖4 VN請求映射成功率

圖5 VN請求總映射價格

圖6 OFInP集剩余資源極差

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

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

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

5 結 論

本文對基于openflow網絡跨域的虛擬網絡映射進行了研究。由于多域環境下各域不公開網絡拓撲等詳細信息且各域的資源處于動態變化的情況下,針對VN請求跨域映射問題提出一種競價機制的跨域虛擬網絡映射框架,并且在虛擬節點映射問題上提出一種啟發式均衡算法。模擬實驗結果表明，本文提出的算法在高效快速地滿足多域下VN請求可靠需求的同時,仍能達到較低的映射開銷和底層網絡各域之間的負載均衡。

在完成虛擬節點映射工作后,需在跨域鏈路上進行跨域鏈路映射,今后應在現有的工作基礎上進一步研究跨域鏈路映射的問題。

[1] 程祥,張忠寶,蘇森,等.虛擬網絡映射問題研究綜述[J].通信學報,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] 李文,吳春明,陳健,等.物理節點可重復映射的虛擬網映射算法[J].電子與信息學報,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].電子學報,2011,39(6):1315-1320.

[9] 程祥,張忠寶,蘇森,等.基于粒子群優化的虛擬網絡映射算法[J].電子學報,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] 肖藹玲,王穎,孟洛明,等.基于知識描述和遺傳算法的跨域虛擬網絡映射[J].軟件學報,2014,25(10):2189-2205.

[14] 徐鵬,李勇,金德鵬.改進的兩階段虛擬網映射算法[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.

(責任編輯 張 镅)

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

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

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

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

10.3969/j.issn.1003-5060.2016.10.011

TP393

A

1003-5060(2016)10-1352-05