基于動態(tài)規(guī)劃的服務(wù)功能鏈映射算法

袁紹露，張向利

（桂林電子科技大學(xué)廣西無線寬帶通信與信號處理重點實驗室，桂林 541004）

0 引言

隨著數(shù)據(jù)流量爆發(fā)式增長，智能工廠、車聯(lián)網(wǎng)等新型技術(shù)日益成熟需要多樣的網(wǎng)絡(luò)服務(wù)，以及5G網(wǎng)絡(luò)需利用網(wǎng)絡(luò)切片技術(shù)為用戶提供定制化網(wǎng)絡(luò)服務(wù)［1］，傳統(tǒng)的TCP/IP架構(gòu)網(wǎng)絡(luò)面臨巨大挑戰(zhàn)。傳統(tǒng)網(wǎng)絡(luò)采用的是分布式網(wǎng)絡(luò)架構(gòu)，通過簡單地增加網(wǎng)絡(luò)設(shè)備和線路修補式的解決網(wǎng)絡(luò)擁堵問題，不僅會增加網(wǎng)絡(luò)流量傳輸動態(tài)調(diào)控的難度，而且不能對整體網(wǎng)絡(luò)性能有較大的提高［2］。因此，各大運營商利用網(wǎng)絡(luò)功能虛擬化（NFV）技術(shù)構(gòu)建全新的網(wǎng)絡(luò)體系結(jié)構(gòu)解決上述問題。

VNF核心思想是將傳統(tǒng)網(wǎng)絡(luò)中專用網(wǎng)絡(luò)設(shè)備上網(wǎng)絡(luò)功能的軟件實現(xiàn)與昂貴的專用硬件資源進行解耦，在通用服務(wù)器上共享硬件設(shè)施并以軟件方式實現(xiàn)不同的網(wǎng)絡(luò)功能。VNF可以靈活快速地在最優(yōu)位置上部署所需的網(wǎng)絡(luò)功能［3］，根據(jù)用戶服務(wù)需求將所需的VNF構(gòu)建成一個有序的服務(wù)功能鏈（SFC），然后將SFC映射到切片網(wǎng)絡(luò)中為用戶實現(xiàn)定制化網(wǎng)絡(luò)服務(wù)，實現(xiàn)差異化服務(wù)。將如何在基礎(chǔ)設(shè)施中為網(wǎng)絡(luò)服務(wù)分配所需要資源稱為VNF資源分配（VNF-RA）問題［4］。NFV-RA問題第二階段稱為VNF轉(zhuǎn)發(fā)圖嵌入，也稱之為服務(wù)功能鏈的映射。如何對服務(wù)功能鏈的映射是對不同服務(wù)請求進行差異化服務(wù)的前提。關(guān)于服務(wù)功能鏈映射問題的研究。文獻［5］將用戶服務(wù)請求構(gòu)建成SFC后，對SFC映射問題轉(zhuǎn)成類似于VNE問題，其兩者的差別在于約束條件和優(yōu)化目標不同。文獻［6］是在虛擬機上尚未部署網(wǎng)絡(luò)功能情況下對SFC進行映射，將問題分成網(wǎng)絡(luò)功能部署和SFC調(diào)度兩個子問題，以網(wǎng)絡(luò)切片中服務(wù)功能鏈的最小服務(wù)時延為優(yōu)化目標，并通過粒子群算法對目標進行優(yōu)化。文獻［7］提出基于馬爾科夫模型的SAMA啟發(fā)式算法，通過計算虛擬機優(yōu)先接收優(yōu)先級高的SFC進行映射，降低搜索空間，從而提高映射效率。

SFC映射被證明是NP難問題［8］，當(dāng)前研究方法采用較多的是啟發(fā)式算法。當(dāng)SFC數(shù)目較多時，利用啟發(fā)式算法對多目標求解具有快速求解的優(yōu)勢，但實際網(wǎng)絡(luò)環(huán)境中存在需要映射SFC數(shù)目較少情況，如果繼續(xù)利用基于啟發(fā)式的算法，存在優(yōu)化時間較長的問題。因此，本文提出一種SFC映射算法（DI-MCMF），即將該問題分成VNF映射和虛擬鏈路映射物理鏈路兩個子問題，首先分別找出VNF匹配的虛擬機，然后通過動態(tài)規(guī)劃有向無環(huán)低時延算法獲得VNF映射方案；再采用最小費用最大流算法獲得虛擬鏈路映射方案。

1 問題描述

一個核心切片網(wǎng)絡(luò)可以根據(jù)不同用戶需求為其提供差異化網(wǎng)絡(luò)服務(wù)，這些網(wǎng)路服務(wù)可以用服務(wù)功能鏈（SFC）進行表示。服務(wù)功能鏈上VNF的服務(wù)是由切片網(wǎng)絡(luò)中服務(wù)器上的虛擬機所部署的網(wǎng)絡(luò)功能來提供。由于虛擬機的資源是有限的，因此在實際網(wǎng)絡(luò)環(huán)境中不同服務(wù)功能鏈上相同的虛擬網(wǎng)絡(luò)功能需要共享某個虛擬機上的網(wǎng)絡(luò)功能，如圖1所示。

圖1 SFC與網(wǎng)絡(luò)切片

在圖1中，SFC1中的虛擬網(wǎng)絡(luò)功能vf和SFC2中的虛擬網(wǎng)絡(luò)功能vf共享服務(wù)器3上部署網(wǎng)絡(luò)功能為NFf的虛擬機。在采用VNF技術(shù)的網(wǎng)絡(luò)環(huán)境下，通過在服務(wù)器的虛擬機上部署網(wǎng)絡(luò)功能作為虛擬網(wǎng)絡(luò)功能設(shè)備來提供該功能的網(wǎng)絡(luò)服務(wù)。為了進一步提高資源的利用率，不僅讓某個虛擬網(wǎng)絡(luò)功能設(shè)備可以被不同的服務(wù)功能鏈中同類型的VNF共享使用，而且可以在服務(wù)器上配置多個虛擬機以提供更多的網(wǎng)絡(luò)服務(wù)。如圖1中服務(wù)器1上兩個虛擬機分別部署了網(wǎng)絡(luò)功能NFa和網(wǎng)絡(luò)功能NFd。但是由于單個虛擬網(wǎng)絡(luò)功能設(shè)備資源的限制，所以單個虛擬網(wǎng)路功能設(shè)備服務(wù)用戶的數(shù)目也是有限的，就會造成不同服務(wù)功能鏈上相同的VNF被調(diào)度到不同服務(wù)器的虛擬網(wǎng)絡(luò)設(shè)備上。如圖1中，SFC1與SFC3具有相同的虛擬網(wǎng)絡(luò)功能va，但被分別調(diào)度到服務(wù)器1和服務(wù)器0上進行信息的處理。單個服務(wù)功能鏈中各虛擬網(wǎng)絡(luò)功能會調(diào)度到不同服務(wù)器上具備該類型的虛擬機來處理，并且各個虛擬網(wǎng)絡(luò)功能之間的虛擬鏈路可以由多條物理鏈進行數(shù)據(jù)流的傳輸。

本文研究的是服務(wù)功能鏈映射問題，是指在切片網(wǎng)絡(luò)中為虛擬機分配了資源并且虛擬機上已經(jīng)部署了相應(yīng)的網(wǎng)路功能的情況下，將服務(wù)功能鏈上虛擬網(wǎng)絡(luò)功能調(diào)度到各自匹配的虛擬機上處理數(shù)據(jù)流，還需要解決服務(wù)功能鏈上虛擬鏈路分配哪些物理鏈路進行信息的傳遞。如圖2所示。

圖2 服務(wù)功能鏈調(diào)度

在圖2中，切片網(wǎng)絡(luò)中各服務(wù)器上的虛擬機已經(jīng)部署相應(yīng)的網(wǎng)絡(luò)功能。在對SFC1功能鏈進行映射時會存在多種映射方案。方案Ⅰ的部署方式為先從服務(wù)器2上的NFa到服務(wù)器1上的NFf再到服務(wù)器4上的NFg。方案Ⅱ的部署方式為從服務(wù)器3上的Nfa到服務(wù)器1上的NFf再到服務(wù)器5上的NFg。方案Ⅰ和方案Ⅱ的部署方式有相同的服務(wù)器1，也有不同的服務(wù)器2、服務(wù)器3等。由于已經(jīng)有服務(wù)功能鏈在物理網(wǎng)絡(luò)上運行，就會造成部署相同網(wǎng)絡(luò)功能的不同服務(wù)器剩余的計算力不相同，例如服務(wù)器2和服務(wù)器3上有相同的NFa，但是它們的剩余計算力不相同，就會造成虛擬網(wǎng)絡(luò)功能a處理時延不相同，并且不同服務(wù)器之間的傳輸時延也會不同，所以方案Ⅰ和方案Ⅱ的部署方式就會造成服務(wù)功能鏈的服務(wù)時延不相同。當(dāng)有新的服務(wù)功能鏈需要映射物理網(wǎng)絡(luò)時，如何選擇低服務(wù)時延的映射路徑非常重要。因此，本文提出了DI-MCMF算法來解決上述問題。

2 數(shù)學(xué)模型

數(shù)學(xué)模型使用的符號及其物理意義如表1所示。

表1 數(shù)學(xué)模型中的符號及其物理意義

2.1 網(wǎng)絡(luò)模型及SFC模型

在本文中使用一個加權(quán)無向圖G=（N,E）對物理傳輸網(wǎng)絡(luò)進行表示。將物理服務(wù)器與物理交換節(jié)點視為一個節(jié)點，每個服務(wù)器上可部署V S個虛擬機，每個虛擬機部署一個網(wǎng)絡(luò)功能。根據(jù)用戶的服務(wù)需求構(gòu)建成相應(yīng)的SFC，服務(wù)功能鏈上不同的虛擬網(wǎng)絡(luò)功能處理單個數(shù)據(jù)流時延不同，相同的虛擬網(wǎng)絡(luò)功能處理單個數(shù)據(jù)流時延相同。

2.2 約束條件

2.2.1 服務(wù)器上部署虛擬網(wǎng)絡(luò)功能約束條件

在本文中一個服務(wù)器可以虛擬化出多個網(wǎng)絡(luò)功能，每個服務(wù)器上有多個虛擬機，每個虛擬機上部署一個虛擬網(wǎng)絡(luò)功能。使用表示網(wǎng)絡(luò)功能F d是否部署到第n個服務(wù)器的第m個虛擬機上，則：

2.2.2 SFC中VNF離線匹配的約束條件

通過映射算法將集合C中SFC上的虛擬網(wǎng)絡(luò)功能映射虛擬機上，當(dāng)虛擬機上部署的網(wǎng)絡(luò)功能與的功能相同，或者上還沒有部署網(wǎng)絡(luò)功能。使用表示第k個服務(wù)功能鏈的第h虛擬網(wǎng)絡(luò)功能映射到第n個服務(wù)器上的第m個虛擬機，并且SFC上的網(wǎng)絡(luò)功能只能映射到一個虛擬機上，則：

網(wǎng)絡(luò)功能對業(yè)務(wù)處理能力是有限的，一個虛擬機上的網(wǎng)絡(luò)功能對映射到該虛擬機的SFC數(shù)據(jù)流之和不能超過網(wǎng)絡(luò)功能業(yè)務(wù)能力，則：

2.2.3 SFC中虛擬鏈路映射的約束條件

SFC上兩個虛擬網(wǎng)絡(luò)功能的虛擬鏈路的帶寬為，一個虛擬鏈路可映射到物理網(wǎng)絡(luò)的多條物理鏈路e i,j，用來表示是否占用物理鏈路e i,j的帶寬，用表示在物理鏈路e i,j上占用帶寬的大小。物理鏈路e i,j剩余的可利用的帶寬用b i,j表示，則：

2.3 核心網(wǎng)絡(luò)切片的服務(wù)時延

服務(wù)功能鏈的服務(wù)時延由兩部分構(gòu)成，分別為服務(wù)功能鏈各虛擬網(wǎng)絡(luò)功能在所映射虛擬機上處理時延和服務(wù)功能鏈在物理網(wǎng)絡(luò)上傳輸時延τC K。處理時延由網(wǎng)絡(luò)功能所需的計算量與該功能所映射物理網(wǎng)絡(luò)上服務(wù)器的計算速度來表示，每條服務(wù)功能鏈上所有虛擬網(wǎng)絡(luò)功能處理時延用進行表示，則：

使用Ttotal表示服務(wù)功能鏈集合C服務(wù)時延之和，則有：

3 服務(wù)功能鏈映射算法

本文提出的服務(wù)功能鏈映射DI-MCMF算法分成SFC上虛擬網(wǎng)絡(luò)功能映射虛擬機和虛擬鏈路映射物理鏈路兩個部分。

3.1 虛擬鏈路映射算法

當(dāng)一個SFC上的兩個VNF映射到物理網(wǎng)絡(luò)上后，需要將這兩個VNF之間的虛擬鏈路映射到物理網(wǎng)絡(luò)上。由于物理網(wǎng)絡(luò)上鏈路有多條虛擬鏈路映射，就有可能造成該物理鏈路不能滿足虛擬鏈路的帶寬需求。如果將虛擬鏈路只映射到一條物理鏈路上，當(dāng)該物理鏈路發(fā)生故障的時候，就會直接影響到用戶的網(wǎng)絡(luò)服務(wù)。因此，需要將分配到多條物理路徑上。不同物理鏈路的需要費用不一樣，為滿足SFC上虛擬鏈路帶寬要求和降低使用成本，采用最小費用最大流算法的思路［9］。由于本文物理鏈路的參數(shù)設(shè)定義為帶寬和時延，因此需要將問題轉(zhuǎn)化為最小時延最大帶寬問題。在對虛擬鏈路進行映射的時候，先找出最小時延時路徑，即在物理網(wǎng)絡(luò)上尋找兩個VNF映射節(jié)點間以時延為權(quán)值的最短路徑，然后沿著最小時延路增加帶寬，直到滿足SFC虛擬鏈路的帶寬需求，虛擬鏈路映射算法步驟如下：

（1）在物理網(wǎng)絡(luò)拓撲上分別增加一個虛擬發(fā)送節(jié)點S和一個虛擬接收節(jié)點R。生成鄰接矩陣M。虛擬發(fā)送節(jié)點S到所映射的服務(wù)器h∈S N為單向流出鏈路，該單向鏈路的帶寬為第C k個服務(wù)功能鏈的帶寬需求，并且將該單向鏈路的時延設(shè)置為0。虛擬接收節(jié)點R到所映射的服務(wù)器l∈S N為單向流入鏈路，該單向鏈路的帶寬同樣為，鏈路的時延也為0。物理網(wǎng)絡(luò)鏈路都只設(shè)定帶寬和時延這兩個約束條件，服務(wù)功能鏈的虛擬鏈路映射問題就轉(zhuǎn)變成虛擬發(fā)送節(jié)點S到虛擬接收節(jié)點R之間的最小時延最大帶寬問題，如圖3所示。

圖3 （帶寬、時延）拓撲圖

（2）新建路徑集合P，并賦初始值為空；新建S節(jié)點到R節(jié)點帶寬f，并賦初始值為0。

（3）用Dijkstra求解節(jié)點S到節(jié)點R之間的最小時延有向路徑a，在路徑上的可用帶寬為b。

7.學(xué)習(xí)成功后點擊“確定”進行第二把的匹配(哈佛H6鑰匙匹配時至少需要匹配2把才能著車)，如圖8所示。

步驟3-1：增加帶寬f+=b，在M中把路徑a上所有鏈路的可用帶寬減去b，同時反向鏈路可用帶寬值上加b。若M中某條鏈路的帶寬為0，則在M中取消該條鏈路。

步驟3-2：將路徑a和該路徑的帶寬分別賦給路徑集合P和帶寬f。

重復(fù)執(zhí)行步驟3直到f≥。若f≥，則能夠映射到物理網(wǎng)絡(luò)中，P值作為映射方案，的傳輸時延為t。否則映射失敗。

3.2 SFC上VNF的映射

服務(wù)功能鏈中VNF映射到最優(yōu)位置上的虛擬機問題類似于動態(tài)規(guī)劃有向無環(huán)最短路徑問題，如圖4所示。

圖4 VNF所匹配的虛擬機

當(dāng)新服務(wù)功能鏈需要添加到物理網(wǎng)絡(luò)中時，首先按照服務(wù)功能鏈上虛擬網(wǎng)絡(luò)功能的依賴順序?qū)ふ腋髯云ヅ浞?wù)器的集合其中，S i∈S表示服務(wù)功能鏈上第i個虛擬網(wǎng)絡(luò)功能所匹配服務(wù)器的集合。如圖4上待映射服務(wù)功能鏈C k上虛擬網(wǎng)絡(luò)功能a匹配的服務(wù)器集合為服務(wù)器2和服務(wù)器3。添加源節(jié)點S，節(jié)點S單向連接服務(wù)功能鏈C k上第一個虛擬網(wǎng)絡(luò)功能匹配的服務(wù)器節(jié)點。添加終節(jié)點T，服務(wù)功能鏈C k上最后一個虛擬網(wǎng)絡(luò)功能單向連接節(jié)點T。

由于虛擬網(wǎng)絡(luò)功能之間是單向傳遞的關(guān)系，所以服務(wù)功能鏈上各虛擬網(wǎng)路功能所匹配的服務(wù)器集合之間就能構(gòu)建一個以服務(wù)器為節(jié)點的有向圖G S=（N S,E S），N S表示以服務(wù)器節(jié)點和源終節(jié)點的集合，E S表示服務(wù)器之間鏈路的集合。集合Si里的服務(wù)器節(jié)點之間沒有鏈路連接。集合Si上的服務(wù)器均與集合Si+1上的服務(wù)器都存在單向連接關(guān)系。源節(jié)點S到S0的各服務(wù)器節(jié)點的邊權(quán)值為0。服務(wù)器節(jié)點與服務(wù)器節(jié)點的邊權(quán)值表示在滿足服務(wù)功能鏈上v i與v i+1帶寬需求前提下的傳輸時延加上v i在服務(wù)器處理時延，處理時延利用公式（7）計算。到終節(jié)點T邊權(quán)值為服務(wù)功能鏈C k上最后一個虛擬網(wǎng)絡(luò)功能在服務(wù)器上的處理時延。

服務(wù)功能鏈C K映射優(yōu)化目標是服務(wù)時延，因此將問題轉(zhuǎn)變成動態(tài)規(guī)劃有向無循環(huán)低時延問題。首先對圖GG進行分段，每一層的各個節(jié)點互不連通，后驅(qū)節(jié)點均在同一層。將節(jié)點S列為第一層，終節(jié)點T為最后一層，中間各層為服務(wù)功能鏈上虛擬網(wǎng)絡(luò)功能所匹配的服務(wù)器集合S i（i表示SFC的虛擬網(wǎng)絡(luò)能的序號）。用Tde_min（）表示源點S到節(jié)點的最優(yōu)服務(wù)時延，則有如下狀態(tài)轉(zhuǎn)移方程：

算法3：DI-MCMF算法

輸入：待映射服務(wù)功能鏈C k，已有SFC的物理網(wǎng)絡(luò)G。

輸出：C k映射方案。

1.nfv_num←SFC虛擬網(wǎng)絡(luò)功能個數(shù)；

vm_num←切片網(wǎng)絡(luò)中虛擬機個數(shù)。

2.for i←0 to nfv_num do

3. for j←0 to vm_num do

4. 將服務(wù)功能鏈C k上VNF匹配虛擬機編號記錄到Store_num中

5. //Store_num表示二維數(shù)組，將C k上VNF匹配的虛擬機進行編號

6. end for

7.end for

8.size←store_ser_num.size（）-2

9.for i←size 0 to 0 do

10.nextPos//一維數(shù)組，記錄距離目的節(jié)點T最小服務(wù)時延的鄰接的node

11.nextPos［T］=NO-NEXT;

//NO-NEXT表示沒有下一個節(jié)點

12.dist［T］=0;//dist表示一維數(shù)組，記錄該pos到目的節(jié)點T的服務(wù)時延

13. for j←0 to store_ser_num［i］.size（）do

14. nowpos←store_ser_num［i］［i］;

15. dist［nowpos］=INT_MAX;

16. for m←0 to Store_num［i+1］.size（）

17. last SegNodePos←Store_num［i+1］［m］;

18. 計算dist［nowpos］最小時延，記錄next Pos［nowpos］最小時延節(jié)點//該過程需利用虛擬鏈路映射算法計算傳輸時延

19. end for

20. end for

21.end for

22.nextPos為C k上VNF映射的虛擬機，虛擬鏈路利用虛擬鏈路映射算法映射，輸出映射方案

4 仿真實驗

為了驗證算法的性能，本文的仿真實驗平臺是Visual Studio 2017，硬件配置為Intel Core i7-8550 CPU、16GB RAM的計算機。實驗采用的經(jīng)典EURO網(wǎng)絡(luò)撲圖［10］。總計為28個節(jié)點，其中部分帶有灰色填充的節(jié)點表示帶有物理計算服務(wù)器的節(jié)點，總數(shù)為6個，且每臺物理服務(wù)器上擁有3個虛擬機，剩余的為普通的路由節(jié)點。物理網(wǎng)絡(luò)中相連的節(jié)點之間均為全雙工鏈路，鏈路帶寬為1 Gbps。每條服務(wù)功能鏈隨機生成U（5,8）個虛擬網(wǎng)絡(luò)功能，虛擬鏈路的帶寬由均勻分布U（3,7）Mbps生成。

為了驗證本章提出的DI-MCMF算法有效性，是在切片網(wǎng)絡(luò)中已有服務(wù)功能鏈映射到物理網(wǎng)絡(luò)中，通過對新的服務(wù)功能鏈映射后，切片網(wǎng)絡(luò)中服務(wù)功能鏈的平均服務(wù)時延和映射新的服務(wù)功能鏈算法運行時間進行評估，并與PSO-MCMF和GA-MCMF算法進行對比。新映射服務(wù)功能鏈后切片網(wǎng)路中SFC平均服務(wù)時延如圖5所示。

圖5 映射不同SFC數(shù)目后平均服務(wù)時延

算法DI-MCMF是當(dāng)物理網(wǎng)絡(luò)上虛擬機已部署網(wǎng)絡(luò)功能后，添加新服務(wù)功能鏈。當(dāng)需要添加新服務(wù)功能鏈到物理網(wǎng)絡(luò)上時不會影響到原本已經(jīng)成功映射的服務(wù)功能鏈。通過PSO-MCMF和GA-MCMF算法在物理網(wǎng)絡(luò)對新映射服務(wù)功能鏈時，需要將原先的服務(wù)功能鏈和新增的服務(wù)功能鏈組合成一個服務(wù)功能鏈集合后，再利用各自算法進行映射。PSO-MCMF和GA-MCMF算法都會影響原本服務(wù)功能鏈的正常服務(wù)。圖5顯示的是三種算法在新增服務(wù)功能鏈后，物理網(wǎng)絡(luò)上服務(wù)功能鏈的平均服務(wù)時延。從圖5可以看出，通過DI-MCMF算法與PSO-MCMF算法映射的服務(wù)功能鏈的平均服務(wù)時延基本處于重疊，低于PSOMCMF算法的平均服務(wù)時延。所以通過DI-MCMF算法能夠為新增的服務(wù)功能鏈匹配到較好的映射方案。

添加不同數(shù)目的SFC三種算法運行的時間，如圖6所示。隨著SFC數(shù)目的增加，DI-MCMF算法運行時間均低于PSO-MCMF和GA-MCMF算法運行時間，DI-MCMF算法對SFC映射效率更高。

圖6 映射SFC不同算法運行時間

5 結(jié)語

本文研究了核心網(wǎng)絡(luò)切片中服務(wù)功能鏈映射問題，對問題進行了數(shù)學(xué)建模，提出了利用動態(tài)規(guī)劃尋找最短服務(wù)時延算法對服務(wù)功能鏈的虛擬網(wǎng)絡(luò)功能映射最優(yōu)的虛擬機，利用最小費用最大流算法獲得虛擬鏈路映射方案，從而對服務(wù)功能鏈進行映射。通過實驗對比分析，該方法映射效率得到提高，同時不會影響到切片網(wǎng)絡(luò)中其他SFC的正常運行。