一種基于強化學習的CDN流量調(diào)度系統(tǒng)設計方法

林春鶯

(集美大學理學院，福建 廈門 361021)

0 引言

內(nèi)容分發(fā)網(wǎng)絡(content delivery network，CDN)是一種在服務提供方和消費方之間，通過架設節(jié)點或者服務器，讓用戶就近獲取所需的內(nèi)容，從而達到緩解網(wǎng)絡擁塞，提高用戶訪問網(wǎng)站響應速度的目的?；谶@種服務結構，如何有效管理不同服務的資源調(diào)度分配，保證高質(zhì)量的服務是一個需要深入研究的問題。特別是當資源處于超負荷運轉或網(wǎng)絡波動時，如何通過調(diào)度來及時選擇合適的替代資源，是保證服務質(zhì)量的關鍵。傳統(tǒng)業(yè)界的調(diào)度方式一般采用基于規(guī)則的方式[1],即，先收集大量服務器資源的指標(比如負載情況、網(wǎng)絡情況、物理位置、服務冗余度等)，再統(tǒng)計評價指標，最后以此來制定規(guī)則。但指標量越大則導致調(diào)度規(guī)則越復雜，使修改和維護成本更高，靈活性更差，同時調(diào)度策略往往只考慮服務質(zhì)量，而沒有考慮現(xiàn)實的成本問題。

近年來強化學習(reinforcement learning,RL)[2]因其強大的探索能力和自主學習能力，在游戲[3]、機器人控制[4]、交通控制[5]等領域都有廣泛的應用。在資源調(diào)度策略領域，文獻[6]利用Q值強化學習，將虛擬機資源調(diào)度描述成馬爾科夫決策過程，并設計了動作的獎勵函數(shù)，實現(xiàn)虛擬機的資源調(diào)度策略；文獻[7]將深度強化學習的思路應用到微電網(wǎng)在線優(yōu)化調(diào)度過程中；文獻[8]應用強化學習算法求解置換流水車間調(diào)度問題；文獻[9]提出DeepRM模型，將資源調(diào)度系統(tǒng)的狀態(tài)信息建模成圖像形式，將獲取的圖像信息輸入到卷積神經(jīng)網(wǎng)絡中，通過卷積神經(jīng)網(wǎng)絡對圖像信息進行快速特征提取，用強化學習的方法對神經(jīng)網(wǎng)絡中的參數(shù)進行迭代更新，形成最終的策略；文獻[10]使用分析集群狀態(tài)和機器狀態(tài)的兩層深度強化學習模型來共同完成對集群資源和能耗的管理工作。這些應用都是將現(xiàn)實問題轉化為強化學習問題，通過訓練智能體(agent)以及定義符合領域知識的環(huán)境反饋，進行動態(tài)靈活的學習。

為了解決CDN資源調(diào)度中存在的復雜規(guī)則問題，同時綜合考慮服務質(zhì)量和成本，本文擬結合強化學習的優(yōu)勢，對CDN資源調(diào)度問題進行重新定義，提出一種基于深度強化學習的CDN資源調(diào)度系統(tǒng)設計方法，以避免人為指定調(diào)度規(guī)則帶來的不準確、維護困難以及成本波動等問題。

1 系統(tǒng)設計

1.1 總體框架設計

本文提出的基于深度強化學習的流量調(diào)度系統(tǒng)的設計內(nèi)容，主要包括調(diào)度的智能告警觸發(fā)模塊、綜合質(zhì)量和成本的調(diào)度評估模塊、強化學習模塊。其工作原理主要為：1)采集節(jié)點和服務器相關指標以及故障數(shù)據(jù)，構建基于馬爾可夫模型的智能報警網(wǎng)絡，產(chǎn)生流量調(diào)度的增量帶寬需求；2)對節(jié)點和服務器的帶寬情況、服務能力、用戶覆蓋情況、響應時間等進行綜合考慮，建立質(zhì)量評估模型(強化學習環(huán)境的獎勵函數(shù)的組成部分)；3)對節(jié)點和服務器的計費類型、計費系數(shù)等進行綜合考慮，建立成本評估模型(強化學習環(huán)境的獎勵函數(shù)的組成部分)；4)針對增量帶寬需求，結合質(zhì)量和成本評估獎勵函數(shù)，在線上受限環(huán)境(model-free)或者虛擬環(huán)境(model-base)中進行迭代學習，建立深度強化學習模型；5)在全網(wǎng)環(huán)境部署模型后，根據(jù)調(diào)度產(chǎn)生的數(shù)據(jù)不斷進行在線學習，完善調(diào)度系統(tǒng)。

1.2 故障報警網(wǎng)絡設計

建立故障報警網(wǎng)絡是為了能及時發(fā)現(xiàn)出現(xiàn)服務質(zhì)量的節(jié)點或服務器，觸發(fā)流量調(diào)度。本研究通過采集近期故障報警歷史數(shù)據(jù)，建立基于馬爾科夫鏈的異常檢測算法，進行智能告警。主要有：1)采集故障報警歷史數(shù)據(jù)。歷史數(shù)據(jù)指因監(jiān)控服務器而產(chǎn)生的從底層機器指標(CPU、請求數(shù)、響應時間)到高層機器指標(客戶投訴)報警的時間序列。2)對故障報警歷史數(shù)據(jù)進行離散化，設立低、中、高三個告警級別，從而建立不同告警級別前后相連的馬爾科夫鏈。3)基于報警馬爾可夫鏈，建立故障報警網(wǎng)絡。當發(fā)生低級別機器指標報警時，根據(jù)網(wǎng)絡內(nèi)各個報警級別間的轉化關系及概率，預測高級別報警產(chǎn)生的概率，若概率較高，則會以較大概率觸發(fā)調(diào)度。

1.3 基于Stacking模型的質(zhì)量評估模型

在基于強化學習的調(diào)度系統(tǒng)中，當調(diào)度系統(tǒng)生成一個動作時，需要環(huán)境給出獎勵來指導整個學習過程。本研究為強化學習提供服務質(zhì)量的獎勵函數(shù)。當一個帶寬增量需求提出時，雖然機器的承載帶寬可承載，但是由于業(yè)務特性不同，對機器的CPU、內(nèi)存等要求是不同的，若不加以區(qū)分就會造成機器資源耗竭，影響服務質(zhì)量。因此，本研究提出基于Stacking模型的服務質(zhì)量評估模塊，用來預測加量后機器資源的CPU使用率，并以此作為機器負載的判斷標準。過程步驟如下：

1)采集訓練數(shù)據(jù)：采集線上機器資源的業(yè)務屬性(帶寬量、http請求數(shù))和機器屬性(內(nèi)存大小、磁盤類型、CPU核數(shù)、CPU主頻大小)作為輸入特征，采集機器資源的多核CPU實時使用率均值為預測值，同時統(tǒng)計不同業(yè)務特征每1 Mibit/s帶寬對應增加的http請求。

2)數(shù)據(jù)集劃分：將歷史n天數(shù)據(jù)作為訓練集，第n+1天數(shù)據(jù)作為測試集，并采用滑動窗口方式在時間軸上將數(shù)據(jù)集不斷劃分。

3)基模型訓練：先使用Xgboost、RandomForest、Lightgbm算法作為基模型，采用K折交叉驗證方式對每種模型進行訓練，然后每種基模型訓練后會得到K個子模型以及對訓練集樣本的CPU使用率預測結果，再保存每種基模型的各個子模型。

4)模型融合：用K-NearestNeighbor(KNN)進行模型融合，將步驟3)中每種基模型下的子模型對應訓練集的CPU使用率預測結果作為KNN模型的輸入特征，將訓練集真實CPU使用率作為KNN模型的輸出，設置訓練模型近鄰個數(shù)為5(見圖1左邊部分)。

5)預測階段：假設要給機器資源加量500 Mibit/s帶寬量，實時采集當前機器的業(yè)務屬性(帶寬量、http請求數(shù))和機器屬性(內(nèi)存大小、磁盤類型、CPU核數(shù)、CPU主頻大小)，在此基礎上將增量的500 Mibit/s按照統(tǒng)計系統(tǒng)換算成http請求數(shù)加到當前值中，帶寬量也加500 Mibit/s，訓練好的模型對增量后的特征進行預測，得到CPU使用率，如圖1所示。

1.4 深度強化學習調(diào)度模型設計

本文所要解決的CDN資源調(diào)度問題為服務的增量需求問題。當客戶請求訪問增加，導致當前服務的機器資源負載增加，出現(xiàn)服務響應時間變長，服務質(zhì)量降低，此時需要為當前的客戶請求增加額外的機器資源。其調(diào)度結構如圖2所示。其中：增量需求包含帶寬增量(如需要增加300 Mibit/s)和地理屬性(如福建)兩個重要屬性；服務器資源是有額定帶寬上限的機器資源，可用資源池為機器剩余的可用帶寬，不同的機器資源有不同的價格系數(shù)，代表了機器的成本因素；調(diào)度策略為強化學習的智能體(agent)結構，調(diào)度策略的目標是既要滿足帶寬增量的要求，又要兼顧服務質(zhì)量和成本的均衡。

1.4.1 問題建模

與傳統(tǒng)的機器學習相比，強化學習更注重與環(huán)境的交互，通過不斷與環(huán)境交互獲得獎勵學習，以此得到最佳的動作(如圖3所示)。

本文將CDN增量需求的調(diào)度問題轉化為基于有限的馬爾科夫決策過程。這種過程可以用一個五元組表示(S,A,Pa(st,st+1),Ra(st,st+1),γ)。其中：S為狀態(tài)集合；A是動作集合；Pa(st,st+1)為在時刻t的狀態(tài)st經(jīng)過執(zhí)行動作a可以在t+1時刻轉換到狀態(tài)st+1的轉換概率；Ra(st,st+1)為執(zhí)行動作a所產(chǎn)生的獎勵值；γ為折扣因子，值處于[0,1]區(qū)間，用來表示獎勵值對累積獎勵值的影響權重。對于本文要解決的CDN增量需求的調(diào)度問題，動作A為將可用資源池中服務器資源分配給某個增量需求；狀態(tài)S為分配后增量需求滿足情況和資源的剩余情況；而獎勵R為分配后CDN服務產(chǎn)生的服務質(zhì)量和成本。本文設計的強化學習的目標就是學習最佳的策略(h)，能使整個任務過程的累積獎勵值最大。

本文采用Q學習方法中的動作評價函數(shù)Q(s,a)來描述在狀態(tài)s時agent選擇動作a后所得到的最大累積獎勵。在agent訓練過程中，總是選擇Q最大值的動作：

Q(st,at)=r(st,at)+γmaxQ(st+1,at+1)。

1.4.2 策略設計

本文采用基于卷積網(wǎng)絡的DQN(deep Q-network)[11]算法來訓練agent智能體。DQN算法使用參數(shù)為θ的深度卷積神經(jīng)網(wǎng)絡作為動作值函數(shù)的網(wǎng)絡模型，用模型Q(s,a,θ)來模擬最佳Q(s,a)。在訓練過程中，該網(wǎng)絡模型生成每個動作的Q值，采用遞增的ε-greedy策略來選擇動作，生成一系列的狀態(tài)、動作和獎勵值。DQN訓練模型如圖4所示。

DQN采用均方誤差作為深度網(wǎng)絡的損失函數(shù)，公式為Li(θi)=E[(r+γmaxa′Q(s′,a′;θi)-Q(s,a;θi))2]。其中：γ為折扣因子；θi為第i次迭代的網(wǎng)絡參數(shù)；s′,a′為下一個狀態(tài)和動作。

DQN采用mini-batch方式的隨機下降法來實現(xiàn)對目標損失函數(shù)的優(yōu)化。每產(chǎn)生一個動作a和環(huán)境交互后，神經(jīng)網(wǎng)絡都會進行一次迭代學習，同時更新參數(shù)，直到收斂。

1.4.3 狀態(tài)空間

策略中狀態(tài)空間包含可用的機器資源池和增量帶寬需求。由問題定義可知，資源池和增量需求都是以數(shù)值屬性帶寬量(如500 Mibit/s)表示，這樣動作設計(分配資源)時只能整個分配或者不分配，使資源分配方式受限。所以在狀態(tài)空間設計時，需將資源和需求量拆分成更小的單元(如100 Mibit/s)。如圖5所示，左邊為5個帶寬需求，有顏色的部分代表最小單元帶寬，第一個需求為增強500 Mibit/s；右邊為當前資源池中每臺機器可用帶寬資源，同樣有顏色的表示最小帶寬單元，第一個帶寬資源為700 Mibit/s。將有顏色的部分用1表示，空白的地方用0表示，就可以將資源狀態(tài)轉換為圖像矩陣的形式，作為DQN深度卷積網(wǎng)絡的輸入，從而提取重要特征。由于DQN神經(jīng)網(wǎng)絡需要保持輸入的固定大小，狀態(tài)空間設計時，設定固定M個需求，而對于剩余的需求則可以放在等待隊列。

1.4.4 動作空間

策略中的動作空間為將資源分配給帶寬需求的動作集合。設策略中包括M個帶寬需求，N個機器資源，則總的狀態(tài)空間數(shù)量為N×M+1個，{0,1,2,3,…,N×M-1,φ},φ表示空動作，不做分配。在每次迭代時，調(diào)度器將資源分配給合適的帶寬需求，并更新系統(tǒng)中的資源狀態(tài)，直到所有的帶寬需求都分配完或者所有的資源都分配完才中止迭代。

1.4.5 獎勵函數(shù)

本策略中針對CDN資源調(diào)度問題，兼顧質(zhì)量和成本的目標，設計了一個基于模型的評估函數(shù)。當一個機器資源分配給一個帶寬需求時，除了要滿足需求的帶寬，還要使機器資源在地理位置上盡可能相同，這樣才能保證就近訪問，提高響應時間。另外，還需要考慮加量后機器資源是否會出現(xiàn)高機器負載。雖然機器資源帶寬是允許承接設定的帶寬量，但由于業(yè)務特性不同，使用CPU資源不同，即使同樣的帶寬量產(chǎn)生的負載也會不同，如網(wǎng)頁和流媒體的CPU資源使用率就完全不同。服務成本要求盡可能選擇價格系數(shù)小的機器資源。

因此，策略中的獎勵函數(shù)可以表示成：r=(m×g×l)/p。其中:m表示滿足帶寬的比例，可以在分配后計算;g表示地理位置的匹配程度，可以根據(jù)帶寬需求的地理屬性和機器資源的地理屬性匹配情況，按照不同層級設定不同的比例(如同城為1，同省為0.8，同大區(qū)為0.5，跨大區(qū)為-0.5,跨國為-1)；l表示加量后負載情況；p為價格系數(shù)，是機器資源的固有屬性。

對于如何判斷加量后會不會產(chǎn)生機器負載問題，本策略先采用Stacking質(zhì)量評估模型進行預測，得到增量帶寬后的CPU使用率；再根據(jù)CPU使用率的不同等級設置不同的分數(shù)，如>90%為-1，[80%，90%]為0.2，[50%，80%]為0.6，<50%為1。

1.5 深度強化學習調(diào)度模型訓練

1.5.1 訓練參數(shù)

在DQN網(wǎng)絡訓練中，為使agent 在訓練前期對最優(yōu)策略的探索力度增加，采用遞增的ε-greedy策略來選擇動作。設ε的初始值為0.5，最大值為0.9，增幅為0.001；折扣因子為0.95；經(jīng)驗池規(guī)模為30 000；迭代次數(shù)為1000;采用Mini-batch 訓練方法，設batch-size為32；采用隨機梯度下降方法更新Q網(wǎng)絡參數(shù)，優(yōu)化器為Adam，學習率為0.001。每C個訓練回合后將當前Q網(wǎng)絡的參數(shù)值復制給目標Q′網(wǎng)絡，并更新一次目標網(wǎng)絡參數(shù)。

1.5.2 受限環(huán)境調(diào)度系統(tǒng)

CDN是一個復雜的內(nèi)容分發(fā)網(wǎng)絡，在訓練本文提出的基于強化學習的CDN流量調(diào)度系統(tǒng)時，需要在不影響現(xiàn)有網(wǎng)絡基礎上構造一個可行的環(huán)境。受限環(huán)境(model-free)調(diào)度系統(tǒng)是指系統(tǒng)的學習過程、調(diào)度過程都是在真實的環(huán)境下進行，同樣，接收到的結果反饋也來自于真實的環(huán)境。model-free調(diào)度系統(tǒng)結構圖見圖6。

本文構建CDN受限環(huán)境的目的在于從CDN全網(wǎng)環(huán)境中規(guī)劃出一個小范圍的環(huán)境，使得深度強化學習模型在訓練和驗證期間的一系列試錯行為產(chǎn)生的負面影響，被控制在一個較小的范圍，避免給全網(wǎng)的服務質(zhì)量和成本帶來波動。該受限環(huán)境可以根據(jù)物理位置、運營商或者不同等級的用戶等進行劃分。

本文提出的設計方法分成CDN受限環(huán)境下的訓練階段和CDN全網(wǎng)環(huán)境下的應用階段。

在訓練階段，若出現(xiàn)觸發(fā)調(diào)度的情況，則設置CDN受限環(huán)境下資源配置情況為模型輸入狀態(tài)，模型會基于當前網(wǎng)絡中的參數(shù)，輸出替代資源的挑選概率或者分數(shù)，并根據(jù)一定策略選擇替代資源，然后評估系統(tǒng)對替代資源的服務情況進行評估并反饋給模型，模型接收到反饋信號后，根據(jù)反向傳播算法，調(diào)整網(wǎng)絡參數(shù)，使后續(xù)調(diào)度能夠朝著全局最優(yōu)的方向進行。

當訓練達到一定迭代次數(shù)或者結束條件時，會生成性能較好的調(diào)度模型。該調(diào)度模型會應用到CDN全網(wǎng)環(huán)境上，在后續(xù)的運行過程中仍然持續(xù)進行在線學習。若發(fā)生觸發(fā)調(diào)度的情況時，模型會根據(jù)學習的結果選擇可能對未來產(chǎn)生正面影響的替代資源進行服務，同時評估系統(tǒng)會對替代資源的選擇進行評估，調(diào)度模型根據(jù)反饋信號進行參數(shù)調(diào)整。

1.5.3 虛擬環(huán)境調(diào)度系統(tǒng)

虛擬環(huán)境(model-based)調(diào)度系統(tǒng)是指系統(tǒng)的學習過程是在虛擬環(huán)境中完成，而調(diào)度過程是在真實環(huán)境中進行。虛擬環(huán)境調(diào)度系統(tǒng)結構圖如圖7所示。

CDN虛擬環(huán)境是指根據(jù)線上CDN全網(wǎng)環(huán)境虛擬出的一個環(huán)境。該環(huán)境支持調(diào)度系統(tǒng)與其進行交互，且支持根據(jù)調(diào)度結果，模擬線上CDN全網(wǎng)環(huán)境對其的響應。其評估系統(tǒng)的工作方式和原理與受限環(huán)境調(diào)度系統(tǒng)一樣，但由于是虛擬環(huán)境，調(diào)度觸發(fā)條件中的故障報警功能可以用簡單的元胞自動機進行模擬。

基于CDN虛擬全網(wǎng)環(huán)境來訓練模型有兩點優(yōu)勢：

1)線上真實環(huán)境需要等待調(diào)度觸發(fā)條件出現(xiàn)，才能進行調(diào)度，評估調(diào)度結果，累積訓練數(shù)據(jù)。在這樣的情況下讓模型的性能收斂，可能需要一個比較長的時間周期。如果是在虛擬環(huán)境中，可以通過元胞自動機進行觸發(fā)條件模擬，相較于真實環(huán)境下能有千倍甚至萬倍的效率對模型進行訓練，大大縮短訓練時間周期。

2)CDN受限環(huán)境是為了減小模型在訓練期間的試錯行為對線上服務質(zhì)量和成本帶來的負面影響，而規(guī)劃出的CDN全網(wǎng)環(huán)境的一個子集。該子集環(huán)境雖然能夠?qū)⒇撁嬗绊懴拗圃谝粋€較小的范圍內(nèi)，但是卻不能完全消除影響。另外，由于是一個CDN的子集環(huán)境，在該環(huán)境上產(chǎn)生的用于模型訓練的數(shù)據(jù)是一個局部數(shù)據(jù)集，可能與CDN全網(wǎng)環(huán)境產(chǎn)生的全局數(shù)據(jù)集不是來自同一個分布，可能會導致深度強化學習模型出現(xiàn)過擬合現(xiàn)象，而不能很好地泛化到全網(wǎng)環(huán)境。而CDN虛擬環(huán)境則解決了以上兩個問題，一方面，它在虛擬環(huán)境中的任何操作都不會對真實環(huán)境造成影響；另一方面，虛擬環(huán)境是模擬真實的全局環(huán)境，避免了數(shù)據(jù)層面的局限性。

2 仿真實驗結果分析

在阿里云申請了全球10個機房節(jié)點資源，20臺服務器設備，對本文算法進行實驗仿真。

首先，訓練Stacking質(zhì)量評估模型。實驗定義ABS(實際CPU-預測CPU)<5表示模型預測準確，模型預測精度=模型預測準確數(shù)量/樣本總數(shù)。預測結果顯示，CPU的精度整體可以達到95%。從在線運行結果(見圖8)可知，21:03實際帶寬2.57 Gibit/s，預期加量700 Mibit/s，模型判斷不能加量；21:12實際帶寬3.15Gibit/s，機器的健康值為0.7，加量導致機負載超負荷。由實驗可知，質(zhì)量評估模型能有效評估加量后的機器質(zhì)量情況，能夠為強化學習提供有效的獎勵反饋。

圖9顯示了強化學習訓練過程不同迭代的獎勵值。由圖9可知，隨著迭代的增加，智能體agent完成調(diào)度任務所獲得的獎勵值不斷增長直至收斂。

在線上部署強化學習過程中，對比開啟強化學習調(diào)度前后的效果(見圖10)，發(fā)現(xiàn)本算法在不同產(chǎn)品線上不僅能滿足合適的帶寬要求，而且機器的服務質(zhì)量也有明顯的提升。

在帶寬調(diào)度上，線上實驗結果表明強化學習模型可以有效地控制節(jié)點跑高。如圖11所示，節(jié)點跑高后1 min內(nèi)開始降量。

最后對比了基于規(guī)則調(diào)度系統(tǒng)和深度強化學習調(diào)度系統(tǒng)在不同場景中的調(diào)度耗時。由表1可見，深度強化學習調(diào)度系統(tǒng)提升效果明顯。

表1 調(diào)度耗時對比圖Fig.1 Time consuming comparison of scheduling