徐澤汐，莊雷，張坤麗，桂明宇

（鄭州大學(xué)計算機(jī)與人工智能學(xué)院，河南 鄭州 450001）

0 引言

網(wǎng)絡(luò)功能虛擬化（NFV,network function virtualization）[1]實現(xiàn)了網(wǎng)元功能的軟硬解耦，推動了網(wǎng)絡(luò)的軟件化和虛擬化實現(xiàn)，為未來網(wǎng)絡(luò)提供了一種新的網(wǎng)絡(luò)設(shè)計思路。隨著互聯(lián)網(wǎng)中間件的增多，為滿足業(yè)務(wù)需求，國際互聯(lián)網(wǎng)工程任務(wù)組（IETF,Internet Engineering Task Force）[2]對網(wǎng)絡(luò)服務(wù)提出了更詳細(xì)的要求——按特定路徑，遍歷部署在不同通用設(shè)備內(nèi)的多個虛擬網(wǎng)絡(luò)功能（VNF,virtual network function），被稱為服務(wù)功能鏈（SFC,service function chain）[3]。然而，在網(wǎng)絡(luò)業(yè)務(wù)中，VNF 之間通常具有錯綜復(fù)雜的依賴關(guān)系，例如，解密服務(wù)器應(yīng)該部署在加密服務(wù)器之后，防火墻與網(wǎng)絡(luò)監(jiān)視器則可以被并行部署[4]，圖1 上半部分展示了一個由4 個VNF 組成的端到端網(wǎng)絡(luò)服務(wù)，其中節(jié)點代表VNF，邊代表數(shù)據(jù)流的流向。因此，為保證網(wǎng)絡(luò)服務(wù)的可獲得性，當(dāng)網(wǎng)絡(luò)數(shù)據(jù)流需要穿過這組VNF時，必須考慮它們之間的依賴關(guān)系，將網(wǎng)絡(luò)服務(wù)的時延、可靠性等控制在一定的服務(wù)質(zhì)量（QoS,quantity of service）等級內(nèi)。圖1 下半部分展示了一種網(wǎng)絡(luò)SFC 的組建情況，為提高時效性，VNF2、VNF3被并行部署在VNF1后，VNF4被部署在VNF2、VNF3后，其中節(jié)點代表VNF，邊代表VNF 之間的依賴關(guān)系。

圖1 網(wǎng)絡(luò)服務(wù)功能鏈

因此，盡管NFV 被寄予厚望，如何鏈接和放置VNF，是NFV 部署所面對的主要挑戰(zhàn)之一，也被稱作SFC 部署問題[5]。該問題旨在將一組按特定順序排放的VNF 高效地部署到底層底層網(wǎng)絡(luò)或NFV 基礎(chǔ)設(shè)施中，以適應(yīng)網(wǎng)絡(luò)客戶提出的個性化要求。該問題的求解主要面臨2 個挑戰(zhàn)：1)隨著信息網(wǎng)絡(luò)業(yè)務(wù)如沉浸式云XR 等新興業(yè)務(wù)的出現(xiàn)，為精準(zhǔn)把控網(wǎng)絡(luò)服務(wù)質(zhì)量，如何在遵循VNF 之間復(fù)雜依賴關(guān)系下部署服務(wù)功能鏈；2)網(wǎng)絡(luò)的業(yè)務(wù)需求通常是不可預(yù)知的，對于實時到達(dá)且具有特定生存周期的網(wǎng)絡(luò)業(yè)務(wù)請求，如何對其進(jìn)行動態(tài)且滿足服務(wù)質(zhì)量等級的資源分配。這對VNF 的部署帶來了持續(xù)的挑戰(zhàn)。

針對此問題，國內(nèi)外學(xué)者關(guān)注于網(wǎng)絡(luò)資源的可獲得性，設(shè)計了許多經(jīng)典的啟發(fā)式VNF 部署方法，例如，Pham 等[6]設(shè)計了一種啟發(fā)式方法來協(xié)調(diào)VNF 的編排并將其部署到底層網(wǎng)絡(luò)。Zhang 等[7]設(shè)計了2 種啟發(fā)式方法來求解SFC 部署問題，一種是先路由后部署的方法，另一種是基于節(jié)點優(yōu)先的路由引導(dǎo)式部署的方法。Freitas 等[8]將VNF 部署建模為一個綜合考慮了部署與能耗的多目標(biāo)問題，并使用非支配排序遺傳算法和微分進(jìn)化算法2 種優(yōu)化算法來解決該問題。另外，人工智能的蓬勃發(fā)展也引起了學(xué)術(shù)界和工業(yè)界的關(guān)注，研究人員也基于機(jī)器學(xué)習(xí)在NFV 部署方面進(jìn)行了卓有成效的研究。例如，Soualah 等[9]將SFC 編排問題建模為決策樹，基于蒙特卡羅樹搜索利用強(qiáng)化學(xué)習(xí)技術(shù)設(shè)計了一種NFV 部署算法。袁泉等[10]利用深度學(xué)習(xí)方法設(shè)計了一種基于多層前饋神經(jīng)網(wǎng)絡(luò)的虛擬網(wǎng)絡(luò)功能資源需求預(yù)測方法，然后根據(jù)資源需求預(yù)測結(jié)果，基于動態(tài)編碼遺傳算法實現(xiàn)了虛擬網(wǎng)絡(luò)功能動態(tài)部署。Chen 等[11]提出了一種基于深度強(qiáng)化學(xué)習(xí)的服務(wù)質(zhì)量、體驗質(zhì)量感知的自適應(yīng)在線編排方法來適應(yīng)實時網(wǎng)絡(luò)變化進(jìn)行NFV 資源配置。

需要注意的是，在求解VNF 部署問題時，為使那些最初為歐幾里得結(jié)構(gòu)數(shù)據(jù)而開發(fā)的智能算法（機(jī)器學(xué)習(xí)[12]、深度學(xué)習(xí)[13]、聯(lián)邦學(xué)習(xí)[14]等）能夠適用于解決網(wǎng)絡(luò)功能部署這種圖類問題，需要將網(wǎng)絡(luò)業(yè)務(wù)先轉(zhuǎn)換為統(tǒng)一的結(jié)構(gòu)化數(shù)據(jù)，而目前幾乎所有的研究都采用了簡單矩陣（如鄰接矩陣、邊表）的形式來對網(wǎng)絡(luò)業(yè)務(wù)進(jìn)行表征。但是，使用傳統(tǒng)矩陣表示的網(wǎng)絡(luò)業(yè)務(wù)有2 個致命的缺點：1)矩陣元素難以表示VNF 之間錯綜復(fù)雜的關(guān)系；2)矩陣元素不便對多屬性網(wǎng)絡(luò)業(yè)務(wù)進(jìn)行表示。因此利用矩陣表征的網(wǎng)絡(luò)會使算法在輸入階段就遺失許多重要信息，進(jìn)而造成計算結(jié)果的偏差。出于同樣原因，利用矩陣表示底層網(wǎng)絡(luò)則面臨更多的局限性，因為底層網(wǎng)絡(luò)的資源和狀態(tài)都是隨著VNF 的部署在不斷變化的。因此，以往基于矩陣表征網(wǎng)絡(luò)而設(shè)計的NFV 部署方法在應(yīng)對上述SFC 部署問題的2 個挑戰(zhàn)時，能力非常有限。

基于此，本文使用知識圖譜（KG,knowledge graph）[15]對網(wǎng)絡(luò)業(yè)務(wù)以及底層網(wǎng)絡(luò)進(jìn)行表征，將網(wǎng)絡(luò)中的元素存儲為以“實體?關(guān)系?實體”三元組為基本單位的結(jié)構(gòu)化數(shù)據(jù)，并提出了一種基于關(guān)系對齊的SFC 部署算法。與其他算法相比，本文算法的創(chuàng)新點體現(xiàn)在以下3 個方面。

1)使用知識圖譜對網(wǎng)絡(luò)以及復(fù)雜業(yè)務(wù)進(jìn)行表征。

2)定義了關(guān)系的聚合屬性相似度計算方法。

3)基于知識圖譜中實體對齊的思想，設(shè)計了一種基于編輯距離的關(guān)系對齊方法，用以指導(dǎo)SFC的部署。

1 基于知識圖譜的SFC 部署模型

1.1 知識圖譜與知識圖譜實體對齊

定義1知識圖譜。本文將一個知識圖譜表示為 KG=(E,R,A,L,T)，其中E、R、A、L分別是實體集合、關(guān)系集合、屬性集合以及屬性值集合，T?(E×R×E)∪(E×A×L)是知識圖譜三元組集合，即知識圖譜基本組成單位是描述實體之間關(guān)系的“實體1?關(guān)系?實體2”三元組，以及描述實體屬性的“實體?屬性?值”三元組。

定義2知識圖譜實體對齊。給定2 個知識圖譜 KG0=(E0,R0,A0,L0,T0)和KG1=(E1,R1,A1,L1,T1)，知識圖譜實體對齊[16]被定義為對E0中的每個實體，找出E1中的等效實體，即

1.2 問題規(guī)劃

為實現(xiàn)對網(wǎng)絡(luò)業(yè)務(wù)中功能組件、VNF 之間的依賴關(guān)系，以及網(wǎng)絡(luò)資源數(shù)目的準(zhǔn)確表示，本文將網(wǎng)絡(luò)業(yè)務(wù)與底層網(wǎng)絡(luò)這種圖類數(shù)據(jù)轉(zhuǎn)存為三元組形式的結(jié)構(gòu)化數(shù)據(jù)，分別得到知識圖譜 KGf=(Ef,Rf,Af,Lf,Tf)表示的SFC 和知識圖譜KGs=(Es,Rs,As,Ls,Ts)表示的底層網(wǎng)絡(luò)，表1 展示了 KGf與KGs的結(jié)構(gòu)化信息?；诖?，SFC 部署問題可以表示為

表1 KGf 與KGs 的結(jié)構(gòu)化信息

在傳統(tǒng)的知識圖譜實體對齊方法中，通常通過評估實體的相似度來對齊不同知識圖譜中的實體，其本質(zhì)上為分類問題。然而，在本文提出的在線SFC部署問題中，需保證在部署VNF 時能夠兼顧網(wǎng)絡(luò)的資源屬性以及不同VNF 之間的依賴關(guān)系，以實現(xiàn)實時、按需的分配。因此，為使知識圖譜實體對齊方法能夠適應(yīng)SFC 部署問題，本文聚焦于網(wǎng)絡(luò)中的依賴關(guān)系，在結(jié)構(gòu)化SFC 與底層網(wǎng)絡(luò)的信息構(gòu)建與之對應(yīng)的知識圖譜KGf與KGs之后，分解出知識圖譜KGf與KGs的關(guān)系集合，通過對2 個關(guān)系集合中的所有元素執(zhí)行對齊操作，即 Alignentity(KGf,KGs)={(R,r)|R∈Rf,r∈Rs}，以實現(xiàn)在線SFC 部署。這樣，由于SFC 與底層網(wǎng)絡(luò)被轉(zhuǎn)換為以“實體1?關(guān)系?實體2”為單位的知識集合，在部署SFC 時，物理鏈路與其兩端的物理節(jié)點被視為一個整體，用以承載有依賴關(guān)系的2 個VNF，這就避免了任何額外的隱藏資源被使用，保證了在整個部署過程中消耗的總能量最少。同時也解決了基于“點對點”設(shè)計的矩陣表征網(wǎng)絡(luò)SFC 部署方法由于忽略了VNF之間的依賴關(guān)系而造成的QoS難以把控等問題。

2 算法設(shè)計

在現(xiàn)實網(wǎng)絡(luò)世界中，服務(wù)、應(yīng)用程序和用戶需要與基礎(chǔ)設(shè)施網(wǎng)絡(luò)之間進(jìn)行實時的交互。因此，在網(wǎng)絡(luò)功能虛擬化背景下，必須對網(wǎng)絡(luò)業(yè)務(wù)進(jìn)行在線分析和部署，進(jìn)而有效利用共享資源，同時需定期更新底層底層網(wǎng)絡(luò)的資源狀況，以便在其他網(wǎng)絡(luò)業(yè)務(wù)需求到達(dá)時自動評估部署的可能性?；诖?，本文提出一種針對在線場景設(shè)計的算法，其主要目標(biāo)是在考慮資源受限的網(wǎng)絡(luò)環(huán)境下，實現(xiàn)具有復(fù)雜依賴關(guān)系的SFC 的實時部署。本文算法一次處理一個網(wǎng)絡(luò)業(yè)務(wù)請求，并定期更新底層網(wǎng)絡(luò)，以釋放更多的資源供新的網(wǎng)絡(luò)業(yè)務(wù)請求使用。

2.1 系統(tǒng)模型

2.1.1 底層網(wǎng)絡(luò)

在一個NFV 使能網(wǎng)絡(luò)環(huán)境中，物理基礎(chǔ)設(shè)施網(wǎng)絡(luò)被表示為一個無向連接圖Gs=(N,L)，其中N表示物理節(jié)點集合，L表示物理鏈路集合。任一節(jié)點n∈N都擁有用loc(n)表示的位置屬性，以及用Cap(n)表示的資源容量，這里的資源包含計算資源與存儲資源，每個節(jié)點都根據(jù)場景（例如，虛擬CPU 核心數(shù)、CPU 時間等）選用合適的單位。對于每條連接物理節(jié)點a 和b 的雙向物理鏈路lab∈L，具有帶寬和時延2 個基本屬性。

2.1.2 SFC 請求

如圖2 所示，SFC 請求被描述為一個有向的加權(quán)圖Gf=（F,A），其中F表示VNF 的集合，|F|表示該業(yè)務(wù)中的VNF 數(shù)量；A表示SFC 中的依賴關(guān)系集合，是VNF 之間的傳輸路徑，在本文中也被稱為虛擬鏈路。對于每個VNF∈F都有一定的部署位置要求與計算資源、存儲資源需求，分別用loc(f)、D(f)表示。另外，在線場景中，VNF 之間的虛擬鏈路通常有著最高數(shù)據(jù)率與時延的要求，且SFC 通常包含到達(dá)時間與生存時間2 個屬性，它們反映了網(wǎng)絡(luò)業(yè)務(wù)的動態(tài)特征。

圖2 SFC 部署示例

2.2 基于知識圖譜的在線SFC 部署算法

在任意時刻t，為將動態(tài)到達(dá)的SFCi部署到滿足QoS 的NFV 基礎(chǔ)設(shè)施上，首先，對該網(wǎng)絡(luò)業(yè)務(wù)請求與底層網(wǎng)絡(luò)進(jìn)行知識提取，構(gòu)建或更新相應(yīng)的知識圖譜，然后分解出它們的關(guān)系集合，分別命名為Sf、Ss。接下來，定義2 個關(guān)系集合中關(guān)系的聚合屬性相似度，利用本文設(shè)計的基于編輯距離的關(guān)系對齊方法求得該SFCi部署的解。在每次迭代部署中，算法都檢查網(wǎng)絡(luò)業(yè)務(wù)的生存時間，以便將失效的SFC 從底層資源中刪除，進(jìn)而更新整個底層網(wǎng)絡(luò)?；谥R圖譜的在線SFC 部署算法如算法1 所示，具體操作流程如下。

2.2.1 初始化

首先，提取初始狀態(tài)的底層網(wǎng)絡(luò)的知識，包括物理節(jié)點、物理鏈路，以及它們初始狀態(tài)的資源數(shù)目，將其存儲為以三元組為基本單位的結(jié)構(gòu)化數(shù)據(jù)，并為其構(gòu)建知識圖譜KGs=(Es,Rs,As,Ls,Ts)。其中，KGs的實體指代了物理節(jié)點；由于底層網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)在物理上是固定的，即構(gòu)成底層網(wǎng)絡(luò)的主要元素節(jié)點和鏈路的數(shù)量以及連通性也是固定不變的，因此，本文中兩節(jié)點之間的物理鏈路就對應(yīng)著KGs的實體關(guān)系；根據(jù)2.1.1 節(jié)可知，As包括實體屬性——物理節(jié)點的計算資源Capcpu(n)和存儲資源Capmem(n)與關(guān)系屬性——物理鏈路的帶寬Capbw(l)和時延Capd(l)，其值用Ls={Rs1,Rs2,…,Rs|n|}表示，Ts?(Es×Rs×Es)∪(Es×As×Ls)是KGs的基本單位三元組集合。

然后，提取動態(tài)到達(dá)的SFC 的知識，即組成該網(wǎng)絡(luò)業(yè)務(wù)的VNF、VNF 之間的依賴關(guān)系，以及資源需求，用知識圖譜 KGf=(Ef,Rf,Af,Lf,Tf)表示。KGf中，Ef代表的實體集合即網(wǎng)絡(luò)業(yè)務(wù)中的所有VNF 組件；Rf代表的關(guān)系集合即VNF 之間的依賴關(guān)系集合，它是從起點開始，按照廣度優(yōu)先順序遍歷得到的該SFC 弧的有序集合。對于每個關(guān)系Ri，實體1 是其對應(yīng)弧的起點的ID，實體2 是其對應(yīng)弧的終點的ID。根據(jù)2.1.2 節(jié)可知，Af包括實體屬性——VNF 的計算資源需求量Dcpu(f)和存儲資源需求量Dmem(f)與關(guān)系屬性——虛擬鏈路的最高數(shù)據(jù)率Dbw(L)與時延Dd(L)的集合，其值用Lf={Df1,Df2,…,Df|F|}表示，Tf?(Ef×Rf×Ef)∪(Ef×Af×Lf)是KGf的基本單位三元組集合。

另外，為方便操作，本文將結(jié)構(gòu)化數(shù)據(jù)分別存儲在其知識圖譜的命名為sheet1 和sheet2 的實體集合與關(guān)系集合列表中。表2～表5 展示了根據(jù)圖2中底層網(wǎng)絡(luò)與SFC 所構(gòu)建的知識圖譜KGs1與KGf1的實體屬性結(jié)構(gòu)化信息。

表2 知識圖譜KGs1 的實體列表sheet1

表3 知識圖譜KGs1 的關(guān)系列表sheet2

表4 知識圖譜KGf1 的實體列表sheet1

表5 知識圖譜KGf1 的關(guān)系列表sheet2

2.2.2 分解知識圖譜

與知識圖譜傳統(tǒng)的實體對齊方法不同，在SFC部署問題中，只有所有的VNF 都按照既定的依賴關(guān)系部署到底層網(wǎng)絡(luò)中，才能得到一個有效的部署解，即

在本文中，對齊KGf與KGs中的關(guān)系，需為Rf中的每一個R找到Rs中與之匹配的r，即將虛擬/物理鏈路及其兩端節(jié)點看作一個整體，作為關(guān)系對齊的基本單位。因此，本文在初始化SFC 與底層網(wǎng)絡(luò)后，分解它們對應(yīng)的知識圖譜，分別得到KGf與KGs的用n×n矩陣表示的關(guān)系集合Sf與Ss，其中，關(guān)系集合的對角線元素fii與sii分別是關(guān)系Ri與ri的聚合屬性值，用f(Ri)與s(ri)表示。關(guān)系的聚合屬性包含了其對應(yīng)的虛擬/物理鏈路的資源屬性，以及關(guān)系中實體1、實體2 的資源屬性，即實體屬性與關(guān)系屬性的聚合。集合中其他元素表示關(guān)系之間是否存在相繼關(guān)系，若有則為1，反之為無窮。例如，圖3 是分解KGs1與KGf1得到的關(guān)系集合。

圖3 分解KGs1 與KGf1 得到的關(guān)系集合

2.2.3 定義關(guān)系聚合屬性相似度

為對齊實體，一般會定義2 個實體的屬性相似性函數(shù)，用以評估2 個實體的相似度[17]。同樣地，在評估2 個關(guān)系的相似度時，本文基于一種廣泛使用的Jaccard 相似度[18]計算方法，設(shè)計了2 個關(guān)系集合中關(guān)系的聚合屬性相似度。

其中，2 個關(guān)系集合對角線元素之間的減操作代表2 個關(guān)系的聚合屬性相似度計算，代表2 個關(guān)系集合中待匹配元素的聚合屬性中相同屬性的個數(shù)，為簡化操作，本文僅討論底層NFV設(shè)備與 VNF 的資源屬性一致的情況；代表對ri與Ri的所有屬性值執(zhí)行⊙操作之后的值，若ri中所有元素的資源剩余量均大于Ri需求量，則與分母數(shù)值相等，否則為正無窮。例如圖3 的2 個關(guān)系集合中，R1與r1均考慮計算與存儲資源2 個節(jié)點屬性以及時延與帶寬2 個鏈路屬性，因此，=4；另外，根據(jù)圖2 中所標(biāo)的資源數(shù)目值可知，r1中的2 個節(jié)點及其之間的鏈路剩余資源數(shù)目均大于R1的資源需求量，因此，；則R1與r1的聚合屬性相似度為。

2.2.4 線性規(guī)劃求解關(guān)系對齊

基于實體對齊中廣泛使用的基于編輯距離[19]的相似性度量方法，本文將關(guān)系集合Ss與Sf之間的距離定義為最小化目標(biāo)函數(shù)，將式(2)的關(guān)系對齊問題表示為

其中，Φ是關(guān)系r與R之間的映射關(guān)系。該匹配問題旨在最小化距離J(Φ)，因此，可以重新將該問題表示為

其中，M是本文算法的部署函數(shù)，維度為n×n，M的行對應(yīng)SFC 的VNF，列對應(yīng)底層網(wǎng)絡(luò)中的物理節(jié)點，M中的每一行和每一列都只有一個元素為1，其他元素均為0（元素值為1 代表VNF 被放置在該列的物理節(jié)點上）；Ss?MSfMT是經(jīng)過函數(shù)M作用后Ss與Sf的差；是L1 范式。

根據(jù)文獻(xiàn)[19]可知，問題式(6)是多項式時間無解的，并且一個中等規(guī)模的底層網(wǎng)絡(luò)通常具有數(shù)百個節(jié)點，若使用暴力枚舉法，例如分支界限和枚舉搜索，得到整數(shù)解的時間復(fù)雜度將為指數(shù)級[20]。因此，本文利用一種圖匹配[21]方法將該問題化簡為線性問題。具體操作如下。

首先，為了符合圖匹配問題中頂點數(shù)相同的要求，在矩陣中增加參數(shù)為0 的元素，將關(guān)系矩陣Sf擴(kuò)充到與Ss相同的維度。如圖3 中給出的一組待對齊的SFC 與底層網(wǎng)絡(luò)，由于SFC 的關(guān)系數(shù)為4 而底層網(wǎng)絡(luò)為6，因此需要在SFC 的關(guān)系矩陣Sf中增加2 行0 元素和2 列0 元素，使其與物理鄰接矩陣維度相同。

接下來，定義一個|Rs|×|Rs|的矩陣H1

其中，M為正交矩陣，MMT=I，I為單位矩陣，則式(7)右乘M可得

因為M是置換矩陣，式(8)的L1 范式為

將殘差矩陣表示為H

接下來，將矩陣H={hij}和M={mij}按列劃分為

基于此，H可被表示為

其中，Sfs是根據(jù)關(guān)系矩陣Sf與Ss派生的|Rs|2×|Rs|2的關(guān)系匹配度矩陣，定義為

其中，對角線元素sjj?fii的值為2.2.3 節(jié)中定義的2 個關(guān)系屬性的相似度。

因此，目標(biāo)函數(shù)就等價于

其中，m=VEC(M)是n2×1 的向量。且該目標(biāo)函數(shù)的求解需受到如下所示的位置約束（?Ri∈KGf,rj∈KGs）

式(17)～式(19)確保了被部署到底層網(wǎng)絡(luò)上的節(jié)點對之間均無額外的邊。若有關(guān)系Ri與rj通過關(guān)系對齊成功匹配，es1與es2分別是它們的實體1 與實體2，則ef1與ef2代表的VNF 需分別部署到es1與es2所代表的物理節(jié)點的位置上，且一個VNF 只能被部署到一個物理節(jié)點上。

因此，SFC 的在線部署問題可被表示為

對于某時刻t到達(dá)的SFC，分解該SFC 與底層網(wǎng)絡(luò)對應(yīng)的知識圖譜，分別得到關(guān)系矩陣，作為本文算法的輸入，使用單純形法求解目標(biāo)函數(shù)，得到部署解。

2.2.5 更新底層網(wǎng)絡(luò)

一旦成功部署了t時刻到達(dá)的SFC，算法需更新KGs的sheet1，以更新當(dāng)前底層網(wǎng)絡(luò)的剩余資源數(shù)目，并根據(jù)到達(dá)時間開始處理下一個SFC。但當(dāng)該SFC 中有任意一個的關(guān)系元組未能在底層網(wǎng)絡(luò)中匹配到滿足資源需求量的物理設(shè)備時，則標(biāo)記對齊失敗，算法拒絕該SFC，開始處理下一時刻到達(dá)的SFC。

2.2.6 復(fù)雜度分析

通常服務(wù)功能鏈包含3～8 個不同的網(wǎng)絡(luò)功能，因此，在不考慮網(wǎng)絡(luò)業(yè)務(wù)數(shù)目的情況下，本文算法根據(jù)構(gòu)成底層網(wǎng)絡(luò)的節(jié)點總數(shù)|N|和邊總數(shù)|L|，從其知識圖譜中分解出關(guān)系矩陣，即需在O(|N|+|L|)處理時間內(nèi)搜索并列出所有關(guān)系。一旦列出了所有關(guān)系，便可進(jìn)入關(guān)系對齊階段，該過程消耗的處理時間幾乎可以忽略不計，因為經(jīng)過了線性化的處理之后，對齊階段的主要工作是比較待匹配關(guān)系中所有元素的屬性值，其復(fù)雜度為O(1)。

3 實驗仿真與分析

3.1 實驗環(huán)境

仿真采用TiNet[22]網(wǎng)絡(luò)拓?fù)?，包?4 個節(jié)點和89 條全雙工鏈路。網(wǎng)絡(luò)資源容量均服從均勻分布，其中，節(jié)點的CPU 資源容量與存儲資源容量的分布區(qū)間均為[10,15]，鏈路的帶寬分布區(qū)間為[50,100]，傳輸時延分布區(qū)間為[1,50]。節(jié)點和鏈路能量消耗中常量值設(shè)置為Pl=150,Pb=150,Pn=15。網(wǎng)絡(luò)可以提供8 種功能，每個需要部署的服務(wù)功能鏈由3～8 個不同的網(wǎng)絡(luò)功能組成，VNF 的主要參數(shù)同文獻(xiàn)[23]，如表6 所示。

表6 VNF 的主要參數(shù)

任意VNF 之間具有依賴關(guān)系的概率為0.5，編排方式同文獻(xiàn)[4]，VNF 之間的虛擬鏈路對最高數(shù)據(jù)率與時延的要求服從[20,50]的隨機(jī)分布。為了提高在線算法評估的準(zhǔn)確性，共執(zhí)行2 000 個服務(wù)功能鏈的部署測試，其中網(wǎng)絡(luò)業(yè)務(wù)請求的到達(dá)時間服從泊松分布，平均每1 000 個時間單元約到達(dá)40 個；生存時間服從指數(shù)分布，平均為40 個時間單元。實驗將數(shù)據(jù)采集點設(shè)置在時間窗的開端，一個時間窗等于5 000 個時間單元，實驗仿真在10 個時間窗內(nèi)執(zhí)行完畢。

3.2 初始化結(jié)果

TiNet 拓?fù)浔晦D(zhuǎn)換為197 個三元組，其中包括89 個關(guān)系三元組和108 個屬性三元組。具體來說，本文考慮的底層網(wǎng)絡(luò)的知識包括物理節(jié)點、物理鏈路和資源數(shù)目，分別為它們打上節(jié)點、鏈接和屬性的標(biāo)簽。同樣地，每個在線到達(dá)的網(wǎng)絡(luò)業(yè)務(wù)也根據(jù)標(biāo)簽被抽取相應(yīng)的知識。圖4 展示了本文利用文獻(xiàn)[24]中的Echarts 工具所呈現(xiàn)的部分知識圖譜的可視化結(jié)果，其中圖4(a)是TiNet 的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，圖4(b)是對網(wǎng)絡(luò)執(zhí)行知識抽取后部分三元組的可視化結(jié)果。與僅能包含部分信息的其他傳統(tǒng)網(wǎng)絡(luò)表征方法相比，知識圖譜表征的網(wǎng)絡(luò)能夠提取網(wǎng)絡(luò)中的全部重要信息（關(guān)系與屬性值），避免了算法在輸入階段重要信息遺失而造成的計算結(jié)果的偏差。

圖4 TiNet 網(wǎng)絡(luò)知識抽取可視化結(jié)果

3.3 實驗分析

3.3.1 SFC 部署評價指標(biāo)

本文基于如下4 個指標(biāo)[11]評估算法的性能。

1)請求接收率：一段時間內(nèi)成功部署的SFC個數(shù)占實際總網(wǎng)絡(luò)業(yè)務(wù)請求數(shù)量的比例。

其中，n?(T)表示T時間段內(nèi)到達(dá)網(wǎng)絡(luò)業(yè)務(wù)請求數(shù)，σ(SFCi)是一個取值為0 或1 的二進(jìn)制變量，表示第i個SFC 是否部署成功。

2)總收益：至t時刻，部署網(wǎng)絡(luò)請求所產(chǎn)生的總收益。

3)平均能耗：每個時間間隔T后所有物理節(jié)點和鏈路的總功耗的平均值，單位為W。

若處于開啟狀態(tài)，E(n)=pn+τ(pb?pn)，pn、pb分別為物理節(jié)點的基本能耗和滿負(fù)荷時的能耗，τ為節(jié)點的CPU 負(fù)載率，E(l)=pl，pl為物理鏈路能耗，一般為常量；若處于關(guān)閉狀態(tài)，則無能量消耗。

4)運行時間：客戶端發(fā)出網(wǎng)絡(luò)業(yè)務(wù)請求到其被成功部署到底層網(wǎng)絡(luò)上所需的時間。

3.3.2 部署結(jié)果分析

為驗證所提算法的性能和有效性，本文選取SFC-MCT 算法及First-Fit（FF）算法進(jìn)行對比實驗。SFC-MCT 算法[9]將部署問題轉(zhuǎn)化為決策樹搜索，樹中的每個節(jié)點對應(yīng)于一個VNF 的匹配方案，再用蒙特卡羅樹搜索算法找到一個獎勵值最大的SFC 部署方案，是一種基于強(qiáng)化學(xué)習(xí)的SFC 部署算法。FF 算法采用First-Fit 算法設(shè)計了一種啟發(fā)式的SFC 部署算法，先為每一個VNF 匹配資源數(shù)目最為充足的物理節(jié)點，然后在這些節(jié)點之間使用Dijkstra 在算法部署傳輸路徑，是SFC 部署的經(jīng)典基準(zhǔn)線算法[11,22]。

圖5 顯示了請求接收率的對比結(jié)果。結(jié)果表明，本文算法能夠接收所有到達(dá)系統(tǒng)的網(wǎng)絡(luò)請求，當(dāng)系統(tǒng)達(dá)到穩(wěn)定狀態(tài)后，F(xiàn)F 算法與SFC-MCT 算法的成功率在85%左右，因此，本文算法性能明顯優(yōu)于對比算法。這是因為無論是基于啟發(fā)式的FF 算法還是基于強(qiáng)化學(xué)習(xí)的SFC-MCT 算法，這些SFC 部署方法都是將矩陣表征的SFC 與底層網(wǎng)絡(luò)作為算法的輸入，缺少了網(wǎng)絡(luò)中的關(guān)系以及網(wǎng)絡(luò)屬性等關(guān)鍵信息，復(fù)雜的網(wǎng)絡(luò)環(huán)境便對它們的有效性提出了考驗。隨著網(wǎng)絡(luò)資源逐漸被分配，SFC 匹配到既滿足依賴關(guān)系又能達(dá)到服務(wù)質(zhì)量的物理資源的請求接收率便有所下降。

圖5 請求接收率的對比結(jié)果

圖6 顯示了總收益的對比結(jié)果。從圖6 中可以看出，與其他算法相比，本文算法使互聯(lián)網(wǎng)供應(yīng)商取得了最高的總收益，這與請求接收率的結(jié)果相吻合。

圖6 總收益的對比結(jié)果

圖7 顯示了運行時間的對比結(jié)果。從圖7 可以看到，本文算法平均部署時間約為0.01 ms，F(xiàn)F 算法與SFC-MCT 算法約為0.04 ms 與0.21 ms，因此，本文算法在運行時間上取得了明顯的優(yōu)勢。這是因為FF 算法與SFC-MCT 算法的輸入數(shù)據(jù)中未包含VNF 之間的依賴關(guān)系，因此匹配過程是基于點對點的，即先部署VNF 再連接它們之間的傳輸路徑，這也是目前大多部署算法所面臨的問題。這些算法每部署一個VNF 都需要對整個底層網(wǎng)絡(luò)中的節(jié)點進(jìn)行比對，復(fù)雜度高，并且需要額外的鏈路部署時間。而本文算法僅需從輸入的結(jié)構(gòu)化數(shù)據(jù)中搜索并列出所有關(guān)系后，便可進(jìn)入關(guān)系比對階段，并且因為經(jīng)過了線性化的處理，對齊過程消耗的處理時間幾乎可以忽略不計。本節(jié)實驗是在3.4 GHz CPU、16 GB 內(nèi)存的計算機(jī)上通過Pycharm 進(jìn)行的仿真實驗。

圖7 運行時間的對比結(jié)果

圖8 是平均能耗的對比結(jié)果，結(jié)果表明，本文算法的平均能耗比FF 算法低約30%，比SFC-MCT算法的低約13%。這是因為FF 算法是先根據(jù)節(jié)點資源數(shù)目啟發(fā)式地計算得到網(wǎng)絡(luò)業(yè)務(wù)中VNF 的部署位置，VNF 的部署位置通常較為分散，因此，通過Dijkstra 算法計算得到的VNF 之間的傳輸路徑就要占用較多的鏈路資源；SFC-MCT 算法雖然利用強(qiáng)化學(xué)習(xí)計算得到了獎勵值最高的部署方案，但節(jié)點與鏈路的關(guān)系仍然是被割裂地考慮的，在部署過程中不可避免地會開啟一些隱藏節(jié)點。而本文算法在部署SFC 時，SFC 與底層網(wǎng)絡(luò)被轉(zhuǎn)換為以“實體1–關(guān)系–實體2”為單位的知識集合，以節(jié)點和鏈路組成的三元組為單位進(jìn)行部署，這就避免了任何額外的隱藏資源被使用，因此在整個部署過程中消耗的總能量最少。圖9 與圖10 也證實了這一結(jié)果，隨著服務(wù)功能鏈的持續(xù)部署，本文算法的節(jié)點開啟量與鏈路開啟量在整個過程中一直是最少的。

圖8 平均能耗的對比結(jié)果

圖9 節(jié)點開啟量的對比結(jié)果

圖10 鏈路開啟量的對比結(jié)果

4 結(jié)束語

新型網(wǎng)絡(luò)業(yè)務(wù)的出現(xiàn)對服務(wù)功能鏈的部署提出了更高的要求，即必須在資源受限的前提下遵循網(wǎng)絡(luò)功能之間的依賴關(guān)系執(zhí)行部署。因此，針對具有復(fù)雜依賴關(guān)系服務(wù)功能鏈在線部署問題，本文利用知識圖譜對網(wǎng)絡(luò)業(yè)務(wù)及底層網(wǎng)絡(luò)進(jìn)行表征，提出了一種基于知識圖譜的服務(wù)功能鏈部署方法。與基于傳統(tǒng)矩陣表征的部署算法相比，由于本文算法將網(wǎng)絡(luò)中的屬性與關(guān)系信息轉(zhuǎn)化為了以實體?關(guān)系?實體的結(jié)構(gòu)化數(shù)據(jù)，沒有造成重要信息的缺失，因此在線部署網(wǎng)絡(luò)功能時，其精確性與時效性均有所提高。此外，雖然將知識圖譜引入了服務(wù)功能鏈部署中，但使用知識圖譜對網(wǎng)絡(luò)進(jìn)行表征學(xué)習(xí)還有深入研究的空間。因此，下一步將繼續(xù)在知識圖譜表征服務(wù)網(wǎng)絡(luò)上展開工作，挖掘更加精準(zhǔn)、有效的表征方法。