面向未知數(shù)據(jù)流的數(shù)據(jù)中心網(wǎng)絡(luò)調(diào)度算法研究

陳金魚

(廈門軟件職業(yè)技術(shù)學(xué)院，福建 廈門 361024)

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

1 系統(tǒng)模型

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

由于短數(shù)據(jù)流具有更少的完成時(shí)間，因此本文算法優(yōu)先調(diào)度短數(shù)據(jù)流。這樣一來就能降低算法的平均數(shù)據(jù)流完成時(shí)間。同時(shí)通過將長數(shù)據(jù)流降低到優(yōu)先級較低的隊(duì)列，能有效地避免護(hù)航效應(yīng)，有助于最小化長數(shù)據(jù)流的響應(yīng)時(shí)間。

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

2 問題建模

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

(1)

為了簡化問題，將θ替換為p。根據(jù)排隊(duì)論的相關(guān)理論，第l個(gè)隊(duì)列的平均等待時(shí)間為Dl，計(jì)算公式如下所示：

(2)

(3)

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

在優(yōu)化問題(3)中，由于流量負(fù)載β是小于等于1，于是有以下關(guān)系：

(4)

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

(5)

3 算法模塊與仿真實(shí)驗(yàn)

3.1 算法模塊

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

交換機(jī)執(zhí)行嚴(yán)格的優(yōu)先隊(duì)列機(jī)制，并根據(jù)優(yōu)先級對數(shù)據(jù)包進(jìn)行分類。采用了基于即時(shí)隊(duì)列長度的擁塞標(biāo)記。除了交換機(jī)的排隊(duì)時(shí)延外，網(wǎng)卡的時(shí)延也是不可忽略的。由網(wǎng)卡等硬件帶來的時(shí)延會嚴(yán)重降低應(yīng)用程序的性能。為了解決這個(gè)問題，以線路速率對傳輸速率進(jìn)行限速。

3.2 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)首先采用一個(gè)由16臺工作站組成的網(wǎng)絡(luò)拓?fù)?，這些工作站均連接到華為S1720-52GWR-4P 48口全千兆以太網(wǎng)絡(luò)交換機(jī)。交換機(jī)的每個(gè)端口最多支持8個(gè)服務(wù)隊(duì)列，工作站均為聯(lián)想工作站ThinkStation P920。服務(wù)器安裝了CentOS 7操作系統(tǒng)，內(nèi)核的版本為3.10.0，往返時(shí)延為100 μs。還設(shè)置了一個(gè)較小的網(wǎng)絡(luò)拓?fù)?，用于測量高速網(wǎng)絡(luò)中終端主機(jī)的排隊(duì)時(shí)延。該拓?fù)溆?個(gè)服務(wù)器和1個(gè)交換機(jī)組成。

本算法默認(rèn)使用8個(gè)優(yōu)先隊(duì)列，并在每個(gè)端口啟用擁塞標(biāo)記。將擁塞標(biāo)記的閾值設(shè)置為推薦的30 kB。使用兩個(gè)真實(shí)的流量數(shù)據(jù)集：網(wǎng)頁搜索流量和數(shù)據(jù)中心網(wǎng)絡(luò)數(shù)據(jù)挖掘流量。

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

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

圖1 兩種算法在小數(shù)據(jù)流下的流完成時(shí)間

圖2 兩種算法在大數(shù)據(jù)流下的流完成時(shí)間

圖3 兩種算法的查詢完成時(shí)間

4 結(jié)論

在一個(gè)信息不可知的數(shù)據(jù)中心網(wǎng)絡(luò)中，DCIA算法利用商品交換機(jī)來最小化數(shù)據(jù)流的平均完成時(shí)間。通過仿真實(shí)驗(yàn)進(jìn)行性能評估，實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有方法相比，DCIA算法具有較好的性能。未來的工作將集中于利用不同的大規(guī)模網(wǎng)絡(luò)，設(shè)置不同的真實(shí)場景，對該算法進(jìn)行深入地分析評估。