sigcomm'18--香港科技大學

摘要：

目前DRL（深度強化學習）算法的時延過大，不能直接應(yīng)用于處理流級別的數(shù)據(jù)中心流量優(yōu)化，因為短流在決策未生成之前已經(jīng)結(jié)束了。

基于數(shù)據(jù)中心的流量分布類型為長尾分布，本文提出了兩級DRL系統(tǒng)：周邊（PS）和中樞系統(tǒng)（CS）。PS位于終端，收集流信息，在本地為短流作出決策，保證最小時延，但PS的決策還是由CS干預的。CS擁有全局流量信息，為長流作出決策。實驗搭建在32個服務(wù)器的實驗床上，相比現(xiàn)有方法，AuTO將RTT從幾周降低到了100毫秒，同時提高了性能。平均FCT也比現(xiàn)有方法降低了48.14%。

簡介：

問題：現(xiàn)有TO算法依賴于人工啟發(fā)式算法，依據(jù)為流量負荷，流量大小分布，流量密集度等分量分布狀況。存在問題有：1）TO算法的參數(shù)設(shè)置與真實情況不匹配，造成性能下降。舉例：PIAS，pFabric，Aalo。2）已存在的TO啟發(fā)式算法的RTT太長，以周為單位。因為需要很長的時間收集應(yīng)用信息，流量數(shù)據(jù)信息，才能設(shè)置啟發(fā)式算法的相關(guān)參數(shù)。舉例： 部署監(jiān)測系統(tǒng)，收集足夠多的數(shù)據(jù)分析，設(shè)計啟發(fā)式算法，仿真優(yōu)化工具尋找合適參數(shù)，最后在實驗床上測試啟發(fā)式算法。這一完整的周期很長。

動機：強化學習是機器學習的分支，主要用于決策和動作控制。現(xiàn)有領(lǐng)域在深度學習方面取得了成果：DeepMind的Atari結(jié)果，AlphaGo等等。受到這些啟發(fā)，本文嘗試在數(shù)據(jù)中心TO方面應(yīng)用DRL工具。一個流調(diào)度的小測試驗證了單一的集中式TO系統(tǒng)在大規(guī)模的數(shù)據(jù)中心（10的5次方臺服務(wù)器）中不能滿足短流的需求，存在決策速度慢，無用的問題，因此本文才嘗試用分層TO架構(gòu)。

關(guān)鍵：AuTO可擴展的關(guān)鍵將耗時的DRL算法處理與需要快速采取動作的短流處理分開。解決方案為在PS系統(tǒng)采用多級反饋隊列（MLFQ）和一組門限值進行流調(diào)度。每條新流都是最高優(yōu)先級，隨著發(fā)送的字節(jié)數(shù)增加，優(yōu)先級會降低。這樣，PS系統(tǒng)就會根據(jù)本地信息（發(fā)送字節(jié)數(shù)和門限值）對每條流進行快速決策。門限值由CS系統(tǒng)通過DRL算法優(yōu)化，更新周期會較長。對于長流來說，CS系統(tǒng)會使用另一種DRL算法確定路由，速率和優(yōu)先級。

實驗測試：搭建環(huán)境為32臺服務(wù)器和2臺交換機。流量模式為固定的負載和流分布，對比方案為標準的啟發(fā)式算法（最少工作優(yōu)先和最小服務(wù)優(yōu)先），訓練時間為8小時，平均FCT降低了8.71%。

背景和動機：

介紹了DRL模型，通過小型流調(diào)度實驗證明現(xiàn)有DRL系統(tǒng)處理時延過長，不能滿足數(shù)據(jù)中心級TO。

AuTO設(shè)計：

兩級系統(tǒng)：PS運行在終端，為短流做TO決策，CS為長流做決策。

AuTO系統(tǒng)

PS系統(tǒng)：

根據(jù)CS下發(fā)的一組門限值和流的大小，為流打上不同的優(yōu)先級標簽，從而確保PS系統(tǒng)僅僅根據(jù)本地信息就可以為短流作出全局最優(yōu)決策。分為執(zhí)行模塊和監(jiān)測模塊。

MLFQ-多級優(yōu)先級反饋隊列

執(zhí)行模塊：采用MLFQ（最早在PIAS中出現(xiàn)）為短流分配優(yōu)先級。優(yōu)先級字段填充在IP頭部的服務(wù)類型字段中的DSCP字段中（占6個比特）。這樣每條流就可以在終端根據(jù)發(fā)送的字節(jié)數(shù)和門限值快速打上相應(yīng)的優(yōu)先級標簽。這樣，長短流自然就分開了，對于長流，CS也可以單獨做決策（路由策略，速率限制和優(yōu)先級）。

監(jiān)測模塊：主要用來收集已完成流的大小、流完成時間。CS根據(jù)收集信息更新流分布模型。同時，檢測系統(tǒng)也需向CS報告即將到來的長流信息，以便CS及時作出決策。

CS系統(tǒng)：

4隊列的AuTO系統(tǒng)示例

CS系統(tǒng)由兩種DRL代理（agent）組成：短流代理（sRLA）和長流代理（lRLA）。短流代理解決最小化FCT的問題，使用DDPG算法，用來更新門限值；長流使用PG（策略梯度）算法生成長流的路由、速率、優(yōu)先級。

DRL理論分析

優(yōu)化MLFQ門限值：

難點在于計算最優(yōu)門限值。之前的工作提供了計算門限值的數(shù)據(jù)分析，并且建議更新周期為周或月。AuTO的優(yōu)化目標是在連續(xù)的動作空間中尋求一個真實的最優(yōu)值。將門限值優(yōu)化問題看做一個DRL問題，用DNN網(wǎng)絡(luò)模擬復雜的數(shù)據(jù)中心網(wǎng)絡(luò)。

將門限值優(yōu)化轉(zhuǎn)化為M/M/1排隊模型：到達時間服從泊松分布，服務(wù)時間服從指數(shù)分布，先到先服務(wù)，隊列長度無限制，可加入隊列的人數(shù)無限。假設(shè)流分布的累計密度函數(shù)為F(x)，表示流大小不大于x的概率，Li表示給定流在隊列Qi中引入的數(shù)據(jù)包的數(shù)量， 則E[Li]≤(αi-αi-1)(1-F (αi-1))。流到達速率為λ，則隊列Qi中數(shù)據(jù)包到達速率為λi=λE[Li ]。假定鏈路服務(wù)速率為μ，則Q1的服務(wù)速率為μ，空閑概率為1-ρ1，ρi表示服務(wù)被占用的概率。imax (x)表示大小為x 的流的大于x的最小門限值的下標。

隊列i的服務(wù)速率

數(shù)據(jù)包在Qi中的逗留時間

T(x) ：大小為x的流的平均FCT

則最小化FCT即可表示為：

最小化FCT數(shù)學表達

狀態(tài)空間：一組已完成流的屬性集合。每條流有7個屬性：五元組、流大小、流完成時間。100條短流

動作空間：一組MLFQ門限值{αi，t}

反饋函數(shù)：前一時刻與當前時刻目標函數(shù)的比值。

優(yōu)化長流：

使用PG算法，優(yōu)化長流。

動作空間：每條流對應(yīng)優(yōu)先級，限速，路徑（路徑的枚舉方式與XPath相同）

狀態(tài)空間：未結(jié)束的流（11條長流）：五元組，優(yōu)先級；已經(jīng)結(jié)束的流（10條長流）：五元組，流大小，F(xiàn)CT

反饋函數(shù)：通過已經(jīng)結(jié)束的流獲得。每條已完成流的吞吐量為流大小與流完成時間的比值。則反饋函數(shù)設(shè)置為兩個連續(xù)時間所有已完成流的平均吞吐量的比值。

（a）反饋函數(shù)? （b）單一流的吞吐量計算公式

系統(tǒng)實現(xiàn)部分：

語言Python2.7，深度學習框架Keras，PS和CS系統(tǒng)是通過RPC接口通信的。

PS系統(tǒng)：

監(jiān)測模塊：在linux內(nèi)核中實現(xiàn)是最高效的，但現(xiàn)有方案是在流發(fā)生器中實現(xiàn)的。一個周期為T秒，MM收集已結(jié)束的流（7個屬性）（10條長流，100條短流），未結(jié)束的流（6個屬性）（11條未結(jié)束的長流）信息，并將其整合通過RPC接口發(fā)送給CS。收集流的個數(shù)是由流量負載和采樣周期決定的。

執(zhí)行模塊：在linux內(nèi)核實現(xiàn)。周期性接收CS下發(fā)的一組門限值和本地長流的路由、限速、優(yōu)先級信息。對于短流，用ECMP選路和負載均衡，這樣就不需要對每條流進行集中式控制和擁塞控制。對于長流，EM利用相同的linux內(nèi)核模塊為長流打上優(yōu)先級標簽。在限速操作上，使用TCHTB實現(xiàn)。HTB隊列“控發(fā)不控收”。EM首先建立一個父類的HTB隊列，將速率設(shè)置為CS指定該節(jié)點的總出口帶寬。當某條流到達最低優(yōu)先級隊列時，EM通過HTB過濾器匹配流的五元組為其設(shè)置CS下發(fā)的速率。速率上限為min{原始速率，CS下發(fā)的速率的兩倍}。

CS系統(tǒng)：

借鑒了SEDA系統(tǒng)架構(gòu)，分為三塊：HTTP請求處理、深度網(wǎng)絡(luò)學習或處理、回復發(fā)送。使用三個進程分別實現(xiàn)，進程之間使用隊列，這樣避免了Python實現(xiàn)過程中的全局鎖問題。超參數(shù)（架構(gòu)，神經(jīng)網(wǎng)絡(luò)層數(shù)，節(jié)點數(shù)等）的選擇由經(jīng)驗得出。

評估：

1.在固定的流大小分布和流量負載分布情況下，AuTO性能與標準啟發(fā)式算法相比：平均FCT降低了48.14%

2.當流量特征變化時，AuTO能夠適應(yīng)這種變化嗎：四組服務(wù)器分別生成不同流大小分布的流量，測試結(jié)果為平均流完成時間降低了37.20%

3.AuTO在多長時間內(nèi)可以應(yīng)對流量特征變化：四組服務(wù)器的流量模式周期性變化，性能穩(wěn)定，優(yōu)于標準啟發(fā)式算法。

4.AuTO的整體性能開銷和可擴展性如何：平均10ms就可以完成門限值等更新，傳統(tǒng)算法需要幾個月或者幾周。對于PS系統(tǒng)，CPU利用率和吞吐量的開銷也顯著下降。