面向未知數據流的數據中心網絡調度算法研究

陳金魚

(廈門軟件職業技術學院，福建 廈門 361024)

數據中心網絡承載著大量應用程序流量。一部分應用有著嚴格的限期，因此最小化數據流的完成時間是數據中心網絡的主要目標[1]。對于有著嚴格截止時間的應用，錯過數據流的截止日期會使應用性能急劇下降[2-4]。數據中心網絡是一個具有混合數據流的環境，具有嚴格截止時間的數據流需要在其限期前完成任務，而普通數據流(即沒有嚴格截止時間的數據流)則需要盡快地完成任務。現有關于混合數據流調度的研究是基于完整的數據流先驗知識(如流的大小)，但是在大多數實際應用場景中，并不能直接獲得這些先驗知識。本文提出一種實用的數據中心網絡信息無關流調度算法(DCIA)，該算法能夠在沒有先驗知識的情況下最小化數據流的完成時間。

1 系統模型

DCIA算法的核心思想是利用數據中心網絡交換機中的多優先級隊列，并實現多級反饋隊列，以減少短數據流的完成時間。對于缺乏先驗知識的流調度，LAS策略是最小化平均流完成時間的有效算法之一[5]。由于數據中心網絡的流量具有長尾分布的特征(即短數據流的數量較大)，因此LAS策略尤其有效。但是LAS策略需要直接在交換機上比較每個流傳輸的字節數，然而現有的交換機卻不支持這一操作。另外，雖然數據中心網絡流量分布符合長尾理論，但數據流在時間和空間上的表現都是不同的。例如，多個長數據流可能在某時刻經過某一交換機的端口，采用LAS策略會引起“護航效應”，使流調度算法的性能變差。本文算法根據優先級調度不同隊列中的數據流，根據先入先出算法調度同一隊列中數據流。當某數據流所傳輸的數據量大于預設閾值，該數據流會從當前隊列i降級到隊列i+1，直到進入最后一個隊列(即優先級最低的隊列)。

由于短數據流具有更少的完成時間，因此本文算法優先調度短數據流。這樣一來就能降低算法的平均數據流完成時間。同時通過將長數據流降低到優先級較低的隊列，能有效地避免護航效應，有助于最小化長數據流的響應時間。

DCIA算法在終端主機上進行分布式的數據包標記。假設有K種優先級Pi(1≤i≤K)，有K-1個降級閾值θj(1≤j≤K-1)。當一個新的數據流在終端主機初始化時，算法將其標記為最高優先級P1。當該數據流所傳輸數據包的數量大于等于閾值θ1，該數據流會被降級到優先級P2。DCIA算法的難點在于如何設計合理的降級閾值，以最小化平均的流完成時間。

2 問題建模

本研究目的是最小化平均流完成時間的最優降級閾值，將問題建模為線性組合問題，并求解出最優閾值的解析解。降級閾值取決于網絡負載和流量大小分布，閾值會隨著流量大小分布和負載在時間和空間上的變化而變化。假設在K種優先級隊列Pi(1≤i≤K)中，隊列P1具有最高的優先級，閾值θK=以及θ0=0，數據流i的大小為si。數據流大小分布的累計密度函數為Ω(s)，用pj表示數據流大小在區間[θj-1,θj)內的百分比。其中，定義pj=Ω(θj)-Ω(θj-1)。第j個隊列的平均時延為Dj。因此，數據流的平均完成時間是其中，su是被標記為最低優先級的數據流的剩余大小，即su=s-θmax(s)，θmax(s)是比s小的最大降級閾值，jmax(s)是閾值的索引。我們有以下的最優化問題：

(1)

為了簡化問題，將θ替換為p。根據排隊論的相關理論，第l個隊列的平均等待時間為Dl，計算公式如下所示：

(2)

(3)

由問題(3)可知，平均流完成時間的上界與數據流的分布無關，且只與p有關。一般來說，問題(3)是NP-hard。即在給定一組pj的值的情況下，很容易就能計算到問題(3)中的目標函數值。但要想找到是函數值最大的一組pj的值，就可能需要窮舉出所有pj的可能值。因此本研究通過分析問題的性質來推導出問題的解析解。

在優化問題(3)中，由于流量負載β是小于等于1，于是有以下關系：

(4)

由(4)可以得到以下關系：

(5)

3 算法模塊與仿真實驗

3.1 算法模塊

標記模塊負責維護每個數據流的狀態，并根據數據流的優先級來標記數據包的優先級。該模塊實現在系統的內核模塊中，位于TCP/IP協議棧和系統流量控制模塊之間。系統流量控制模塊包括了過濾器、哈希表以及修改器3個主要部分。過濾器攔截所有傳出的數據包，并將它們導向哈希表。哈希表的每一個表項是一個5元組(即源/目的地IP地址、源/目的地端口以及協議類型)，該5元組定義了數據包所屬的數據流類型。當接收到數據包時，首先為該數據包創建一個哈希表項(或識別它所屬的數據流)，并增加發送的字節數。修改器根據數據流的優先級來設置數據包的優先級。為了計算標記模塊的開銷，將算法實現在聯想工作站ThinkStation P920上，并測量了處理器的使用情況。該工作站配置了一個英特爾至強Gold 5122處理器、一個華碩XG-C100C 10G網卡。結果表明，與沒有使用該標記模塊相比，使用該模塊所引入的額外處理器開銷小于0.5%。

交換機執行嚴格的優先隊列機制，并根據優先級對數據包進行分類。采用了基于即時隊列長度的擁塞標記。除了交換機的排隊時延外，網卡的時延也是不可忽略的。由網卡等硬件帶來的時延會嚴重降低應用程序的性能。為了解決這個問題，以線路速率對傳輸速率進行限速。

3.2 仿真實驗

仿真實驗首先采用一個由16臺工作站組成的網絡拓撲，這些工作站均連接到華為S1720-52GWR-4P 48口全千兆以太網絡交換機。交換機的每個端口最多支持8個服務隊列，工作站均為聯想工作站ThinkStation P920。服務器安裝了CentOS 7操作系統，內核的版本為3.10.0，往返時延為100 μs。還設置了一個較小的網絡拓撲，用于測量高速網絡中終端主機的排隊時延。該拓撲由3個服務器和1個交換機組成。

本算法默認使用8個優先隊列，并在每個端口啟用擁塞標記。將擁塞標記的閾值設置為推薦的30 kB。使用兩個真實的流量數據集：網頁搜索流量和數據中心網絡數據挖掘流量。

本實驗開發基于客戶端/服務器的通信模型，根據真實的數據集生成動態的流量，在應用層測量數據流的完成時間。安裝在1臺工作站的客戶機應用程序定期向其它工作站生成請求以獲取數據，請求服從泊松分布；運行在另外15臺工作站上的服務器應用程序用相應的數據對請求進行響應。將本算法與數據中心網絡數據傳輸協議(DTCP)進行對比。圖1和圖2分別是不同算法在小數據流和大數據流下的平均數據流完成時間。小數據流中數據包的大小在區間(0,1 MB]范圍內，小數據流中數據包的大小在區間(1 MB,10 MB]范圍內。由實驗結果可知，本算法在小流量和大流量下均能獲得較好的性能。

接下來評估本算法在延遲敏感應用程序下的性能。在16臺工作站中，1臺工作站用作客戶端，15臺用作服務器。客戶端向15個服務器發送一個查詢，每個服務器對查詢進行響應。只有當客戶端從所有服務器接收到響應時，一次查詢完成。將查詢完成時間作為性能度量。圖3是兩種算法查詢完成時間的實驗結果。由于交換機上啟用了動態緩沖區管理和擁塞標志，因此兩種算法均沒有發生TCP超時。隨著流量負載的增加，DTCP的平均查詢完成時間也在增加。與DTCP相比，DCIA算法的性能相對穩定，并實現了低平均查詢完成時間。

圖1 兩種算法在小數據流下的流完成時間

圖2 兩種算法在大數據流下的流完成時間

圖3 兩種算法的查詢完成時間

4 結論

在一個信息不可知的數據中心網絡中，DCIA算法利用商品交換機來最小化數據流的平均完成時間。通過仿真實驗進行性能評估，實驗結果表明，與現有方法相比，DCIA算法具有較好的性能。未來的工作將集中于利用不同的大規模網絡，設置不同的真實場景，對該算法進行深入地分析評估。