馬 丁， 費(fèi) 選， 慕小武

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

0 引言

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

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

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

1 問(wèn)題模型與描述

1.1 虛擬化層

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

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

SFC請(qǐng)求在虛擬化層進(jìn)行映射的過(guò)程分為兩個(gè)階段，如圖1所示，其中，彩色的橢圓表示NFP部署的VNF，白色圓圈表示PoP。

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

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

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

1.2 問(wèn)題描述

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

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

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

服務(wù)功能鏈請(qǐng)求(service function chain request，SFCR)可以使用帶權(quán)有向圖表示，標(biāo)記為GR=(NR,LR)，其中，NR和LR分別表示邏輯節(jié)點(diǎn)和邏輯鏈路的集合。邏輯節(jié)點(diǎn)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)無(wú)向圖表示，標(biāo)記為GV=(NV,LV)，其中NV和LV分別表示VL的節(jié)點(diǎn)集合和鏈路集合。

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

(1)

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

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

(2)

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

同時(shí)建立NV與Nf之間的逆映射：

(3)

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

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

(2)鏈路集合構(gòu)建。VL節(jié)點(diǎn)之間的鏈路構(gòu)建可以采用節(jié)點(diǎn)間最短路徑的構(gòu)建方法，即計(jì)算?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é)點(diǎn)集合NV所需要的CPU資源開銷和構(gòu)建鏈路集合所需要的帶寬資源開銷，定義如下：

(5)

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

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

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

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

2.1 定義冗余鏈路

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

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

(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))。首先，在映射鏈路時(shí)，選擇相應(yīng)功能節(jié)點(diǎn)之間有效路徑長(zhǎng)度在跳數(shù)約束內(nèi)且無(wú)冗余的鏈路。其次，由低至高調(diào)整候選路徑的跳數(shù)約束，隨著跳數(shù)增加，VL的鏈路數(shù)量增加，服務(wù)提供能力增加，開銷也隨之增加，當(dāng)跳數(shù)約束達(dá)到閾值時(shí)，繼續(xù)增加跳數(shù)，開銷繼續(xù)增加，但服務(wù)提供能力趨于穩(wěn)定。

整合面向業(yè)務(wù)感知的節(jié)點(diǎn)映射方法和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é)點(diǎn)n部署有SFCR所需的VNFI

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

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

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

⑤elseif

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

⑦endif

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

⑨forallnV∈NV

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

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

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

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

3 實(shí)驗(yàn)及分析

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

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

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

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

3.2 仿真結(jié)果分析

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

圖2 SFC平均請(qǐng)求接受率比較Figure 2 Comparison of average request acceptance ratio

圖3 長(zhǎng)期平均收益比較Figure 3 Comparison of long-term average revenue

圖4 長(zhǎng)期平均開銷比較Figure 4 Comparison of long-term average cost

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

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

4 結(jié)論

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

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

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

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