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

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

0 引言

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

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

因此，盡管NFV 被寄予厚望，如何鏈接和放置VNF，是NFV 部署所面對(duì)的主要挑戰(zhàn)之一，也被稱作SFC 部署問題[5]。該問題旨在將一組按特定順序排放的VNF 高效地部署到底層底層網(wǎng)絡(luò)或NFV 基礎(chǔ)設(shè)施中，以適應(yīng)網(wǎng)絡(luò)客戶提出的個(gè)性化要求。該問題的求解主要面臨2 個(gè)挑戰(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ù)知的，對(duì)于實(shí)時(shí)到達(dá)且具有特定生存周期的網(wǎng)絡(luò)業(yè)務(wù)請(qǐng)求，如何對(duì)其進(jìn)行動(dòng)態(tài)且滿足服務(wù)質(zhì)量等級(jí)的資源分配。這對(duì)VNF 的部署帶來了持續(xù)的挑戰(zhàn)。

針對(duì)此問題，國內(nèi)外學(xué)者關(guān)注于網(wǎng)絡(luò)資源的可獲得性，設(shè)計(jì)了許多經(jīng)典的啟發(fā)式VNF 部署方法，例如，Pham 等[6]設(shè)計(jì)了一種啟發(fā)式方法來協(xié)調(diào)VNF 的編排并將其部署到底層網(wǎng)絡(luò)。Zhang 等[7]設(shè)計(jì)了2 種啟發(fā)式方法來求解SFC 部署問題，一種是先路由后部署的方法，另一種是基于節(jié)點(diǎn)優(yōu)先的路由引導(dǎo)式部署的方法。Freitas 等[8]將VNF 部署建模為一個(gè)綜合考慮了部署與能耗的多目標(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è)計(jì)了一種NFV 部署算法。袁泉等[10]利用深度學(xué)習(xí)方法設(shè)計(jì)了一種基于多層前饋神經(jīng)網(wǎng)絡(luò)的虛擬網(wǎng)絡(luò)功能資源需求預(yù)測方法，然后根據(jù)資源需求預(yù)測結(jié)果，基于動(dòng)態(tài)編碼遺傳算法實(shí)現(xiàn)了虛擬網(wǎng)絡(luò)功能動(dòng)態(tài)部署。Chen 等[11]提出了一種基于深度強(qiáng)化學(xué)習(xí)的服務(wù)質(zhì)量、體驗(yàn)質(zhì)量感知的自適應(yīng)在線編排方法來適應(yīng)實(shí)時(shí)網(wǎng)絡(luò)變化進(jìn)行NFV 資源配置。

需要注意的是，在求解VNF 部署問題時(shí)，為使那些最初為歐幾里得結(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ù)，而目前幾乎所有的研究都采用了簡單矩陣（如鄰接矩陣、邊表）的形式來對(duì)網(wǎng)絡(luò)業(yè)務(wù)進(jìn)行表征。但是，使用傳統(tǒng)矩陣表示的網(wǎng)絡(luò)業(yè)務(wù)有2 個(gè)致命的缺點(diǎn)：1)矩陣元素難以表示VNF 之間錯(cuò)綜復(fù)雜的關(guān)系；2)矩陣元素不便對(duì)多屬性網(wǎng)絡(luò)業(yè)務(wù)進(jìn)行表示。因此利用矩陣表征的網(wǎng)絡(luò)會(huì)使算法在輸入階段就遺失許多重要信息，進(jìn)而造成計(jì)算結(jié)果的偏差。出于同樣原因，利用矩陣表示底層網(wǎng)絡(luò)則面臨更多的局限性，因?yàn)榈讓泳W(wǎng)絡(luò)的資源和狀態(tài)都是隨著VNF 的部署在不斷變化的。因此，以往基于矩陣表征網(wǎng)絡(luò)而設(shè)計(jì)的NFV 部署方法在應(yīng)對(duì)上述SFC 部署問題的2 個(gè)挑戰(zhàn)時(shí)，能力非常有限。

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

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

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

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

1 基于知識(shí)圖譜的SFC 部署模型

1.1 知識(shí)圖譜與知識(shí)圖譜實(shí)體對(duì)齊

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

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

1.2 問題規(guī)劃

為實(shí)現(xiàn)對(duì)網(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ù)，分別得到知識(shí)圖譜 KGf=(Ef,Rf,Af,Lf,Tf)表示的SFC 和知識(shí)圖譜KGs=(Es,Rs,As,Ls,Ts)表示的底層網(wǎng)絡(luò)，表1 展示了 KGf與KGs的結(jié)構(gòu)化信息?；诖耍琒FC 部署問題可以表示為

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

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

2 算法設(shè)計(jì)

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

2.1 系統(tǒng)模型

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

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

2.1.2 SFC 請(qǐng)求

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

圖2 SFC 部署示例

2.2 基于知識(shí)圖譜的在線SFC 部署算法

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

2.2.1 初始化

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

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

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

表2 知識(shí)圖譜KGs1 的實(shí)體列表sheet1

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

表4 知識(shí)圖譜KGf1 的實(shí)體列表sheet1

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

2.2.2 分解知識(shí)圖譜

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

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

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

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

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

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

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

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

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

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

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

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

接下來，定義一個(gè)|Rs|×|Rs|的矩陣H1

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

因?yàn)镸是置換矩陣，式(8)的L1 范式為

將殘差矩陣表示為H

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

基于此，H可被表示為

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

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

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

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

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

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

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

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

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

2.2.6 復(fù)雜度分析

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

3 實(shí)驗(yàn)仿真與分析

3.1 實(shí)驗(yàn)環(huán)境

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

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

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

3.2 初始化結(jié)果

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

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

3.3 實(shí)驗(yàn)分析

3.3.1 SFC 部署評(píng)價(jià)指標(biāo)

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

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

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

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

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

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

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

3.3.2 部署結(jié)果分析

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

圖5 顯示了請(qǐng)求接收率的對(duì)比結(jié)果。結(jié)果表明，本文算法能夠接收所有到達(dá)系統(tǒng)的網(wǎng)絡(luò)請(qǐng)求，當(dāng)系統(tǒng)達(dá)到穩(wěn)定狀態(tài)后，F(xiàn)F 算法與SFC-MCT 算法的成功率在85%左右，因此，本文算法性能明顯優(yōu)于對(duì)比算法。這是因?yàn)闊o論是基于啟發(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)境便對(duì)它們的有效性提出了考驗(yàn)。隨著網(wǎng)絡(luò)資源逐漸被分配，SFC 匹配到既滿足依賴關(guān)系又能達(dá)到服務(wù)質(zhì)量的物理資源的請(qǐng)求接收率便有所下降。

圖5 請(qǐng)求接收率的對(duì)比結(jié)果

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

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

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

圖7 運(yùn)行時(shí)間的對(duì)比結(jié)果

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

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

圖9 節(jié)點(diǎn)開啟量的對(duì)比結(jié)果

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

4 結(jié)束語

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