馬 丁， 費 選， 慕小武

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

0 引言

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

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

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

1 問題模型與描述

1.1 虛擬化層

網絡拓撲的抽象對于有效地進行SFC映射是至關重要的[10]。例如，網絡功能提供商(network function provider，NFP)的信息發(fā)布策略是不同的：互聯(lián)網服務提供商(internet service provider,ISP)通常發(fā)布簡化的PoP(point of pre-sence)級別的拓撲[14]；云服務提供商(如亞馬遜)可以跨越不同區(qū)域廣告其所能夠提供的資源。對網絡拓撲的抽象可以隱藏NFPs認為是機密的信息。

虛擬化層(virtualization layer，VL)是對底層物理網絡拓撲的抽象，是介于物理網絡與SFC之間的中間層，如圖1所示。建立VL需要對SFC請求的業(yè)務類型進行感知，對網絡拓撲進行抽象，構建業(yè)務一致性視圖，隱藏業(yè)務無關細節(jié)，隱藏NFPs的隱私信息。

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

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

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

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

1.2 問題描述

1.2.1 物理網絡

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

1.2.2 服務功能鏈請求

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

1.2.3 虛擬化層

VL的拓撲也可以用帶權無向圖表示，標記為GV=(NV,LV)，其中NV和LV分別表示VL的節(jié)點集合和鏈路集合。

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

(1)

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

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

(2)

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

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

(3)

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

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

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

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

(4)

映射完成之后，VL的鏈路集合構建完成。

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

(5)

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

VL構建的目標是在保證SFC承載能力的基礎上最小化構建開銷C(GV)。

2 虛擬化層構建算法

在1.2節(jié)描述問題的同時給出了構建節(jié)點集合與鏈路集合的基本思路。首先在節(jié)點映射時考慮了SFCR的VNF需求，因此映射完畢后所有與該類業(yè)務無關的VNF不再出現(xiàn)在VL中，實現(xiàn)了業(yè)務感知。但是，在鏈路映射后構建出的VL拓撲是完全圖，冗余鏈路過多，由式(5)可知，鏈路數(shù)量越多，帶寬開銷越大，因此必須要進行冗余鏈路的識別與消除。而鏈路數(shù)量與VL的服務提供能力是成正比的，因此在進一步優(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è)務感知和可調節(jié)跳數(shù)的構建算法

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

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

算法1VLC-VAAH。

輸入：物理網絡拓撲G=(N,L)，SFCRGR=(NR,LR)，跳數(shù)約束hop；

輸出：VL拓撲GV=(NV,LV)，映射結果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é)點映射結束

⑨forallnV∈NV

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

當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|，在物理網絡構建BFS樹的時間復雜度為O(|N|+|L|)，因此VLC-VAAH算法的時間復雜度為O(|NV|(|N|+|L|))。

3 實驗及分析

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

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

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

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

3.2 仿真結果分析

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

4 結論

(1)在物理網絡與SFC請求之間構建VL可以生成業(yè)務一致性視圖，屏蔽底層無關細節(jié)，隱藏NFPs的隱私信息。

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

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

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