基于改進(jìn)深度強(qiáng)化學(xué)習(xí)的虛擬網(wǎng)絡(luò)功能部署優(yōu)化算法

唐 倫 賀蘭欽* 連沁怡 譚 頎

1 引言

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

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

目前，已有大量工作對(duì)VNF部署機(jī)制展開(kāi)了研究，其中，文獻(xiàn)[3]在保證用戶服務(wù)質(zhì)量(Quality of Service， QoS)的同時(shí)，減少運(yùn)營(yíng)商的成本，但是它采用的是靜態(tài)VNF部署策略，由于網(wǎng)絡(luò)環(huán)境是動(dòng)態(tài)變化的，需要考慮長(zhǎng)時(shí)間的優(yōu)化，文獻(xiàn)[4]在SFC部署的時(shí)候，以最小化SFC端到端時(shí)延為目標(biāo)，通過(guò)減少SFC傳輸時(shí)延和處理時(shí)延達(dá)到減少SFC端到端時(shí)延的目的，但是沒(méi)有關(guān)注到物理網(wǎng)絡(luò)資源利用率的情況，在文獻(xiàn)[5]中，在考慮服務(wù)器資源容量和流速率的同時(shí)，平衡VNF的操作成本、維護(hù)VNF實(shí)例成本以及VNF部署成本，但是沒(méi)有考慮SFC時(shí)延，進(jìn)而忽略了用戶的QoS。

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

2 系統(tǒng)模型

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

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

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

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

圖1 系統(tǒng)模型

2.2.4 SFC部署成本模型

2.2.3 SFC時(shí)延模型

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

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

該優(yōu)化目標(biāo)受到C1～C6限制條件約束，保證優(yōu)化目標(biāo)的有效性。C1用于保證虛擬網(wǎng)絡(luò)中每個(gè)VNF只能選擇一個(gè)服務(wù)器進(jìn)行映射。C2確保每臺(tái)通用服務(wù)器分配給映射在其上的VNF CPU資源之和不能超過(guò)該通用服務(wù)器的CPU容量。C3用于保證通用服務(wù)器的資源利用率，即每臺(tái)通用服務(wù)器的剩余CPU資源低于閾值，否則將不會(huì)使用，進(jìn)一步達(dá)到節(jié)能的效果。C4表示映射到某條物理鏈路上的所有虛擬鏈路數(shù)據(jù)量之和不能超過(guò)該物理鏈路的總帶寬資源。C5用于保證每條SFC的隊(duì)列長(zhǎng)度不溢出。C6用于保證每條SFC在任何時(shí)隙都要滿足時(shí)延要求。C7表示VNF映射的二進(jìn)制變量。

本文將該隨機(jī)優(yōu)化問(wèn)題轉(zhuǎn)化成一個(gè)MDP模型，主要包含狀態(tài)空間、動(dòng)作空間和回報(bào)函數(shù)。

設(shè)狀態(tài)空間為 X，且定義x(t)表示網(wǎng)絡(luò)在時(shí)隙t時(shí)的狀態(tài)，由每條SFC的隊(duì)列狀態(tài)，物理鏈路帶寬剩余資源和通用服務(wù)器剩余CPU資源構(gòu)成，其表達(dá)式為

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

在網(wǎng)絡(luò)狀態(tài)x(t)采取動(dòng)作a(t)后，網(wǎng)絡(luò)環(huán)境會(huì)得到即時(shí)獎(jiǎng)勵(lì)r(x(t)，a(t))，本文的獎(jiǎng)勵(lì)為效用函數(shù)，則r(x(t)，a(t))定義為

設(shè)網(wǎng)絡(luò)初始狀態(tài)x(0)的動(dòng)作策略為π ，即π :x →a，具體表示為

通常最優(yōu)策略 π*是通過(guò)動(dòng)作值函數(shù)Qπ(x，a)得到的，即

動(dòng)作值函數(shù)Qπ(x(t)，a(t))是用來(lái)評(píng)判當(dāng)前狀態(tài)為x(t)時(shí)選擇行為a(t)的好壞，可以通過(guò)貝爾曼方程迭代獲得，即

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

則最優(yōu)動(dòng)作值函數(shù)Q*(x(t)，a(t))可以表示為

最優(yōu)動(dòng)作值函數(shù)Q*(x(t)，a(t))對(duì)應(yīng)著當(dāng)前狀態(tài)x(t)下采取的最優(yōu)動(dòng)作a*(t)，將其表示為

3 基于改進(jìn)深度強(qiáng)化學(xué)習(xí)的VNF部署算法

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

圖2 改進(jìn)深度強(qiáng)化學(xué)習(xí)算法框架

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

其中， θQ表示估計(jì)Q網(wǎng)絡(luò)的權(quán)重，a(t)是通過(guò)actor網(wǎng)絡(luò)輸出得到的。

critic網(wǎng)絡(luò)中的TD-error定義為

進(jìn)一步，估計(jì)Q網(wǎng)絡(luò)的損失函數(shù)就可以表示為

當(dāng)從經(jīng)驗(yàn)回放池中抽取 N個(gè)樣本時(shí)，損失函數(shù)就變?yōu)?/p>

然后采用隨機(jī)梯度下降算法對(duì)估計(jì)Q網(wǎng)絡(luò)的參數(shù)進(jìn)行更新。

actor網(wǎng)絡(luò)的作用是得到一個(gè)確定性策略π(x，θμ)，其中θμ表示估計(jì)actor網(wǎng)絡(luò)的權(quán)重，等到神經(jīng)網(wǎng)絡(luò)參數(shù)訓(xùn)練完成之后，就可以得到近似最優(yōu)策略，即

其中，Q(x(t)，a(t)，θQ)是通過(guò)估計(jì)Q網(wǎng)絡(luò)得到的。

在經(jīng)驗(yàn)回放池抽取 N個(gè)樣本后，策略梯度可以轉(zhuǎn)化為

最后，為了探索最優(yōu)動(dòng)作，篩選出更好的策略問(wèn)題，引入隨機(jī)噪聲，從而獲得動(dòng)作，即

其中， N表示隨機(jī)過(guò)程。

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

在深度強(qiáng)化學(xué)習(xí)代理開(kāi)始訓(xùn)練的時(shí)候，通常將h(x(0))設(shè)置為1。另外，由于本文的狀態(tài)空間過(guò)大，因此本文采用深度神經(jīng)網(wǎng)絡(luò)去近似h(x(t))的值，然后將該深度神經(jīng)網(wǎng)絡(luò)定義為? 網(wǎng)絡(luò)。

該神經(jīng)網(wǎng)絡(luò)的輸入為狀態(tài)(x(t))，輸出為?h(x(t))，即

該神經(jīng)網(wǎng)絡(luò)的參數(shù)通過(guò)最小化損失函數(shù)L(w)進(jìn)行訓(xùn)練，表示為

其中， w表示網(wǎng)絡(luò)的權(quán)重，y(t)表示目標(biāo)值，將其表示為

從經(jīng)驗(yàn)回放池抽取 N個(gè)樣本后，h 網(wǎng)絡(luò)的損失函數(shù)通過(guò)式(27)計(jì)算得到

最后采用隨機(jī)梯度下降算法對(duì) h網(wǎng)絡(luò)參數(shù)w 進(jìn)行更新。

另外，由于傳統(tǒng)的深度強(qiáng)化學(xué)習(xí)算法對(duì)經(jīng)驗(yàn)回放池的樣本是隨機(jī)采樣，有些無(wú)用的樣本被重復(fù)使用，導(dǎo)致樣本的利用率低下，于是本文提出雙重經(jīng)驗(yàn)回放池架構(gòu)，利用TD-error的值來(lái)區(qū)分樣本的好壞，當(dāng)TD-error的絕對(duì)值很大的，δ(t)＞Λ，其中， Λ表示一個(gè)正數(shù)，說(shuō)明當(dāng)前樣本對(duì)神經(jīng)網(wǎng)絡(luò)的權(quán)重改變大，給神經(jīng)網(wǎng)絡(luò)帶來(lái)的信息量多，在后面的訓(xùn)練過(guò)程中，優(yōu)先選擇該樣本[12]。于是將這種樣本存儲(chǔ)到有效經(jīng)驗(yàn)回放池中，另外，考慮到一般性，防止過(guò)擬合的現(xiàn)象發(fā)生，同時(shí)也需要從所有的樣本值進(jìn)行隨機(jī)采樣，于是在每個(gè)時(shí)隙，假設(shè)深度強(qiáng)化學(xué)習(xí)代理需要抽取的樣本集大小為 N，則從有效經(jīng)驗(yàn)回放池中抽取(1-γ)·N個(gè)樣本，從一般經(jīng)驗(yàn)回放池中抽取γ·N個(gè)樣本進(jìn)行訓(xùn)練，其中γ表示權(quán)重值。

4 性能仿真與分析

為了評(píng)估算法的有效性以及收斂性，本文將SFC端到端時(shí)延、SFC部署成本、資源利用率等作為算法評(píng)價(jià)標(biāo)準(zhǔn)，對(duì)所提算法進(jìn)行仿真驗(yàn)證。為了更好地評(píng)估基于改進(jìn)深度強(qiáng)化學(xué)習(xí)的VNF在線部署算法的有效性，與文獻(xiàn)[13]基于遺傳算法(Genetic Algorithm，GA)的VNF部署算法，文獻(xiàn)[14]中的DDPG算法以及文獻(xiàn)[15]中的深度信念網(wǎng)絡(luò)-服務(wù)功能鏈 (Deep Q Network-Service Function Chain， DQN-SFC)算法進(jìn)行了對(duì)比，所有仿真實(shí)驗(yàn)均在i7 CPU和內(nèi)存為8 GB的主機(jī)上運(yùn)行，仿真平臺(tái)主要基于Python 3.6，通過(guò)TensorFlow模塊對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行搭建。

4.1 參數(shù)設(shè)置

本文假設(shè)物理網(wǎng)絡(luò)為全連接網(wǎng)絡(luò)，其中包括6臺(tái)物理通用服務(wù)器，假設(shè)每條SFC由2～5個(gè)VNF構(gòu)成，另外參考文獻(xiàn)[9]對(duì)相關(guān)參數(shù)進(jìn)行設(shè)置，具體網(wǎng)絡(luò)參數(shù)如表1所示。

4.2 仿真分析

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

表1 網(wǎng)絡(luò)場(chǎng)景的仿真參數(shù)

圖4、圖5分別表示在相同的SFC數(shù)量下，本文所提基于改進(jìn)深度強(qiáng)化學(xué)習(xí)的VNF在線部署算法與其他3種算法在系統(tǒng)總時(shí)延和部署成本方面的對(duì)比。在此仿真過(guò)程中，設(shè)置權(quán)重值e1，e2都為0.5。

圖3 損失函數(shù)對(duì)比

圖4 系統(tǒng)總時(shí)延對(duì)比

從圖4、圖5可以看出，隨著SFC數(shù)量的增加，4種算法下的部署成本和系統(tǒng)總時(shí)延都將增大，由于GA算法只對(duì)時(shí)延進(jìn)行優(yōu)化，所以它的系統(tǒng)總時(shí)延是最低的，但是其沒(méi)有考慮VNF的部署成本，沒(méi)有進(jìn)行合理的資源分配，導(dǎo)致其產(chǎn)生的部署成本是最大的，DQN-SFC算法由于同時(shí)優(yōu)化時(shí)延和部署失敗產(chǎn)生的運(yùn)維開(kāi)銷(xiāo)，故它的總時(shí)延比GA算法要高，其次，DQN算法適用于解決離散的動(dòng)作空間，由于本文的動(dòng)作空間是連續(xù)值，故DQNSFC算法在優(yōu)化時(shí)延和VNF部署成本方面明顯劣于DDPG算法和改進(jìn)深度強(qiáng)化學(xué)習(xí)算法，而且改進(jìn)深度強(qiáng)化學(xué)習(xí)算法比DDPG算法在部署成本和系統(tǒng)總時(shí)延方面更低，這是因?yàn)楦倪M(jìn)深度強(qiáng)化學(xué)習(xí)算法在DDPG算法基礎(chǔ)上通過(guò)狀態(tài)值函數(shù)差異去刻畫(huà)每時(shí)隙動(dòng)作的探索率，使其能夠找到更優(yōu)的動(dòng)作，進(jìn)而獲得更好的獎(jiǎng)勵(lì)值，因此改進(jìn)深度強(qiáng)化學(xué)習(xí)算法的效用是最大的，如圖6所示，由于隨SFC數(shù)量增加時(shí)系統(tǒng)總時(shí)延和總部署成本增大，導(dǎo)致效用也會(huì)隨SFC數(shù)量增加而減少，其中，DQN-SFC算法的效用下降最快，而改進(jìn)深度強(qiáng)化學(xué)習(xí)中的效用下降最慢。

圖5 部署成本對(duì)比

圖6 效用對(duì)比

5 結(jié)論

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