一種基于業(yè)務(wù)感知和可調(diào)節(jié)跳數(shù)的虛擬化層構(gòu)建算法

馬 丁， 費 選， 慕小武

(1.河南工業(yè)大學(xué) 人工智能與大數(shù)據(jù)學(xué)院，河南 鄭州 450001； 2.鄭州大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，河南 鄭州 450001)

0 引言

近年來，隨著網(wǎng)絡(luò)流量的迅速增長，多樣化應(yīng)用的不斷涌現(xiàn)，傳統(tǒng)中間盒(middlebox)的設(shè)備架構(gòu)已經(jīng)難以滿足現(xiàn)有的需求，網(wǎng)絡(luò)功能虛擬化(network function virtualization, NFV)正是在此背景下應(yīng)運而生[1-2]。VNF(virtual network function)將網(wǎng)絡(luò)功能與物理設(shè)備解耦，然后將網(wǎng)絡(luò)功能軟件化，抽象為虛擬網(wǎng)絡(luò)功能。VNF可以部署在通用x86平臺上，極大增加了核心網(wǎng)絡(luò)的靈活性和可擴展性，降低了網(wǎng)絡(luò)企業(yè)的硬件投資成本和運維成本[3-4]。

為了滿足業(yè)務(wù)的需求，網(wǎng)絡(luò)數(shù)據(jù)流從源端系統(tǒng)到目的端系統(tǒng)通常需要以特定的順序依次經(jīng)過一系列VNFs。其中，通過特定順序鏈接起來的VNFs邏輯序列被稱為服務(wù)功能鏈(service function chain, SFC)。目前，針對SFC映射的研究較多集中在5G、互聯(lián)網(wǎng)、光網(wǎng)絡(luò)等多樣化網(wǎng)絡(luò)場景中VNF實例(virtual network function instance，VNFI)的部署與映射。其中，Sahhaf等[5]將高層VNF分解為多個子圖，通過分組和建立集群的方式進行映射，提高了資源利用率，降低了開銷。胡宇翔等[6]針對已有研究未考慮具有高性能數(shù)據(jù)處理需求的服務(wù)鏈VNF部署問題，提出一種支持硬件加速的VNF部署模型。Ye等[7]基于5G網(wǎng)絡(luò)背景，提出了一種面向多路數(shù)據(jù)流SFC映射的端到端數(shù)據(jù)包時延模型。Cao等[8]針對虛擬網(wǎng)服務(wù)提供中的資源利用率問題，提出了一種動態(tài)VNF的映射和調(diào)度方法。Pei等[9]針對云系統(tǒng)地理位置分散的特點，對動態(tài)VNF放置以及SFC的映射問題進行了研究。Abujoda等[10]提出了一個分布式的SFC映射框架，使不同提供商既能夠合作完成映射，又能夠維持各自的隱私和自治。Hu等[11]從網(wǎng)絡(luò)安全的角度出發(fā)，通過SFC的柔性組合，構(gòu)建安全保證的端到端路徑。Fu等[12]針對動態(tài)、復(fù)雜的物聯(lián)網(wǎng)環(huán)境，提出一種基于深度學(xué)習(xí)方法的SFC映射機制。Sun等[13]針對能量感知的在線SFC映射方法展開了研究。

然而，上述研究均未涉及中間虛擬化層的構(gòu)建細(xì)節(jié)。本文嘗試對NFV環(huán)境下的虛擬化層構(gòu)建方法進行研究，探究面向業(yè)務(wù)感知的節(jié)點集合構(gòu)建方法和高性能低開銷的鏈路集合構(gòu)建方法。并通過分層圖算法對所構(gòu)建的虛擬化層的服務(wù)提供能力進行了模擬仿真。

1 問題模型與描述

1.1 虛擬化層

網(wǎng)絡(luò)拓?fù)涞某橄髮τ谟行У剡M行SFC映射是至關(guān)重要的[10]。例如，網(wǎng)絡(luò)功能提供商(network function provider，NFP)的信息發(fā)布策略是不同的：互聯(lián)網(wǎng)服務(wù)提供商(internet service provider,ISP)通常發(fā)布簡化的PoP(point of pre-sence)級別的拓?fù)鋄14]；云服務(wù)提供商(如亞馬遜)可以跨越不同區(qū)域廣告其所能夠提供的資源。對網(wǎng)絡(luò)拓?fù)涞某橄罂梢噪[藏NFPs認(rèn)為是機密的信息。

虛擬化層(virtualization layer，VL)是對底層物理網(wǎng)絡(luò)拓?fù)涞某橄?，是介于物理網(wǎng)絡(luò)與SFC之間的中間層，如圖1所示。建立VL需要對SFC請求的業(yè)務(wù)類型進行感知，對網(wǎng)絡(luò)拓?fù)溥M行抽象，構(gòu)建業(yè)務(wù)一致性視圖，隱藏業(yè)務(wù)無關(guān)細(xì)節(jié)，隱藏NFPs的隱私信息。

SFC請求在虛擬化層進行映射的過程分為兩個階段，如圖1所示，其中，彩色的橢圓表示NFP部署的VNF，白色圓圈表示PoP。

(1)分析SFC請求的業(yè)務(wù)類型，選擇匹配該類業(yè)務(wù)的VL；

(2)根據(jù)SFC請求，選擇SFC映射算法在VL上進行VNF和邏輯鏈路的映射，構(gòu)建源端系統(tǒng)到目的端系統(tǒng)的服務(wù)路徑，如圖1中的紅色箭頭線段序列所示。

圖1 基于虛擬化層的SFC映射Figure 1 Virtualization layer based SFC mapping

1.2 問題描述

1.2.1 物理網(wǎng)絡(luò)

物理網(wǎng)絡(luò)拓?fù)淇梢杂脦?quán)無向圖表示，標(biāo)記為G=(N,L)，其中N和L分別表示物理網(wǎng)絡(luò)節(jié)點和鏈路的集合。VNFI可以部署在物理網(wǎng)絡(luò)的任意功能節(jié)點上。功能節(jié)點n(n∈N)的CPU容量(CPU capacity) 標(biāo)記為C(n)；該節(jié)點上部署的VNFI集合標(biāo)記為S(n)={Sk|節(jié)點n部署有VNFISk}，如果S(n)≠?，該節(jié)點為功能節(jié)點，否則為交換節(jié)點，只進行數(shù)據(jù)包的轉(zhuǎn)發(fā)。物理鏈路l(l∈L)的帶寬標(biāo)記為B(l)。表示物理網(wǎng)絡(luò)無環(huán)路徑的集合，ni,nj∈N之間的無環(huán)路徑集合標(biāo)記為(ni,nj)，P∈表示物理網(wǎng)絡(luò)中的一條無環(huán)路徑，H(P)表示路徑P的跳數(shù)(hop count)，即長度。

1.2.2 服務(wù)功能鏈請求

服務(wù)功能鏈請求(service function chain request，SFCR)可以使用帶權(quán)有向圖表示，標(biāo)記為GR=(NR,LR)，其中，NR和LR分別表示邏輯節(jié)點和邏輯鏈路的集合。邏輯節(jié)點nR(nR∈NR)的VNF需求標(biāo)記為S(nR)，CPU資源需求標(biāo)記為μ(S(nR))，邏輯鏈路lR(lR∈LR)的帶寬需求標(biāo)記為μ(lR)。

1.2.3 虛擬化層

VL的拓?fù)湟部梢杂脦?quán)無向圖表示，標(biāo)記為GV=(NV,LV)，其中NV和LV分別表示VL的節(jié)點集合和鏈路集合。

VL的構(gòu)建問題定義：根據(jù)SFCR中的VNF需求，建立從GV到G的子集Gf=(Nf,f) 的映射：

(1)

整個構(gòu)建過程包括節(jié)點集合NV的構(gòu)建與鏈路集合LV的構(gòu)建。

(1)節(jié)點集合構(gòu)建。首先需要分析業(yè)務(wù)的VNF需求，將已部署相應(yīng)VNF的功能節(jié)點集合Nf作為VL的候選節(jié)點集合，建立物理功能節(jié)點與VL節(jié)點之間的映射：

(2)

如果M′N(nV)=M′N(mV), 當(dāng)且僅當(dāng)nV=mV,即不同的VL節(jié)點不能由相同的功能節(jié)點映射。

同時建立NV與Nf之間的逆映射：

(3)

如果M′N(n)=M′N(m), 當(dāng)且僅當(dāng)n=m, 即每個功能節(jié)點只能托管一個VL節(jié)點，即NV和Nf是一對一映射。

映射完成之后，VL的節(jié)點集合構(gòu)建完成。

(2)鏈路集合構(gòu)建。VL節(jié)點之間的鏈路構(gòu)建可以采用節(jié)點間最短路徑的構(gòu)建方法，即計算?nV,mV∈NV,MN(nV)與MN(mV)之間的最短路徑，然后再將VL鏈路(nV,mV)映射其上，建立鏈路映射ML：

ML(nV,mV)?f(MN(nV)，MN(mV))。

(4)

映射完成之后，VL的鏈路集合構(gòu)建完成。

(3)構(gòu)建開銷。VL的構(gòu)建開銷C(GV)包括構(gòu)建節(jié)點集合NV所需要的CPU資源開銷和構(gòu)建鏈路集合所需要的帶寬資源開銷，定義如下：

(5)

式中：C(nV)是映射VL節(jié)點所分配的CPU資源；B(lV)是映射VL鏈路所分配的帶寬資源。

VL構(gòu)建的目標(biāo)是在保證SFC承載能力的基礎(chǔ)上最小化構(gòu)建開銷C(GV)。

2 虛擬化層構(gòu)建算法

在1.2節(jié)描述問題的同時給出了構(gòu)建節(jié)點集合與鏈路集合的基本思路。首先在節(jié)點映射時考慮了SFCR的VNF需求，因此映射完畢后所有與該類業(yè)務(wù)無關(guān)的VNF不再出現(xiàn)在VL中，實現(xiàn)了業(yè)務(wù)感知。但是，在鏈路映射后構(gòu)建出的VL拓?fù)涫峭耆珗D，冗余鏈路過多，由式(5)可知，鏈路數(shù)量越多，帶寬開銷越大，因此必須要進行冗余鏈路的識別與消除。而鏈路數(shù)量與VL的服務(wù)提供能力是成正比的，因此在進一步優(yōu)化鏈路數(shù)量、減少帶寬開銷的同時，需要保證SFC請求的映射性能。

2.1 定義冗余鏈路

在該鏈路所映射的物理路徑中，至少存在一條物理鏈路，使該物理鏈路的兩個頂點逆映射后為VL的已有頂點。

?nV,mV∈NV,MN(nV)與MN(mV)之間的最短路徑記為Pshortest(MN(nV),MN(mV))，(nV,mV)為冗余鏈路，需要同時滿足條件：

(1)H(Pshortest(MN(nV),MN(mV)))>1；

(2)?(nij,nij+1)∈Pshortest(MN(nV),MN(mV))，?nix,nix+1,M′N(nix),M′N(nix+1) ∈NV。

2.2 面向業(yè)務(wù)感知和可調(diào)節(jié)跳數(shù)的構(gòu)建算法

本文提出一種可調(diào)節(jié)跳數(shù)的非冗余鏈路映射方法(non-redundant link mapping method with adjustable hop count，NRLMAH))。首先，在映射鏈路時，選擇相應(yīng)功能節(jié)點之間有效路徑長度在跳數(shù)約束內(nèi)且無冗余的鏈路。其次，由低至高調(diào)整候選路徑的跳數(shù)約束，隨著跳數(shù)增加，VL的鏈路數(shù)量增加，服務(wù)提供能力增加，開銷也隨之增加，當(dāng)跳數(shù)約束達(dá)到閾值時，繼續(xù)增加跳數(shù)，開銷繼續(xù)增加，但服務(wù)提供能力趨于穩(wěn)定。

整合面向業(yè)務(wù)感知的節(jié)點映射方法和NRLMAH，提出一種面向業(yè)務(wù)感知和可調(diào)節(jié)跳數(shù)的VL構(gòu)建算法(visualization layer constructing algorithm based on VNF-aware and adjustable hop count, VLC-VAAH)如下。

算法1VLC-VAAH。

輸入：物理網(wǎng)絡(luò)拓?fù)銰=(N,L)，SFCRGR=(NR,LR)，跳數(shù)約束hop；

輸出：VL拓?fù)銰V=(NV,LV)，映射結(jié)果MN和ML。

①foralln∈Ndo

②if節(jié)點n部署有SFCR所需的VNFI

③ 創(chuàng)建節(jié)點nV∈NV；

④ 創(chuàng)建節(jié)點nV與節(jié)點n之間的映射

MN(nV)及逆映射M′N(n)；

⑤elseif

⑥ 將n納入非候選功能節(jié)點集合Q；

⑦endif

⑧endfor//節(jié)點映射結(jié)束

⑨forallnV∈NV

⑩ 以MN(nV)為根，不斷添加節(jié)點n，建立高度為hop+1的BFS樹T(MN(nV))。為確保無冗余鏈路，需進行以下處理：

當(dāng)n?Q&&M′N(n)≠nV，將n添加為樹的葉子節(jié)點；如果n∈Q，則以n為子樹的根繼續(xù)生成BFS樹；

ML(nV,M′N(nleaf))={P(MN(nV),nleaf)}；

在算法VLC-VAAH中，VL的節(jié)點數(shù)量為|NV|，在物理網(wǎng)絡(luò)構(gòu)建BFS樹的時間復(fù)雜度為O(|N|+|L|)，因此VLC-VAAH算法的時間復(fù)雜度為O(|NV|(|N|+|L|))。

3 實驗及分析

本文使用所提出的虛擬化層構(gòu)建算法建立跳數(shù)約束為2、3、4、5的虛擬服務(wù)層，并在其上分別運行分層圖算法[15]映射SFC請求，滿足最小化時延的需求。通過服務(wù)請求接受率、收益、開銷、收益開銷比[16]等性能指標(biāo)對虛擬層服務(wù)提供能力進行仿真實驗研究。

3.1 仿真環(huán)境設(shè)置

物理網(wǎng)絡(luò)拓?fù)淅肎T-ITM隨機生成，包含50個節(jié)點和約123條鏈路。節(jié)點CPU容量和鏈路帶寬容量在[2 500,5 000]區(qū)間均勻分布，每個節(jié)點可以部署1～5個VNF。根據(jù)文獻(xiàn)[5]，將VNF的執(zhí)行時延和鏈路傳輸時延的設(shè)定在[1,10]區(qū)間，VL節(jié)點與鏈路的資源分配系數(shù)設(shè)定為0.2，因此VL的節(jié)點CPU容量和鏈路帶寬容量在[50,100]區(qū)間均勻分布。

SFC請求需求的VNF數(shù)量設(shè)定為3，類型隨機選擇，其中每個VNF的計算資源需求在[1,25]區(qū)間均勻分布，VNF之間的鏈路帶寬需求在[1,50]區(qū)間均勻分布。SFC請求的到達(dá)時間服從泊松分布，平均100個時間單位內(nèi)到達(dá)5個，每個請求的服務(wù)時間服從平均1 000個時間單位的指數(shù)分布。每次仿真的時間約為50 000個時間單位，從0開始每間隔2 000個時間單位采集一次數(shù)據(jù)。

3.2 仿真結(jié)果分析

圖2表明，當(dāng)跳數(shù)約束等于3、4、5時，平均請求接受率較為接近，但與跳數(shù)約束為2相比，至少提高了15%。圖3和圖4表明，當(dāng)跳數(shù)約束等于3、4、5時，長期平均收益和開銷也非常接近，比跳數(shù)為2時分別至少提高33%和19%。進一步從圖5中可以看出，與跳數(shù)為2時相比，跳數(shù)等于3、4、5時的長期收益開銷比分別提高了12%、13.5%和15.5%。分析其原因，當(dāng)跳數(shù)為2時，鏈路數(shù)量過少，難以建立有效的鏈路映射，請求接受率較低，收益開銷比較低。當(dāng)跳數(shù)約束提高為3時，鏈路數(shù)量增加，可映射路徑選擇增多，服務(wù)提供能力提升，各項指標(biāo)均得到大幅提升。當(dāng)繼續(xù)增加跳數(shù)約束值時，VL構(gòu)建開銷持續(xù)增加，與跳數(shù)為3時相比，跳數(shù)為4和5的構(gòu)建開銷分別增加約27%和52%，如表1所示。然而性能提升卻趨于平緩，例如，與跳數(shù)為3時相比，跳數(shù)為4和5的平均請求接受率，分別增加約0.7%和1.2%，其他指標(biāo)的增加與之類似。仿真結(jié)果表明，VLC-VAAH算法是有效的，能夠在特定規(guī)模的物理網(wǎng)絡(luò)上構(gòu)建性價比最優(yōu)的VL。

圖2 SFC平均請求接受率比較Figure 2 Comparison of average request acceptance ratio

圖3 長期平均收益比較Figure 3 Comparison of long-term average revenue

圖4 長期平均開銷比較Figure 4 Comparison of long-term average cost

圖5 長期平均收益開銷比比較Figure 5 Comparison of long-term revenue/cost ratio

表1 VL構(gòu)建開銷對比Table 1 Comparison of cost of VL

4 結(jié)論

(1)在物理網(wǎng)絡(luò)與SFC請求之間構(gòu)建VL可以生成業(yè)務(wù)一致性視圖，屏蔽底層無關(guān)細(xì)節(jié)，隱藏NFPs的隱私信息。

(2)可調(diào)節(jié)跳數(shù)的非冗余鏈路映射方法能夠有效地消除VL上的冗余鏈路，同時能夠通過跳數(shù)的調(diào)節(jié)有效地均衡VL的構(gòu)建開銷與服務(wù)提供能力。

(3)所提出VLC-VAAH算法是有效的，能夠在特定規(guī)模的物理網(wǎng)絡(luò)上構(gòu)建性價比最優(yōu)的VL，所構(gòu)建的VL能夠有效地進行SFC映射。

(4)如何針對5G網(wǎng)絡(luò)的不同應(yīng)用場景構(gòu)建特定的VL，并進行跨域的資源編排是下一階段研究的問題。