張 鑫，賈瑩瑩，王曉璇

(1.南京郵電大學(xué) 寬帶無線通信與傳感器技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003；2.江蘇省無線通信點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003)

基于SDN的虛擬網(wǎng)絡(luò)映射問題研究綜述

張 鑫1,2，賈瑩瑩1,2，王曉璇1,2

(1.南京郵電大學(xué) 寬帶無線通信與傳感器技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京210003；2.江蘇省無線通信點(diǎn)實(shí)驗(yàn)室，江蘇 南京210003)

傳統(tǒng)IP網(wǎng)絡(luò)架構(gòu)越來越不適應(yīng)日益增長的網(wǎng)絡(luò)業(yè)務(wù)與應(yīng)用，一種新型的網(wǎng)絡(luò)架構(gòu)應(yīng)運(yùn)而生，即軟件定義網(wǎng)絡(luò)。它實(shí)現(xiàn)數(shù)據(jù)面和控制面相分離，同時(shí)具有集中控制、開放接口、可編程等特性。研究了基于該網(wǎng)絡(luò)架構(gòu)的虛擬網(wǎng)絡(luò)映射問題，即如何將帶有約束條件的虛擬網(wǎng)絡(luò)請求映射到由傳統(tǒng)電信商提供的底層物理網(wǎng)絡(luò)中。首先給出虛擬網(wǎng)絡(luò)映射問題的定義及目標(biāo)，然后對現(xiàn)有的多種經(jīng)典映射算法進(jìn)行分類，并同時(shí)對比與分析，最后在此基礎(chǔ)上對未來虛擬網(wǎng)絡(luò)映射算法提出一些建議與改進(jìn)思路。

軟件定義網(wǎng)絡(luò)；虛擬網(wǎng)絡(luò)映射；網(wǎng)絡(luò)虛擬化；映射算法

0 引言

目前傳統(tǒng)互聯(lián)網(wǎng)的架構(gòu)難以應(yīng)對日益復(fù)雜和多樣的社會發(fā)展，尤其是處在大數(shù)據(jù)和云計(jì)算時(shí)代，面對各種紛繁的用戶需求與業(yè)務(wù)，現(xiàn)有的網(wǎng)絡(luò)體系面臨著巨大的壓力與挑戰(zhàn)。針對這種情況，研究學(xué)者們提出一種新型的網(wǎng)絡(luò)架構(gòu)——軟件定義網(wǎng)絡(luò)(Software Defined Network,SDN)及OpenFlow[1-2]協(xié)議，將網(wǎng)絡(luò)分為基礎(chǔ)設(shè)施層、控制層、應(yīng)用層，使得網(wǎng)絡(luò)扁平化，更好地適應(yīng)未來網(wǎng)絡(luò)的發(fā)展趨勢。由于SDN是將底層數(shù)據(jù)平面分離出一個(gè)邏輯的集中控制平面，而網(wǎng)絡(luò)虛擬化[3-5]是將物理網(wǎng)絡(luò)抽象成一個(gè)個(gè)虛擬網(wǎng)絡(luò)，兩者的相似使得新型網(wǎng)絡(luò)下的網(wǎng)絡(luò)虛擬化變得更加靈活高效，可以更好地為用戶提供服務(wù)與應(yīng)用。SDN網(wǎng)絡(luò)架構(gòu)圖如圖1所示。

圖1 SDN網(wǎng)絡(luò)架構(gòu)圖

1 虛擬網(wǎng)絡(luò)映射問題模型

虛擬網(wǎng)絡(luò)映射問題就是將帶有條件約束的虛擬網(wǎng)絡(luò)映射到底層物理網(wǎng)絡(luò)中。虛擬網(wǎng)絡(luò)映射又分為節(jié)點(diǎn)映射和鏈路映射，但因節(jié)點(diǎn)資源屬性眾多，在映射過程中物理網(wǎng)絡(luò)都要滿足，這便成為NP-hard問題。其中映射目標(biāo)函數(shù)的選擇、節(jié)點(diǎn)與鏈路的匹配原則都是虛網(wǎng)映射中需要解決的問題。

1.1底層網(wǎng)絡(luò)

1.2虛擬網(wǎng)絡(luò)

1.3虛擬網(wǎng)絡(luò)映射問題描述

MN:?nv∈Nv,MN(nv)∈NS(C(nv)lt;RN(MN(nv)))

(1)

鏈路映射可表示為：

ML:對?lv=(mv,nv)∈Lv,ML(lv)?PS(MN(mv),

MN(nv))

constraints:b(lv)≤RL(P),?P∈ML(lv)

(2)

虛擬網(wǎng)絡(luò)映射模型如圖2所示。

圖2 虛擬網(wǎng)絡(luò)映射模型

1.4虛網(wǎng)映射算法的主要評價(jià)標(biāo)準(zhǔn)

虛擬網(wǎng)絡(luò)映射的主要目標(biāo)是充分利用物理網(wǎng)絡(luò)資源，接受更多的虛擬網(wǎng)絡(luò)請求，提高底層網(wǎng)絡(luò)的運(yùn)營收益。評價(jià)標(biāo)準(zhǔn)相關(guān)函數(shù)具體定義如下。

(1)收益函數(shù)

所有成功映射的虛擬網(wǎng)絡(luò)所請求的節(jié)點(diǎn)CPU資源和鏈路帶寬資源總和決定虛擬網(wǎng)絡(luò)收益，t時(shí)刻映射一個(gè)虛擬網(wǎng)絡(luò)收益可表示為:

(3)

(2)開銷函數(shù)

映射開銷即底層網(wǎng)絡(luò)為滿足虛網(wǎng)的節(jié)點(diǎn)及鏈路資源約束而消耗的物理資源，可表示為：

(4)

(3)底層網(wǎng)絡(luò)平均收益函數(shù)

(5)

(4)虛擬網(wǎng)絡(luò)請求接受率函數(shù)

虛網(wǎng)請求接受率是指在某個(gè)時(shí)間段內(nèi)虛擬網(wǎng)絡(luò)請求成功映射的個(gè)數(shù)，定義為：

(6)

其中，式(6)中分子部分表示0～T時(shí)刻內(nèi)成功映射虛擬網(wǎng)絡(luò)請求個(gè)數(shù)，式(6)中分母部分表示0～T時(shí)刻內(nèi)虛擬網(wǎng)絡(luò)請求總個(gè)數(shù)。

綜合以上，選擇不同的評價(jià)標(biāo)準(zhǔn)會產(chǎn)生不同的結(jié)果，在實(shí)際問題中要根據(jù)不同應(yīng)用場景，選擇合適的度量函數(shù)，以求獲得最大收益和資源的利用率。

2 虛擬網(wǎng)絡(luò)映射算法分類

從各種因素考慮，根據(jù)資源約束、接入控制、虛網(wǎng)請求處理方式、虛網(wǎng)映射的計(jì)算方式、映射類型、拓?fù)湫畔⒌确矫姹容^了最近10年一些經(jīng)典虛擬網(wǎng)絡(luò)映射算法[6-12]，如表1所示。

由于受節(jié)點(diǎn)CPU、鏈路帶寬條件約束，而且存在虛擬網(wǎng)絡(luò)請求的時(shí)間等是不可知的，因此使得虛擬網(wǎng)絡(luò)映射研究變得復(fù)雜，一些采用忽略節(jié)點(diǎn)資源約束、忽略接入控制、假設(shè)預(yù)先已知虛擬網(wǎng)絡(luò)請求信息(離線)等限制地址位置的方式尋求虛擬網(wǎng)絡(luò)映射的解決方案；另一些則從擴(kuò)大問題空間的角度出發(fā)，研究貼近實(shí)際生活的映射算法。最終可將已有的虛網(wǎng)映射算法分為兩大類：限制地理位置的映射算法[6-7]和不限制地理位置的映射算法[8-12]。

2.1限制地理位置的虛網(wǎng)映射算法

文獻(xiàn)[6]在忽略節(jié)點(diǎn)資源約束、假設(shè)所有的虛網(wǎng)請求事先已知等限制地理位置的條件下，提出了一種QoSMap機(jī)制，該機(jī)制在建立虛擬網(wǎng)絡(luò)時(shí)著重考慮了虛網(wǎng)的QoS與拓?fù)鋸椥詥栴}。通過選擇高質(zhì)量保證的物理鏈路滿足虛網(wǎng)的QoS要求，并利用一跳中繼路由節(jié)點(diǎn)構(gòu)建后備路由路徑以提供虛擬鏈路映射的彈性保障。該算法雖能獲得更優(yōu)的服務(wù)質(zhì)量和彈性保證，但其資源利用率低，計(jì)算開銷大。

表1 虛擬網(wǎng)絡(luò)映射算法比較

文獻(xiàn)[7]在離線且未考慮節(jié)點(diǎn)映射階段，提出將隱藏跳數(shù)(虛擬鏈路映射到的底層路徑經(jīng)過的中間物理節(jié)點(diǎn))納入到鏈路映射階段，鏈路映射后作為中間節(jié)點(diǎn)的物理節(jié)點(diǎn)也要消耗CPU資源。算法將虛擬網(wǎng)絡(luò)請求分成有特定資源請求和無明確資源請求兩類，先處理有特定需求的請求，目的是在成功映射每個(gè)虛擬網(wǎng)絡(luò)請求后使得剩余資源盡可能地大(即開銷盡可能小)，再處理資源請求不明確的虛擬網(wǎng)絡(luò)請求，對它們進(jìn)行資源的平均分配。該算法中間節(jié)點(diǎn)的資源消耗更接近實(shí)際，但不適合于大規(guī)模虛網(wǎng)請求，對于支持鏈路可分流的情況計(jì)算復(fù)雜度比較高。

2.2不限制地理位置的虛網(wǎng)映射算法

不限制地理位置的虛網(wǎng)映射算法，又可根據(jù)是否考慮拓?fù)涮匦?，?xì)分為同時(shí)考慮拓?fù)湫畔⒌奶摼W(wǎng)映射算法[10-12]和未考慮拓?fù)湫畔⒌奶摼W(wǎng)絡(luò)映射算法[8-9]。

(1)考慮拓?fù)湫畔⒌奶摼W(wǎng)映射算法

文獻(xiàn)[10]從已有的算法平等地對待底層網(wǎng)絡(luò)的節(jié)點(diǎn)和鏈路資源，實(shí)際上這些物理資源中某些資源相比其他的資源更重要，這些關(guān)鍵資源的耗盡會對未來的請求接受率有較大的影響。因此根據(jù)物理網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路的剩余可用容量和在底層網(wǎng)絡(luò)中的重要程度分配不同的權(quán)重，拓?fù)涓兄成湓谝延兴惴ǖ某杀竞瘮?shù)中引入比例因子，對資源進(jìn)行區(qū)分。同時(shí)，新的虛擬網(wǎng)絡(luò)到達(dá)和已有的虛擬網(wǎng)絡(luò)服務(wù)終止使得底層網(wǎng)絡(luò)可用資源的分布變得零散，底層網(wǎng)絡(luò)資源利用率降低，請求接受率下降。解決方案是引入重優(yōu)化機(jī)制，周期性的重優(yōu)化機(jī)制不適用于實(shí)際的網(wǎng)絡(luò)，文獻(xiàn)中提出當(dāng)有虛擬網(wǎng)絡(luò)請求被拒絕時(shí)執(zhí)行重優(yōu)化算法，有效地均衡負(fù)載。

文獻(xiàn)[11]在節(jié)點(diǎn)映射階段引入網(wǎng)絡(luò)拓?fù)鋵傩?，即在考慮CPU和帶寬的同時(shí)考慮節(jié)點(diǎn)的度(度是節(jié)點(diǎn)最基本和最重要的拓?fù)鋵傩裕珊饬吭谕負(fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)的相對影響和相對重要性，反映了與網(wǎng)絡(luò)剩余部分的連接程度，節(jié)點(diǎn)的度等于其與鄰居節(jié)點(diǎn)的直接鏈路數(shù))以增強(qiáng)節(jié)點(diǎn)與其他節(jié)點(diǎn)聯(lián)系能力的影響，從而提高虛擬網(wǎng)絡(luò)接受率、長期平均收益和底層資源利用率。

文獻(xiàn)[12]從馬爾可夫隨機(jī)游動模型出發(fā)，利用K-核分解技術(shù)將虛擬網(wǎng)絡(luò)劃分為核心網(wǎng)絡(luò)和邊緣網(wǎng)絡(luò)兩大部分，同時(shí)優(yōu)先考慮生存時(shí)間最短的虛擬網(wǎng)絡(luò)請求(區(qū)別于以收入為導(dǎo)向的調(diào)度策略)。在映射過程中，首先采用RW-MM-SP算法映射核心網(wǎng)絡(luò)，然后采用RW-BFS算法映射邊緣網(wǎng)絡(luò)，其中核心網(wǎng)絡(luò)中與邊緣網(wǎng)絡(luò)直接相連的節(jié)點(diǎn)稱為星節(jié)點(diǎn)。

(2)未考慮拓?fù)湫畔⒌奶摼W(wǎng)映射算法

文獻(xiàn)[8]中，在不限制地理位置的條件下，底層物理網(wǎng)絡(luò)支持路徑遷移與路徑分裂特性，節(jié)點(diǎn)映射按照貪心算法來映射，鏈路映射采用基于商品流鏈路映射，從而提高虛擬網(wǎng)絡(luò)請求接受率，但由于節(jié)點(diǎn)屬性是節(jié)點(diǎn)CPU與鄰接鏈路帶寬之和的乘積，容易導(dǎo)致任意一個(gè)值的變化，從而導(dǎo)致鏈路映射失敗。

文獻(xiàn)[9]中，為應(yīng)對底層資源浪費(fèi)大的問題，將虛網(wǎng)的資源請求劃分為兩部分：基本子請求和可變子請求，提出了一種新的ORS(Opportunistic Resource Sharing)映射框架，包括宏觀層面的虛網(wǎng)映射和微觀層面的虛網(wǎng)映射。宏觀層面的虛網(wǎng)映射，采用傳統(tǒng)的貪婪算法，為基本子請求分配固定的專用時(shí)隙。微觀層面的虛網(wǎng)映射，由于可變子請求以小于1的概率發(fā)生，因此共享時(shí)隙可節(jié)約底層資源，其映射問題即可轉(zhuǎn)化為如何為可變子請求分配底層時(shí)隙的問題。文獻(xiàn)[9]定義沖突閾值以代表底層時(shí)隙的量，繼而提出了沖突概率的第一擬合算法(First-Fit by Collision Probability，CFF)和指標(biāo)和的第一擬合期望算法(First-Fit Expectation of Indicators Sum,EFF)兩種共享時(shí)隙的映射算法。CFF將可變子請求映射到率先滿足沖突概率不大于沖突閾值的底層時(shí)隙上，直到分配給可變子請求的時(shí)隙數(shù)滿足要求為止。EFF是對CFF的改進(jìn)，減少了沖突概率的計(jì)算量，比CFF運(yùn)行得快。

3 虛擬網(wǎng)絡(luò)映射算法的改進(jìn)思路與方向

盡管現(xiàn)有的虛擬網(wǎng)絡(luò)映射算法取得了一些進(jìn)展與突破，但是仍然面臨著以下一些問題：

(1)目前絕大多數(shù)映射算法的假設(shè)條件都是由單個(gè)電信運(yùn)營商提供底層物理資源，但是在實(shí)際應(yīng)用中會面臨著由多個(gè)提供商提供的網(wǎng)絡(luò)，如何在多個(gè)底層網(wǎng)絡(luò)中進(jìn)行選擇和映射，這將是未來研究的重點(diǎn)與熱點(diǎn)。

(2)虛擬網(wǎng)絡(luò)映射過程遇到因某種原因突然出現(xiàn)節(jié)點(diǎn)和鏈路失效，從而使得映射失敗，導(dǎo)致虛網(wǎng)映射可靠性降低，例如可以考慮為虛擬網(wǎng)絡(luò)分配冗余資源，或者為節(jié)點(diǎn)、鏈路建立資源備份池，當(dāng)該節(jié)點(diǎn)或者鏈路失效時(shí)，可以及時(shí)切換到其他節(jié)點(diǎn)和鏈路上，確保網(wǎng)絡(luò)可以繼續(xù)運(yùn)行下去。

(3)網(wǎng)絡(luò)安全也應(yīng)該成為未來虛擬網(wǎng)絡(luò)映射潛在的研究點(diǎn)，考慮虛擬網(wǎng)絡(luò)映射過程中引入身份認(rèn)證機(jī)制，使得虛擬網(wǎng)絡(luò)變得更加安全與可靠。

(4)同時(shí)虛擬網(wǎng)絡(luò)映射過程中會消耗一定的能量，可以考慮將能耗這一因素納入映射算法的衡量指標(biāo)中，使得未來的映射變得更加綠色和節(jié)能。

(5)電信運(yùn)營商為了利益最大化，優(yōu)先接受收益大的虛網(wǎng)請求，即收益為導(dǎo)向的調(diào)度策略，一些虛擬映射算法中采用以時(shí)間為導(dǎo)向的調(diào)度策略，率先映射生存周期短的虛擬網(wǎng)絡(luò)，為未來的VNR預(yù)留更多的剩余資源，提高了虛網(wǎng)的接受率，進(jìn)一步增加了收益。因此，從虛擬網(wǎng)絡(luò)請求排隊(duì)機(jī)制的優(yōu)先級出發(fā)，尋找更高效的虛擬網(wǎng)絡(luò)映射算法。

4 結(jié)論

SDN網(wǎng)絡(luò)的特性與網(wǎng)絡(luò)虛擬化技術(shù)相契合，為未來網(wǎng)絡(luò)的發(fā)展提供基礎(chǔ)，同時(shí)也有利于網(wǎng)絡(luò)技術(shù)的革新和用戶業(yè)務(wù)的發(fā)展。虛擬網(wǎng)絡(luò)映射過程中，不僅需要考慮虛擬網(wǎng)絡(luò)請求的鏈路帶寬和CPU資源的約束，還要考慮傳輸時(shí)延及物理網(wǎng)絡(luò)中可用資源大小，這是今后研究的重點(diǎn)和難點(diǎn)。本文從限制地理位置與不限制地理位置兩個(gè)方面對多種虛擬網(wǎng)絡(luò)映射算法進(jìn)行了簡要分析，并指明了今后進(jìn)一步的研究發(fā)展方向。

[1] MCKEOWN N,ANDERSON T,BALAKRISHNAN H,et al.OpenFlow:enabling innovation in campus networks[J].ACM SIGCOMM Computer Communication Review,2008.

[2] CHOWDHURY N M M K, BOUTABA R. Network virtualization: state of the art and research challenges[J]. IEEE Communieations Magazine, 2009, 47(7):20-26.

[3] CHOWDHURY M, BOUTABA R. A survey of network virtualization[J]. Computer Networks, 2010, 54(5):862-876.

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

[5] 溫濤，虞紅芳，李樂民.網(wǎng)絡(luò)虛擬化的過去、現(xiàn)在和未來[J].中興通訊技術(shù),2014,20(3):2-7.

[6] SHAMSI J, BROCKMEYER M. QoSMap: QoS aware mapping of virtual networks for resiliency and efficiency[A]. Proceedings of the IEEE GLOBECOM Workshop[C]. Washington, DC, USA, 2007: 1-6.

[7] BETORO J F, HEESELBACH X, FISCHER A, et al. Optimal mapping of virtual networks with hidden hops[J]. Telecommunication Systems, 2013, 52(3): 1-10.

[8] Yu Minlan, 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.

[9] Zhang Sheng, Qian Zhuzhong, Wu Jie, et al. Virtual network embedding with opportunistic resource sharing[C]. IEEE Transactions on Parallel and Distributed Systems, 2014: 816-827.

[10] BUTT N F, CHOWDHURY N M M K, BOUTABA R. Topology awareness and reoptimization mechanism for virtual network embedding[C]. Networking, 2010: 27-39.

[11] Feng Min, Zhang Lei, Zhu Xiaomin, et al. Topology-aware virtual network embedding through the degree[C]. National Doctoral Academic Forum on Information and Communications Technology 2013, IET, 2013: 1-6.

[12] Qing Sude, Liao Jianxin, Wang Jingyu, et al. Hybrid virtual network embedding with K-core decomposition and time-oriented priority[C]. Proceedings of IEEE International Conference on Communications, 2012: 2695-2699.

[13] 桂燕興，沈蘇彬，毛燕琴.基于SDN的虛擬映射技術(shù)的研究與實(shí)現(xiàn)[J].微型機(jī)與應(yīng)用,2015,34(13):69-76.

2017-05-17)

張鑫(1993-)，通信作者，男，碩士研究生，主要研究方向：軟件定義網(wǎng)絡(luò)與網(wǎng)絡(luò)虛擬化。E-mail：zhangxin9312@163.com。

賈瑩瑩(1992-)，女，碩士研究生，主要研究方向：下一代網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)。

王曉璇(1993-)，女，碩士研究生，主要研究方向：下一代網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)。

Research on virtual network embedding problems based on SDN

Zhang Xin1,2, Jia Yingying1,2, Wang Xiaoxuan1,2

(1. Key Lab of Broadband Wireless Communication and Sensor Network Technology, Nanjing University of Posts and Telecommunications, Ministry of Education, Nanjing 210003, China; 2. Jiangsu Key Lab of Wireless Communication, Nanjing 210003, China)

Traditional IP network architecture is not adaptive to the increasing number of network services and applications ,and then a new type of network architecture is introduced, which is software defined network. It enables data plane and control plane to separate, and has central control,open interfaces,and programmable features. This paper studies the virtual network embedding problem based on the network architecture, that is, how to map virtual network requests with constraints to the underlying physical network provided by traditional telecommunication operators. Firstly, the definition and goal of the virtual network embedding problem are given. Then, a variety of classical mapping algorithms are classified and compared with each other. Finally, the future virtual network embedding algorithms’ suggestions and improvements are offered.

software defined network; virtual network embedding; network virtualization; mapping algorithm

TP393

A

10.19358/j.issn.1674- 7720.2017.22.004

張鑫，賈瑩瑩，王曉璇.基于SDN的虛擬網(wǎng)絡(luò)映射問題研究綜述J.微型機(jī)與應(yīng)用，2017,36(22)：11-14.