基于強(qiáng)化學(xué)習(xí)的多階段網(wǎng)絡(luò)分組路由方法

高遠(yuǎn)翔，羅 龍，孫 罡*

(1. 電子科技大學(xué)光纖傳感與通信教育部重點(diǎn)實(shí)驗(yàn)室 成都 611731)

近年來，機(jī)器學(xué)習(xí)方法在包括圖像識別[1]、機(jī)器翻譯[2]等多個領(lǐng)域得到了廣泛應(yīng)用。由于數(shù)據(jù)量及算法復(fù)雜度的增長，機(jī)器學(xué)習(xí)應(yīng)用通常在一個由大量計(jì)算資源組成的集群系統(tǒng)上分布式運(yùn)行。機(jī)器學(xué)習(xí)應(yīng)用周期性地在集群網(wǎng)絡(luò)中產(chǎn)生跨計(jì)算資源的數(shù)據(jù)分組，這些數(shù)據(jù)分組在網(wǎng)絡(luò)中的傳輸延遲對機(jī)器學(xué)習(xí)應(yīng)用的時間效率具有關(guān)鍵影響。

機(jī)器學(xué)習(xí)集群常用多階段Clos 網(wǎng)絡(luò)[3-5]，其通過多個階段的交換機(jī)將各個計(jì)算資源互聯(lián)起來。多階段網(wǎng)絡(luò)在兩個計(jì)算資源間提供了大量可供選擇的路徑，且網(wǎng)絡(luò)中同時有大量分組需要路由決策，所以分組的路由是一個組合優(yōu)化難題。

基于最短路徑的擬靜態(tài)路由算法[6]，如貝爾曼-福特算法、狄克斯特拉算法，無法跟隨集群網(wǎng)絡(luò)負(fù)載狀態(tài)的迅速變化。而多階段網(wǎng)絡(luò)通常采用基于啟發(fā)式的動態(tài)路由算法[3,7]，目前，廣泛使用的是基于“加入最短隊(duì)列”策略[3]的啟發(fā)式路由算法。該算法將分組轉(zhuǎn)發(fā)到具有最少排隊(duì)分組的下一跳交換機(jī)。這些啟發(fā)式算法基于網(wǎng)絡(luò)局部的負(fù)載信息進(jìn)行路由決策，常導(dǎo)致網(wǎng)絡(luò)全局負(fù)載不均衡，無法保證最小的平均分組傳輸延遲。

本文提出一種基于強(qiáng)化學(xué)習(xí)的分組路由算法，將多階段網(wǎng)絡(luò)的路由問題建模為一個馬爾科夫決策過程[8](markov decision process, MDP)，這是該問題的首個MDP 模型。為了求解該MDP 的最佳路由策略，本文提出了最大似然策略迭代(maximum likelihood policy iteration, MLPI)算法。該算法在策略評估步驟中使用最大似然價值函數(shù)估計(jì)器，該價值函數(shù)估計(jì)器克服了現(xiàn)有強(qiáng)化學(xué)習(xí)方法[9-10]中蒙泰卡羅(Monte Carlo, MC)或時間差分(temporaldifference, TD)價值函數(shù)估計(jì)器樣本效率低的問題。為了應(yīng)對MLPI 算法策略改進(jìn)步驟中涉及的組合優(yōu)化難題，本文提出了一個序列最小化的方法，通過將組合優(yōu)化分解為一系列可求解的簡單優(yōu)化子問題來進(jìn)行有效的策略改進(jìn)。

基于NS-3 網(wǎng)絡(luò)模擬器的仿真實(shí)驗(yàn)結(jié)果表明，本文的MLPI 算法找到的路由策略較“加入最短隊(duì)列”啟發(fā)式策略減少了38.3% 的平均排隊(duì)分組數(shù)目，同時減少了17.6%的平均分組延遲。此外，MLPI算法的學(xué)習(xí)效率遠(yuǎn)高于基于蒙泰卡羅(MC)或時間差分(TD)價值函數(shù)估計(jì)器的強(qiáng)化學(xué)習(xí)算法。

1 多階段網(wǎng)絡(luò)的分組路由

如圖1a 所示，在一個三階段網(wǎng)絡(luò)中，分組路由問題的模型是一個離散時間排隊(duì)系統(tǒng)的控制問題。在一個特殊的時刻t，由計(jì)算資源產(chǎn)生的數(shù)據(jù)分組到達(dá)輸入階段的交換機(jī)。一個輸入或輸出交換機(jī)通常連接多個計(jì)算資源。為了簡潔表達(dá)，連接到輸入輸出交換機(jī)上的計(jì)算資源沒有在圖中呈現(xiàn)。在第i個輸入交換機(jī)，目的地為第j個輸出交換機(jī)的到達(dá)分組數(shù)目服從一個到達(dá)率為 λi j的泊松分布，且這些到達(dá)分組排在第i個輸入交換機(jī)的第j個隊(duì)列中，網(wǎng)絡(luò)狀態(tài)是該網(wǎng)絡(luò)中各隊(duì)列分組的數(shù)目。

在每個時刻t，不同階段交換機(jī)之間的每條鏈路負(fù)責(zé)將分組從上游交換機(jī)傳輸?shù)揭粋€下游交換機(jī)，具有一個單位的容量。假設(shè)使用先入先出排隊(duì)準(zhǔn)則，路由算法需要為每一個隊(duì)列中的隊(duì)首分組選擇一個下游鏈路來傳輸它。如圖1b 所示，所有隊(duì)首分組的路由選擇可視作一個全局的路由動作。遵循這個路由動作，隊(duì)首分組在選擇的鏈路上傳輸。在下一個時刻t+1，如圖1c 所示，傳輸中的分組同時到達(dá)下游交換機(jī)的相應(yīng)隊(duì)列。所有分組到達(dá)下游交換機(jī)后，到達(dá)輸入階段交換機(jī)的新一輪分組遵循同樣的泊松分布。然后類似的路由動作和分組傳輸重復(fù)進(jìn)行。

圖1 三階段網(wǎng)絡(luò)分組路由的離散時間排隊(duì)系統(tǒng)模型

2 MDP 模型

本節(jié)將多階段網(wǎng)絡(luò)分組路由問題建模為一個馬爾科夫決策過程MDP。該MDP 由一個四元組S,A,c,P指定，其中S是狀態(tài)空間， A是動作空間，c是代價函數(shù)，P是狀態(tài)轉(zhuǎn)移概率。該MDP 的具體定義如下。

狀態(tài)：該MDP 在時刻t的狀態(tài)表示為st，是一個3 維矩陣，其元素表示為n(sti)j，表示第i個交換機(jī)上第j個隊(duì)列在第s個階段的分組數(shù)目。

動作：假設(shè)網(wǎng)絡(luò)中有M個隊(duì)首分組，該MDP在時刻t的動作是為每一個隊(duì)首分組選擇的鏈路所組成的集合{a1,a2,···,aM}。動作產(chǎn)生的順序是從在最上游階段的最低指標(biāo)輸入交換機(jī)上最低指標(biāo)隊(duì)列中的隊(duì)首分組開始，逐漸輪詢到同一個輸入交換機(jī)上更高指標(biāo)隊(duì)列中的隊(duì)首分組，然后輪詢到同一個階段中更高指標(biāo)的輸入交換機(jī)上的各隊(duì)首分組，最終輪詢到更下游交換機(jī)上的各隊(duì)首分組。為第m個隊(duì)首分組選擇的鏈路am是沒有被其他隊(duì)首分組選擇的空閑下游鏈路中的一個。當(dāng)一個交換機(jī)上的某些隊(duì)列沒有隊(duì)首分組時，為了充分利用鏈路，該交換機(jī)上其他隊(duì)列中的非隊(duì)首分組也可能在隊(duì)首分組選擇鏈路后獲得一個鏈路分配。

3 基于最大似然價值估計(jì)的策略評估

式中，St+w表示時刻t+w狀態(tài)的隨機(jī)變量,w是窗口大小。窗口大小通常設(shè)為能使得更遠(yuǎn)未來狀態(tài)的代價可以忽略不計(jì)的值，如在γ=0.99時設(shè)為500。Eπ,Λ[·]是在策略 π和泊松參數(shù) Λ下，相對于St+w的概率分布的期望。由于到達(dá)參數(shù)通常是未知的，作為其函數(shù)，上述價值函數(shù)需要從采樣的狀態(tài)樣本軌跡中估計(jì)得到。

現(xiàn)有強(qiáng)化學(xué)習(xí)算法使用蒙泰卡羅(MC)或時間差分(TD)價值函數(shù)估計(jì)器[9-10]，但MC 和TD 價值估計(jì)樣本效率低[9]。本文使用價值函數(shù)的最大似然估計(jì)器，推導(dǎo)如下。

給定一個策略 π，式(3) 中價值函數(shù)是未知泊松到達(dá)參數(shù) Λ的函數(shù)。給定一個時間長度為T的樣本軌跡，參數(shù){λij}的最大似然估計(jì)(maximum likelihood estimate, MLE)由如下的平均到達(dá)率給出[12]：

式中，樣本軌跡{st,st+1,···,st+w}是在估計(jì)的到達(dá)參數(shù)和策略π下模擬的狀態(tài)轉(zhuǎn)移。

4 最大似然策略迭代

4.1 基于序列最小化的策略改進(jìn)

式中，s′是在狀態(tài)s采取動作序列{a1,a2,···,aM}所導(dǎo)致的下一個狀態(tài)。式(7)中的最小化問題是一個困難的組合優(yōu)化問題，其搜索空間隨網(wǎng)絡(luò)中隊(duì)首分組數(shù)目呈指數(shù)式增加。為了快速求解問題，本文使用一種在神經(jīng)動態(tài)規(guī)劃文獻(xiàn)[15] 中被稱為動作空間復(fù)雜度與狀態(tài)空間復(fù)雜度折衷的方法，通過引入一系列描述每個動作后果的人工狀態(tài)使得策略改進(jìn)步驟能序列地對每一個動作進(jìn)行。

4.2 最大似然策略迭代算法

如算法1 所示，該MLPI 算法首先初始化一個近似價值函數(shù)估計(jì)的卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural network, CNN)，Vθ0作為初始的價值函數(shù)估計(jì)。初始路由策略 π0是相對于Vθ0的ε-貪婪策略。具體地，在每步序列最小化時以概率為1-ε選取最佳動作而以概率ε隨機(jī)選取鏈路。在第n次策略迭代時，該算法觀察網(wǎng)絡(luò)進(jìn)行T步狀態(tài)轉(zhuǎn)移，且累加到達(dá)輸入交換機(jī)各隊(duì)列的分組總數(shù)。然后，該算法計(jì)算泊松參數(shù)的最大似然估計(jì)Λ?。

接下來，MLPI 算法跟隨策略 πn執(zhí)行K(K?T)步模擬的狀態(tài)轉(zhuǎn)移。模擬狀態(tài)轉(zhuǎn)移中經(jīng)歷的狀態(tài)作為輸入集S={sl,l=1,2,···,L}，對應(yīng)的折扣樣本總代價C={c(sl)+γ1c(sl+1)+···+γWc(sl+W)}作為輸出集構(gòu)成了一個龐大的數(shù)據(jù)集Dn。該數(shù)據(jù)集用來訓(xùn)練Vθn幾個來回(epochs)，得到的價值網(wǎng)絡(luò)Vθn+1是最大似然價值函數(shù)的近似。之后，在下一次迭代中遇到的每個狀態(tài)，該算法通過ε-貪婪地相對于Vθn+1求解式(9)中的序列最小化來產(chǎn)生新策略πn+1。

5 實(shí) 驗(yàn)

5.1 測試網(wǎng)絡(luò)和路由代理

NS-3 網(wǎng)絡(luò)模擬器是一個廣泛使用的分組級別的離散事件仿真器[16]。本文基于NS-3 搭建了一個多階段的網(wǎng)絡(luò)測試環(huán)境，參考強(qiáng)化學(xué)習(xí)中環(huán)境-代理(agent) 的交互框架[10]搭建了一個網(wǎng)絡(luò)路由代理。該網(wǎng)絡(luò)路由代理使用由MLPI 算法訓(xùn)練完成的價值網(wǎng)絡(luò)產(chǎn)生最佳的路由動作序列。

具體來說，該測試網(wǎng)絡(luò)是一個按時隙產(chǎn)生控制和進(jìn)行傳輸?shù)木W(wǎng)絡(luò)，在每個時隙t，該測試網(wǎng)絡(luò)中各交換機(jī)將各隊(duì)列的分組數(shù)目上報給網(wǎng)絡(luò)路由代理。網(wǎng)絡(luò)路由代理得到該時刻的網(wǎng)絡(luò)狀態(tài)，作為產(chǎn)生路由決策的初始狀態(tài)。從該狀態(tài)開始，路由代理相對于訓(xùn)練好的價值網(wǎng)絡(luò)逐步求解序列最小化問題(無需ε-探索)，來得到該狀態(tài)下所有隊(duì)首分組的最佳路由向量{a*1,a*2,···,a*M}。之后，路由代理將該最佳路由動作序列下達(dá)給各交換機(jī)，各交換機(jī)按照指定的路由動作發(fā)送各隊(duì)列的隊(duì)首分組。當(dāng)發(fā)送的各分組到達(dá)下游交換機(jī)后，網(wǎng)絡(luò)進(jìn)入下一個時隙t+Δt并重復(fù)上述交互過程。

5.2 實(shí)驗(yàn)設(shè)定

本文在一個每階段包含16 個或20 個交換機(jī)的三階段網(wǎng)絡(luò)中測試MLPI 算法。在實(shí)驗(yàn)前，分組到達(dá)率{λij}由獨(dú)立同分布的0～1 之間的均勻分布產(chǎn)生，網(wǎng)絡(luò)負(fù)載ρ定義為總到達(dá)率除以單階段的總鏈路容量。

表2 MLPI 算法的超參數(shù)

5.3 對比方案

將MLPI 算法與典型及現(xiàn)有最優(yōu)的路由啟發(fā)式算法進(jìn)行對比。

1)隨機(jī)路由(Rand) 算法：交換機(jī)隨機(jī)選擇一個空閑鏈路來傳輸隊(duì)首分組。

2)加入最短隊(duì)列(join-the-shortest-queue, JSQ)[3,6]算法：對于交換機(jī)上第j個隊(duì)列的隊(duì)首分組，交換機(jī)在所有空閑鏈路里選擇其下游交換機(jī)上第j個隊(duì)列最短的鏈路來傳輸該分組。

表1 卷積神經(jīng)網(wǎng)絡(luò)的超參數(shù)

3) Power-of-two-choices(Po2)[7,18]算法：對于交換機(jī)上第j個隊(duì)列的隊(duì)首分組，交換機(jī)首先隨機(jī)選取兩個空閑鏈路作為候選鏈路，再在候選鏈路中選擇其下游交換機(jī)上第j個隊(duì)列更短的鏈路來傳輸該分組。

4)基于蒙泰卡羅價值估計(jì)的強(qiáng)化學(xué)習(xí)(MC)[10]算法：該方法遵循相對于價值網(wǎng)絡(luò)ε-貪婪的策略來與測試網(wǎng)絡(luò)進(jìn)行交互，在交互過程中產(chǎn)生的狀態(tài)轉(zhuǎn)移樣本集合被用來在線訓(xùn)練價值網(wǎng)絡(luò)。對每個狀態(tài)，價值網(wǎng)絡(luò)的訓(xùn)練目標(biāo)為在一個窗口范圍內(nèi)未來狀態(tài)的總折扣代價值。在產(chǎn)生一批訓(xùn)練示例后，該算法相對于價值網(wǎng)絡(luò)參數(shù)執(zhí)行一步隨機(jī)梯度下降。

5)基于n-步TD 價值估計(jì)的強(qiáng)化學(xué)習(xí)(TD)[10]算法：類似于MC，對每個狀態(tài)，價值網(wǎng)絡(luò)的訓(xùn)練目標(biāo)是在一個大小為n(n=100)的窗口內(nèi)的未來狀態(tài)的總折扣代價，再加上第n+1個未來狀態(tài)在γn+1折扣后的價值估計(jì)值。在產(chǎn)生一批訓(xùn)練示例后，該算法執(zhí)行一步隨機(jī)梯度下降。

5.4 實(shí)驗(yàn)結(jié)果

在實(shí)驗(yàn)中，MLPI 算法執(zhí)行一系列的策略迭代步驟直到策略不再改進(jìn)。在第n次策略迭代時，MLPI算法觀察測試網(wǎng)絡(luò)，進(jìn)行20 個時隙的狀態(tài)轉(zhuǎn)移來更新對泊松參數(shù)的估計(jì)。然后，MLPI 算法執(zhí)行3 200步模擬的狀態(tài)轉(zhuǎn)移，這個過程中收集到的訓(xùn)練示例(接近1 000 000 個，包含中間狀態(tài))用來訓(xùn)練價值網(wǎng)絡(luò)10 個來回。訓(xùn)練完成后，從一個空的網(wǎng)絡(luò)狀態(tài)開始，路由代理使用現(xiàn)有價值網(wǎng)絡(luò)對應(yīng)的路由策略來控制測試網(wǎng)絡(luò)200 個時隙，且將平均排隊(duì)分組總數(shù)和平均分組延遲記錄下來，作為現(xiàn)有策略πn的性能度量。上述迭代持續(xù)進(jìn)行，直到策略的性能不再改進(jìn)。

5.4.1 平均排隊(duì)分組總數(shù)

圖2 的結(jié)果顯示，對于每階段16 個交換機(jī)的網(wǎng)絡(luò)，在6 次最大似然策略迭代之后，MLPI 找到的路由策略的平均排隊(duì)分組總數(shù)達(dá)到最低點(diǎn)，其相對于JSQ 和Po2 算法分別減少了約26.6%和21.1%的平均分組總數(shù)。圖3 的結(jié)果顯示，對于每階段20 個交換機(jī)的網(wǎng)絡(luò)，在7 次最大似然策略迭代后，MLPI 找到的路由策略相對于JSQ 和Po2 分別減少了約20.7%和17.2%的平均排隊(duì)分組總數(shù)。然而，MC 或TD 算法的平均排隊(duì)分組總數(shù)始終保持在較高的程度，幾乎沒有從經(jīng)驗(yàn)中學(xué)習(xí)的跡象。

圖2 每階段16 個交換機(jī)時的平均排隊(duì)分組總數(shù)

圖3 每階段20 個交換機(jī)時的平均排隊(duì)分組總數(shù)

5.4.2 平均分組延遲

如圖4 所示，經(jīng)過8 次最大似然策略迭代，MLPI 收斂到的路由策略相對于JSQ 和Po2 分別減少約17.6% 和13.9% 的平均分組延遲。如圖5 所示，經(jīng)過8 次最大似然策略迭代，MLPI 算法收斂到的路由策略相對于JSQ 和Po2 分別減少了約13.0%和10.3%的平均分組延遲。可以觀察到平均分組延遲的下降趨勢與平均排隊(duì)分組總數(shù)的下降趨勢一致。

圖4 每階段16 個交換機(jī)時的平均分組延遲

圖5 每階段20 個交換機(jī)時的平均分組延遲

5.4.3 網(wǎng)絡(luò)負(fù)載的影響

圖6 展示了MLPI 算法在各負(fù)載條件下收斂到的路由策略的平均排隊(duì)分組總數(shù)。不論負(fù)載條件如何變化，MLPI 算法找到的路由策略的平均排隊(duì)分組總數(shù)都顯著低于啟發(fā)式路由策略。在越重的負(fù)載條件下，MLPI 算法找到的路由策略相對于其他對比方案的平均排隊(duì)分組總數(shù)減少量越大。當(dāng)網(wǎng)絡(luò)負(fù)載為0.8 時，MLPI 算法相對于JSQ 和Po2 算法的平均排隊(duì)分組總數(shù)減少量分別約為38.3%和28.9%。

圖6 不同負(fù)載條件下的平均排隊(duì)分組總數(shù)

5.4.4 負(fù)載均衡的效果

在對不同路由算法的測試運(yùn)行中，記錄在每個時隙泊松到達(dá)事件之前的網(wǎng)絡(luò)狀態(tài)，且對所收集的狀態(tài)取平均來得到各路由算法下總體的排隊(duì)行為。如圖7 所示，每一個熱圖代表一個16×16 矩陣，其第ij個元素表示在某個階段中第i個交換機(jī)上的第j個隊(duì)列的平均排隊(duì)分組數(shù)。

圖7 的結(jié)果顯示，在第一個階段，在記錄狀態(tài)的時刻各隊(duì)列中沒有分組累積。在第二個階段，MC算法找到的路由策略導(dǎo)致了一些擁塞的隊(duì)列和不均衡的負(fù)載分布。在第三個階段，Po2 路由算法導(dǎo)致了顯著的負(fù)載不均衡，這是因?yàn)槠鋵㈥?duì)首分組路由到一些擁塞隊(duì)列中而讓其他隊(duì)列保持空載。這種對鏈路資源的欠利用降低了網(wǎng)絡(luò)吞吐量，導(dǎo)致分組滯留在網(wǎng)絡(luò)中。對比之下，MLPI 算法通過最大似然策略迭代學(xué)會了達(dá)到近乎理想的負(fù)載均衡狀態(tài)。

圖7 不同路由策略下各隊(duì)列的平均排隊(duì)分組數(shù)

強(qiáng)化學(xué)習(xí)算法如MC 或TD，需要與實(shí)際網(wǎng)絡(luò)進(jìn)行大量的交互并收集大量的試錯數(shù)據(jù)，這會在訓(xùn)練過程中顯著損害網(wǎng)絡(luò)的延遲性能。MLPI 算法通過模擬的狀態(tài)轉(zhuǎn)移來學(xué)習(xí)路由策略，其訓(xùn)練過程不會對實(shí)際網(wǎng)絡(luò)的正常運(yùn)行產(chǎn)生干擾。由于集群網(wǎng)絡(luò)需要不間斷地為用戶提供低延遲的傳輸服務(wù)，MLPI算法是一種更加實(shí)用的路由策略學(xué)習(xí)方法。

6 結(jié) 束 語

本文提出最大似然策略迭代(MLPI)算法來求解多階段網(wǎng)絡(luò)分組路由問題，MLPI 采用了高效的最大似然價值估計(jì)器來進(jìn)行策略評估。為了有效地改進(jìn)策略，MLPI 采用序列最小化的方法將復(fù)雜的組合優(yōu)化問題分解為一系列簡單的優(yōu)化子問題進(jìn)行高效求解。基于NS-3 的實(shí)驗(yàn)證實(shí)相較于現(xiàn)有最優(yōu)的啟發(fā)式算法，MLPI 學(xué)習(xí)到的路由策略能將網(wǎng)絡(luò)中的平均排隊(duì)分組總數(shù)和平均分組延遲分別降低約21.1%和13.9%。