基于改進深度強化學習的虛擬網絡功能部署優化算法

唐 倫 賀蘭欽* 連沁怡 譚 頎

1 引言

近年來，網絡功能虛擬化技術作為網絡服務提供的一個重要范式轉變，受到了業界和學術界廣泛的關注，在網絡功能虛擬化 (Network Function Virtualization， NFV)架構下，一系列虛擬網絡功能 (Virtual Network Function， VNF)按照特定的順序構成的服務功能鏈(Service Function Chain，SFC)為用戶提供服務[1]，相同類型的VNF可以部署或者重新實例化在不同通用服務器上，不需要重新購買硬件。

在網絡功能虛擬化/軟件定義網絡 (Network Function Virtualization/Software Defined Network， NFV/SDN)架構下，VNF部署需要解決問題的關鍵是如何在有限的物理資源中選擇滿足服務需求的物理通用服務器和物理鏈路進行部署，在保證網絡性能的同時，最大化資源利用率[2]。

目前，已有大量工作對VNF部署機制展開了研究，其中，文獻[3]在保證用戶服務質量(Quality of Service， QoS)的同時，減少運營商的成本，但是它采用的是靜態VNF部署策略，由于網絡環境是動態變化的，需要考慮長時間的優化，文獻[4]在SFC部署的時候，以最小化SFC端到端時延為目標，通過減少SFC傳輸時延和處理時延達到減少SFC端到端時延的目的，但是沒有關注到物理網絡資源利用率的情況，在文獻[5]中，在考慮服務器資源容量和流速率的同時，平衡VNF的操作成本、維護VNF實例成本以及VNF部署成本，但是沒有考慮SFC時延，進而忽略了用戶的QoS。

綜上所述，在目前研究VNF部署的相關文獻中，大多數文獻研究都是基于環境狀態已知的情況下，沒有考慮到環境隨時間的動態變化，而且沒有考慮到大量的網絡業務請求達到，引起業務請求積壓，進而影響網絡穩定性問題，而且在考慮SFC部署成本的同時，沒有保證用戶的QoS。本文針對網絡服務請求動態到達引起的SFC部署優化問題，提出了一種基于改進深度強化學習的虛擬網絡功能部署算法，本文主要貢獻有：(1) 將隨機優化問題建立為馬爾科夫決策過程(Markov Decision Process，MDP)模型，該模型聯合優化SFC端到端時延和SFC部署成本，同時受限于每條SFC的端到端時延以及通用服務器CPU資源、物理鏈路帶寬資源約束；(2) 在VNF部署和資源分配的過程中，存在狀態空間過大、動作空間維度高、狀態轉移概率未知等問題，提出了一種基于深度強化學習的VNF智能部署算法，本算法通過神經網絡近似最優動作值函數，從而得到近似最優的VNF部署策略和資源分配策略；(3) 針對深度強化學習代理通過ε貪婪算法進行動作探索和利用，造成神經網絡學習效率低、收斂速度慢等問題，提出了一種基于值函數差異的動作探索和利用方法，并進一步采用雙重經驗回放池，解決經驗樣本利用率低的問題，加速訓練神經網絡。

2 系統模型

2.1 網絡場景

本文采用NFV編排和控制架構[6]，如圖1所示，主要分為3層。

2.2 網絡模型

2.2.1 物理網絡

圖1 系統模型

2.2.4 SFC部署成本模型

2.2.3 SFC時延模型

2.3 優化目標

本文主要考慮的問題是：在保證用戶時延的同時最小化SFC的部署成本，并將物理通用服務器的CPU資源、物理鏈路帶寬資源以及SFC端到端時延作為約束條件，設計了一個效用函數U(t)，將其定義為

該優化目標受到C1～C6限制條件約束，保證優化目標的有效性。C1用于保證虛擬網絡中每個VNF只能選擇一個服務器進行映射。C2確保每臺通用服務器分配給映射在其上的VNF CPU資源之和不能超過該通用服務器的CPU容量。C3用于保證通用服務器的資源利用率，即每臺通用服務器的剩余CPU資源低于閾值，否則將不會使用，進一步達到節能的效果。C4表示映射到某條物理鏈路上的所有虛擬鏈路數據量之和不能超過該物理鏈路的總帶寬資源。C5用于保證每條SFC的隊列長度不溢出。C6用于保證每條SFC在任何時隙都要滿足時延要求。C7表示VNF映射的二進制變量。

本文將該隨機優化問題轉化成一個MDP模型，主要包含狀態空間、動作空間和回報函數。

設狀態空間為 X，且定義x(t)表示網絡在時隙t時的狀態，由每條SFC的隊列狀態，物理鏈路帶寬剩余資源和通用服務器剩余CPU資源構成，其表達式為

值得注意的是，動作空間需要滿足式(7)中的約束C1～C6。

在網絡狀態x(t)采取動作a(t)后，網絡環境會得到即時獎勵r(x(t)，a(t))，本文的獎勵為效用函數，則r(x(t)，a(t))定義為

設網絡初始狀態x(0)的動作策略為π ，即π :x →a，具體表示為

通常最優策略 π*是通過動作值函數Qπ(x，a)得到的，即

動作值函數Qπ(x(t)，a(t))是用來評判當前狀態為x(t)時選擇行為a(t)的好壞，可以通過貝爾曼方程迭代獲得，即

其中，γ ∈(0，1)表示折扣因子。

則最優動作值函數Q*(x(t)，a(t))可以表示為

最優動作值函數Q*(x(t)，a(t))對應著當前狀態x(t)下采取的最優動作a*(t)，將其表示為

3 基于改進深度強化學習的VNF部署算法

由式(15)知，當獲取到每時隙狀態的最優值函數，便可得到狀態對應的最優動作，且每時隙的最優動作就構成了最優策略π *，由于本文中數據包的到達是隨機的，狀態轉移概率很難獲知，因此無法使用值迭代的方式進行求解，同時，傳統的基于模型的優化方法通常要作一些假設，存在一定的局限性。根據式(7)，本文的關鍵問題是確定待VNF部署的目標服務器和資源分配策略，文獻[10]中的Q學習算法可以用來直接解決上述問題，但是本文的狀態空間和動作空間都是連續值集合，Q學習算法面臨維度災、收斂速度慢等問題。本文接下來提出一種基于改進深度確定性策略梯度(Deep Deterministic Policy Gradient， DDPG)的虛擬網絡功能在線部署算法，該算法通過神經網絡近似動作值函數，解決維度災的問題，并且通過基于探索的值函數差異(Value-Difference Based Exploration， VDBE)方法[11]擴展ε貪婪策略，平衡代理在動作選取時的探索和利用問題，進一步針對傳統深度強化學習算法從經驗回放池中抽取訓練樣本利用效率低的問題，設置了雙重經驗回放池，加速神經網絡的訓練速度。改進的深度強化學習算法框架如圖2所示。

圖2 改進深度強化學習算法框架

在該算法框架中，式(14)中Q*(x(t)，a(t))的值是通過critic網絡中估計Q網絡近似得到，即

其中， θQ表示估計Q網絡的權重，a(t)是通過actor網絡輸出得到的。

critic網絡中的TD-error定義為

進一步，估計Q網絡的損失函數就可以表示為

當從經驗回放池中抽取 N個樣本時，損失函數就變為

然后采用隨機梯度下降算法對估計Q網絡的參數進行更新。

actor網絡的作用是得到一個確定性策略π(x，θμ)，其中θμ表示估計actor網絡的權重，等到神經網絡參數訓練完成之后，就可以得到近似最優策略，即

其中，Q(x(t)，a(t)，θQ)是通過估計Q網絡得到的。

在經驗回放池抽取 N個樣本后，策略梯度可以轉化為

最后，為了探索最優動作，篩選出更好的策略問題，引入隨機噪聲，從而獲得動作，即

其中， N表示隨機過程。

其中， σ表示一個正數，稱為反向靈敏度，σ 的值越小，探索概率就越大，δ ∈[0，1)表示所選動作對探索概率的影響參數，通常δ的值為當前狀態下可以采取動作總數的倒數[11]，即δ =1/|A(x)|。

在深度強化學習代理開始訓練的時候，通常將h(x(0))設置為1。另外，由于本文的狀態空間過大，因此本文采用深度神經網絡去近似h(x(t))的值，然后將該深度神經網絡定義為? 網絡。

該神經網絡的輸入為狀態(x(t))，輸出為?h(x(t))，即

該神經網絡的參數通過最小化損失函數L(w)進行訓練，表示為

其中， w表示網絡的權重，y(t)表示目標值，將其表示為

從經驗回放池抽取 N個樣本后，h 網絡的損失函數通過式(27)計算得到

最后采用隨機梯度下降算法對 h網絡參數w 進行更新。

另外，由于傳統的深度強化學習算法對經驗回放池的樣本是隨機采樣，有些無用的樣本被重復使用，導致樣本的利用率低下，于是本文提出雙重經驗回放池架構，利用TD-error的值來區分樣本的好壞，當TD-error的絕對值很大的，δ(t)＞Λ，其中， Λ表示一個正數，說明當前樣本對神經網絡的權重改變大，給神經網絡帶來的信息量多，在后面的訓練過程中，優先選擇該樣本[12]。于是將這種樣本存儲到有效經驗回放池中，另外，考慮到一般性，防止過擬合的現象發生，同時也需要從所有的樣本值進行隨機采樣，于是在每個時隙，假設深度強化學習代理需要抽取的樣本集大小為 N，則從有效經驗回放池中抽取(1-γ)·N個樣本，從一般經驗回放池中抽取γ·N個樣本進行訓練，其中γ表示權重值。

4 性能仿真與分析

為了評估算法的有效性以及收斂性，本文將SFC端到端時延、SFC部署成本、資源利用率等作為算法評價標準，對所提算法進行仿真驗證。為了更好地評估基于改進深度強化學習的VNF在線部署算法的有效性，與文獻[13]基于遺傳算法(Genetic Algorithm，GA)的VNF部署算法，文獻[14]中的DDPG算法以及文獻[15]中的深度信念網絡-服務功能鏈 (Deep Q Network-Service Function Chain， DQN-SFC)算法進行了對比，所有仿真實驗均在i7 CPU和內存為8 GB的主機上運行，仿真平臺主要基于Python 3.6，通過TensorFlow模塊對神經網絡進行搭建。

4.1 參數設置

本文假設物理網絡為全連接網絡，其中包括6臺物理通用服務器，假設每條SFC由2～5個VNF構成，另外參考文獻[9]對相關參數進行設置，具體網絡參數如表1所示。

4.2 仿真分析

由于本文數據包的到達是隨機的、狀態空間大以及VNF部署和資源分配的動作空間維度高，因此采用改進深度強化學習算法去近似狀態Q值，得到近似最優的VNF部署和資源分配策略，圖3證明了本文所提改進深度強化學習算法收斂性，并且在相同的學習率α=0.0001下，對比DDPG算法，在訓練50次的時候，改進深度強化學習算法已經收斂，而DDPG算法大約在訓練100次的時候收斂，因此改進的深度強化學習算法能夠快速收斂，原因是本文所提算法在DDPG算法基礎上，改進動作探索和利用，解決經驗池樣本利用率低的問題。

表1 網絡場景的仿真參數

圖4、圖5分別表示在相同的SFC數量下，本文所提基于改進深度強化學習的VNF在線部署算法與其他3種算法在系統總時延和部署成本方面的對比。在此仿真過程中，設置權重值e1，e2都為0.5。

圖3 損失函數對比

圖4 系統總時延對比

從圖4、圖5可以看出，隨著SFC數量的增加，4種算法下的部署成本和系統總時延都將增大，由于GA算法只對時延進行優化，所以它的系統總時延是最低的，但是其沒有考慮VNF的部署成本，沒有進行合理的資源分配，導致其產生的部署成本是最大的，DQN-SFC算法由于同時優化時延和部署失敗產生的運維開銷，故它的總時延比GA算法要高，其次，DQN算法適用于解決離散的動作空間，由于本文的動作空間是連續值，故DQNSFC算法在優化時延和VNF部署成本方面明顯劣于DDPG算法和改進深度強化學習算法，而且改進深度強化學習算法比DDPG算法在部署成本和系統總時延方面更低，這是因為改進深度強化學習算法在DDPG算法基礎上通過狀態值函數差異去刻畫每時隙動作的探索率，使其能夠找到更優的動作，進而獲得更好的獎勵值，因此改進深度強化學習算法的效用是最大的，如圖6所示，由于隨SFC數量增加時系統總時延和總部署成本增大，導致效用也會隨SFC數量增加而減少，其中，DQN-SFC算法的效用下降最快，而改進深度強化學習中的效用下降最慢。

圖5 部署成本對比

圖6 效用對比

5 結論

針對NFV/SDN架構下網絡服務請求動態到達引起的VNF部署優化問題，本文首先將隨機優化問題建立為一個MDP模型，該模型以最小化SFC部署成本和時延成本為目標，同時受限于每條SFC時延、通用服務器CPU資源以及物理鏈路帶寬資源約束，其次提出一種基于改進深度強化學習的VNF在線部署算法，通過深度神經網絡去近似最優的動作狀態值函數，從而獲得近似最優的VNF部署策略和資源分配策略，最后提出一種基于探索的值函數差異方法去動態地刻畫動作探索率，并采用雙重經驗回放池，解決經驗樣本利用率低的問題。仿真結果顯示，本文所提算法能夠加速收斂，并能夠優化SFC端到端時延和部署成本。