袁紹露,張向利
(桂林電子科技大學(xué)廣西無線寬帶通信與信號處理重點實驗室,桂林 541004)
隨著數(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è)備和線路修補(bǔ)式的解決網(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)與昂貴的專用硬件資源進(jì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ù)請求進(jìn)行差異化服務(wù)的前提。關(guān)于服務(wù)功能鏈映射問題的研究。文獻(xiàn)[5]將用戶服務(wù)請求構(gòu)建成SFC后,對SFC映射問題轉(zhuǎn)成類似于VNE問題,其兩者的差別在于約束條件和優(yōu)化目標(biāo)不同。文獻(xiàn)[6]是在虛擬機(jī)上尚未部署網(wǎng)絡(luò)功能情況下對SFC進(jìn)行映射,將問題分成網(wǎng)絡(luò)功能部署和SFC調(diào)度兩個子問題,以網(wǎng)絡(luò)切片中服務(wù)功能鏈的最小服務(wù)時延為優(yōu)化目標(biāo),并通過粒子群算法對目標(biāo)進(jìn)行優(yōu)化。文獻(xiàn)[7]提出基于馬爾科夫模型的SAMA啟發(fā)式算法,通過計算虛擬機(jī)優(yōu)先接收優(yōu)先級高的SFC進(jìn)行映射,降低搜索空間,從而提高映射效率。
SFC映射被證明是NP難問題[8],當(dāng)前研究方法采用較多的是啟發(fā)式算法。當(dāng)SFC數(shù)目較多時,利用啟發(fā)式算法對多目標(biāo)求解具有快速求解的優(yōu)勢,但實際網(wǎng)絡(luò)環(huán)境中存在需要映射SFC數(shù)目較少情況,如果繼續(xù)利用基于啟發(fā)式的算法,存在優(yōu)化時間較長的問題。因此,本文提出一種SFC映射算法(DI-MCMF),即將該問題分成VNF映射和虛擬鏈路映射物理鏈路兩個子問題,首先分別找出VNF匹配的虛擬機(jī),然后通過動態(tài)規(guī)劃有向無環(huán)低時延算法獲得VNF映射方案;再采用最小費用最大流算法獲得虛擬鏈路映射方案。
一個核心切片網(wǎng)絡(luò)可以根據(jù)不同用戶需求為其提供差異化網(wǎng)絡(luò)服務(wù),這些網(wǎng)路服務(wù)可以用服務(wù)功能鏈(SFC)進(jìn)行表示。服務(wù)功能鏈上VNF的服務(wù)是由切片網(wǎng)絡(luò)中服務(wù)器上的虛擬機(jī)所部署的網(wǎng)絡(luò)功能來提供。由于虛擬機(jī)的資源是有限的,因此在實際網(wǎng)絡(luò)環(huán)境中不同服務(wù)功能鏈上相同的虛擬網(wǎng)絡(luò)功能需要共享某個虛擬機(jī)上的網(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的虛擬機(jī)。在采用VNF技術(shù)的網(wǎng)絡(luò)環(huán)境下,通過在服務(wù)器的虛擬機(jī)上部署網(wǎng)絡(luò)功能作為虛擬網(wǎng)絡(luò)功能設(shè)備來提供該功能的網(wǎng)絡(luò)服務(wù)。為了進(jìn)一步提高資源的利用率,不僅讓某個虛擬網(wǎng)絡(luò)功能設(shè)備可以被不同的服務(wù)功能鏈中同類型的VNF共享使用,而且可以在服務(wù)器上配置多個虛擬機(jī)以提供更多的網(wǎng)絡(luò)服務(wù)。如圖1中服務(wù)器1上兩個虛擬機(jī)分別部署了網(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上進(jìn)行信息的處理。單個服務(wù)功能鏈中各虛擬網(wǎng)絡(luò)功能會調(diào)度到不同服務(wù)器上具備該類型的虛擬機(jī)來處理,并且各個虛擬網(wǎng)絡(luò)功能之間的虛擬鏈路可以由多條物理鏈進(jìn)行數(shù)據(jù)流的傳輸。
本文研究的是服務(wù)功能鏈映射問題,是指在切片網(wǎng)絡(luò)中為虛擬機(jī)分配了資源并且虛擬機(jī)上已經(jīng)部署了相應(yīng)的網(wǎng)路功能的情況下,將服務(wù)功能鏈上虛擬網(wǎng)絡(luò)功能調(diào)度到各自匹配的虛擬機(jī)上處理數(shù)據(jù)流,還需要解決服務(wù)功能鏈上虛擬鏈路分配哪些物理鏈路進(jìn)行信息的傳遞。如圖2所示。
圖2 服務(wù)功能鏈調(diào)度
在圖2中,切片網(wǎng)絡(luò)中各服務(wù)器上的虛擬機(jī)已經(jīng)部署相應(yīng)的網(wǎng)絡(luò)功能。在對SFC1功能鏈進(jìn)行映射時會存在多種映射方案。方案Ⅰ的部署方式為先從服務(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算法來解決上述問題。
數(shù)學(xué)模型使用的符號及其物理意義如表1所示。
表1 數(shù)學(xué)模型中的符號及其物理意義
在本文中使用一個加權(quán)無向圖G=(N,E)對物理傳輸網(wǎng)絡(luò)進(jìn)行表示。將物理服務(wù)器與物理交換節(jié)點視為一個節(jié)點,每個服務(wù)器上可部署V S個虛擬機(jī),每個虛擬機(jī)部署一個網(wǎng)絡(luò)功能。根據(jù)用戶的服務(wù)需求構(gòu)建成相應(yīng)的SFC,服務(wù)功能鏈上不同的虛擬網(wǎng)絡(luò)功能處理單個數(shù)據(jù)流時延不同,相同的虛擬網(wǎng)絡(luò)功能處理單個數(shù)據(jù)流時延相同。
2.2.1 服務(wù)器上部署虛擬網(wǎng)絡(luò)功能約束條件
在本文中一個服務(wù)器可以虛擬化出多個網(wǎng)絡(luò)功能,每個服務(wù)器上有多個虛擬機(jī),每個虛擬機(jī)上部署一個虛擬網(wǎng)絡(luò)功能。使用表示網(wǎng)絡(luò)功能F d是否部署到第n個服務(wù)器的第m個虛擬機(jī)上,則:
2.2.2 SFC中VNF離線匹配的約束條件
通過映射算法將集合C中SFC上的虛擬網(wǎng)絡(luò)功能映射虛擬機(jī)上,當(dāng)虛擬機(jī)上部署的網(wǎng)絡(luò)功能與的功能相同,或者上還沒有部署網(wǎng)絡(luò)功能。使用表示第k個服務(wù)功能鏈的第h虛擬網(wǎng)絡(luò)功能映射到第n個服務(wù)器上的第m個虛擬機(jī),并且SFC上的網(wǎng)絡(luò)功能只能映射到一個虛擬機(jī)上,則:
網(wǎng)絡(luò)功能對業(yè)務(wù)處理能力是有限的,一個虛擬機(jī)上的網(wǎng)絡(luò)功能對映射到該虛擬機(jī)的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表示,則:
服務(wù)功能鏈的服務(wù)時延由兩部分構(gòu)成,分別為服務(wù)功能鏈各虛擬網(wǎng)絡(luò)功能在所映射虛擬機(jī)上處理時延和服務(wù)功能鏈在物理網(wǎng)絡(luò)上傳輸時延τC K。處理時延由網(wǎng)絡(luò)功能所需的計算量與該功能所映射物理網(wǎng)絡(luò)上服務(wù)器的計算速度來表示,每條服務(wù)功能鏈上所有虛擬網(wǎng)絡(luò)功能處理時延用進(jìn)行表示,則:
使用Ttotal表示服務(wù)功能鏈集合C服務(wù)時延之和,則有:
本文提出的服務(wù)功能鏈映射DI-MCMF算法分成SFC上虛擬網(wǎng)絡(luò)功能映射虛擬機(jī)和虛擬鏈路映射物理鏈路兩個部分。
當(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)化為最小時延最大帶寬問題。在對虛擬鏈路進(jìn)行映射的時候,先找出最小時延時路徑,即在物理網(wǎng)絡(luò)上尋找兩個VNF映射節(jié)點間以時延為權(quán)值的最短路徑,然后沿著最小時延路增加帶寬,直到滿足SFC虛擬鏈路的帶寬需求,虛擬鏈路映射算法步驟如下:
(1)在物理網(wǎng)絡(luò)拓?fù)渖戏謩e增加一個虛擬發(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 (帶寬、時延)拓?fù)鋱D
(2)新建路徑集合P,并賦初始值為空;新建S節(jié)點到R節(jié)點帶寬f,并賦初始值為0。
(3)用Dijkstra求解節(jié)點S到節(jié)點R之間的最小時延有向路徑a,在路徑上的可用帶寬為b。
7.學(xué)習(xí)成功后點擊“確定”進(jìn)行第二把的匹配(哈佛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。否則映射失敗。
服務(wù)功能鏈中VNF映射到最優(yōu)位置上的虛擬機(jī)問題類似于動態(tài)規(guī)劃有向無環(huán)最短路徑問題,如圖4所示。
圖4 VNF所匹配的虛擬機(jī)
當(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)化目標(biāo)是服務(wù)時延,因此將問題轉(zhuǎn)變成動態(tài)規(guī)劃有向無循環(huán)低時延問題。首先對圖GG進(jìn)行分段,每一層的各個節(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ò)中虛擬機(jī)個數(shù)。
2.for i←0 to nfv_num do
3. for j←0 to vm_num do
4. 將服務(wù)功能鏈C k上VNF匹配虛擬機(jī)編號記錄到Store_num中
5. //Store_num表示二維數(shù)組,將C k上VNF匹配的虛擬機(jī)進(jìn)行編號
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映射的虛擬機(jī),虛擬鏈路利用虛擬鏈路映射算法映射,輸出映射方案
為了驗證算法的性能,本文的仿真實驗平臺是Visual Studio 2017,硬件配置為Intel Core i7-8550 CPU、16GB RAM的計算機(jī)。實驗采用的經(jīng)典EURO網(wǎng)絡(luò)撲圖[10]??傆嫗?8個節(jié)點,其中部分帶有灰色填充的節(jié)點表示帶有物理計算服務(wù)器的節(jié)點,總數(shù)為6個,且每臺物理服務(wù)器上擁有3個虛擬機(jī),剩余的為普通的路由節(jié)點。物理網(wǎng)絡(luò)中相連的節(jié)點之間均為全雙工鏈路,鏈路帶寬為1 Gbps。每條服務(wù)功能鏈隨機(jī)生成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ù)功能鏈算法運行時間進(jìn)行評估,并與PSO-MCMF和GA-MCMF算法進(jìn)行對比。新映射服務(wù)功能鏈后切片網(wǎng)路中SFC平均服務(wù)時延如圖5所示。
圖5 映射不同SFC數(shù)目后平均服務(wù)時延
算法DI-MCMF是當(dāng)物理網(wǎng)絡(luò)上虛擬機(jī)已部署網(wǎng)絡(luò)功能后,添加新服務(wù)功能鏈。當(dāng)需要添加新服務(wù)功能鏈到物理網(wǎng)絡(luò)上時不會影響到原本已經(jīng)成功映射的服務(wù)功能鏈。通過PSO-MCMF和GA-MCMF算法在物理網(wǎng)絡(luò)對新映射服務(wù)功能鏈時,需要將原先的服務(wù)功能鏈和新增的服務(wù)功能鏈組合成一個服務(wù)功能鏈集合后,再利用各自算法進(jìn)行映射。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不同算法運行時間
本文研究了核心網(wǎng)絡(luò)切片中服務(wù)功能鏈映射問題,對問題進(jìn)行了數(shù)學(xué)建模,提出了利用動態(tài)規(guī)劃尋找最短服務(wù)時延算法對服務(wù)功能鏈的虛擬網(wǎng)絡(luò)功能映射最優(yōu)的虛擬機(jī),利用最小費用最大流算法獲得虛擬鏈路映射方案,從而對服務(wù)功能鏈進(jìn)行映射。通過實驗對比分析,該方法映射效率得到提高,同時不會影響到切片網(wǎng)絡(luò)中其他SFC的正常運行。