0 引言

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

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

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

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

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

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

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

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é)點(diǎn)映射時(shí)要滿足物理節(jié)點(diǎn)不可分拆、計(jì)算資源及存儲(chǔ)資源的約束，表示如下：

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

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

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

1.1.3  性能指標(biāo)

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

虛擬網(wǎng)絡(luò)的映射成本包括節(jié)點(diǎn)映射成本和鏈路映射成本。總映射成本 C(G_V) 表示如下：

其中， 代表節(jié)點(diǎn)映射的計(jì)算成本， 代表節(jié)點(diǎn)映射的存儲(chǔ)成本，C_E(l_V) 代表鏈路映射成本。

1.2  廣義最小費(fèi)用流問(wèn)題描述

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

1.2.1  廣義最小費(fèi)用流問(wèn)題

令 G=(N, A) 為一個(gè)有向網(wǎng)絡(luò)，其中N為節(jié)點(diǎn)的集合，A為弧的集合。對(duì)于任意的弧 (i, j)∈A，令 x_ij表示從節(jié)點(diǎn)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é)點(diǎn)i發(fā)送一個(gè)單位流量時(shí)，有 μij 個(gè)單位流量到達(dá)節(jié)點(diǎn)j。對(duì)于節(jié)點(diǎn) i∈N，定義 E（i）和 L（i） 分別為“進(jìn)入”和“離開(kāi)”該節(jié)點(diǎn)的弧的集合，即：

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

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

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

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

對(duì)于轉(zhuǎn)運(yùn)節(jié)點(diǎn)O-節(jié)點(diǎn)，滿足：

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

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

2  本文算法

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

2.1 虛擬節(jié)點(diǎn)排序

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

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

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

2.2 虛擬節(jié)點(diǎn)映射

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

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

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

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

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

2.3  虛擬鏈路映射

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

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

虛擬鏈路映射成本問(wèn)題的模型可以表示為：

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

賦予每一個(gè)節(jié)點(diǎn) i∈N一個(gè)勢(shì) π(i)，定義弧(i, j)∈A 的檢驗(yàn)數(shù)  為：

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

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

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

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

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

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

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

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

算法  S-NVM

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

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

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

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

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

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= ∮)// 第一個(gè)虛擬節(jié)點(diǎn)映射

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é)點(diǎn)和虛擬鏈路映射

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

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

14. order niS∈NS by Nrank(niS)

15. for all niS∈NS and step < N

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

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  實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

4  結(jié)論

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

參考文獻(xiàn)

［1］ 桂燕興, 沈蘇彬, 毛燕琴. 基于SDN的虛擬網(wǎng)絡(luò)映射技術(shù)的研究與實(shí)現(xiàn)［J］. 微型機(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ò)映射問(wèn)題研究綜述［J］. 通信學(xué)報(bào), 2011, 32(10):143-151.

［5］ 蔡志平, 劉強(qiáng), 呂品,等. 虛擬網(wǎng)絡(luò)映射模型及其優(yōu)化算法［J］. 軟件學(xué)報(bào), 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é)點(diǎn)鄰近感知與路徑綜合評(píng)估的虛擬網(wǎng)絡(luò)映射算法［J］. 電子與信息學(xué)報(bào), 2017, 39(8):1979-1985.

［9］ 魯海燕. 最小費(fèi)用網(wǎng)絡(luò)流的若干新問(wèn)題研究［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）

作者簡(jiǎn)介：

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

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

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