基于深度確定性策略梯度的虛擬網(wǎng)絡(luò)功能遷移優(yōu)化算法

唐 倫 賀蘭欽 譚 頎 陳前斌

(重慶郵電大學(xué)通信與信息工程學(xué)院 重慶 400065)

(重慶郵電大學(xué)移動通信技術(shù)重點實驗室 重慶 400065)

1 引言

在軟件定義網(wǎng)絡(luò)(Software Defined Network,SDN)環(huán)境下，網(wǎng)絡(luò)功能虛擬化(Network Function Virtualization, NFV)技術(shù)根據(jù)當(dāng)前的用戶服務(wù)請求創(chuàng)建服務(wù)功能鏈(Service Function Chain, SFC),SFC由多個虛擬網(wǎng)絡(luò)功能(Virtual Network Function,VNF)按照特定的順序編排構(gòu)成[1]，將VNF部署在不同服務(wù)器上，進而為用戶提供服務(wù)，增強了網(wǎng)絡(luò)的靈活性以及拓展性，使得基礎(chǔ)設(shè)施資源高效利用[2]。由于SFC的資源需求是動態(tài)變化的，帶來了資源利用率低等問題，因此研究VNF遷移機制十分有必要。

目前，已有大量工作對VNF遷移機制展開了研究，主要考慮觸發(fā)VNF遷移的時機，待遷移VNF的選擇和遷移的目的節(jié)點選擇，文獻[3]考慮在某臺服務(wù)器的資源利用率過低時，觸發(fā)VNF聚合，將該服務(wù)器上的所有VNF遷移至其他服務(wù)器，進入休眠狀態(tài)，降低系統(tǒng)的整體能量消耗，但是沒有考慮用戶服務(wù)質(zhì)量(Quality of Service, QoS)降低，而且當(dāng)服務(wù)器的資源利用率達到閾值時立即觸發(fā)遷移，會造成頻繁遷移，降低系統(tǒng)的穩(wěn)定性。文獻[4]主要考慮低時延網(wǎng)絡(luò)，當(dāng)系統(tǒng)監(jiān)測到VNF遷移后能夠降低SFC端到端時延，則觸發(fā)遷移，但是忽略了VNF遷移后網(wǎng)絡(luò)能耗的增加。文獻[5]建立成本模型來評估遷移開銷，同時提出一種貪婪算法最小化VNF遷移開銷，但是它采用的是靜態(tài)遷移策略，由于網(wǎng)絡(luò)環(huán)境是動態(tài)變化的，需要考慮長時間的優(yōu)化。

綜上所述，現(xiàn)有的VNF遷移機制均沒有對網(wǎng)絡(luò)能耗最小化及SFC端到端時延最小化進行聯(lián)合考慮，而且大多數(shù)文獻研究都是基于環(huán)境狀態(tài)已知的情況下，沒有考慮到環(huán)境隨時間的動態(tài)變化，另外，針對有生命周期的SFC，在長時間尺度下研究VNF遷移的工作并不多。因此本文提出了一種基于深度確定性策略梯度(Deep Deterministic Policy Gradient, DDPG)的VNF遷移方案，該方案首先考慮SFC資源需求動態(tài)變化，在保證底層物理資源和用戶QoS需求的前提下，通過VNF遷移，并確定每個通用物理服務(wù)器的工作狀態(tài)，實現(xiàn)網(wǎng)絡(luò)能耗與SFC端到端時延的聯(lián)合優(yōu)化。其次，由于本文所提問題為隨機優(yōu)化問題，因此將該優(yōu)化問題轉(zhuǎn)換成馬爾可夫決策過程(Markov Decision Processes, MDP)。最后，由于本文的狀態(tài)轉(zhuǎn)移概率是未知的，狀態(tài)和動作空間都是連續(xù)值集合，故提出一種基于DDPG的VNF遷移算法求解MDP，得出近似最優(yōu)的VNF遷移策略。

2 系統(tǒng)模型

2.1 網(wǎng)絡(luò)場景

本文采用NFV編排和控制架構(gòu)[6]，如圖1所示，主要分為3層。應(yīng)用層主要為網(wǎng)絡(luò)業(yè)務(wù)請求創(chuàng)建SFC，通過SFC為用戶提供服務(wù)。虛擬化層主要負(fù)責(zé)網(wǎng)絡(luò)狀態(tài)監(jiān)控和底層網(wǎng)絡(luò)負(fù)載分析，物理層為SFC提供其實例化的物理資源，包括計算資源和鏈路帶寬資源，物理網(wǎng)絡(luò)主要由通用服務(wù)器組成。

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

2.2.1 物理網(wǎng)絡(luò)

2.2.2 SFC請求

圖1 系統(tǒng)模型

2.2.3 SFC時延模型

本文在計算SFC端到端時延的時候，因為傳播時延的值可以忽略不計，所以主要考慮處理時延和傳輸時延。

當(dāng)映射到服務(wù)器上的VNF資源需求增加時，將導(dǎo)致服務(wù)器的CPU負(fù)載增大，進而SFC的處理時延也將增大。參考文獻[7]，假設(shè)處理時延是處理負(fù)載的凸函數(shù)，使用分段線性化來近似凸時延曲線。所以底層物理服務(wù)器的處理時延可以表示為

其中， εi和χi表示近似凸時延函數(shù)曲線的線性函數(shù)的系數(shù)。

SFC的傳輸時延與SFC上的虛擬鏈路映射到物理鏈路的位置有關(guān)，假設(shè)每跳虛擬鏈路映射到物理鏈路的時延為djk， 第i條SFC傳輸時延為

因此，第i條 SFC的端到端時延可以表示為

2.2.4 網(wǎng)絡(luò)能耗模型

本文的網(wǎng)絡(luò)能耗主要考慮底層物理服務(wù)器的能耗，網(wǎng)絡(luò)能耗包括服務(wù)器運行狀態(tài)時能耗和服務(wù)器狀態(tài)切換時能耗P(t)，基于文獻[8]，服務(wù)器的運行狀態(tài)時能耗分為服務(wù)器待機時的能耗 P(t)和服務(wù)器CPU資源負(fù)載產(chǎn)生的能耗P(t)， 因此服務(wù)器m在t 時隙的待機能耗和CPU負(fù)載能耗，分別用式(5)和式(6)表示。

其中， Pidle表示服務(wù)器待機時產(chǎn)生的能耗，為服務(wù)器m 中CPU資源全部占用時所產(chǎn)生的能耗。

另外，參考文獻[9]，基站切換工作狀態(tài)時會有能量消耗。本文假設(shè)服務(wù)器工作狀態(tài)發(fā)生變化時會產(chǎn)生能耗， 服務(wù)器m 在 t 時隙產(chǎn)生的切換能耗為

其中，ηm(t)表 示服務(wù)器m 在t 時隙狀態(tài)是否發(fā)生了改變，用式(8)表示。

因此網(wǎng)絡(luò)能耗可以通過每臺服務(wù)器的能耗之和表示，即

2.3 優(yōu)化目標(biāo)

本文要解決的問題是：在最小化網(wǎng)絡(luò)能耗的前提下最小化SFC端到端時延，同時把底層物理資源等作為限制條件。故該優(yōu)化問題屬于多目標(biāo)優(yōu)化問題，具體表示為

其中， a1,a2是 權(quán)重系數(shù)，且a1+a2=1, Pmax表示網(wǎng)絡(luò)能耗的最大值。

該優(yōu)化目標(biāo)受到C1～C11限制條件約束，保證優(yōu)化目標(biāo)的有效性。C1用于保證一條SFC上的VNF只能選擇一個服務(wù)器進行映射。C2～C5表示物理網(wǎng)絡(luò)CPU資源和帶寬資源限制。C6表示SFC中相鄰兩個VNF映射到底層服務(wù)器 n和m 時，nm之間必須存在一條連續(xù)路徑，滿足流守恒原則。C7表示每條SFC在任意時隙都要滿足時延要求。C8表示如果某一臺服務(wù)器上有VNF映射，那么這臺服務(wù)器一定處于開啟狀態(tài)。C9～C11分別表示VNF映射，虛擬鏈路映射和底層服務(wù)器狀態(tài)的二進制變量約束。

3 本文算法

3.1 MDP模型

本文先將優(yōu)化問題建模成MDP模型，得到深度強化學(xué)習(xí)的基礎(chǔ)框架，用一個四元組(S,A,P,R)對其進行描述。

(1) 狀態(tài)空間為S：定義狀態(tài)空間為S(t)={(φ(t),c(t),b(t)|?φ ∈ψ,?c ∈C,?b ∈B} ，其中，φ 表示底層物理網(wǎng)絡(luò)拓?fù)洌?ψ表示網(wǎng)絡(luò)拓?fù)錉顟B(tài)空間，c(t), b(t)分 別表示在t 時隙VNF的CPU資源和鏈路帶寬資源需求，而 C, B則分別表示VNF的CPU資源和虛擬鏈路帶寬資源需求狀態(tài)空間：

(2) 動作空間為 A ：在t 時隙定義動作空間為A(t)={θ(t)|θ ∈Θ} ，其中θ 表示VNF的映射動作，Θ則表示VNF的映射動作空間。

(3) 狀態(tài)轉(zhuǎn)移概率為 P ：在t 時隙狀態(tài)s (t)采取動作a (t)， 將轉(zhuǎn)移到下一時隙的狀態(tài)s (t+1)，狀態(tài)轉(zhuǎn)移概率為P (s(t+1)|s(t), a(t))。

(4) 獎勵函數(shù) R：本文定義一個效用函數(shù)r (t)作為即時獎勵，通過式(10)轉(zhuǎn)化得到

環(huán)境在 t 時隙處于狀態(tài)s (t) ， 會根據(jù)策略π 采取一個動作 a(t)=π(s(t))。 通過該映射策略π ，環(huán)境在t 時隙會通過值函數(shù)Qπ(s(t),a(t))來評判采取映射動作的好壞，可以將其表示為

VNF最優(yōu)遷移策略就可以表示為

3.2 基于DDPG的VNF遷移算法

MDP 模型通常由動態(tài)規(guī)劃(Dynamic Programming,DP)或強化學(xué)習(xí)(Reinforcement Learning, RL)方法來解決[10]，因此本文采用深度強化學(xué)習(xí)算法進行求解，但是常見的深度強化學(xué)習(xí)算法如深度Q學(xué)習(xí)(Deep Q Network, DQN)[11]等不適合解決連續(xù)動作問題，因此本文提出一種基于DDPG的虛擬網(wǎng)絡(luò)功能遷移算法，DDPG算法以確定性策略梯度(Deterministic Policy Gradient, DPG)算法為基礎(chǔ)，首先采用行動者-評判家(Actor-Critic, AC)框架，其次在評判家網(wǎng)絡(luò)和行動者網(wǎng)絡(luò)里面采用雙神經(jīng)網(wǎng)絡(luò)架構(gòu)，分別構(gòu)成了估計行動者網(wǎng)絡(luò)( θπ)，目標(biāo)行動者網(wǎng)絡(luò)( θπ′)， 估計評判家網(wǎng)絡(luò)( θQ)與目標(biāo)評判家網(wǎng)絡(luò)( θQ′) ， 其中θπ, θπ′, θQ和θQ′分別代表各個深度神經(jīng)網(wǎng)絡(luò)的權(quán)重值，并且它們具有相同的神經(jīng)網(wǎng)絡(luò)架構(gòu)。最后采用經(jīng)驗回放池打破數(shù)據(jù)的關(guān)聯(lián)性和非平穩(wěn)分布問題。

在評判家網(wǎng)絡(luò)中，估計critic網(wǎng)絡(luò)負(fù)責(zé)近似式(13)中的Q值函數(shù)，即

近似過程通過深度神經(jīng)網(wǎng)絡(luò)(Deep Neural Network, DNN)完成。首先對輸入的狀態(tài) s(t)和VNF映射動作 a (t)進行預(yù)處理，文獻[12]通過狀態(tài)標(biāo)準(zhǔn)化來預(yù)處理訓(xùn)練樣本狀態(tài)，加快梯度下降求最優(yōu)解的速度，進而加快神經(jīng)網(wǎng)絡(luò)模型的訓(xùn)練，因此本文對狀態(tài)和動作做歸一化處理。

最后，DNN的輸出為當(dāng)前狀態(tài)s (t)采取VNF映射動作a (t)對 應(yīng)的Q (s(t),a(t))值，而在對估計評判家網(wǎng)絡(luò)進行參數(shù)更新時，主要通過最小化損失函數(shù)，即

當(dāng)損失函數(shù)對參數(shù)θQ連續(xù)可微時，估計評判家網(wǎng)絡(luò)參數(shù)可以用損失函數(shù)的梯度進行更新，即

其中，lc表示估計評判家網(wǎng)絡(luò)的學(xué)習(xí)率。

在行動者網(wǎng)絡(luò)中，估計行動者網(wǎng)絡(luò)使用策略梯度算法評估和改進策略，該算法會迭代評估策略，然后按照梯度進行改進以優(yōu)化策略。策略梯度更新思想為：代理根據(jù)采取某種動作得到結(jié)果的好壞而決定是否增加或者減少采取該動作的可能性。

估計行動者網(wǎng)絡(luò)同樣采取DNN架構(gòu)，將預(yù)處理后的狀態(tài)s ? (t) 作 為輸入，輸出為當(dāng)前環(huán)境狀態(tài)s(t)采取的策略π (s(t)|θπ)。對估計行動者網(wǎng)絡(luò)參數(shù)更新時，先從經(jīng)驗回放池隨機抽取一部分樣本訓(xùn)練DNN參數(shù)，接著以最大化長期平均回報為目標(biāo)，迭代改進策略，策略目標(biāo)函數(shù)可以表示為

其中，d (s(t))表示狀態(tài)分布，然后對策略目標(biāo)函數(shù)偏微分，得到策略目標(biāo)函數(shù)梯度

其中， Qπ(s(t),a(t))通過估計critic網(wǎng)絡(luò)近似得到。如果式(14)中， QθQ(s(t),a(t)) 很 接近Qπ(s(t),a(t))，就可以用QθQ(s(t),a(t))代 替Qπ(s(t),a(t))，將式(18)轉(zhuǎn)化為

最后沿著目標(biāo)策略函數(shù)梯度上升方向更新DNN參數(shù)

其中，la表 示估計actor網(wǎng)絡(luò)的學(xué)習(xí)率。

為了探索VNF遷移最優(yōu)動作，篩選出更好的策略問題，DDPG算法引入隨機噪聲 n，從而獲得動作a (t)，即

其中，n 表示高斯隨機噪聲，均值為n0。

目標(biāo)評判家網(wǎng)絡(luò)和目標(biāo)行動者網(wǎng)絡(luò)采用軟更新參數(shù)，可以將其表示為

具體的VNF遷移策略訓(xùn)練如表1所示。

4 性能仿真與分析

本文通過調(diào)整評判家網(wǎng)絡(luò)的學(xué)習(xí)率 lc ，保持行動者網(wǎng)絡(luò)的學(xué)習(xí)率不變，驗證DDPG算法的收斂性能。由圖2可以看出，當(dāng)評判家網(wǎng)絡(luò)學(xué)習(xí)率 lc為0.0020時，損失函數(shù)的收斂速度最快，抖動最明顯，但是梯度可能會在最小值附近來回波動，容易得到局部極小值，隨著學(xué)習(xí)率的降低，收斂速度較緩慢，但是損失函數(shù)曲線較平穩(wěn)，會使得在收斂時，損失函數(shù)值更加趨近于最優(yōu)值。由圖3可以看出，當(dāng)評判家網(wǎng)絡(luò)學(xué)習(xí)率 lc為0.0010時，得到的累積獎勵值最多，更加利于本文求得最優(yōu)解。因此本文選取評判家學(xué)習(xí)率l c為0.0010。

本文將權(quán)重 a1分別取值為0.7, 0.5和0.3，驗證算法的有效性，考慮應(yīng)用層有10條SFC的情況下，經(jīng)過15000次訓(xùn)練迭代后，得到系統(tǒng)總時延和網(wǎng)絡(luò)能耗情況如圖4、圖5所示。隨著 a1的減小，系統(tǒng)總時延占的優(yōu)化比重減小，故收斂時的時延值逐漸增大。隨著 a2的增大，網(wǎng)絡(luò)能耗占的優(yōu)化比重增大，故收斂時的能耗值逐漸增大?；谝陨戏治?，本文算法能夠在優(yōu)化網(wǎng)絡(luò)能耗的同時，降低遷移帶來的時延增量，保證用戶的QoS。

本文首先從DDPG算法可以實現(xiàn)系統(tǒng)總時延與網(wǎng)絡(luò)能耗聯(lián)合優(yōu)化的角度，與遷移僅實現(xiàn)SFC端到端時延最小化的實時VNF遷移(Virtual Network Functions Real-time Migration, VNF-RM)算法[4]，及僅實現(xiàn)網(wǎng)絡(luò)能耗最小化的VNF映射最小化能耗(VNFI Mapping Minimizing the Power Consumption, VMMPC)算法[13]進行對比，驗證算法的性能。此時a1=0.5, a2=0.5。

仿真參數(shù)

圖2 不同評判家學(xué)習(xí)率下的損失函數(shù)值

圖3 不同評判家學(xué)習(xí)率下的累積獎勵值

圖4 權(quán)重對系統(tǒng)總時延的影響

圖5 權(quán)重對系統(tǒng)總能耗的影響

從圖6，圖7可以看出，由于VNF-RM算法只考慮在VNF遷移前后，SFC端到端時延是否減少，而忽略了對底層低負(fù)載服務(wù)器的整合，因此通過VNF-RM算法得到的能耗必然會高于通過DDPG算法得到的能耗。同樣地，VMMPC算法盡可能整合底層服務(wù)器資源，最小化網(wǎng)絡(luò)能耗，但是沒有考慮SFC端到端時延是否增加，因此通過VMMPC算法得到的SFC端到端時延必然會大于通過DDPG算法得到的SFC端到端時延?；谝陨戏治?，DDPG算法能夠?qū)崿F(xiàn)網(wǎng)絡(luò)能耗與系統(tǒng)總時延的聯(lián)合優(yōu)化。

其次，本文與同樣可以實現(xiàn)網(wǎng)絡(luò)能耗與SFC端到端時延聯(lián)合優(yōu)化的AC(Actor-Critic)算法進行對比，得到物理網(wǎng)絡(luò)計算資源利用率情況如圖8所示，由于AC算法主要取決于Critic的價值判斷，但是Critic難收斂，再加上Actor的更新，就更難收斂，故AC算法很容易得到一個局部最優(yōu)解，DDPG算法通過神經(jīng)網(wǎng)絡(luò)近似價值函數(shù)，解決了收斂難問題，因此通過AC算法得到的資源利用率必然要低于通過DDPG算法得到的資源利用率，進一步說明在VNF遷移過程中，DDPG算法能夠有效提升物理網(wǎng)絡(luò)計算資源利用率。

圖6 系統(tǒng)總時延對比

圖7 網(wǎng)絡(luò)能耗對比

圖8 計算資源利用率

5 結(jié)束語

本文基于NFV/SDN架構(gòu)，針對 SFC資源需求動態(tài)變化引起的VNF遷移問題，聯(lián)合優(yōu)化SFC時延與系統(tǒng)能耗，然后將該隨機優(yōu)化問題建立成MDP模型，由于狀態(tài)轉(zhuǎn)移概率未知，以及狀態(tài)空間過大和動作維度高，本文提出一個基于DDPG算法的VNF遷移方案，通過VNF遷移，實現(xiàn)收益最大化。仿真結(jié)果顯示，本文所提算法能夠有效地收斂，并可以實現(xiàn)SFC時延和網(wǎng)絡(luò)能耗折中，提高服務(wù)器資源利用率。