馬 丁, 費 選, 慕小武
(1.河南工業(yè)大學(xué) 人工智能與大數(shù)據(jù)學(xué)院,河南 鄭州 450001; 2.鄭州大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院,河南 鄭州 450001)
近年來,隨著網(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ù)提供能力進行了模擬仿真。
網(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 物理網(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)。
在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請求的映射性能。
在該鏈路所映射的物理路徑中,至少存在一條物理鏈路,使該物理鏈路的兩個頂點逆映射后為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。
本文提出一種可調(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|))。
本文使用所提出的虛擬化層構(gòu)建算法建立跳數(shù)約束為2、3、4、5的虛擬服務(wù)層,并在其上分別運行分層圖算法[15]映射SFC請求,滿足最小化時延的需求。通過服務(wù)請求接受率、收益、開銷、收益開銷比[16]等性能指標(biāo)對虛擬層服務(wù)提供能力進行仿真實驗研究。
物理網(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ù)。
圖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
(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,并進行跨域的資源編排是下一階段研究的問題。