NFV 中基于量子遺傳算法的網絡服務擴展算法

邱航，湯紅波，游偉，趙宇，柏溢

（信息工程大學信息技術研究所，河南 鄭州 450002）

0 引言

網絡功能虛擬化（NFV,network function virtualization）作為5G 的關鍵技術之一，使網絡服務的部署和管理變得更加靈活和高效。NFV 將傳統網絡設備解耦成通用的商用硬件（交換機或服務器等）和獨立的軟件功能，軟件功能也稱虛擬網絡功能（VNF,virtual network function），可以基于云原生技術靈活部署[1]。基于5G 服務化架構，NFV 與軟件定義網絡共同實現了5G 網絡架構的轉型，特別是基于NFV 的網絡切片技術促進了垂直行業的蓬勃發展[2]。云環境中，服務提供商接收服務請求后以虛擬網絡功能轉發圖（VNF-FG,VNF-forwarding graph）的形式部署網絡服務實例，為用戶按需提供定制化網絡服務。VNF-FG 包含一系列服務相關的VNF，并通過有向虛擬鏈路相互連接[3]。同時，各種VNF-FG 需要被部署在NFV 基礎設施（NFVI,NFV infrastructure）上才能為用戶提供服務。因此，有效的VNF-FG 部署對網絡服務的性能和資源使用開銷有著極大的影響。

當前最新的研究熱點是尋找多樣化約束和優化目標下最優的VNF-FG 部署方案[4-6]。文獻[6]將VNF-FG 部署算法分為精確式算法、啟發式算法、元啟發式算法和基于機器學習的算法。精確式算法主要采用傳統數學方法建立最優化模型，例如混合整數線性規劃[7]、混合整數二次規劃[8]，然后采用數學求解器（例如CPLEX、Gurobi 等）求解，但局限于小規模網絡求解，擴展性較差。啟發式算法[9-10]大多基于設計者來自經驗的創新性想法，較適用于實際網絡場景，通過一些操作來減少求解過程的搜索空間，但受設計者水平的影響較大，獲得最優解的性能難以保障。元啟發式算法是在啟發式算法基礎上的改進，其混合了隨機算法和局部搜索算法，常見的有遺傳算法[11]、模擬退火算法[12]等。基于機器學習的算法是近些年隨著機器學習的發展而興起的算法，主要以強化學習為主[13-14]，通過智能體與環境不斷交互訓練，最終獲得最佳部署方案。在部署完成后，用戶流量的變化也促使服務提供商必須修改運行中的VNF 實例容量以保障服務質量和優化資源使用效率[15]。VNF 實例的容量調整可分為2種方式：水平擴縮容，通過增減實例數量的方式實現；垂直擴縮容，通過修改已存在實例資源容量的方式實現[16]。此外，因為當前VNF 多采用微服務架構設計，已有部分VNF 支持通過調整內部VNF組件的容量進行細粒度擴縮容。

隨著業務類型變化和流量增長，服務提供商不僅要維持原來的服務和應用功能，還需要通過額外的轉發圖（添加新的轉發路徑、新的VNF 和新的服務鏈等）擴展其已經部署的VNF-FG 實例，進而實現服務應用升級。例如，在5G 應用中，初始部署的網絡切片以面向高清視頻通話為主，現在因為用戶數量增加導致流量增長，服務提供商需要增加用戶面功能（UPF,user plane function）進行負載分擔，避免用戶體驗質量不佳；同時，部分用戶需要使用視頻會議功能，需添加相關安全VNF 以保護視頻傳輸過程中的信息安全、減少抖動，因此服務提供商需要在初始部署網絡切片的基礎上添加額外的VNF 并調整轉發路徑，在擴展完成后提供安全保障的視頻通話業務。網絡服務擴展包含2 個階段，第一階段是初始VNF-FG 的擴展，即添加新的VNF 和虛擬鏈路；第二階段是將擴展的VNF 和虛擬鏈路部署在NFVI 以更新網絡服務和應用。需要注意的是，在網絡服務擴展過程中不能對已經部署且正在運行的服務和應用產生影響，尤其是高可靠低時延網絡服務難以容忍中斷、遷移和破壞等情況對服務質量和體驗的影響[17]。在網絡服務的生命周期內，服務提供商通過運行/業務支撐系統聯合NFV管理和編排（MANO,management and orchestration）功能，實現在滿足用戶新的應用需求或業務升級時進行網絡服務擴展。

為滿足上述需求，文獻[18]研究了動態環境中服務功能鏈的重調整問題，假設多條服務鏈可共用同種VNF，設計了一種聯合新到達服務請求的優化部署和正在運行服務鏈的再調整方法，以滿足用戶接入點變化的需求等。文獻[19]第一次提出服務圖擴展問題并將其建模為整數線性規劃，為改善精確式算法的擴展性，提出了基于斯坦納樹的VNF-FG擴展（STVE,Steiner tree based for VNF-FG extension）算法和特征分解的VNF-FG 擴展（EDVE,eigen decomposition for VNF-FG extension）算法2 種啟發式算法。STVE 算法基于斯坦納樹模型，采用最小跳最短路徑算法進行擴展網絡功能的部署；EDVE算法采用Umeyama 特征分解方法計算虛擬網絡功能轉發圖和基礎設施物理圖的最優匹配，實現網絡功能的擴展部署和路由路徑選擇。2 種算法相對數學規劃擴展性有所提高，但其復雜度仍為O(N3)。然而，未來通信需要支撐更大范圍的服務和應用，這必然導致網絡拓撲不斷擴展，而且部分網絡節點（如空天衛星、車聯網節點等）具有移動屬性而導致網絡拓撲發生變化。同時，由于用戶和行業的多樣化業務需求，運營商需要為其定制化網絡服務按需提供資源，且通過業務實時感知、測量和資源調度等手段保障業務質量，這將導致未來網絡具有更高的動態性和復雜性。上述方法采用靜態的計算方式，假設基礎設施網絡的拓撲和資源狀態不會發生變化，在動態網絡中的求解效率和最優解的質量將難以得到保障。面向未來動態復雜的云網絡場景，本文研究的網絡服務擴展問題不僅需要在應用層擴展初始VNF-FG 以添加新的VNF 和虛擬鏈路，而且需要完成擴展VNF 在基礎設施層的最優化部署。

本文主要的研究工作如下。

1) 建立云網絡中網絡服務擴展問題的整數線性規劃模型。以最小化資源開銷為目標，并滿足初始服務部署不變約束、擴展VNF 唯一性部署約束、資源容量約束，以及節點親和性約束等。該問題已被證明是一個NP 難題，在大規模網絡中計算復雜度高，求解時間長，不具備良好的擴展性。

2) 針對未來云網絡的動態性和復雜性，設計了一種基于量子遺傳算法（QGA,quantum genetic algorithm）的網絡服務擴展算法。采用量子態作為基本信息單元，利用量子態特性，通過量子并行計算來解決大規模網絡中擴展部署求解的復雜性。

3) 仿真結果表明，所提算法在擴展成功率和平均資源開銷方面與現有的最小斯坦納樹和特征分解算法相比均表現較好，驗證了所提算法的有效性。

1 系統模型

1.1 NFV 基礎設施

NFV 基礎設施可以表示為一個無向加權圖G=(N,L)，其中，N和L分別表示底層節點集合和物理鏈路集合。一個底層節點n∈N可能由一臺或多臺商用服務器構成，其通過云計算技術可以實現資源的集中池化管理并支持實例化VNF。底層節點n∈N的可用處理資源容量表示為Cn。底層節點之間通過高速光纖全雙工連接，連接節點m∈N和n∈N的物理鏈路表示為lm,n∈L，其可用帶寬為Bm,n。

1.2 VNF 轉發圖

用戶請求可以表示為一個有向加權圖Gr=(N r,Lr)，其中，Nr表示相關VNF 集合，L r表示VNF-FG 中有向虛擬鏈路的集合。對于任意VNFf∈Nr，cf表示將其實例化在一個虛擬機或者容器中需要的處理資源（包括計算、存儲和網絡等資源）。對于連接相鄰VNFf∈Nr和g∈Nr的虛擬鏈路，其帶寬需求為。因此，為了提供用戶服務請求，服務提供商必須部署所有需求的VNF，并根據虛擬鏈路的方向尋找合適的路由路徑以按照預定的順序依次通過相關VNF 序列。

此外，服務提供商需要能夠根據用戶新的應用需求提供新的網絡服務部署方案，或者通過添加額外的VNF 和虛擬鏈路擴展正在運行的網絡服務以滿足新的應用需求。對于新服務請求的部署，很多工作已經對此開展研究，本文作者團隊也做出了部分成果[20-21]。本文重點關注已部署網絡服務的擴展問題。VNF-FG 擴展示意如圖1 所示，其中，實線部分表示用戶請求的初始VNF-FG，點畫線和虛線部分分別表示因為新的應用需求和流量增長而額外添加的VNF 和虛擬鏈路。本文要解決的是一種更加通用的網絡服務擴展問題，即通過添加額外的VNF 和新的虛擬鏈路來調整網絡功能和轉發圖，不僅可以添加新類型VNF 和虛擬鏈路來匹配新的業務需求（如VNF4），而且在流量增長時可以添加已有類型VNF 以適應負載變化（如VNF2）。初始VNF-FG 已經部署在基礎設施之上并正在為用戶提供服務，為了不影響初始服務的提供，服務提供商需要在初始請求部署的基礎上執行網絡服務擴展部署，在擴展部署完成后更新以提供新的服務。擴展的VNF-FG 表示為= (Nr∪N e,Lr∪Le)，其中，Ne和Le分別表示額外添加的擴展VNF 集合和擴展虛擬鏈路集合。額外添加的VNF 種類和數量是由用戶新的應用需求決定的，而虛擬鏈路是服務提供商根據網絡服務對流量的處理順序確定的流量在VNF 之間的轉發路徑。擴展VNFf∈Ne的屬性用請求的處理資源cf表示，擴展虛擬鏈路的權重用請求的帶寬表示。特別地，如果在VNF-FG 擴展中初始虛擬鏈路的流量增加，已部署虛擬鏈路的請求帶寬應更新為初始帶寬和增加帶寬。例如，圖1 中接入點和VNF1之間的流量由于擴展VNF2而增加。

圖1 VNF-FG 擴展示意

1.3 整數線性規劃

VNF-FG 部署的優化目標直接取決于服務提供商的收益和成本，且同時需要滿足盡可能多的用戶需求。因此，本文的優化目標設置為最小化服務提供商網絡服務部署的資源使用開銷。優化目標包含底層節點處理資源開銷和物理鏈路帶寬開銷兩部分，如式(1)所示。

為統一底層節點處理資源開銷和物理鏈路帶寬開銷兩部分的計算單位，借鑒網絡資源的經濟學衡量資源方式[22]，設φ和ξ分別表示每單位底層節點處理資源和物理鏈路帶寬的價格。

網絡服務擴展過程不能影響正在提供服務的網絡服務實例的運行，即保持初始化的VNF 部署和流量路由不能改變。初始的網絡服務部署包含2 個部分：VNF 部署和虛擬鏈路映射。初始VNF 部署和虛擬鏈路路由約束分別如式(2)和式(3)所示，分別保證正在運行的VNF 部署位置和虛擬鏈路的路由路徑不變，其中，nf表示VNFf∈Nr的初始部署位置。

然后，部署擴展的VNF 和虛擬鏈路。式(4)保證每個擴展的VNFf∈Ne必須部署且僅部署在一個底層節點n∈N上，即一個VNF（可能包含多個VNF組件）不能分割部署在多個物理節點上。同時，式(5)確保部署在節點n∈N上的所有VNF 請求的處理資源之和不能超過節點可用處理資源容量。

虛擬鏈路的映射根據連接情況需要分為2 種情況討論。一種情況是當虛擬鏈路的一端是初始VNF，另一端是擴展VNF 時，根據虛擬鏈路的源節點和目的節點不同，可分為式(6)和式(7)這2 個約束。

另一種情況是擴展虛擬鏈路的兩端都是新擴展的VNF，等同于一條新虛擬鏈路的部署。新虛擬鏈路的部署必須保證在底層鏈路路由的連續性，且不能產生回路。

式(10)保證物理鏈路剩余可用帶寬必須滿足映射在其上的虛擬鏈路帶寬需求之和。

一些VNF 因為安全因素或應用需求必須部署在同一個節點上，因此式(11)也稱為節點親和性約束。

2 算法設計

VNF-FG 部署已經被證明是一個NP 難題[6]，而網絡服務擴展可以看作一個VNF-FG 部署的變體，所以VNF-FG 擴展也是一個NP 難題。考慮到未來云網絡的動態性和復雜性以及算法的擴展性，本文設計了一種基于QGA 的網絡服務擴展算法。

近年來，量子計算作為一種新的計算模式取得了長足的發展。與在傳統通用計算機上運行的經典算法相比，量子算法由于量子疊加和量子糾纏，在解決一些計算問題時要快得多。與經典算法相比的量子計算的加速通常被稱為量子霸權[23]。量子計算所展示的計算能力引起了研究人員越來越多的關注。隨著含噪聲的中等尺度量子器件的出現，探索量子計算的應用成為當前研究的熱點。文獻[24]提出了一種具有矩陣積態量子電路的Born 機器模型，該模型比一般參數化量子電路所需的量子比特更少，可以更好地利用近期量子器件中稀缺的量子比特資源。文獻[25]設計了一種改進的量子粒子群優化算法，可以改善傳統粒子群優化算法的收斂效率，并提高搜索精度。QGA 是量子計算和遺傳算法的混合產物，是一種新興的概率性進化算法[26]。由于不適當的選擇、交叉或變異操作等，遺傳算法可能出現收斂速度慢或陷入局部最優解的問題。QGA 將量子態矢量引入遺傳編碼，并采用量子邏輯門實現染色體的進化，可以實現比遺傳算法更好的效果。

2.1 量子染色體編碼

QGA 用量子比特存儲和表達一個基因。量子比特的不同之處在于它可以為|0〉態或|1〉態，或者處在2 個量子態的疊加態。因此，量子染色體通常成對出現，染色體中第i個基因用αi和βi表示，且=1。量子比特編碼使一個染色體可以同時表達多個態的疊加，因此QGA 比經典遺傳算法擁有更好的多樣性特征。相比于傳統QGA 的全隨機量子編碼，本文研究的網絡服務擴展問題涉及初始VNF 和擴展VNF。如圖2 所示，量子染色體編碼分為2 個部分，前半部分是固定編碼，表示初始VNF的位置；后半部分表示擴展VNF 可能部署的位置。本文在仿真部分采用50 個節點的網絡拓撲，因此每個VNF 的部署位置采用8 位編碼表示，總染色體的長度為總VNF 的數量乘以8，即解碼階段每8位基因確定一個VNF 的部署位置。采用這種編碼方式，一方面可以保證已部署VNF 的位置不變而不影響正在運行的網絡服務；另一方面可以減少染色體中需要進化編碼的數量，相對提高收斂速度。同時，量子門旋轉策略僅在擴展VNF 編碼部分執行以尋找最優部署位置。在染色體解碼時，需要先測量量子染色體的矢量態，然后將其解碼為0-1編碼。

圖2 量子染色體編碼

2.2 適應度計算

QGA 根據最大適應度選擇進化方向，但是網絡服務擴展的優化目標是最小化資源開銷。因此，本文采用優化目標式(1)的負值作為適應度函數。對于不滿足約束式(2)～式(11)的染色體，它的適應度被定義為一個非常小的值以作為懲罰項，便于將其在選擇和進化階段淘汰。根據染色體的適應度，量子門旋轉策略將會向最優的方向進化。

2.3 量子門旋轉策略

量子門旋轉是實現進化操作的執行者，也是QGA 中實現量子并行運算的關鍵。基于量子疊加態的編碼方式，量子門旋轉同時對一條染色體中的所有基因進行變換，即量子并行運算，使染色體向最優個體的方向進化，最后收斂獲取最優解。因為本文特殊的編碼方式，量子門旋轉操作僅在染色體的后半部分編碼執行。本文采用的量子門旋轉策略如表1 所示，且染色體中每個基因的變換策略如下。

表1 中，xi表示當前染色體的第i位編碼，besti表示當前代內最優染色體的第i位編碼；f(x)表示染色體x的適應度；s(αi,βi)表示旋轉角方向；Δθi表示旋轉角大小，其數值可以根據表1 中所列的選擇策略確定，也可以根據實際情況設定自適應變化。量子門旋轉策略是將個體當前測量值的適應度f(x)與該種群最優個體的適應度f(best)進行比較，如果f(x) ＞f(best)，則調整個體相應位置量子比特，使(αi,βi)向有利于xi出現的方向進化；相反，如果f(x) ＜f(best)，則調整個體中相應位置量子比特，使(αi,βi)向有利于besti出現的方向進化。

2.4 基于QGA 的網絡服務擴展算法

基于上述染色體編碼和量子門旋轉策略，本文在算法1中詳細描述了基于QGA的網絡服務擴展算法。步驟1)初始化QGA 參數，包含種群規模popsize 和最大迭代次數maxgen。基于初始VNF 和擴展VNF的數量計算染色體長度；在染色體初始化階段，隨機生成種群規模大小的個體數量；同時，因為量子編碼的特殊性，染色體數量是個體數量的2 倍（步驟2)～步驟3)）。由于QGA 采用量子比特作為編碼的基本單元，因此需要測量量子態，將其轉化為二進制0-1 編碼形式，再計算每個染色體對應的VNF 部署方案（步驟4)～步驟5)）。如果染色體對應的VNF 部署方案滿足約束式(2)～式(11)，則它的適應度可以根據適應度函數求得，否則它的適應度將會設為非常小的懲罰項值（步驟6)～步驟10)）。在最大迭代次數內，根據表1 定義的量子門旋轉策略執行種群進化。重復步驟4)～步驟11)，更新并記錄所有染色體對應的部署策略和適應度（步驟12)～步驟15)）。最后，根據迭代結果，輸出最優的擴展VNF 部署方案。

表1 量子門旋轉策略

算法1基于QGA 的網絡服務擴展算法

輸入G=(N,E),=(Nr∪N e,Lr∪Le)

輸出最優擴展VNF 部署方案

1) 初始化參數：種群規模popsize，最大迭代次數maxgen

2) 基于VNF 數量計算染色體長度

3) 隨機初始化生成種群

4) 測量染色體量子態并轉化為二進制編碼

5) 計算每個染色體的適應度

6) if 染色體對應的部署方案滿足約束

7) 計算當前染色體對應的適應度

8) else

9) 適應度設置為極小值

10) end if

11) 記錄最優染色體的適應度和部署方案

12) for gen=2:maxgen

13) 對種群執行量子門旋轉策略，使種群進化

14) 重復步驟4)～步驟11)

15) end for

16) 保留最優個體，輸出其對應的部署方案和適應度

3 仿真分析

本節從擴展成功數量、擴展成功率和平均資源開銷方面比較本文提出的基于QGA 的網絡服務擴展算法與STVE 算法和EDVE 算法[19]。

3.1 仿真設置

仿真在一臺64 GB 內存的Intel(R) Xeon(R) Silver 4210 CPU @ 2.20 GHz 虛擬機上進行，算法的執行工具是 MATLAB 2019b。本文使用 SNDlib 中的Germany50[27]拓撲來評估網絡服務擴展算法的性能。底層節點的處理資源容量和物理鏈路的帶寬從[100,120]unit 內隨機生成，每單位底層節點處理資源和物理鏈路帶寬的價格分別設置為φ=0.7和ξ=0.3。初始VNF-FG 的VNF 數量設置為[3,5]隨機，每個服務請求擴展的VNF 數量為[1,3]。初始VNF-FG 中每個VNF 請求的處理資源需求和虛擬鏈路的帶寬需求均為10 unit。在網絡服務擴展時，擴展VNF 的處理資源需求和虛擬鏈路的帶寬資源需求為20 unit。仿真中隨機生成1 000 個VNF-FG 請求和相應的擴展請求。不失一般性，采用文獻[21]的方法部署初始VNF-FG。

3.2 結果分析

擴展成功數量是指在滿足連接性約束和資源約束的條件下成功實現VNF-FG擴展請求在NFVI部署的數量。擴展成功率表示擴展請求成功部署數量與總擴展數量的比值。本文需要考慮擴展請求的平均部署開銷。平均部署開銷是指成功擴展VNF-FG 占用的平均資源開銷，其反映了所提算法的資源使用效率。

收斂速度是衡量一個算法性能的重要標準。本文所提基于QGA 的網絡服務擴展算法（圖中用QGA 表示）與GA 收斂速度對比如圖3 所示。從圖3 可以看出，基于QGA 的網絡服務擴展算法在收斂速度和最優個體的適應度方面均有改進，這是因為其量子比特的編碼方式可以表示量子疊加態，使染色體具有更好的多樣性；同時，量子并行計算也使搜索最優解的速度得到提升。收斂速度和最優個體的適應度證明了所提算法在實際網絡場景中獲取最優解方面的可行性。

圖3 收斂速度對比

擴展成功數量與擴展請求數量之間的關系如圖4 所示。基于QGA 的網絡服務擴展算法相對STVE 算法和EDVE 算法表現較好，擴展成功數量分別為810、753、688。因為EDVE 算法采用Umeyama 特征分解進行最優化匹配，所以它在靜態轉發圖與底層拓撲具有高相似性時表現更好，實際網絡環境的動態性和復雜性導致其在本文仿真實驗中求解性能下降。STVE 算法本質上是最短路徑策略。基于QGA 的網絡服務擴展算法的并行計算特點是對解空間的整體搜索，避免單點搜索的貪婪策略，獲得最優解的質量更高，從而提高資源利用效率。因此，基于QGA 的網絡服務擴展算法可以接受更多的擴展請求。

圖4 擴展成功數量與擴展請求數量之間的關系

擴展成功率與擴展請求數量的關系如圖5 所示。當擴展請求數量較少時，因為資源充足，所以服務擴展請求可以被完全接受。隨著擴展請求數量的增加，節點和帶寬資源逐漸被占據，導致后續的擴展請求因為資源約束而被拒絕，因此擴展成功率逐漸下降。STVE 算法采用貪婪策略，局部中心節點被過度使用以致后續擴展虛擬鏈路的請求帶寬無法滿足而導致擴展請求失敗。EDVE 算法隨著底層資源消耗拓撲匹配性下降，導致擴展成功率下降。基于QGA 的網絡服務擴展算法由于采用并行計算的方式，具有全局整體尋優的特點，因此獲得的最優解在資源使用率方面更占優勢，擴展成功率下降相對較慢。

圖5 擴展成功率與擴展請求數量之間的關系

平均資源開銷與擴展請求數量之間的關系如圖6所示。從圖6 可以看出，隨著服務請求數量增加，平均資源開銷逐漸上升。這是因為隨著擴展請求的到達，底層網絡中靠近初始VNF-FG 部署的資源被逐漸占據，導致后續的擴展方案必須擴大范圍而使平均資源開銷上升。與其他2 種算法相比，基于QGA 的網絡服務擴展算法一方面因為量子比特編碼方式提高了染色體的多樣性，避免陷入局部最優；另一方面并行計算方式有更好的全局搜索能力而獲得更高的搜索精度，所以平均資源開銷上升較慢。最后，因為擴展請求被拒絕較多，所以平均資源開銷趨于穩定。

圖6 平均資源開銷與擴展請求數量之間的關系

算法執行時間是衡量算法復雜度的一個重要指標。不同網絡規模下算法執行時間對比如圖7 所示。基于QGA 的網絡服務擴展算法在執行時間方面相較于STVE 算法和EDVE 算法具有明顯優勢，基本呈線性增長。一方面，群體智能進化算法采用群體搜索的方式，具有較好的全局搜索和并行性，使求解效率顯著提升；另一方面，量子計算采用量子疊加態作為基本單位，通過量子并行運算可以提高運算效率。因此，所提算法的時間復雜度明顯較低，且在大規模網絡中具有更好的適應性。

圖7 不同網絡規模下算法執行時間對比

4 結束語

針對服務提供過程中用戶新的應用需求或額外的安全保護機制，本文對網絡功能虛擬化環境中的網絡服務擴展方法進行研究。將網絡服務擴展分為2 個階段，分別為VNF-FG 擴展和基礎設施層部署；考慮到不影響已部署網絡服務以及底層基礎設施的資源容量約束，建立了網絡服務擴展的整數線性規劃模型；為應對未來云網絡的復雜和動態性，設計了一種基于量子遺傳算法的網絡服務擴展算法。仿真結果表明，所提算法在擴展成功率和平均資源開銷方面均具有較好的性能。