陳金魚
(廈門軟件職業(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)用,錯(cuò)過數(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í)間。
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í)間。
本研究目的是最小化平均流完成時(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)
標(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)行限速。
仿真實(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í)間
在一個(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)行深入地分析評估。