0 引言

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

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

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

1  相關技術

1.1  虛擬網絡映射問題描述

1.1.1  虛擬網絡映射模型

在虛擬網絡映射模型中^［10］，物理網絡由一個無向圖 G_S=(N_S, E_S, C_S, B_S) 表示，其中 NS代表物理節點，E_S代表物理鏈路，C_S代表物理節點的資源，B_S代表物理鏈路的資源。本文研究的是在有存儲的物理網絡上進行虛擬網絡映射，因此，C_S代表的節點資源包括節點計算資源和存儲資源。VN請求也可以表示為G_V=(N_V, E_V, C_V, B_V) ,各字符代表的意義與物理網絡類似。虛擬網絡映射過程用映射函數 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  約束條件

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

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

定義虛擬鏈路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  性能指標

虛擬網絡映射問題是節點和鏈路資源約束下的優化問題，主要的性能指標有映射成本、映射時間^［11］及VN請求的接受率等。本文以映射成本和映射時間作為評價算法的性能指標。

虛擬網絡的映射成本包括節點映射成本和鏈路映射成本。總映射成本 C(G_V) 表示如下：

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

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

在一些實際的網絡流問題中，有些節點和弧并不滿足流量平衡條件，使得經典的網絡模型無法對其描述，現有研究將其稱為廣義費用流問題^［9］。

1.2.1  廣義最小費用流問題

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

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

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

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

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

1.2.2  各節點約束條件

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

對于轉運節點O-節點，滿足：

對于分配節點D-節點，輸出弧上的流量與進入弧上的流量成比例，滿足：

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

2  本文算法

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

2.1 虛擬節點排序

一個具體的VN請求包含多個虛擬節點，由于物理網絡資源有限，對資源需求越大的節點越難映射成功，因此優先映射該類節點。同時，為了保證映射的相關性，在進行下一個虛擬節點映射時，優先選擇與已映射的虛擬節點集合有關聯的節點。

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

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

2.2 虛擬節點映射

本文提出的虛擬節點映射算法是基于物理節點連通性和映射總成本實現的。

定義與虛擬節點 n_V相關聯的已映射虛擬節點在物理網絡中的映射節點集合為M。定義物理節點 n_s與集合M的連通性為 N_rank(n_s)：

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

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

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

2.3  虛擬鏈路映射

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

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

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

其中，x是在給定網絡G=(N, A) 的弧集上的可行流，F是所有滿足式（7）~(12)的可行流的集合，Cij是從節點i出發的單位流量沿弧 (i, j) 到達節點j所產生的費用。

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

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

則 (F, L) 為最優結構。

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

(1) 生成初始基本可行結構 (F, L)。

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

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

(4) 在進基弧 (k, l) 上增加適當的流量，計算基本可行圖上各弧上流量的調整量，更新基本可行解x和基本可行結構 (F, L)，轉步驟(2)。

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

算法  S-NVM

輸入：VN請求(NV, EV)，物理網絡(NS, ES)；

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

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

// Di 代表待選物理節點的集合

2. for all nV∈NV //虛擬節點排序

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= ∮)// 第一個虛擬節點映射

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// 虛擬節點和虛擬鏈路映射

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

// 選擇與上一個映射的虛擬節點有關聯的節點

14. order niS∈NS by Nrank(niS)

15. for all niS∈NS and step < N

// 選擇按照連通性大小排序后的前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  實驗與結果分析

實驗通過MATLAB進行仿真評估。采用GT-ITM拓撲產生器隨機生成物理網絡和虛擬網絡請求。本文將D-ViNE算法和vnmFlib simple算法作為對照，從映射成本和算法運行時間兩方面進行比較。

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

基于以上仿真環境，運行三種映射算法，結果如圖1和圖2所示。

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

4  結論

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

參考文獻

［1］ 桂燕興, 沈蘇彬, 毛燕琴. 基于SDN的虛擬網絡映射技術的研究與實現［J］. 微型機與應用, 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］ 程祥, 張忠寶, 蘇森, 等. 虛擬網絡映射問題研究綜述［J］. 通信學報, 2011, 32(10):143-151.

［5］ 蔡志平, 劉強, 呂品,等. 虛擬網絡映射模型及其優化算法［J］. 軟件學報, 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］ 趙志遠, 孟相如, 蘇玉澤, 等. 基于節點鄰近感知與路徑綜合評估的虛擬網絡映射算法［J］. 電子與信息學報, 2017, 39(8):1979-1985.

［9］ 魯海燕. 最小費用網絡流的若干新問題研究［D］. 杭州：浙江大學, 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-），女，碩士，主要研究方向：未來網絡、虛擬網絡映射。

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

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