一種基于強化學習的CDN流量調度系統設計方法

林春鶯

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

0 引言

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

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

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

1 系統設計

1.1 總體框架設計

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

1.2 故障報警網絡設計

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

1.3 基于Stacking模型的質量評估模型

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

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

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

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

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

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

1.4 深度強化學習調度模型設計

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

1.4.1 問題建模

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

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

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

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

1.4.2 策略設計

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

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

DQN采用mini-batch方式的隨機下降法來實現對目標損失函數的優化。每產生一個動作a和環境交互后，神經網絡都會進行一次迭代學習，同時更新參數，直到收斂。

1.4.3 狀態空間

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

1.4.4 動作空間

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

1.4.5 獎勵函數

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

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

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

1.5 深度強化學習調度模型訓練

1.5.1 訓練參數

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

1.5.2 受限環境調度系統

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

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

本文提出的設計方法分成CDN受限環境下的訓練階段和CDN全網環境下的應用階段。

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

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

1.5.3 虛擬環境調度系統

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

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

基于CDN虛擬全網環境來訓練模型有兩點優勢：

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

2)CDN受限環境是為了減小模型在訓練期間的試錯行為對線上服務質量和成本帶來的負面影響，而規劃出的CDN全網環境的一個子集。該子集環境雖然能夠將負面影響限制在一個較小的范圍內，但是卻不能完全消除影響。另外，由于是一個CDN的子集環境，在該環境上產生的用于模型訓練的數據是一個局部數據集，可能與CDN全網環境產生的全局數據集不是來自同一個分布，可能會導致深度強化學習模型出現過擬合現象，而不能很好地泛化到全網環境。而CDN虛擬環境則解決了以上兩個問題，一方面，它在虛擬環境中的任何操作都不會對真實環境造成影響；另一方面，虛擬環境是模擬真實的全局環境，避免了數據層面的局限性。

2 仿真實驗結果分析

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

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

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

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

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

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

表1 調度耗時對比圖Fig.1 Time consuming comparison of scheduling