0 引言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，為了解決當(dāng)前互聯(lián)網(wǎng)“僵化”問題，研究者提出了網(wǎng)絡(luò)虛擬化技術(shù)，它可以為用戶提供多樣化服務(wù)^［1-2］，也是構(gòu)建新一代網(wǎng)絡(luò)體系架構(gòu)的重要支撐^［3］。虛擬網(wǎng)絡(luò)映射是實現(xiàn)網(wǎng)絡(luò)虛擬化的關(guān)鍵環(huán)節(jié)，其目的是在滿足虛擬網(wǎng)絡(luò)請求（Virtual Network Request, VN請求）的前提下，將虛擬網(wǎng)絡(luò)以最小化成本映射到物理網(wǎng)絡(luò)上，實現(xiàn)網(wǎng)絡(luò)資源的高效利用^［4］。

虛擬網(wǎng)絡(luò)映射問題包括節(jié)點映射和鏈路映射兩個問題，一般在節(jié)點映射階段采用啟發(fā)式算法，然后在確定源和目的節(jié)點的基礎(chǔ)上，將鏈路映射轉(zhuǎn)化為最小費用流問題，采用最短路徑算法完成映射。根據(jù)兩個問題是否獨立進(jìn)行，可將虛擬網(wǎng)絡(luò)映射分為同階段映射和兩階段映射^［5］。同階段映射中，在映射虛擬節(jié)點的同時考慮鏈路映射，如D-ViNE算法^［6］和vnmFlib算法^［7］。兩階段映射中，節(jié)點映射和鏈路映射獨立進(jìn)行，先映射節(jié)點后映射鏈路，如NA-PVNM算法^［8］。

在已有的研究中，VN請求大都是對節(jié)點計算資源和鏈路帶寬資源的需求。本文研究的是將含有文件需求的VN請求映射到有存儲的物理網(wǎng)絡(luò)上，VN請求不僅包括以上的需求，還包括對節(jié)點存儲資源的需求。因為物理節(jié)點上可能存在請求文件的存儲，所以當(dāng)請求命中時，該節(jié)點流向下游的流量減少。該情況可以轉(zhuǎn)化為節(jié)點的損耗問題，即廣義最小費用流問題^［9］。本文提出了一種基于節(jié)點連通性和廣義網(wǎng)絡(luò)單純形法的虛擬網(wǎng)絡(luò)映射算法——S-VNM算法，在節(jié)點映射階段綜合考慮節(jié)點位置和鏈路映射的映射成本兩個因素，從而減小搜索空間，降低映射成本。通過實驗仿真驗證了該算法的有效性和良好性能。

1  相關(guān)技術(shù)

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

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

在虛擬網(wǎng)絡(luò)映射模型中^［10］，物理網(wǎng)絡(luò)由一個無向圖 G_S=(N_S, E_S, C_S, B_S) 表示，其中 NS代表物理節(jié)點，E_S代表物理鏈路，C_S代表物理節(jié)點的資源，B_S代表物理鏈路的資源。本文研究的是在有存儲的物理網(wǎng)絡(luò)上進(jìn)行虛擬網(wǎng)絡(luò)映射，因此，C_S代表的節(jié)點資源包括節(jié)點計算資源和存儲資源。VN請求也可以表示為G_V=(N_V, E_V, C_V, B_V) ,各字符代表的意義與物理網(wǎng)絡(luò)類似。虛擬網(wǎng)絡(luò)映射過程用映射函數(shù) M (G_V, G_S)來表示：

M (G_V, G_S) :

（N_V, E_V, C_V, B_V） →（N_S, E_S, C_S, B_S）(1)

1.1.2  約束條件

虛擬節(jié)點映射時要滿足物理節(jié)點不可分拆、計算資源及存儲資源的約束，表示如下：

其中，式(2)表示每個虛擬節(jié)點只能映射到單個且互不相同的物理節(jié)點上；式(3)和式(4)分別表示物理節(jié)點可用的計算資源和存儲資源不少于虛擬節(jié)點的所需。

定義虛擬鏈路l_V=(i, j) 映射到物理鏈路上的路徑集合為 P_M(l_V) 。定義路徑 p∈P_M(l_V) 上為虛擬鏈路分配的帶寬為 B(l_V, p)。虛擬鏈路映射時約束如下：

式(5)表示鏈路映射過程中物理鏈路 l_S上有足夠的帶寬資源 B_S(l_S)。

1.1.3  性能指標(biāo)

虛擬網(wǎng)絡(luò)映射問題是節(jié)點和鏈路資源約束下的優(yōu)化問題，主要的性能指標(biāo)有映射成本、映射時間^［11］及VN請求的接受率等。本文以映射成本和映射時間作為評價算法的性能指標(biāo)。

虛擬網(wǎng)絡(luò)的映射成本包括節(jié)點映射成本和鏈路映射成本?？傆成涑杀?C(G_V) 表示如下：

其中， 代表節(jié)點映射的計算成本， 代表節(jié)點映射的存儲成本，C_E(l_V) 代表鏈路映射成本。

1.2  廣義最小費用流問題描述

在一些實際的網(wǎng)絡(luò)流問題中，有些節(jié)點和弧并不滿足流量平衡條件，使得經(jīng)典的網(wǎng)絡(luò)模型無法對其描述，現(xiàn)有研究將其稱為廣義費用流問題^［9］。

1.2.1  廣義最小費用流問題

令 G=(N, A) 為一個有向網(wǎng)絡(luò)，其中N為節(jié)點的集合，A為弧的集合。對于任意的弧 (i, j)∈A，令 x_ij表示從節(jié)點i出發(fā)沿著弧 (i, j) 行進(jìn)的流量，u_ij為 x_ij的上界，即：

0 ≤ x_ij≤ u_ij,(i, j)∈A                 (7)

令 0<μ_ij<1 為弧 (i, j) 上的損耗因子，并假設(shè)當(dāng)沿著弧 (i, j) 從節(jié)點i發(fā)送一個單位流量時，有 μij 個單位流量到達(dá)節(jié)點j。對于節(jié)點 i∈N，定義 E（i）和 L（i） 分別為“進(jìn)入”和“離開”該節(jié)點的弧的集合，即：

E(i)={( j, i)∈A : j∈N} 且

L(i)={(i, j)∈A : j∈N}                              (8)

1.2.2  各節(jié)點約束條件

對于源節(jié)點S-節(jié)點，令 NS表示所有S-節(jié)點的集合。對每一個 i∈NS，有 E(i)=∮，且有一個輸入流 x_i使得：

對于轉(zhuǎn)運節(jié)點O-節(jié)點，滿足：

對于分配節(jié)點D-節(jié)點，輸出弧上的流量與進(jìn)入弧上的流量成比例，滿足：

對于目的節(jié)點T-節(jié)點，對每一個 i∈NT，有 L(i)= ∮，且有一個輸出流 x_i使得：

2  本文算法

本節(jié)詳細(xì)介紹了S-VNM算法，該算法實現(xiàn)了將含有文件需求的VN請求映射到有存儲的物理網(wǎng)絡(luò)上。其分為三個階段：(1) 虛擬節(jié)點排序；(2) 虛擬節(jié)點映射；(3) 虛擬鏈路映射。

2.1 虛擬節(jié)點排序

一個具體的VN請求包含多個虛擬節(jié)點，由于物理網(wǎng)絡(luò)資源有限，對資源需求越大的節(jié)點越難映射成功，因此優(yōu)先映射該類節(jié)點。同時，為了保證映射的相關(guān)性，在進(jìn)行下一個虛擬節(jié)點映射時，優(yōu)先選擇與已映射的虛擬節(jié)點集合有關(guān)聯(lián)的節(jié)點。

定義虛擬節(jié)點的需求 C_R（n_V） 如下：

其中，C_C(n_V) 代表虛擬節(jié)點 n_V 的計算資源需求，C_S(n_V) 代表 n_V 的存儲資源需求，L(n_V)代表所有與 n_V相關(guān)聯(lián)的鏈路集合，B(l) 代表與 n_V相關(guān)聯(lián)的鏈路所需的帶寬資源。

2.2 虛擬節(jié)點映射

本文提出的虛擬節(jié)點映射算法是基于物理節(jié)點連通性和映射總成本實現(xiàn)的。

定義與虛擬節(jié)點 n_V相關(guān)聯(lián)的已映射虛擬節(jié)點在物理網(wǎng)絡(luò)中的映射節(jié)點集合為M。定義物理節(jié)點 n_s與集合M的連通性為 N_rank(n_s)：

其中，C_C(n_s) 代表物理節(jié)點 n_s的可用計算資源，C_S(n_s) 代表 n_s的可用存儲資源，C_available(n_t, n_s) 代表物理節(jié)點 n_t 與 n_s 之間的可行流，D(n_t, n_s) 代表兩節(jié)點之間的距離。

按照節(jié)點連通性將物理節(jié)點由大到小排序后，選擇排序靠前的節(jié)點作為待選節(jié)點。然后，對待選節(jié)點進(jìn)行節(jié)點映射和鏈路映射，根據(jù)每一次映射結(jié)果，統(tǒng)計節(jié)點的映射成本和所有相關(guān)鏈路的映射成本作為效用函數(shù) C_total(n_s)，以此來評價物理節(jié)點 n_s，最終選擇效用函數(shù)最小的節(jié)點作為映射節(jié)點。效用函數(shù)C_total(n_s) 表示如下：

其中， 代表節(jié)點映射的計算成本， 代表節(jié)點映射的存儲成本，C_E(n_t, n_s) 代表映射到物理節(jié)點 n_s的最小鏈路映射成本。

2.3  虛擬鏈路映射

在虛擬節(jié)點映射時，節(jié)點映射成本易求出，但如何求最小鏈路映射成本的問題可轉(zhuǎn)化為最小費用流問題。

本文的VN請求含有文件需求，因此在映射的過程中，應(yīng)考慮該情況：如果當(dāng)下的映射節(jié)點與已映射節(jié)點之間的路徑上存在含有該文件的節(jié)點，當(dāng)請求命中時，有該文件的節(jié)點類似于分配節(jié)點D-節(jié)點，需留下該文件的流而將其他需求的流送出。由此可見，求解鏈路映射成本問題可轉(zhuǎn)化為廣義最小費用流問題。

虛擬鏈路映射成本問題的模型可以表示為：

其中，x是在給定網(wǎng)絡(luò)G=(N, A) 的弧集上的可行流，F(xiàn)是所有滿足式（7）~(12)的可行流的集合，Cij是從節(jié)點i出發(fā)的單位流量沿弧 (i, j) 到達(dá)節(jié)點j所產(chǎn)生的費用。

賦予每一個節(jié)點 i∈N一個勢 π(i)，定義弧(i, j)∈A 的檢驗數(shù)  為：

定義迭代終止的最優(yōu)性條件，設(shè) (F, L) 為基本可行結(jié)構(gòu)，其中，F(xiàn)表示可行解x的基本可行圖，L表示取值下界的弧的集合。如果對于某個給定的勢向量 π，弧上的檢驗數(shù)滿足下列條件：

則 (F, L) 為最優(yōu)結(jié)構(gòu)。

本文提出的虛擬鏈路映射算法的核心思想是：

(1) 生成初始基本可行結(jié)構(gòu) (F, L)。

(2) 根據(jù)公式(18)計算節(jié)點的勢 π 和弧的檢驗數(shù)。

(3) 檢驗式(19)和式(20)所示的最優(yōu)條件。如果所有的最優(yōu)性條件全都滿足，則算法停止；否則，選擇一條不滿足最優(yōu)性條件的弧 (k, l) 作為進(jìn)基弧。

(4) 在進(jìn)基弧 (k, l) 上增加適當(dāng)?shù)牧髁?，計算基本可行圖上各弧上流量的調(diào)整量，更新基本可行解x和基本可行結(jié)構(gòu) (F, L)，轉(zhuǎn)步驟(2)。

由此，可求出基本可行解x，進(jìn)而計算出虛擬鏈路映射的最小成本，再計算出待選節(jié)點的效用函數(shù) C_total(n_s)，選擇該值最小的節(jié)點作為映射節(jié)點，最終完成虛擬網(wǎng)絡(luò)映射。

算法  S-NVM

輸入：VN請求(NV, EV)，物理網(wǎng)絡(luò)(NS, ES)；

輸出：虛擬映射M(GV, GS)。

1. M= ∮，Di=∮，i=0，step=0，N// 初始化

// Di 代表待選物理節(jié)點的集合

2. for all nV∈NV //虛擬節(jié)點排序

3. count the CR（nV） of nV

4. end for

5.arrange nV in descending according to CR（nV）

6.for all niV∈NV

7.if (M= ∮)// 第一個虛擬節(jié)點映射

8.select niV∈NV which has the biggest CR（nV）

9.select niS∈NS which has the biggest C（niS）

10. map niV to niS

11. end if

12. else// 虛擬節(jié)點和虛擬鏈路映射

13. select niV∈NV which has the biggest CR（nV）

// 選擇與上一個映射的虛擬節(jié)點有關(guān)聯(lián)的節(jié)點

14. order niS∈NS by Nrank(niS)

15. for all niS∈NS and step < N

// 選擇按照連通性大小排序后的前N個節(jié)點

16. count the Ctotal(niS)

17. step++

18. niS→Di

19. end for

20. select niS∈Di which has minimum Ctotal(niS)

21. niS→M

22. map niV to niS

23.end else

24.i++

25.end for

3  實驗與結(jié)果分析

實驗通過MATLAB進(jìn)行仿真評估。采用GT-ITM拓?fù)洚a(chǎn)生器隨機生成物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)請求。本文將D-ViNE算法和vnmFlib simple算法作為對照，從映射成本和算法運行時間兩方面進(jìn)行比較。

物理網(wǎng)絡(luò)包含60個節(jié)點，150條鏈路。物理節(jié)點的可用計算和存儲容量服從［50,150］均勻分布，單位成本服從［1,5］均勻分布。物理鏈路可用帶寬容量服從［1,100］均勻分布，單位成本服從［1,10］分布。虛擬網(wǎng)絡(luò)節(jié)點個數(shù)服從［3,15］均勻分布，任意兩個虛擬節(jié)點之間以0.5的概率連接，虛擬節(jié)點和虛擬鏈路需求服從［10,50］均勻分布。 μ_ij=0.7。

基于以上仿真環(huán)境，運行三種映射算法，結(jié)果如圖1和圖2所示。

實驗結(jié)果表明，S-VNM算法整體上比其他兩種算法有優(yōu)勢。在映射成本方面，S-VNM算法性能最好，因為在搜索解空間過程中每次都取映射成本最小的節(jié)點作為映射結(jié)果。在運行時間方面，S-VNM算法優(yōu)于D-ViNE算法，這是因為S-VNM算法在映射時選擇連通性較大的節(jié)點進(jìn)行映射，減小搜索空間，從而降低運行時間。但S-VNM在運行時間方面劣于vnmFlib simple算法，這是因為vnmFlib simple算法直接使用區(qū)間內(nèi)的最大跳數(shù)作為路徑條數(shù)約束，雖沒有減小搜索空間，但算法復(fù)雜度低，所以運行時間短。

4  結(jié)論

本文提出一種啟發(fā)式搜索和基于廣義網(wǎng)絡(luò)單純形法的虛擬網(wǎng)絡(luò)映射算法——S-VNM算法，其實現(xiàn)了將含有文件需求的VN請求映射到有存儲的物理網(wǎng)絡(luò)上。S-VNM算法在節(jié)點映射階段把物理節(jié)點之間的連通性作為篩選標(biāo)準(zhǔn)，虛擬節(jié)點的映射成本作為效用函數(shù)，與傳統(tǒng)算法相比減小了搜索空間，降低了映射成本。在鏈路映射階段采用廣義網(wǎng)絡(luò)單純形法，與最短路徑算法相比降低了映射的時間復(fù)雜度。實驗結(jié)果表明，在綜合考慮映射成本和算法運行時間的情況下，本文提出的算法性能最優(yōu)。

參考文獻(xiàn)

［1］ 桂燕興, 沈蘇彬, 毛燕琴. 基于SDN的虛擬網(wǎng)絡(luò)映射技術(shù)的研究與實現(xiàn)［J］. 微型機與應(yīng)用, 2015，34(13): 69-72.

［2］ CHOWDHURY N M M K, BOUTABAR. A survey of network virtualization［J］. Computer Networks, 2010, 54(5):862-876.

［3］ WANG A, IYER M, DUTTA R, et al. Network virtualization: technologies, perspectives, and frontiers［J］. Journal of Lightwave Technology, 2013, 31(4):523-537.

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

［5］ 蔡志平, 劉強, 呂品,等. 虛擬網(wǎng)絡(luò)映射模型及其優(yōu)化算法［J］. 軟件學(xué)報, 2012, 23(4):864-877.

［6］ CHOWDHURY N M M K, RAHMAN M R, BOUTABA R. Virtual network embedding with coordinated node and link mapping［J］. Proceedings-IEEE INFOCOM, 2009, 20(1):783-791.

［7］ LISCHKA J, KARL H. A virtual network mapping algorithm based on subgraph isomorphism detection［C］. ACM Workshop on Virtualized Infrastructure Systems and Architectures. ACM, 2009:81-88.

［8］ 趙志遠(yuǎn), 孟相如, 蘇玉澤, 等. 基于節(jié)點鄰近感知與路徑綜合評估的虛擬網(wǎng)絡(luò)映射算法［J］. 電子與信息學(xué)報, 2017, 39(8):1979-1985.

［9］ 魯海燕. 最小費用網(wǎng)絡(luò)流的若干新問題研究［D］. 杭州：浙江大學(xué), 2007.

［10］ 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.

［11］ Di Hao, Yu Hongfang, ANAND V, et al. Efficient online virtual network mapping using resource evaluation［J］. Journal of Network & Systems Management, 2012, 20(4):468-488.

（收稿日期：2018-03-30）

作者簡介：

陳晨（1994-），女，碩士，主要研究方向：未來網(wǎng)絡(luò)、虛擬網(wǎng)絡(luò)映射。

鄭烇（1970-），通信作者，男，博士，副教授，主要研究方向：未來網(wǎng)絡(luò)、命名數(shù)據(jù)網(wǎng)絡(luò)緩存和虛擬網(wǎng)絡(luò)映射。E-mail: qzheng@ustc.edu.cn。

王志臻（1993-），男，碩士，主要研究方向：未來網(wǎng)絡(luò)、虛擬網(wǎng)絡(luò)映射。