吳曉春，洪晨，張?jiān)?，張俊楠，周靜靜

基于微服務(wù)架構(gòu)的粒度可變服務(wù)功能鏈映射算法

吳曉春，洪晨，張?jiān)溃瑥埧￠?，周靜靜

（浙江工商大學(xué)信息與電子工程學(xué)院，浙江 杭州 310018）

針對(duì)5G環(huán)境下服務(wù)功能鏈（SFC）端到端時(shí)延無(wú)法滿足時(shí)延敏感型應(yīng)用需求的問(wèn)題，將傳統(tǒng)虛擬網(wǎng)絡(luò)功能（VNF）拆分成粒度不一的映射單元，提出了基于微服務(wù)架構(gòu)的粒度可變服務(wù)功能鏈映射（VG-SFCM）算法。首先將傳統(tǒng)粗粒度的VNF解耦成細(xì)粒度的微服務(wù)單元，隨后通過(guò)SFC內(nèi)冗余微服務(wù)單元的合并及SFC間微服務(wù)單元的復(fù)用，減少微服務(wù)單元的實(shí)例化，降低SFC的處理時(shí)間。仿真結(jié)果表明，所提算法在降低平均部署網(wǎng)絡(luò)成本的同時(shí)，其SFC端到端時(shí)延相較于傳統(tǒng)的映射算法降低了14.81%。

網(wǎng)絡(luò)功能虛擬化；微服務(wù)架構(gòu)；服務(wù)功能鏈；時(shí)延

0 引言

隨著互聯(lián)網(wǎng)的不斷普及和物聯(lián)網(wǎng)相關(guān)技術(shù)的飛速發(fā)展，人們對(duì)網(wǎng)絡(luò)的需求呈指數(shù)級(jí)增長(zhǎng)，各式各樣的服務(wù)請(qǐng)求日新月異。為了應(yīng)對(duì)不斷增長(zhǎng)且紛繁復(fù)雜的服務(wù)請(qǐng)求，網(wǎng)絡(luò)功能虛擬化（network function virtualization，NFV）技術(shù)應(yīng)運(yùn)而生。NFV通過(guò)虛擬化的技術(shù)將網(wǎng)絡(luò)功能以軟件化的形式呈現(xiàn)，形成虛擬網(wǎng)絡(luò)功能（virtualized network function，VNF），實(shí)現(xiàn)了網(wǎng)絡(luò)功能與專用物理設(shè)備的解耦，使資源可以靈活共享，并大大降低了運(yùn)營(yíng)商的運(yùn)營(yíng)成本（operating expense，OPEX）及資本支出（capital expenditure，CAPEX）[1]。不同的VNF按照一定邏輯順序進(jìn)行鏈接并形成服務(wù)功能鏈（service function chain，SFC）[2]。通過(guò)SFC，運(yùn)營(yíng)商可以更加快速且靈活地為用戶提供所需的服務(wù)，當(dāng)用戶的服務(wù)需求或網(wǎng)絡(luò)環(huán)境發(fā)生變化時(shí)也可快速進(jìn)行VNF的遷移、創(chuàng)建、銷毀等操作。

5G等技術(shù)的發(fā)展使許多應(yīng)用對(duì)時(shí)延的要求提高，因此，如何合理地部署VNF或?qū)FC本身進(jìn)行一定優(yōu)化，使得SFC端到端時(shí)延得到一定程度的降低是映射問(wèn)題的一大挑戰(zhàn)。目前，已有不少學(xué)者對(duì)SFC的映射及部署問(wèn)題展開(kāi)了研究。當(dāng)前該問(wèn)題通常被建模成整數(shù)線性規(guī)劃（integer linear programming，ILP）模型或混合整數(shù)線性規(guī)劃（mixed integer linear programming，MILP）模型等數(shù)學(xué)規(guī)劃模型。文獻(xiàn)[3]使用基于混合整數(shù)線性規(guī)劃的可變鄰域搜索方法對(duì)時(shí)延受限情況下的SFC映射問(wèn)題進(jìn)行求解。文獻(xiàn)[4]在最小化時(shí)延的約束下，利用混合整數(shù)二次約束規(guī)劃建模對(duì)SFC映射問(wèn)題進(jìn)行求解。但此類數(shù)學(xué)規(guī)劃方法僅在面對(duì)小規(guī)模網(wǎng)絡(luò)時(shí)擁有較快的求解速度，在大規(guī)模網(wǎng)絡(luò)中求解速度較慢并且會(huì)帶來(lái)較高的運(yùn)行成本，因此各類啟發(fā)式算法被相繼提出。文獻(xiàn)[5]采用可拓展的啟發(fā)式算法，每次針對(duì)單個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行映射，若映射不成功則不斷回溯當(dāng)前的結(jié)果，直至完成映射。文獻(xiàn)[6]提出了一種基于改進(jìn)多階段圖的啟發(fā)式算法，從而實(shí)現(xiàn)服務(wù)功能鏈的高效部署。然而，啟發(fā)式算法雖然擁有較快的求解速度，但無(wú)法保證所得的解總是全局最優(yōu)解。因此，元啟發(fā)式算法在啟發(fā)式算法的基礎(chǔ)上進(jìn)行改進(jìn)，結(jié)合了隨機(jī)算法以及局部搜索的策略以避免陷入局部最優(yōu)解。文獻(xiàn)[7]融合遺傳算法與模擬退火算法進(jìn)行求解，同時(shí)通過(guò)判斷個(gè)體約束及糾正遺傳的方法來(lái)規(guī)避局部最優(yōu)解，從而達(dá)到降低服務(wù)功能鏈端到端時(shí)延的目的，但該算法需要反復(fù)迭代才能求出最優(yōu)解，時(shí)間消耗較大，無(wú)法對(duì)VNF進(jìn)行快速部署。文獻(xiàn)[8]首先通過(guò)廣度優(yōu)先搜索完成服務(wù)功能鏈的構(gòu)建，隨后利用改進(jìn)的遺傳粒子群算法對(duì)映射問(wèn)題進(jìn)行求解，提高了服務(wù)功能鏈請(qǐng)求接受率，同時(shí)降低了資源開(kāi)銷，但在對(duì)映射問(wèn)題求解時(shí)沒(méi)有考慮映射順序，產(chǎn)生了一定的時(shí)延。文獻(xiàn)[9]針對(duì)服務(wù)功能鏈端到端時(shí)延優(yōu)化以及服務(wù)可用性最大化問(wèn)題，建立模型后通過(guò)遺傳算法進(jìn)行求解，但面對(duì)大規(guī)模物理拓?fù)鋾r(shí)容易陷入局部最優(yōu)解。而隨著人工智能領(lǐng)域研究的不斷深入，強(qiáng)化學(xué)習(xí)算法憑借其在求解組合優(yōu)化問(wèn)題方面的先天優(yōu)勢(shì)在多個(gè)領(lǐng)域得到應(yīng)用。文獻(xiàn)[10]提出了基于深度強(qiáng)化學(xué)習(xí)的服務(wù)功能鏈可靠部署算法，在保證可靠性的同時(shí)有效減少了服務(wù)功能鏈的損失。文獻(xiàn)[11]使用強(qiáng)化學(xué)習(xí)算法尋找匹配的VNF調(diào)度策略，并提出基于Q學(xué)習(xí)的VNF部署算法，但在大規(guī)模網(wǎng)絡(luò)環(huán)境中強(qiáng)化學(xué)習(xí)算法無(wú)法準(zhǔn)確地描述網(wǎng)絡(luò)資源的動(dòng)態(tài)變化，會(huì)對(duì)VNF的部署產(chǎn)生不良影響。

上述研究大多將作為SFC構(gòu)成單位的VNF視作一個(gè)整體，統(tǒng)一進(jìn)行設(shè)計(jì)、開(kāi)發(fā)和部署，尚未考慮進(jìn)一步細(xì)化的優(yōu)化方案。VNF雖然實(shí)現(xiàn)了與專用硬件設(shè)備的解耦，但這種單體式的映射方法內(nèi)部各邏輯功能間的耦合程度仍較高，且靈活性較差，難以被擴(kuò)展或伸縮。因此提出將微服務(wù)架構(gòu)運(yùn)用到SFC映射及部署的問(wèn)題中，對(duì)VNF進(jìn)行微服務(wù)化的拆分及合并，以實(shí)現(xiàn)端到端時(shí)延的最優(yōu)化。

微服務(wù)體系架構(gòu)[12]的核心在于對(duì)傳統(tǒng)應(yīng)用進(jìn)行功能上的分解，將細(xì)粒度的微服務(wù)單元作為執(zhí)行相關(guān)邏輯操作的最小單元，每個(gè)微服務(wù)單元均能被獨(dú)立部署、運(yùn)行。文獻(xiàn)[13]提出的OpenBox框架首次探索了SFC中多個(gè)VNF的拆分優(yōu)化，并完成了拆分后微服務(wù)單元的定義，但并未考慮SFC中出現(xiàn)不可拆分VNF的狀況。文獻(xiàn)[14]首次探討了服務(wù)功能鏈的優(yōu)化問(wèn)題與微服務(wù)架構(gòu)結(jié)合的可能性，隨后通過(guò)實(shí)例將傳統(tǒng)的粗粒度服務(wù)功能鏈進(jìn)行微服務(wù)化的拆分及合并，繪制了新的有向服務(wù)圖，但在拆分過(guò)程中并未考慮中間狀態(tài)，容易產(chǎn)生過(guò)多的資源開(kāi)銷。

與上述文獻(xiàn)不同，本文針對(duì)服務(wù)功能鏈中虛擬網(wǎng)絡(luò)功能的邏輯功能重復(fù)執(zhí)行問(wèn)題，考慮時(shí)延優(yōu)化，提出一種基于微服務(wù)架構(gòu)的粒度可變服務(wù)功能鏈映射（variable granularity service function chain mapping，VG-SFCM）算法，對(duì)VNF進(jìn)行微服務(wù)化的拆分時(shí)，進(jìn)一步考慮映射時(shí)網(wǎng)絡(luò)拓?fù)渲械馁Y源使用情況和具體的服務(wù)功能鏈請(qǐng)求，以確定粒度不一的映射單元，從而達(dá)到降低SFC端到端時(shí)延及提高資源利用率的目的。該算法通過(guò)基于典型VNF的快速拆分策略將相關(guān)VNF拆分為最細(xì)粒度的微服務(wù)單元，隨后對(duì)單一SFC內(nèi)的冗余微服務(wù)單元進(jìn)行合并，以實(shí)現(xiàn)端到端時(shí)延的最優(yōu)化。針對(duì)物理拓?fù)渲幸淹瓿刹糠諷FC部署的情況，通過(guò)SFC之間的微服務(wù)單元復(fù)用策略，根據(jù)可復(fù)用微服務(wù)單元所處的網(wǎng)絡(luò)節(jié)點(diǎn)及其鄰近節(jié)點(diǎn)的資源狀況，判斷復(fù)用及新到達(dá)SFC中剩余微服務(wù)單元的部署可能性，減少微服務(wù)單元的實(shí)例化。仿真結(jié)果表明，VG- SFCM能夠有效降低SFC的平均端到端時(shí)延及平均部署網(wǎng)絡(luò)成本，提高網(wǎng)絡(luò)資源利用率。

1 問(wèn)題描述與系統(tǒng)模型

1.1 問(wèn)題描述

在傳統(tǒng)網(wǎng)絡(luò)中，每個(gè)中間件都有相對(duì)應(yīng)的專用服務(wù)器，網(wǎng)絡(luò)功能服務(wù)設(shè)備多并且復(fù)雜，不利于按需擴(kuò)展和調(diào)整。虛擬化技術(shù)的出現(xiàn)，使得通用服務(wù)器取代傳統(tǒng)的專用物理設(shè)備成為可能，從而有效降低網(wǎng)絡(luò)功能的平均部署網(wǎng)絡(luò)成本。然而，單條SFC內(nèi)的不同單體VNF間存在許多重復(fù)執(zhí)行的邏輯功能，如數(shù)據(jù)包的輸入輸出、報(bào)文分類等。在SFC映射的過(guò)程中，考慮映射的最小粒度并進(jìn)行微服務(wù)化的拆分及合并，可有效地去除這些冗余的邏輯功能，降低根據(jù)映射方案部署時(shí)產(chǎn)生的端到端時(shí)延及資源開(kāi)銷。

不同映射方案對(duì)比如圖1所示，兩種方案均將單體VNF作為SFC的最小映射單元。單SFC的拆分、合并及映射如圖2所示，該方案首先對(duì)服務(wù)功能鏈中的各VNF進(jìn)行邏輯功能分析，并根據(jù)分析結(jié)果執(zhí)行相應(yīng)的拆分工作，將映射的最小單元轉(zhuǎn)化為粗粒度的微服務(wù)單元。完成SFC中所有VNF的拆分后，按照不改變初始邏輯順序的原則進(jìn)行相同微服務(wù)單元的合并并構(gòu)建新服務(wù)圖，合并后剩下的AtomNF個(gè)數(shù)相較于拆分初期減少了44.4%。合并完成后按照原始的邏輯順序進(jìn)行新服務(wù)功能鏈的構(gòu)建。此類合并操作的對(duì)象為單SFC內(nèi)部的微服務(wù)單元，微服務(wù)單元的實(shí)例是按照映射方案創(chuàng)建并部署的，當(dāng)新服務(wù)功能鏈請(qǐng)求（service function chain request，SFCR）到來(lái)時(shí)，相同的實(shí)例又會(huì)再次創(chuàng)建。因此通過(guò)合并及復(fù)用可有效地減少相關(guān)資源的浪費(fèi)，并降低端到端時(shí)延。

針對(duì)多個(gè)SFCR到來(lái)的情況，后續(xù)到達(dá)的SFCR將依據(jù)上一SFCR的映射方案進(jìn)行可復(fù)用微服務(wù)單元的篩選及節(jié)點(diǎn)資源分析。SFC間的微服務(wù)單元復(fù)用及映射如圖3所示。多SFC映射方案中共有兩個(gè)SFC需完成映射及后續(xù)的部署，SFC1的映射方案與如圖2（b）一致。SFC2包含AtomNF1、AtomNF3這兩個(gè)與SFC1相同的可復(fù)用微服務(wù)單元，通過(guò)判斷節(jié)點(diǎn)B中的計(jì)算資源是否能夠支持AtomNF6和AtomNF7的映射來(lái)確定映射方案。該映射方案復(fù)用了AtomNF1和

圖1 不同映射方案對(duì)比

圖2 單SFC的拆分、合并及映射

圖3 SFC間的微服務(wù)單元復(fù)用及映射

AtomNF3兩個(gè)微服務(wù)單元，并將剩余單元映射至已激活節(jié)點(diǎn)中，相較于傳統(tǒng)映射方案減少了節(jié)點(diǎn)的激活數(shù)量，并通過(guò)減少微服務(wù)單元實(shí)例數(shù)降低了SFC2的端到端時(shí)延及資源開(kāi)銷。

1.2 網(wǎng)絡(luò)模型

為了更好地形式化描述問(wèn)題，列出了與底層網(wǎng)絡(luò)、服務(wù)功能鏈請(qǐng)求相關(guān)的符號(hào)及其含義，相關(guān)符號(hào)及其含義見(jiàn)表1。

1.3 約束分析及優(yōu)化目標(biāo)

考慮底層網(wǎng)絡(luò)中節(jié)點(diǎn)資源約束和鏈路帶寬資源約束，為了最小化SFC的端到端時(shí)延，SFC與VNF的映射及部署問(wèn)題可以建模為一個(gè)整數(shù)規(guī)劃模型。相較于傳統(tǒng)粗粒度的單體VNF映射方案，基于微服務(wù)架構(gòu)的映射方案的主要?jiǎng)?chuàng)新在于映射粒度變?yōu)榧?xì)粒度的微服務(wù)單元，因此在資源約束方面與傳統(tǒng)映射方案的區(qū)別之處在于其中的映射單元，未拆分的VNF在建模過(guò)程中除開(kāi)銷方面的差異外，表現(xiàn)形式與AtomNF保持一致。

表1 相關(guān)符號(hào)及其含義

在服務(wù)功能鏈的部署中，計(jì)算資源可具體化為CPU資源以及內(nèi)存資源，因此必須確保某個(gè)節(jié)點(diǎn)上部署的全部AtomNF的CPU開(kāi)銷及內(nèi)存開(kāi)銷不超過(guò)該節(jié)點(diǎn)可提供的相關(guān)資源。節(jié)點(diǎn)的CPU資源約束如式（1）所示。

完成對(duì)SFC的部署后，數(shù)據(jù)流量按照AtomNF部署后的各個(gè)節(jié)點(diǎn)順序進(jìn)行遍歷。網(wǎng)絡(luò)拓?fù)渲忻織l物理鏈路的帶寬資源有限，因此SFC產(chǎn)生的需求所占用的鏈路帶寬資源需要小于帶寬總?cè)萘?，相關(guān)約束如式（3）所示。

由于不同應(yīng)用對(duì)時(shí)延的敏感程度有差異，用戶對(duì)SFC端到端時(shí)延的需求也各有不同，因此需要進(jìn)行時(shí)延約束的相關(guān)定義。SFC的整體端到端時(shí)延可根據(jù)時(shí)延產(chǎn)生的位置劃分為鏈路時(shí)延和節(jié)點(diǎn)時(shí)延兩大部分，其中鏈路時(shí)延包括傳播時(shí)延、傳輸時(shí)延及排隊(duì)時(shí)延，節(jié)點(diǎn)時(shí)延即處理時(shí)延。因此，SFC部署在物理鏈路上產(chǎn)生的鏈路時(shí)延如式（5）所示。

結(jié)合式（6）與式（8），單條服務(wù)功能鏈的端到端時(shí)延構(gòu)成如式（9）所示。

式（10）的優(yōu)化目標(biāo)是在滿足式（1）～式（3）的情況下，最小化服務(wù)功能鏈端到端時(shí)延。

2 基于微服務(wù)架構(gòu)的粒度可變服務(wù)功能鏈映射算法設(shè)計(jì)

基于微服務(wù)架構(gòu)的粒度可變服務(wù)功能鏈構(gòu)建問(wèn)題的關(guān)鍵在于根據(jù)SFC進(jìn)行合理的邏輯拆分，繼而根據(jù)拆分所得微服務(wù)單元集合篩選重復(fù)執(zhí)行部分，并根據(jù)SFC原始邏輯進(jìn)行服務(wù)圖的繪制。其中，若拆分所得單元的標(biāo)準(zhǔn)不一致，則會(huì)導(dǎo)致后續(xù)重復(fù)執(zhí)行的操作無(wú)法正常合并及復(fù)用，因此需將對(duì)數(shù)據(jù)流執(zhí)行操作的最小邏輯功能作為最小工作單元并定義為微服務(wù)單元。

2.1 基于典型VNF的快速拆分策略

VNF的拆分主要根據(jù)構(gòu)成SFC的VNF集合及其相應(yīng)的邏輯功能，將VNF拆分成若干個(gè)細(xì)粒度的微服務(wù)單元，并定義為AtomNF，一個(gè)微服務(wù)單元代表對(duì)數(shù)據(jù)進(jìn)行操作的最小邏輯單元。

服務(wù)功能鏈構(gòu)成關(guān)系如圖4所示，表述了微服務(wù)單元、虛擬網(wǎng)絡(luò)功能及服務(wù)功能鏈之間的構(gòu)成關(guān)系。3類個(gè)體之間的關(guān)系可用式（11）與式（12）表述。

（12）

服務(wù)功能鏈拆分過(guò)程如圖5所示，該SFC包含邊緣防火墻、監(jiān)視器、應(yīng)用防火墻3個(gè)VNF。通過(guò)邏輯分析，構(gòu)成這3個(gè)VNF的微服務(wù)單元如圖5（b）所示。這些微服務(wù)單元經(jīng)過(guò)拆分?jǐn)嚅_(kāi)相互間原有的關(guān)系后，最終形成的微服務(wù)單元集合如圖5（c）所示。

為了實(shí)現(xiàn)SFC的快速拆分并降低拆分所帶來(lái)的資源開(kāi)銷，基于典型VNF的快速拆分將邏輯分析與拆分工作前置，通過(guò)預(yù)先對(duì)出現(xiàn)頻率較高的VNF進(jìn)行邏輯分析，提前準(zhǔn)備高頻VNF所對(duì)應(yīng)的微服務(wù)單元鏡像文件并放入倉(cāng)庫(kù)。當(dāng)SFCR到達(dá)時(shí)，即可快速根據(jù)相關(guān)的VNF拆分方案查找并直接拉取相關(guān)鏡像。

此外用戶的需求各有不同且無(wú)法預(yù)測(cè)，SFC中出現(xiàn)未經(jīng)前置拆分的VNF情況不可避免。針對(duì)此類情況，基于典型NFV的快速拆分將不對(duì)鏡像倉(cāng)庫(kù)中未包含的VNF執(zhí)行相關(guān)拆分操作，仍將其視作粗粒度的單一整體。

根據(jù)上述相關(guān)流程的描述，基于典型NFV的快速拆分算法流程如下。

算法1：基于典型NFV的快速拆分算法

輸入：服務(wù)功能鏈

輸出：AtomNF集合

2.2 SFC內(nèi)的微服務(wù)單元合并策略

觀察SFC拆分所得的微服務(wù)單元，可以發(fā)現(xiàn)3個(gè)VNF拆分后均存在部分共有的微服務(wù)單元。經(jīng)過(guò)分析可以發(fā)現(xiàn)，重復(fù)執(zhí)行相同的微服務(wù)單元并不會(huì)對(duì)數(shù)據(jù)流帶來(lái)實(shí)際的改變，反而會(huì)增加所對(duì)應(yīng)的映射節(jié)點(diǎn)的資源開(kāi)銷及端到端時(shí)延，因此可以對(duì)這些多次出現(xiàn)的微服務(wù)單元進(jìn)行分析及合并。合并可以有效地縮短服務(wù)功能鏈的總長(zhǎng)度，以降低端到端時(shí)延。此外，減少微服務(wù)單元的重復(fù)執(zhí)行可以相應(yīng)地降低相關(guān)計(jì)算資源的開(kāi)銷。

鑒于不同微服務(wù)單元對(duì)數(shù)據(jù)流的操作各有不同，參考MicroNF[16]的分類規(guī)則，SFC內(nèi)的冗余微服務(wù)單元合并策略將微服務(wù)單元分為端點(diǎn)、區(qū)分、修改、重構(gòu)、流量控制及靜態(tài)6類，AtomNF分類見(jiàn)表2。

為了保證合并后的新SFC所提供的服務(wù)與合并前保持一致，同時(shí)最大限度地降低端到端時(shí)延，微服務(wù)單元的合并需要遵守以下原則：

（1）數(shù)據(jù)包須經(jīng)歷與原始服務(wù)功能鏈相同的處理步驟，但可減少部分冗余步驟的執(zhí)行次數(shù)；

（2）每一個(gè)多次執(zhí)行的微服務(wù)單元均需進(jìn)行合并可能性分析，力求盡可能壓縮服務(wù)功能鏈的端到端長(zhǎng)度；

表2 AtomNF分類

圖6 合并后的服務(wù)功能鏈

（3）與原始SFC相比，微服務(wù)單元在新SFC中的位置均可發(fā)生變化，但變化后不可使數(shù)據(jù)流發(fā)生改變。

合并后的服務(wù)功能鏈如圖6所示，僅需8個(gè)微服務(wù)單元便可實(shí)現(xiàn)原始SFC的相關(guān)功能，最大路徑長(zhǎng)度為7，相較于原始SFC拆分后的路徑長(zhǎng)度14降低了50%。微服務(wù)單元間的通信將采用網(wǎng)絡(luò)服務(wù)分組頭（network service header，NSH）進(jìn)行數(shù)據(jù)的交互[17]，該方法可以有效地處理單一微服務(wù)單元，然后將其傳遞給多個(gè)微服務(wù)單元。

根據(jù)上述條件，SFC內(nèi)的微服務(wù)單元合并算法流程如下。

算法2：SFC內(nèi)的微服務(wù)單元合并算法、

輸入：AtomNF集合

輸出：服務(wù)圖

2.3 SFC間的微服務(wù)單元復(fù)用策略

在實(shí)際應(yīng)用場(chǎng)景中，不同的SFCR內(nèi)部往往包含相同的VNF，此外，從細(xì)粒度的角度進(jìn)行觀察，可進(jìn)一步發(fā)現(xiàn)不同的VNF內(nèi)存在大量相同的邏輯處理部分。從單一SFC內(nèi)部的角度進(jìn)行觀察，相同邏輯處理部分可以通過(guò)合并的形式進(jìn)行優(yōu)化。若從多個(gè)SFC的角度進(jìn)行觀察，單一SFC內(nèi)重復(fù)邏輯部分的合并形式可轉(zhuǎn)化為復(fù)用的形式，以減少節(jié)點(diǎn)的激活，進(jìn)一步降低服務(wù)功能鏈部署產(chǎn)生的網(wǎng)絡(luò)成本。

VNF或AtomNF實(shí)例的復(fù)用目前可通過(guò)多租戶技術(shù)實(shí)現(xiàn)，多租戶技術(shù)可以使得一個(gè)軟件實(shí)例為多個(gè)租戶提供相應(yīng)服務(wù)[18-19]。相較于傳統(tǒng)不可復(fù)用的映射方案，在SFC映射過(guò)程中，通過(guò)一個(gè)可復(fù)用的微服務(wù)單元實(shí)例為多個(gè)SFCR提供服務(wù)，可以有效提高節(jié)點(diǎn)資源利用率。

為了實(shí)現(xiàn)后續(xù)請(qǐng)求的復(fù)用，首次到達(dá)的SFCR需通過(guò)改進(jìn)的灰狼優(yōu)化（grey wolf optimizer，GWO）算法確定最佳映射方案。后續(xù)SFCR將以此映射方案為基準(zhǔn)，通過(guò)對(duì)應(yīng)映射節(jié)點(diǎn)的資源狀況判斷復(fù)用的可能性。

后續(xù)到達(dá)的SFCR在完成前期的編排及拆分合并工作后，將自身的微服務(wù)單元集合與上一SFCR的微服務(wù)單元集合進(jìn)行對(duì)比，重復(fù)出現(xiàn)的微服務(wù)單元即可復(fù)用的微服務(wù)單元，隨后進(jìn)行相關(guān)微服務(wù)單元映射節(jié)點(diǎn)的復(fù)用能力判斷工作。判斷節(jié)點(diǎn)的剩余資源能否承載該SFC其余不可復(fù)用的微服務(wù)單元。若不能，則將相關(guān)微服務(wù)單元部署至資源足夠的鄰近節(jié)點(diǎn)中。當(dāng)出現(xiàn)鄰近節(jié)點(diǎn)的可用資源均無(wú)法滿足相關(guān)需求時(shí)，對(duì)該SFC再次通過(guò)改進(jìn)的灰狼優(yōu)化算法進(jìn)行映射方案的確定。

根據(jù)上述工作流程，SFC間的微服務(wù)單元復(fù)用算法流程如下。

算法3：SFC間的微服務(wù)單元復(fù)用算法

輸入：服務(wù)功能鏈請(qǐng)求

學(xué)術(shù)期刊的周期性、定時(shí)性和多目標(biāo)等特點(diǎn)及相關(guān)主體眾多、編校質(zhì)量受控和刊物內(nèi)容多樣等特征，導(dǎo)致出版流程呈現(xiàn)出多、細(xì)、雜、亂的特點(diǎn)，且執(zhí)行時(shí)間受限。以《船研所學(xué)報(bào)》的編輯出版工作為例，該期刊為季刊，其自由狀態(tài)下的事項(xiàng)梳理見(jiàn)圖3。

輸出：映射方案

2.4 映射算法設(shè)計(jì)

基于微服務(wù)架構(gòu)的粒度可變服務(wù)功能鏈映射算法流程如下。首先與粗粒度單體 VNF映射方案確定流程一致，根據(jù)用戶請(qǐng)求的源節(jié)點(diǎn)和目的節(jié)點(diǎn)，通過(guò)最短路徑算法搜索可能的映射方案；然后通過(guò)基于典型VNF的快速拆分算法進(jìn)行SFC的拆分，并得到相關(guān)微服務(wù)單元集合；最后執(zhí)行SFC內(nèi)的微服務(wù)單元合并操作，以得到端到端長(zhǎng)度盡可能壓縮的新服務(wù)功能鏈。

用戶的SFCR往往是先后到達(dá)的，對(duì)于首個(gè)到來(lái)的SFCR，網(wǎng)絡(luò)中尚無(wú)已經(jīng)部署的SFC，因此無(wú)法執(zhí)行相關(guān)微服務(wù)單元的復(fù)用，故需利用改進(jìn)的灰狼優(yōu)化算法進(jìn)行映射方案的確定。針對(duì)后續(xù)到來(lái)的SFCR，同樣通過(guò)拆分及合并得到細(xì)粒度的服務(wù)功能鏈后，根據(jù)SFC間的微服務(wù)單元復(fù)用策略進(jìn)行映射方案的確定。

算法4：基于微服務(wù)架構(gòu)的粒度可變服務(wù)功能鏈映射算法

輸入：網(wǎng)絡(luò)拓?fù)洹⒎?wù)功能鏈請(qǐng)求集合

輸出：映射方案

3 仿真與結(jié)果分析

為了驗(yàn)證VG-SFCM算法的性能和有效性，本文將其與幾種基線算法進(jìn)行比較，分別是OpenBox解耦（OpenBox decoupling，OBD）算法、隊(duì)列感知可靠嵌入（queue-aware reliable embedding，QARE）算法、基于動(dòng)態(tài)規(guī)劃的成本優(yōu)化算法（dynamic programming based cost optimization algorithm，DP-COA）以及SFC動(dòng)態(tài)編排（SFC dynamic orchestration，SFCDO）算法，并采用服務(wù)功能鏈請(qǐng)求的平均端到端時(shí)延、請(qǐng)求接受率以及平均部署網(wǎng)絡(luò)成本作為評(píng)價(jià)指標(biāo)。仿真使用MATLAB 2020b軟件在配置為AMD Ryzen 7 5800H CPU、16.0 GB RAM的計(jì)算機(jī)上完成。OBD算法利用OpenBox解耦的思想，將處理塊作為映射的最小單元，映射時(shí)基于貪婪策略進(jìn)行節(jié)點(diǎn)的選擇[20]；QARE算法根據(jù)節(jié)點(diǎn)隊(duì)列信息對(duì)VNF進(jìn)行部署[21]；DP-COA算法將VNF部署看成多階段決策過(guò)程[22]，并基于動(dòng)態(tài)規(guī)劃的思想進(jìn)行求解；SFCDO算法采用廣度優(yōu)先搜索對(duì)SFC部署進(jìn)行優(yōu)化[23]。

3.1 仿真設(shè)計(jì)

為了便于進(jìn)行仿真分析，本文采用典型物理網(wǎng)絡(luò)拓?fù)洹獓?guó)家科學(xué)基金會(huì)網(wǎng)絡(luò)（National Science Foundation Network，NSFNET）[24]，NSFNET拓?fù)淙鐖D7所示。網(wǎng)絡(luò)拓?fù)渲心硞€(gè)時(shí)間段內(nèi)到達(dá)的SFCR數(shù)量從0增加至1 200。

圖7 NSFNET拓?fù)?/p>

仿真中產(chǎn)生的不同虛擬網(wǎng)絡(luò)功能預(yù)設(shè)為10種，并對(duì)其中的三層路由器、二層交換機(jī)、IP層防火墻、應(yīng)用層防火墻、虛擬專用網(wǎng)設(shè)備、負(fù)載均衡及監(jiān)視器共計(jì)6種VNF進(jìn)行拆分方案的前置確定，而入侵檢測(cè)系統(tǒng)、入侵防御系統(tǒng)、深度報(bào)文檢測(cè)及虛擬專用網(wǎng)絡(luò)則仍保持粗粒度的單體VNF，以模擬實(shí)際情況中VNF未進(jìn)行前置拆分的情況。各網(wǎng)絡(luò)功能的具體CPU資源開(kāi)銷及內(nèi)存資源開(kāi)銷各不相同，需進(jìn)行前期的設(shè)定，AtomNF級(jí)的微服務(wù)單元的CPU需求及內(nèi)存需求均為1單位。

每條SFC的長(zhǎng)度即拆分前的虛擬網(wǎng)絡(luò)功能數(shù)量，為4～6間的隨機(jī)整數(shù)，每個(gè)服務(wù)功能鏈中具體的VNF隨機(jī)產(chǎn)生于前期預(yù)設(shè)的10種VNF，由經(jīng)過(guò)前置拆分方案確認(rèn)的VNF及未經(jīng)前置拆分方案確認(rèn)的VNF構(gòu)成。物理拓?fù)渲芯W(wǎng)路節(jié)點(diǎn)間鏈路的傳輸時(shí)延設(shè)置為1 ms，排隊(duì)時(shí)延及處理時(shí)延通過(guò)式（6）和式（7）結(jié)合當(dāng)前時(shí)刻的資源利用率進(jìn)行計(jì)算。

3.2 性能指標(biāo)

為了驗(yàn)證NFV環(huán)境中VG-SFCM算法的可用性，本文使用以下3個(gè)性能指標(biāo)作為仿真分析對(duì)象。

（3）服務(wù)功能鏈請(qǐng)求的平均部署網(wǎng)絡(luò)成本定義如式（21）所示。

3.3 仿真結(jié)果分析

式（18）～式（20）描述的各項(xiàng)性能指標(biāo)均將SFCR數(shù)量作為自變量。不同算法的服務(wù)功能鏈請(qǐng)求的平均端到端時(shí)延如圖8所示，展示了部署映射方案后SFC的平均端到端時(shí)延隨SFCR數(shù)量變化的趨勢(shì)。通過(guò)觀察，可得VG-SFCM算法始終保持較低的平均端到端時(shí)延。這是因?yàn)樵撍惴ㄔ诖_定映射方案前總會(huì)進(jìn)行SFC的微服務(wù)化拆分及合并，減少了冗余微服務(wù)單元的執(zhí)行，縮短了處理時(shí)間。隨著SFCR數(shù)量的增加，各算法的平均端到端時(shí)延均呈現(xiàn)上升趨勢(shì)，這種現(xiàn)象主要?dú)w因于各節(jié)點(diǎn)的計(jì)算資源和節(jié)點(diǎn)間的鏈路帶寬資源不斷被消耗。

圖8 不同算法的服務(wù)功能鏈請(qǐng)求的平均端到端時(shí)延

表3 該拓?fù)涞木唧w參數(shù)及仿真過(guò)程中所需的其他參數(shù)

不同算法的服務(wù)功能鏈請(qǐng)求接受率如圖9所示，展示了不同算法在相同SFCR數(shù)量下的請(qǐng)求接受率。由圖9可以得到，當(dāng)服務(wù)功能鏈請(qǐng)求數(shù)量不斷增加時(shí)，各算法的請(qǐng)求接受率均呈下降趨勢(shì)，但VG-SFCM的性能優(yōu)于其他算法。當(dāng)請(qǐng)求數(shù)量超過(guò)1 000時(shí)，SFCDO算法的接受率開(kāi)始直線下降。VG-SFCM算法的請(qǐng)求接受率最后比SFCDO算法高5%左右，比OBD算法高15%左右。這是因?yàn)閂G-SFCM算法改變了最小的映射單元，有效避免了對(duì)比算法中物理節(jié)點(diǎn)剩余資源無(wú)法進(jìn)行單體VNF的部署時(shí)產(chǎn)生資源碎片的情況。此外，通過(guò)微服務(wù)單元的合并及復(fù)用操作減少微服務(wù)單元的實(shí)例化，處理更多SFC，進(jìn)一步提高了SFCR接受率。

圖9 不同算法的服務(wù)功能鏈請(qǐng)求接受率

圖10 不同服務(wù)功能鏈請(qǐng)求數(shù)量下的平均部署網(wǎng)絡(luò)成本

表4 算法性能對(duì)比

為了更加直觀地體現(xiàn)出VG-SFCM算法的優(yōu)勢(shì)，對(duì)VG-SFCM和其他算法的整體性能進(jìn)行總結(jié)，算法性能對(duì)比見(jiàn)表4。通過(guò)觀察可以看出，在同一實(shí)驗(yàn)環(huán)境下，與其他算法相比，VG-SFCM算法確實(shí)有效降低了服務(wù)功能鏈的端到端時(shí)延，提高了服務(wù)功能鏈請(qǐng)求接受率并且減少了平均部署網(wǎng)絡(luò)成本。

4 結(jié)束語(yǔ)

本文研究了NFV環(huán)境中考慮時(shí)延優(yōu)化和可變粒度的服務(wù)功能鏈映射問(wèn)題，旨在最小化服務(wù)功能鏈的端到端時(shí)延，并降低映射及部署產(chǎn)生的平均部署網(wǎng)絡(luò)成本。針對(duì)這一優(yōu)化目標(biāo)，提出了基于微服務(wù)架構(gòu)的粒度可變服務(wù)功能鏈映射算法，該算法首先對(duì)服務(wù)功能鏈進(jìn)行快速拆分，并執(zhí)行合并操作以減少不必要的微服務(wù)單元重復(fù)執(zhí)行。隨后通過(guò)SFC間的微服務(wù)單元復(fù)用策略，減少后續(xù)到達(dá)的SFCR相關(guān)實(shí)例的映射及部署，提高節(jié)點(diǎn)資源利用率。仿真結(jié)果表明，該算法在保證用戶需求的情況下，有效降低了服務(wù)功能鏈的平均端到端時(shí)延，提高了請(qǐng)求接受率，減少了節(jié)點(diǎn)激活成本。但目前該算法對(duì)服務(wù)功能鏈的拆分均基于人工的邏輯分析及微服務(wù)化前置，無(wú)法實(shí)時(shí)地對(duì)未經(jīng)相關(guān)前置操作的虛擬網(wǎng)絡(luò)功能進(jìn)行微服務(wù)化。在后續(xù)的研究中，筆者將對(duì)該算法進(jìn)行相關(guān)優(yōu)化，設(shè)計(jì)對(duì)應(yīng)的自動(dòng)化微服務(wù)拆分算法，以滿足網(wǎng)絡(luò)狀態(tài)動(dòng)態(tài)變化的特征。

[1] SCHARDONG F, NUNES I, SCHAEFFER-FILHO A. NFV resource allocation: a systematic review and taxonomy of VNF forwarding graph embedding[J]. Computer Networks, 2021, 185: 107726.

[2] 翟東, 孟相如, 康巧燕, 等. 面向時(shí)延與可靠性優(yōu)化的服務(wù)功能鏈部署方法[J]. 電子與信息學(xué)報(bào), 2020, 42(10): 2386-2393.

ZHAI D, MENG X R, KANG Q Y, et al. Service function chain deployment method for delay and reliability optimization[J]. Journal of Electronics ＆ Information Technology, 2020, 42(10): 2386-2393.

[3] REDDY V S, BAUMGARTNER A, BAUSCHERT T. Robust embedding of VNF/service chains with delay bounds[C]//Proceedings of 2016 IEEE Conference on Network Function Virtualization and Software Defined Networks. Piscataway: IEEE Press, 2016: 93-99.

[4] MEHRAGHDAM S, KELLER M, KARL H. Specifying and placing chains of virtual network functions[C]//Proceedings of 2014 IEEE 3rd International Conference on Cloud Networking (CloudNet). Piscataway: IEEE Press, 2014: 7-13.

[5] MECHTRI M, GHRIBI C, ZEGHLACHE D. A scalable algorithm for the placement of service function chains[J]. IEEE Transactions on Network and Service Management, 2016, 13(3): 533-546.

[6] QI D D, SHEN S B, WANG G H. Towards an efficient VNF placement in network function virtualization[J]. Computer Communications, 2019, 138: 81-89.

[7] 陳卓, 馮鋼, 劉怡靜, 等. MEC中基于改進(jìn)遺傳模擬退火算法的虛擬網(wǎng)絡(luò)功能部署策略[J]. 通信學(xué)報(bào), 2020, 41(4): 70-80.

CHEN Z, FENG G, LIU Y J, et al. Virtual network function deployment strategy based on improved genetic simulated annealing algorithm in MEC[J]. Journal on Communications, 2020, 41(4): 70-80.

[8] 孫士清, 彭建華, 游偉, 等. 5G網(wǎng)絡(luò)下資源感知的服務(wù)功能鏈協(xié)同構(gòu)建和映射算法[J]. 西安交通大學(xué)學(xué)報(bào), 2020, 54(8): 140-148.

SUN S Q, PENG J H, YOU W, et al. A coordinating composition and mapping algorithm for a service function chain with resource-aware[J]. Journal of Xi’an Jiaotong University, 2020, 54(8): 140-148.

[9] YALA L, FRANGOUDIS P A, KSENTINI A. Latency and availability driven VNF placement in a MEC-NFV environment[C]//Proceedings of 2018 IEEE Global Communications Conference. Piscataway: IEEE Press, 2018: 1-7.

[10] 唐倫, 曹睿, 廖皓, 等. 基于深度強(qiáng)化學(xué)習(xí)的服務(wù)功能鏈可靠部署算法[J]. 電子與信息學(xué)報(bào), 2020, 42(12): 2931-2938.

TANG L, CAO R, LIAO H, et al. Reliable deployment algorithm of service function chain based on deep reinforcement learning[J]. Journal of Electronics ＆ Information Technology, 2020, 42(12): 2931-2938.

[11] LI J L, SHI W S, ZHANG N, et al. Reinforcement learning based VNF scheduling with end-to-end delay guarantee[C]// Proceedings of 2019 IEEE/CIC International Conference on Communications in China (ICCC). Piscataway: IEEE Press, 2019: 572-577.

[12] 馮志勇, 徐硯偉, 薛霄, 等. 微服務(wù)技術(shù)發(fā)展的現(xiàn)狀與展望[J]. 計(jì)算機(jī)研究與發(fā)展, 2020, 57(5): 1103-1122.

FENG Z Y, XU Y W, XUE X, et al. Review on the development of microservice architecture[J]. Journal of Computer Research and Development, 2020, 57(5): 1103-1122.

[13] BREMLER-BARR A, HARCHOL Y, HAY D. OpenBox: a software-defined framework for developing, deploying, and managing network functions[C]//Proceedings of the 2016 ACM SIGCOMM Conference. New York: ACM Press, 2016: 511-524.

[14] CHOWDHURY S R, SALAHUDDIN M A, LIMAM N, et al. Re-architecting NFV ecosystem with microservices: state of the art and research challenges[J]. IEEE Network, 2019, 33(3): 168-176.

[15] DWARAKI A, WOLF T. Adaptive service-chain routing for virtual network functions in software-defined networks[C]//Proceedings of the 2016 workshop on Hot Topics in Middleboxes and Network Function Virtualization. New York: ACM Press, 2016: 32-37.

[16] MENG Z L, BI J, WANG H P, et al. MicroNF: an efficient framework for enabling modularized service chains in NFV[J]. IEEE Journal on Selected Areas in Communications, 2019, 37(8): 1851-1865.

[17] NEKOVEE M, SHARMA S, UNIYAL N, et al. Towards AI-enabled microservice architecture for network function virtualization[C]//Proceedings of 2020 IEEE Eighth International Conference on Communications and Networking (ComNet). Piscataway: IEEE Press, 2020: 1-8.

[18] MA H J, ZHANG J Y, WANG Z X. Implementation of multi-tenancy adaptive cache admission model[J]. Journal of Physics: Conference Series, 2021, 2026(1): 012045.

[19] LEIVADEAS A, FALKNER M. VNF placement problem: a multi-tenant intent-based networking approach[C]//Proceedings of 2021 24th Conference on Innovation in Clouds, Internet and Networks and Workshops (ICIN). Piscataway: IEEE Press, 2021: 143-150.

[20] LI D F, HONG P L, XUE K P, et al. Virtual network function placement considering resource optimization and SFC requests in cloud datacenter[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 29(7): 1664-1677.

[21] TANG L, ZHAO G F, WANG C M, et al. Queue-aware reliable embedding algorithm for 5G network slicing[J]. Computer Networks, 2018, 146: 138-150.

[22] 劉昀. 虛擬網(wǎng)絡(luò)功能資源分配與服務(wù)功能鏈路由研究[D]. 合肥: 中國(guó)科學(xué)技術(shù)大學(xué), 2020.

LIU Y. Virtual network function resource allocation and service function chain routing[D]. Hefei: University of Science and Technology of China, 2020.

[23] SUN G, XU Z, YU H F, et al. Low-latency and resource-efficient service function chaining orchestration in network function virtualization[J]. IEEE Internet of Things Journal, 2020, 7(7): 5760-5772.

[24] STRAWN G. Masterminds of the NSFnet: jennings, wolff, and van houweling[J]. IT Professional, 2021, 23(6): 67-69.

Variable granularity service function chain mapping algorithm based on microservice architecture

WU Xiaochun, HONG Chen, ZHANG Yue, ZHANG Junnan, ZHOU Jingjing

School of Information and Electronic Engineering, Zhejiang Gongshang University, Hangzhou 310018, China

For the problem that the end-to-end delay of the service function chain (SFC) cannot meet the demand of delay-sensitive applications in 5G environment, a variable granularity service function chain mapping (VG-SFCM) algorithm based on microservice architecture was proposed by splitting the traditional virtualized network function (VNF) into mapping units of varying granularity. Firstly, the traditional coarse-grained VNF was decoupled into fine-grained microservice units, and then the instantiation of microservice units was reduced through the consolidation of redundant microservice units within SFC and the reuse of microservice units between SFC, thus reducing the processing time of SFC. The simulation results show that the algorithm reduces the end-to-end delay of SFC by 14.81% compared to the traditional mapping algorithm while reducing the average deployment network cost.

network function virtualization, microservice architecture, service function chain, delay

TN915，TP393

A

10.11959/j.issn.1000–0801.2022289

2022-06-09；

2022-11-14

洪晨，2281026509@qq.com

浙江省自然科學(xué)基金資助項(xiàng)目（No. LY19F020002，No. Y19F020031），浙江省新型網(wǎng)絡(luò)標(biāo)準(zhǔn)與應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室項(xiàng)目（No. 2013E10012）

吳曉春（1983-），女，博士，浙江工商大學(xué)信息與電子工程學(xué)院高級(jí)實(shí)驗(yàn)師、碩士生導(dǎo)師，主要研究方向?yàn)樾乱淮W(wǎng)絡(luò)技術(shù)架構(gòu)、軟件定義網(wǎng)絡(luò)、網(wǎng)絡(luò)功能虛擬化、人工智能與網(wǎng)絡(luò)安全的結(jié)合等。

洪晨（1998-），女，浙江工商大學(xué)信息與電子工程學(xué)院碩士生，主要研究方向?yàn)橹R(shí)圖譜、新一代網(wǎng)絡(luò)技術(shù)架構(gòu)。

張?jiān)溃?998-），女，浙江工商大學(xué)信息與電子工程學(xué)院碩士生，主要研究方向?yàn)橹R(shí)圖譜、新一代網(wǎng)絡(luò)技術(shù)架構(gòu)。

張俊楠（1997-），男，浙江工商大學(xué)信息與電子工程學(xué)院碩士生，主要研究方向?yàn)樾乱淮W(wǎng)絡(luò)技術(shù)架構(gòu)。

周靜靜（1980-），女，博士，浙江工商大學(xué)信息與電子工程學(xué)院副教授、碩士生導(dǎo)師，主要研究方向?yàn)樾乱淮W(wǎng)絡(luò)技術(shù)架構(gòu)、軟件定義網(wǎng)絡(luò)、網(wǎng)絡(luò)流量建模與分析、大數(shù)據(jù)處理、深度學(xué)習(xí)等。

s: The Zhejiang Province Natural Science Foundation (No. LY19F020002, No. Y19F020031), Zhejiang Provincial Key Laboratory of New Network Standards and Application Technology (No. 2013E10012)