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

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

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

?

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

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

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

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

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

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

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

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

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

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

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

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

2 基于競(jìng)價(jià)的跨域VN映射框架

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

圖2 B-MDVNM框架

圖2中具體步驟如下:

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

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

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

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

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

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

3.1 算法步驟

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

輸入:I、R。

輸出:PMR集合(即MR)。

算法具體步驟如下:

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

(1)

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

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

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

(2)

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

(3)

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

(4)

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

(5)

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

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

3.2 評(píng)價(jià)指標(biāo)

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

(1) 完成VN請(qǐng)求集的映射的總時(shí)間T。

(2) 完成VN請(qǐng)求集的映射的總開(kāi)銷,本文以總的開(kāi)銷報(bào)價(jià)的形式表示,公式如下:

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

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

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

4 算法仿真

4.1 仿真環(huán)境

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

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

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

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

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

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

圖3 VN請(qǐng)求平均映射時(shí)間

圖4 VN請(qǐng)求映射成功率

圖5 VN請(qǐng)求總映射價(jià)格

圖6 OFInP集剩余資源極差

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

圖7 一個(gè)VN請(qǐng)求平均處理時(shí)間

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

5 結(jié) 論

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

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

[1] 程祥,張忠寶,蘇森,等.虛擬網(wǎng)絡(luò)映射問(wèn)題研究綜述[J].通信學(xué)報(bào),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é)點(diǎn)可重復(fù)映射的虛擬網(wǎng)映射算法[J].電子與信息學(xué)報(bào),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é)報(bào),2011,39(6):1315-1320.

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

[14] 徐鵬,李勇,金德鵬.改進(jìn)的兩階段虛擬網(wǎng)映射算法[J].計(jì)算機(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é)基金資助項(xiàng)目(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