數(shù)據(jù)中心內(nèi)Incast流量的網(wǎng)內(nèi)聚合研究

郭得科　羅來(lái)龍　李　妍　胡智堯　任棒棒

(信息系統(tǒng)工程國(guó)防科技重點(diǎn)實(shí)驗(yàn)室(國(guó)防科學(xué)技術(shù)大學(xué))　長(zhǎng)沙　410073)

(dekeguo@nudt.edu.cn)

?

數(shù)據(jù)中心內(nèi)Incast流量的網(wǎng)內(nèi)聚合研究

郭得科羅來(lái)龍李妍胡智堯任棒棒

(信息系統(tǒng)工程國(guó)防科技重點(diǎn)實(shí)驗(yàn)室(國(guó)防科學(xué)技術(shù)大學(xué))長(zhǎng)沙410073)

(dekeguo@nudt.edu.cn)

Aggregating Incast Transfers in Data Centers

Guo Deke, Luo Lailong, Li Yan, Hu Zhiyao, and Ren Bangbang

(KeyLaboratoryonInformationSystemandEngineering(NationalUniversityofDefenseTechnology),Changsha410073)

AbstractData transfers, such as the common shuffle and incast communication patterns, contribute most of the network traffic in MapReduce like working paradigms and thus have severe impacts on application performance in modern data centers. This motivates us to bring opportunities for performing the inter-flow data aggregation during the transmission phase as early as possible rather than just at the receiver side. In this paper, we first examine the gain and feasibility of the inter-flow data aggregation with novel data center network structures. To achieve such a gain, we model the incast minimal tree problem. We propose two approximate incast tree construction methods, RS-based and ARS-based incast trees. We are thus able to generate an efficient incast tree solely based on the labels of incast members and the data center topology. We further present incremental methods to tackle the dynamic and fault-tolerant issues of the incast tree. Based on a prototype implementation and large-scale simulations, we demonstrate that our approach can significantly decrease the amount of network traffic, save the data center resources, and reduce the delay of job processing. Our approach for BCube and FBFLY can be adapted to other data centers structures with minimal modifications.

Key wordsin-network aggregation; data centers; incast transfer; shuffle transfer; network transfer

摘要MapReduce等分布式計(jì)算系統(tǒng)應(yīng)用在數(shù)據(jù)中心內(nèi)產(chǎn)生了嚴(yán)重的東西向流量，其中以incast和shuffle為代表的關(guān)聯(lián)性流量占相當(dāng)大的比重，進(jìn)而嚴(yán)重影響到上層應(yīng)用的性能.這促使研究者們考慮在這些關(guān)聯(lián)性流量的網(wǎng)內(nèi)傳輸階段盡可能早而不是僅在流量的接收端進(jìn)行流間數(shù)據(jù)聚合.首先以新型數(shù)據(jù)中心網(wǎng)絡(luò)結(jié)構(gòu)為背景討論流間數(shù)據(jù)聚合的可行性和增益，為最大化該增益，為incast傳輸建立最小代價(jià)樹模型.為解決該模型，提出了2種近似的incast樹構(gòu)造方法，其能夠僅基于incast成員的位置和數(shù)據(jù)中心拓?fù)浣Y(jié)構(gòu)生成一個(gè)有效的incast樹，進(jìn)一步解決了incast樹的動(dòng)態(tài)和容錯(cuò)問(wèn)題.最后，采用原型系統(tǒng)和大規(guī)模仿真的方法評(píng)估了incast流量的網(wǎng)內(nèi)聚合方法，實(shí)驗(yàn)結(jié)果證明該方法能大幅降低incast流量造成的傳輸開銷，能節(jié)約數(shù)據(jù)中心的網(wǎng)絡(luò)資源.同時(shí)，提出的模型和解決方法也適用于其他類型的數(shù)據(jù)中心網(wǎng)絡(luò)結(jié)構(gòu).

關(guān)鍵詞網(wǎng)內(nèi)聚合；數(shù)據(jù)中心；incast傳輸；shuffle傳輸；網(wǎng)絡(luò)流量

大規(guī)模數(shù)據(jù)中心不僅服務(wù)于各類在線云應(yīng)用，而且還直接服務(wù)于大規(guī)模分布式計(jì)算系統(tǒng)，如MapReduce[1]，Dryad[2]，CIEL[3]，Pregel[4]和Spark[5]等.這些分布式計(jì)算系統(tǒng)向數(shù)據(jù)中心提交大量處理作業(yè)，每項(xiàng)作業(yè)都可能需要使用數(shù)據(jù)中心內(nèi)大量的服務(wù)器.這些計(jì)算系統(tǒng)普遍遵從流計(jì)算模式，即在相鄰處理階段間需要傳遞大量的中間計(jì)算結(jié)果.這種類型的數(shù)據(jù)傳輸為數(shù)據(jù)中心貢獻(xiàn)了大約80%的東西向流量[5]，因此對(duì)分布式應(yīng)用的性能和數(shù)據(jù)中心的運(yùn)營(yíng)產(chǎn)生了嚴(yán)重影響.

我們觀察到，上述很多計(jì)算系統(tǒng)的作業(yè)在接收端采用了多種聚合操作以降低其輸出數(shù)據(jù)的規(guī)模.例如，在MapReduce作業(yè)的shuffle階段，每一個(gè)reducer被分配一個(gè)map階段輸出值域空間的唯一子空間；然后reducer從每個(gè)mapper的輸出中提取其負(fù)責(zé)的部分內(nèi)容，并在獲取后進(jìn)行reduce操作.對(duì)于大多數(shù)的reduce函數(shù)，如MIN,MAX,SUM,COUNT,TOP-K和KNN來(lái)說(shuō)，其涉及到的數(shù)據(jù)流之間具有較高的關(guān)聯(lián)性和很好的聚合效益.以Facebook的MapReduce作業(yè)為例，每個(gè)reducer聚合后的輸出數(shù)據(jù)規(guī)模比其輸入數(shù)據(jù)規(guī)模平均減少了81.7%[6].該觀測(cè)結(jié)果促使我們思考，是否可在上述關(guān)聯(lián)性流量的網(wǎng)內(nèi)傳輸過(guò)程中盡可能早地實(shí)施數(shù)據(jù)聚合操作，而不是僅僅在接收端開展.如果網(wǎng)內(nèi)數(shù)據(jù)聚合能夠?qū)崿F(xiàn)，則數(shù)據(jù)中心內(nèi)的東西流量將會(huì)大幅度降低，并且reducer端輸入數(shù)據(jù)量的降低也會(huì)加速作業(yè)的處理速度.

本研究旨在通過(guò)管理和優(yōu)化關(guān)聯(lián)性流量的協(xié)同傳輸以實(shí)現(xiàn)流量的網(wǎng)內(nèi)聚合.本研究重點(diǎn)關(guān)注多對(duì)一的incast傳輸模式[5].當(dāng)前incast傳輸模式普遍被分解為一系列單播來(lái)實(shí)現(xiàn)，并不考慮其關(guān)聯(lián)性數(shù)據(jù)流的潛在聚合行為.

對(duì)于incast傳輸，只有參與聚合的相關(guān)數(shù)據(jù)流能夠在傳播路徑的某些交匯點(diǎn)上進(jìn)行網(wǎng)內(nèi)緩存和網(wǎng)內(nèi)處理時(shí)，網(wǎng)內(nèi)聚合增益才能實(shí)現(xiàn).在以交換機(jī)為核心的數(shù)據(jù)中心互聯(lián)結(jié)構(gòu)[7-12]中，傳統(tǒng)交換機(jī)的計(jì)算能力和緩存空間不足，因此這類互聯(lián)結(jié)構(gòu)支持incast流量網(wǎng)內(nèi)聚合的能力非常有限.但是從技術(shù)發(fā)展趨勢(shì)看，業(yè)界已提出許多以服務(wù)器為核心的數(shù)據(jù)中心互聯(lián)結(jié)構(gòu)[13-17].在這些結(jié)構(gòu)中，主要的互聯(lián)和路由功能由服務(wù)器承擔(dān)，交換機(jī)只提供簡(jiǎn)單的縱橫式交換功能，因此具備網(wǎng)內(nèi)緩存和數(shù)據(jù)包的深度處理能力.另外，由于任意2臺(tái)服務(wù)器間存在多條不相交的路由路徑，易于主動(dòng)構(gòu)造出盡可能多的交匯點(diǎn)以支持網(wǎng)內(nèi)聚合，因此為管理incast傳輸帶來(lái)了機(jī)會(huì).

本文中，我們首先以服務(wù)器為核心的數(shù)據(jù)中心網(wǎng)絡(luò)結(jié)構(gòu)為背景，探討incast傳輸網(wǎng)內(nèi)聚合的可行性及潛在增益.為方便研究，incast傳輸?shù)牧髁烤酆蠁?wèn)題被建模成incast最小聚合樹的構(gòu)建問(wèn)題.我們進(jìn)而提出了2種近似的incast聚合樹構(gòu)建方法，分別為基于RS(routing symbol)的方法和基于ARS(advanced routing symbol)的方法.在此基礎(chǔ)上進(jìn)一步考慮了incast樹構(gòu)造的動(dòng)態(tài)性和容錯(cuò)問(wèn)題，并提出漸進(jìn)式解決方案.

最后通過(guò)原型實(shí)現(xiàn)評(píng)估我們提出的方法，實(shí)驗(yàn)結(jié)果表明我們的方法能顯著減少網(wǎng)絡(luò)流量、節(jié)約數(shù)據(jù)中心的網(wǎng)絡(luò)資源、加快作業(yè)的完成時(shí)間.基于ARS的方法能為數(shù)據(jù)中心BCube(6,k)(3≤k≤9)內(nèi)一個(gè)有320個(gè)發(fā)送端的incast傳輸平均降低了38%的網(wǎng)絡(luò)流量.在容納262 144個(gè)服務(wù)器的數(shù)據(jù)中心BCube(8,5)中，為包含100～4 000個(gè)發(fā)送端的incast傳輸平均節(jié)省了58%的網(wǎng)絡(luò)流量.如果對(duì)每個(gè)incast傳輸?shù)陌l(fā)送端和接收方的部署位置進(jìn)行優(yōu)化，則能節(jié)省更多的網(wǎng)絡(luò)流量.

1背景知識(shí)

1.1數(shù)據(jù)中心的網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu)

在數(shù)據(jù)中心內(nèi)，大量服務(wù)器和交換機(jī)通過(guò)特定的網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu)連接起來(lái).傳統(tǒng)數(shù)據(jù)中心中網(wǎng)絡(luò)設(shè)備被組織成樹型結(jié)構(gòu)，服務(wù)器掛接在網(wǎng)絡(luò)設(shè)備的預(yù)留端口上.近年來(lái)，學(xué)術(shù)界為數(shù)據(jù)中心提出了許多新型網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu)，大致可分為2類：

1) 以交換機(jī)為核心的網(wǎng)絡(luò)結(jié)構(gòu).該結(jié)構(gòu)將交換機(jī)組織成樹型之外的其他特定結(jié)構(gòu)，并將網(wǎng)絡(luò)互聯(lián)和路由功能放到交換機(jī)上.典型代表包括Fat-Tree[7],VL2[8]和PortLand[9]等Clos網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu)，其本質(zhì)上是傳統(tǒng)樹型結(jié)構(gòu)的變種.為進(jìn)一步優(yōu)化現(xiàn)有的互聯(lián)結(jié)構(gòu)，出現(xiàn)了以交換機(jī)為核心的扁平化互聯(lián)結(jié)構(gòu)——FBFLY[10]和HyperX[11].在這2種互聯(lián)結(jié)構(gòu)中，大量的多端口通用交換機(jī)被互聯(lián)為廣義超級(jí)立方體結(jié)構(gòu)[18]，而服務(wù)器掛接在網(wǎng)絡(luò)設(shè)備的剩余端口.所有鏈路和交換機(jī)都被平等均衡地使用，因此不存在設(shè)備或鏈路上的性能瓶頸，其整體性能要優(yōu)于樹型及Clos等結(jié)構(gòu).

2) 以服務(wù)器為核心的網(wǎng)絡(luò)結(jié)構(gòu).其中,主要的互聯(lián)和路由功能交由服務(wù)器承擔(dān)，交換機(jī)只提供簡(jiǎn)單的縱橫式(crossbar)交換功能.DCell[13],BCube[14],CamCube[15],BCN[16],FiConn[19],SWD[20]和Scafida[21]均屬于這類結(jié)構(gòu).其中，F(xiàn)iConn和BCN 重點(diǎn)關(guān)注數(shù)據(jù)中心內(nèi)基于雙端口服務(wù)器的低成本網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu)；SWD和Scafida將小世界和無(wú)標(biāo)度網(wǎng)絡(luò)理論引進(jìn)到數(shù)據(jù)中心網(wǎng)絡(luò)結(jié)構(gòu)中.

在這些新型數(shù)據(jù)中心結(jié)構(gòu)中，F(xiàn)BFLY和BCube(k-aryn-flat flattened butterfly)是上述2類中最具代表性的網(wǎng)絡(luò)結(jié)構(gòu).

1) FBFLY.FBFLY充分利用了高端口交換機(jī)的特性，是一種可拓展的網(wǎng)絡(luò)結(jié)構(gòu)，具有較小的網(wǎng)絡(luò)直徑.其基本思想是用廣義超級(jí)立方體結(jié)構(gòu)來(lái)互連所有交換機(jī).每個(gè)維度的所有交換機(jī)都彼此全互聯(lián)，每個(gè)交換機(jī)用剩余的端口連接服務(wù)器.在FBFLY中，任何服務(wù)器對(duì)之間都不直接相連，且服務(wù)器只能與一個(gè)交換機(jī)相連.例如，對(duì)于c=2的4-ary 3-flat FBFLY，有c×kn-1=2×42=32個(gè)服務(wù)器和kn-1=16個(gè)8口交換機(jī)，每個(gè)交換機(jī)與c=2個(gè)服務(wù)器相連.若c=1，則FBFLY就只能容納16個(gè)服務(wù)器.

2) BCube.BCube是廣義超級(jí)立方體互聯(lián)結(jié)構(gòu)的變形.BCube0是n個(gè)服務(wù)器連到一個(gè)n端口交換機(jī)的整體表示.BCubek(k≥1)是由n個(gè)BCubek-1和nk個(gè)n端口交換機(jī)構(gòu)成，其中BCubek的每臺(tái)服務(wù)器均有k+1個(gè)端口.多NIC端口的服務(wù)器與多層交換機(jī)相連，但交換機(jī)間不能直接相連.圖1為BCube(4,1)的網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu)，其由nk+1=16個(gè)服務(wù)器和2層共nk×(k+1)=8個(gè)交換機(jī)組成.

Fig. 1　Structure of BCube(4,1).圖1　BCube(4,1)結(jié)構(gòu)

雖然新型網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu)之間存在很大的差異，但也存在3個(gè)共同點(diǎn)：1)數(shù)據(jù)中心設(shè)計(jì)的趨勢(shì)是盡可能采用低成本的通用服務(wù)器和交換機(jī)來(lái)替換原來(lái)的專用服務(wù)器和網(wǎng)絡(luò)設(shè)備;2)這些網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu)擁有高鏈路密度，為任意一對(duì)服務(wù)器之間提供多條平行路由路徑;3)這些網(wǎng)絡(luò)結(jié)構(gòu)的構(gòu)造方式簡(jiǎn)單易行.這些趨勢(shì)給管理和聚合數(shù)據(jù)流量帶來(lái)了新的機(jī)會(huì)和挑戰(zhàn).

1.2數(shù)據(jù)中心內(nèi)的shuffle傳輸

我們以MapReduce為例簡(jiǎn)要介紹數(shù)據(jù)中心內(nèi)普遍存在的shuffle傳輸.一個(gè)MapReduce作業(yè)包含2個(gè)連續(xù)的處理階段，即map階段和reduce階段.在map階段，mapper任務(wù)對(duì)輸入的數(shù)據(jù)執(zhí)行map操作，產(chǎn)生一個(gè)鍵值對(duì)的序列;在reduce階段，reducer任務(wù)對(duì)輸入的數(shù)據(jù)執(zhí)行用戶定義的reduce操作，通常是聚合操作.

每個(gè)reducer任務(wù)被分配一個(gè)mapper輸出的值域區(qū)間的一個(gè)唯一劃分，在shuffle階段從每個(gè)mapper的輸出中被動(dòng)提取出分配給它的鍵值對(duì).所有mapper到同一reducer的數(shù)據(jù)流之間高度關(guān)聯(lián)，因?yàn)槊總€(gè)mapper輸出的值域區(qū)間和劃分策略相同.最近，研究人員提出數(shù)據(jù)管道技術(shù)對(duì)shuffle傳輸?shù)倪^(guò)程進(jìn)行優(yōu)化，至此一旦某個(gè)mapper任務(wù)完成，其會(huì)主動(dòng)將中間運(yùn)算結(jié)果向?qū)?yīng)的reducer進(jìn)行推送[21-23].

不管MapReduce作業(yè)采用數(shù)據(jù)提取還是數(shù)據(jù)推送機(jī)制，shuffle傳輸都普遍存在于map和reduce階段之間.Dryad,CIEL,Pregel和Spark等數(shù)據(jù)中心中其他分布式計(jì)算框架，都擁有類似的多階段處理架構(gòu).一般來(lái)說(shuō)，shuffle傳輸包含m個(gè)發(fā)送端和n個(gè)接收端，任意一對(duì)發(fā)送端和接收端之間形成一條數(shù)據(jù)流. incast傳輸則由m個(gè)發(fā)送端和其中一個(gè)接收端形成，每個(gè)發(fā)送端都向同一接收端發(fā)送數(shù)據(jù)流.

2Incast傳輸中的數(shù)據(jù)聚合

由于shuffle 傳輸可以分解為一組彼此獨(dú)立的incast傳輸，因此本研究重點(diǎn)探討incast傳輸?shù)木W(wǎng)內(nèi)數(shù)據(jù)聚合.本節(jié)中，我們首先研究incast流間數(shù)據(jù)聚合的可行性.在此基礎(chǔ)上，進(jìn)一步探索如何構(gòu)造incast最小代價(jià)傳播樹以及如何在傳播樹上執(zhí)行流間的數(shù)據(jù)聚合操作.

2.1Incast數(shù)據(jù)流間聚合的可行性

我們發(fā)現(xiàn)incast傳輸中的諸多數(shù)據(jù)流存在內(nèi)在的高度關(guān)聯(lián)性，其主要原因在于對(duì)所有mapper來(lái)說(shuō)其運(yùn)算結(jié)果的值域和劃分規(guī)則是相同的，這些數(shù)據(jù)流的數(shù)據(jù)(一系列鍵值對(duì))共享分配給相同接收端的同一個(gè)值域區(qū)間.如圖2所示，對(duì)于incast傳輸?shù)哪硞€(gè)數(shù)據(jù)流來(lái)說(shuō)，其鍵值序列與其他數(shù)據(jù)流具有相同的鍵值序列.

Fig. 2　An example of incast aggregation.圖2　關(guān)于incast傳輸?shù)木W(wǎng)內(nèi)聚合示意圖

本文的研究工作基于2個(gè)發(fā)現(xiàn)來(lái)開展:1)在incast傳輸中，接收端普遍對(duì)其所有輸入數(shù)據(jù)流運(yùn)用聚合函數(shù)進(jìn)行處理，如MIN,MAX,SUM,COUNT,TOP-K和KNN;2)雖然發(fā)送端在將其運(yùn)算結(jié)果傳遞給接收端之前采用combine操作，接收端已經(jīng)能發(fā)揮部分聚合效應(yīng)，但不同流之間還存在相當(dāng)大的數(shù)據(jù)聚合機(jī)會(huì).這促使我們考慮能否在傳輸階段盡可能早地對(duì)數(shù)據(jù)流進(jìn)行聚合操作，而不僅僅在接收端執(zhí)行該操作.如果這種流間數(shù)據(jù)聚合能得以應(yīng)用，則能極大地減少網(wǎng)內(nèi)流量以及shuffle階段傳輸?shù)臄?shù)據(jù)量，并且不會(huì)損害接收端計(jì)算結(jié)果的正確性.關(guān)聯(lián)性數(shù)據(jù)流的網(wǎng)絡(luò)聚合要求參與的流量在傳播過(guò)程中遇到一些交匯節(jié)點(diǎn)，同時(shí)這些交匯節(jié)點(diǎn)應(yīng)能支持流量報(bào)文的緩存和聚合.在以交換機(jī)為核心的數(shù)據(jù)中心中，由于傳統(tǒng)交換機(jī)的緩存空間和包處理能力有限，因此不支持?jǐn)?shù)據(jù)流的網(wǎng)內(nèi)聚合功能能力，而網(wǎng)內(nèi)流量聚合則可以在以服務(wù)器為核心的數(shù)據(jù)中心內(nèi)得到自然支持.但是，隨著技術(shù)的發(fā)展，SDN技術(shù)體制下交換機(jī)的可編程成為可能[24-26].當(dāng)前，Cisco和Arista已研制開發(fā)了具有可編程數(shù)據(jù)平面的應(yīng)用交換機(jī)數(shù)據(jù)平面[27-28]，使得在以交換機(jī)為核心的數(shù)據(jù)中心中開展流間數(shù)據(jù)聚合成為可能.

在以服務(wù)器為核心的數(shù)據(jù)中心內(nèi)，多端口商業(yè)服務(wù)器不僅作為終端主機(jī)，同時(shí)也可作為交換機(jī)使用.實(shí)際應(yīng)用中，服務(wù)器通過(guò)千兆可編程交換板卡ServerSwitch來(lái)定制報(bào)文轉(zhuǎn)發(fā)功能[29].由于交換芯片和服務(wù)器的CPU之間存在高吞吐量以及低延時(shí)通道等優(yōu)勢(shì)，ServerSwitch可調(diào)用服務(wù)器的CPU來(lái)進(jìn)行網(wǎng)內(nèi)數(shù)據(jù)分析處理.如先前的研究工作[29-30]所言，配備ServerSwitch的服務(wù)器能支持新型網(wǎng)絡(luò)設(shè)備，如網(wǎng)內(nèi)包緩存.因此，以服務(wù)器為核心的數(shù)據(jù)中心網(wǎng)絡(luò)結(jié)構(gòu)為實(shí)現(xiàn)流間數(shù)據(jù)聚合帶來(lái)了可能.

2.2Incast最小代價(jià)樹

令圖G=(V,E)代表一個(gè)數(shù)據(jù)中心，其中V為點(diǎn)集，E為邊集.圖中的點(diǎn)v代表數(shù)據(jù)中心內(nèi)的交換機(jī)或服務(wù)器，邊(u,v)代表點(diǎn)u到v的鏈路，u,v∈V.

本節(jié)旨在通過(guò)對(duì)網(wǎng)內(nèi)相關(guān)流量進(jìn)行網(wǎng)內(nèi)數(shù)據(jù)聚合，最小化incast傳輸過(guò)程產(chǎn)生的總流量.對(duì)于任意一項(xiàng)incast傳輸，其中接收端為r，發(fā)送端為{s1,s2,…,sm}，我們要在圖G=(V,E)中為其生成一棵incast聚合樹.每個(gè)發(fā)送端的數(shù)據(jù)流沿著生成的聚合樹傳送到相同的接收端r.在BCube和FBFLY等數(shù)據(jù)中心中，對(duì)于每個(gè)incast傳輸而言存在大量該類incast聚合樹.難題在于如何尋找一棵incast聚合樹，其網(wǎng)內(nèi)數(shù)據(jù)聚合后產(chǎn)生最少的網(wǎng)絡(luò)流量.

對(duì)于任意incast聚合樹而言，如果其中某節(jié)點(diǎn)支持網(wǎng)內(nèi)緩存并且接收到至少2個(gè)輸入流，則該節(jié)點(diǎn)能實(shí)現(xiàn)網(wǎng)內(nèi)數(shù)據(jù)聚合.這樣的節(jié)點(diǎn)稱為聚合節(jié)點(diǎn)(aggregating nodes)，其他節(jié)點(diǎn)稱為非聚合節(jié)點(diǎn).需要注意的是，節(jié)點(diǎn)自身生成的數(shù)據(jù)流也可被看作其輸入流.在每個(gè)聚合節(jié)點(diǎn)上，多個(gè)數(shù)據(jù)流被最終聚合為一條新的數(shù)據(jù)流.為便于表述，我們假設(shè)經(jīng)聚合后產(chǎn)生的新數(shù)據(jù)流的大小等于所有輸入中的最大數(shù)據(jù)流大小.在實(shí)驗(yàn)部分，我們將探討更通用的incast傳輸配置.在非聚合節(jié)點(diǎn)，由于其不支持網(wǎng)內(nèi)緩存及數(shù)據(jù)包處理，輸出數(shù)據(jù)流的大小為輸入數(shù)據(jù)流大小的總和.

對(duì)于給定的incast聚合樹，其代價(jià)被定義為完成incast傳輸而引發(fā)的網(wǎng)絡(luò)流量總和.更準(zhǔn)確地說(shuō)，incast聚合樹的代價(jià)是其所有邊權(quán)重的總和，即incast聚合樹中除接收端以外的所有節(jié)點(diǎn)輸出流量的總和.我們假設(shè)所有發(fā)送端生成的流量均為1 MB，由此incast聚合樹的代價(jià)便可標(biāo)準(zhǔn)化.此時(shí)，聚合節(jié)點(diǎn)輸出鏈路的權(quán)值為1.

對(duì)于incast傳輸來(lái)說(shuō)，最小代價(jià)聚合樹問(wèn)題是在G(V,E)中找到一個(gè)覆蓋所有incast成員且代價(jià)最小的連通子圖.因此，問(wèn)題轉(zhuǎn)化為如何為數(shù)據(jù)中心中的incast傳輸構(gòu)建一棵incast最小代價(jià)樹.

2.3基于Incast樹的流間數(shù)據(jù)聚合實(shí)現(xiàn)

對(duì)于incast傳輸而言，為其構(gòu)造出最小代價(jià)incast聚合樹之后，相關(guān)管理器可據(jù)此實(shí)現(xiàn)其傳輸過(guò)程.

首先，incast管理器通過(guò)廣播的方式將生成的incast聚合樹拓?fù)浣Y(jié)構(gòu)通知給樹內(nèi)所有服務(wù)器，則涉及到的服務(wù)器將會(huì)知道其父服務(wù)器和子樹的結(jié)構(gòu).若某個(gè)服務(wù)器有一個(gè)以上的子服務(wù)器或其本身就是發(fā)送端且有一個(gè)子服務(wù)器，則該服務(wù)器為聚合服務(wù)器.如圖3(c)所示，服務(wù)器v0,v1,v2都是聚合服務(wù)器.在此基礎(chǔ)上，管理器將一些數(shù)據(jù)聚合任務(wù)配置到這些聚合服務(wù)器上，聚合服務(wù)器在向下轉(zhuǎn)發(fā)數(shù)據(jù)流之前首先對(duì)其輸入數(shù)據(jù)進(jìn)行聚合運(yùn)算.

若發(fā)送端的數(shù)據(jù)已經(jīng)準(zhǔn)備好，并且其本身并非聚合服務(wù)器，則該發(fā)送端將數(shù)據(jù)流沿著incast聚合樹傳遞給接收端.數(shù)據(jù)流一旦到達(dá)聚合服務(wù)器，所有的包都會(huì)被緩存.若來(lái)自該聚合服務(wù)器所有后續(xù)服務(wù)器的數(shù)據(jù)流都已到達(dá)，則聚合服務(wù)器將按照下面的方式進(jìn)行網(wǎng)內(nèi)數(shù)據(jù)聚合.首先按照數(shù)據(jù)流鍵值對(duì)的鍵值對(duì)其分組，然后分別對(duì)每組使用聚合函數(shù)，最終產(chǎn)生一條新流取代原來(lái)所有的輸入流.

Fig. 3　Different incast trees for an incast transfer in a BCube(4,1).圖3　Bcube(4,1)拓?fù)浣Y(jié)構(gòu)中不同的incast聚合樹

聚合服務(wù)器也可以在數(shù)據(jù)流到達(dá)時(shí)立即進(jìn)行聚合操作.該機(jī)制避免了等待所有輸入流所產(chǎn)生的延遲.在incast傳播樹的唯一接收端對(duì)其所有輸入流使用reduce函數(shù)進(jìn)行聚合.圖2描述了一個(gè)基于incast樹的流間數(shù)據(jù)聚合示例.從圖2可以看出，數(shù)據(jù)流1和數(shù)據(jù)流2匯合成了數(shù)據(jù)流5，數(shù)據(jù)流3和4被聚合成數(shù)據(jù)流6，數(shù)據(jù)流5和流6被轉(zhuǎn)發(fā)到接收端并聚合成數(shù)據(jù)流7.

相關(guān)研究發(fā)現(xiàn)，類似MapReduce的分布式系統(tǒng)面臨計(jì)算偏斜的影響[31].其中，map任務(wù)偏斜程度最大，其運(yùn)行時(shí)間不只取決于輸入數(shù)據(jù)的規(guī)模，而且受隨機(jī)因素的影響較大.此時(shí)，一些map任務(wù)要花費(fèi)比其他任務(wù)更長(zhǎng)的時(shí)間去處理輸入數(shù)據(jù)，這就減緩了整個(gè)作業(yè)的處理過(guò)程.因此，其他發(fā)送端將在最慢的發(fā)送端完成之前沿incast樹傳遞各自的輸出數(shù)據(jù)流.最后一條數(shù)據(jù)流成功到達(dá)接收端的完成時(shí)間即為incast傳輸在shuffle階段的總耗時(shí).其中，最后一條數(shù)據(jù)流在其傳播路徑上的每個(gè)聚合服務(wù)器處都需要耗費(fèi)一定的計(jì)算時(shí)間.然而，對(duì)于數(shù)據(jù)流來(lái)說(shuō)，其所經(jīng)過(guò)的聚合服務(wù)器總數(shù)最大為該樹的深度減去1，例如在BCube(n,k)網(wǎng)絡(luò)中最多為k.這種額外時(shí)間代價(jià)與map或reduce階段的計(jì)算時(shí)間相比，對(duì)整個(gè)作業(yè)完成時(shí)間影響很小.因此，這類額外時(shí)間對(duì)像MapReduce這樣的批處理系統(tǒng)而言可以承受.

3高效Incast聚合樹的構(gòu)建

本節(jié)我們首先提出2種incast聚合樹的近似構(gòu)建方法，即基于RS的方法和基于ARS的方法.在此基礎(chǔ)上優(yōu)化incast聚合樹的構(gòu)造問(wèn)題，提出高效的構(gòu)建策略，并探討了incast聚合樹的動(dòng)態(tài)性和容錯(cuò)問(wèn)題.

3.1Incast聚合樹的構(gòu)建方法

為了滿足大量發(fā)送端的incast聚合樹的快速構(gòu)建需求，我們深入挖掘數(shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)涮卣?，進(jìn)而設(shè)計(jì)了一種近似的構(gòu)造方法.

在數(shù)據(jù)中心網(wǎng)絡(luò)中，任意服務(wù)器對(duì)之間有多條可用平行路徑.在BCube(n,k)中，如果任意一對(duì)服務(wù)器的標(biāo)識(shí)符在k+1個(gè)維度上不同，則二者之間有k+1條平行不相交路徑.incast最小代價(jià)樹問(wèn)題的一種直觀解決方法就是，每個(gè)發(fā)送端獨(dú)立選擇其中一條單播路徑將其數(shù)據(jù)傳輸給接收端.這種單播驅(qū)動(dòng)的incast樹由源自全體發(fā)送端的單播路徑混合而成.不足之處在于，這種方法可獲得的網(wǎng)內(nèi)流量聚合增益并不大.

圖3(a)給出了BCube(4,1)中單播驅(qū)動(dòng)的incast樹的示意圖.唯一的接收端是v0，發(fā)送端集合是{v2,v5,v9,v10,v11,v14}.產(chǎn)生的incast樹由18條鏈路構(gòu)成，總代價(jià)為22，沒(méi)有聚合節(jié)點(diǎn).但是，如果依據(jù)圖3(c)所示的方式來(lái)構(gòu)造incast的傳播樹，則該incast傳播樹只有12條鏈路，總代價(jià)是16，而且其中有2個(gè)聚合節(jié)點(diǎn)v1和v2.

incast網(wǎng)內(nèi)聚合功能需要集中式的管理器負(fù)責(zé)最小傳播樹的構(gòu)造，MapReduce架構(gòu)中的JobTracker可以承擔(dān)該角色.當(dāng)所有incast成員的標(biāo)識(shí)符給定之后，incast管理器可以通過(guò)挖掘數(shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)湫再|(zhì)，高效計(jì)算出傳播代價(jià)盡可能小的incast樹.

數(shù)據(jù)中心的網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu)BCube(n,k)可被抽象為k+1維n-ary的廣義超級(jí)立方體[18].在BCube(n,k)和廣義超級(jí)立方體中，一對(duì)服務(wù)器xkxk-1…x1x0和ykyk-1…y1y0被互稱為維j的1跳鄰居，當(dāng)且僅當(dāng)二者的標(biāo)識(shí)符在維j不同.因此不難得出任意一臺(tái)服務(wù)器在每個(gè)維度上都有n-1個(gè)1跳鄰居.BCube(n,k)和廣義超級(jí)立方體之間的差別僅在于，廣義超級(jí)立方體中的服務(wù)器可以直接相連，而BCube(n,k) 中的服務(wù)器卻需要通過(guò)交換機(jī)相連.也就是說(shuō)，每臺(tái)服務(wù)器和它同維度的所有鄰居都通過(guò)一個(gè)共同的交換機(jī)間接地連在一起.以此類推，若2個(gè)服務(wù)器的標(biāo)識(shí)符在j個(gè)維度存在差異，則二者互為j跳鄰居.

考慮BCube(n,k)中的某個(gè)incast傳輸，其中接收端為r，發(fā)送端的集合為{s1,s2,…,sm}.令接收端的標(biāo)識(shí)符為rkrk-1…r1r0，發(fā)送端的標(biāo)識(shí)符為sksk-1…s1s0.為不失一般性，我們假設(shè)incast傳輸中接收端和發(fā)送端的最大海明距離為k+1，更一般的場(chǎng)景將在后續(xù)進(jìn)行討論.所有發(fā)送端到接收端的最短路徑可被擴(kuò)展為階段k+2的多級(jí)有向圖.其中，只有接收端位于階段0，而位于階段j的服務(wù)器必須是接收端的j跳鄰居.另外，必須有一組交換機(jī)作為2個(gè)相鄰階段的中繼，因?yàn)樵贐Cube(n,k)中服務(wù)器不能直連.

需要注意的是，若某個(gè)發(fā)送端是接收端的j跳鄰居，則其必然出現(xiàn)在階段j.如圖3所示，發(fā)送端v5,v9,v10,v11和v14都位于階段2，但另一個(gè)發(fā)送端v2卻位于階段1.然而，只有這些發(fā)送端和接收端不足以形成包含所有incast成員的連通子圖.因此，問(wèn)題被轉(zhuǎn)化為如何為每個(gè)階段增添最少數(shù)目的額外服務(wù)器，以及如何在相鄰階段之間選擇交換機(jī)以構(gòu)成incast最小代價(jià)樹.

定義1. 對(duì)于incast樹中階段j-1的服務(wù)器集合A以及階段j的服務(wù)器集合B，A包含B當(dāng)且僅當(dāng)B中的每臺(tái)服務(wù)器都存在一條有向鏈路從其自身到A中的服務(wù)器.如果A的任何子集都不包含B，我們就稱A嚴(yán)格包含B.

考慮到交換機(jī)標(biāo)識(shí)符可由與其相連的2個(gè)服務(wù)器推斷得出，因此我們可以只關(guān)注每個(gè)階段新增服務(wù)器的選取.定義 1旨在保證源自階段j服務(wù)器的數(shù)據(jù)流都能被準(zhǔn)確送往階段j-1的服務(wù)器.

我們從階段k+1開始為每階段確定除發(fā)送端以外的新增服務(wù)器，直至階段1.構(gòu)建過(guò)程必須滿足一個(gè)限制條件，即階段j-1的服務(wù)器嚴(yán)格包含階段j的服務(wù)器(1≤j≤k+1).給定階段j的服務(wù)器集合，通過(guò)利用BCube(n,k)的拓?fù)涮卣魍茢嘣跐M足上述約束條件下階段j-1的服務(wù)器.值得注意的是，這種階段j-1服務(wù)器集合并非是唯一的.這是由于在BCube(n,k)中階段j的每臺(tái)服務(wù)器在j維有一個(gè)共同的階段j-1的鄰居，只不過(guò)當(dāng)前服務(wù)器和接收端的標(biāo)識(shí)符在j維存在差異.在此基礎(chǔ)上，我們?yōu)閕ncast傳輸引入路由序列的概念：

定義2. 令e1e2…ej…ekek+1為包含k+1個(gè)路由符號(hào)的路由序列，是(k+1)!個(gè)組合中的一個(gè).一棵incast樹的階段j與一個(gè)路由符號(hào)ej相關(guān)聯(lián).對(duì)于階段j的服務(wù)器X=xk…xj…x1x0和接收端r，我們有：

1) 若2個(gè)標(biāo)識(shí)符的維ej不同，則將服務(wù)器X在ej維的n-1個(gè)鄰居的標(biāo)識(shí)符與接收端的標(biāo)識(shí)符對(duì)比，選擇ej維標(biāo)識(shí)符相同而其他j-1維標(biāo)識(shí)符不同的鄰居.

依照上述規(guī)則，服務(wù)器X的鄰居服務(wù)器將出現(xiàn)在incast樹中的階段j-1.給定incast傳輸及相關(guān)的路由序列e1e2…ej…ekek+1，可通過(guò)下述方法生成對(duì)應(yīng)的incast聚合樹.

我們從k+2個(gè)階段中的任意階段j開始.為不失一般性，假設(shè)j=k+1.一旦階段j的服務(wù)器給定，我們把這些服務(wù)器劃分成一個(gè)個(gè)分組，以便每個(gè)分組內(nèi)的服務(wù)器都互為維度ej上的1跳鄰居.在每個(gè)分組中，每臺(tái)服務(wù)器和接收端的標(biāo)識(shí)符在維度j上不同，即它們是接收端的j跳鄰居.在任意分組中，每臺(tái)服務(wù)器通往接收端的下一跳服務(wù)器的標(biāo)識(shí)符在維度j-1不同，并出現(xiàn)在階段j-1.需要注意的是，任意分組中的每一個(gè)服務(wù)器關(guān)于通往接收端的下一跳服務(wù)器都有j種選擇.這里，我們要求它們?cè)陔A段j-1共用相同的下一跳服務(wù)器.

為此，我們可根據(jù)定義2為所有分組中服務(wù)器各自選擇下一跳的新增服務(wù)器，并且，組中所有服務(wù)器和它們的共同下一跳服務(wù)器的標(biāo)識(shí)符除了ej維外都相同.實(shí)際上，共同的下一跳服務(wù)器和接收端的標(biāo)識(shí)符在維度ej相同.如圖3(b)所示，位于階段2的所有服務(wù)器根據(jù)路由符號(hào)e2=0被劃分為3組，分別為{5}，{9,10,11}和{14}.據(jù)此，可以推斷3個(gè)分組位于階段1的下一跳服務(wù)器分別為4,8和12.在這種方式下，如圖3(b)所示從每組到接收端的數(shù)據(jù)流在階段j-1能實(shí)現(xiàn)所期望的網(wǎng)內(nèi)數(shù)據(jù)聚合；否則，如圖3(a)所示，在階段j-1沒(méi)有機(jī)會(huì)實(shí)現(xiàn)網(wǎng)內(nèi)聚合的機(jī)會(huì).

階段j的其他節(jié)點(diǎn)分組采用同樣的方法進(jìn)行處理，至此階段j-1的服務(wù)器集合嚴(yán)格包含了j階段的服務(wù)器集合.需要注意的是，一些發(fā)送端可能原本就位于階段j-1,因此，階段j-1的服務(wù)器集合是發(fā)送端和其他新增服務(wù)器的并集.在此基礎(chǔ)上，運(yùn)用上述方法可推斷出應(yīng)該出現(xiàn)在階段j-2的新增服務(wù)器.以此類推，所有k+2個(gè)階段的服務(wù)器集合和相鄰階段間的有向路徑形成最終的incast樹，其被稱作基于路由序列的incast樹，簡(jiǎn)寫為基于RS的incast樹構(gòu)造方法.

定理1. 對(duì)于BCube(n,k)中有m個(gè)發(fā)送端的incast傳輸來(lái)說(shuō)，基于RS的incast樹構(gòu)建方法的時(shí)間復(fù)雜度為O(m×logN)，其中N=nk+1表示BCube(n,k)中服務(wù)器的數(shù)量.

證明. 我們的方法最多需要分別考慮k個(gè)階段.其中，根據(jù)ej將階段j的所有服務(wù)器分組的過(guò)程可以簡(jiǎn)化為如下方法.對(duì)處于階段j的已有服務(wù)器，我們提取它除ej維以外的標(biāo)識(shí)符，得到的標(biāo)識(shí)符表征這個(gè)服務(wù)器所在的組；然后將這個(gè)服務(wù)器加到這個(gè)分組中，推斷出組里所有服務(wù)器共同的下一跳服務(wù)器.階段j的計(jì)算開銷與該階段的服務(wù)器數(shù)量成比例.由于每階段的服務(wù)器數(shù)量不會(huì)超過(guò)m，所以其時(shí)間復(fù)雜度為O(m).考慮到算法最多運(yùn)行k個(gè)階段，因此綜上所述該方法的時(shí)間復(fù)雜度是O(m×k).定理1得證.

證畢.

3.2Incast最小代價(jià)樹的構(gòu)造方法

路由序列e1e2…ej…ekek+1可以為BCube(n,k)中任意incast傳輸產(chǎn)生一棵基于RS的incast傳播樹.對(duì)incast傳輸來(lái)說(shuō)，最多存在(k+1)!種這樣的路由序列.不同的路由序列產(chǎn)生的incast傳播樹可獲得的網(wǎng)內(nèi)聚合增益和額外代價(jià)都不同.例如，我們可由路由序列e1e2=10構(gòu)造出如圖3(b)所示的incast樹，也可以路由序列e1e2=01構(gòu)造出圖3(c)所示的另一棵incast樹.

因此，本文所面臨的難題在于，如何從(k+1)!個(gè)路由序列中挑選出某個(gè)路由序列，據(jù)此構(gòu)造的incast樹的聚合增益最大.一種簡(jiǎn)單的方法是，對(duì)所有(k+1)!種路由序列分別應(yīng)用基于RS的方法生成所有可能的incast樹，然后計(jì)算每棵incast樹的代價(jià)，從中挑選出代價(jià)最少的incast樹.這種方法帶來(lái)非常高的計(jì)算開銷，其計(jì)算復(fù)雜度是O((k+1)!×k×m).

為此，我們提出如下更高效的方法來(lái)構(gòu)造incast最小代價(jià)樹.從階段j=k+1開始，在定義了路由符號(hào)ej(0≤j≤k)后，階段j的所有服務(wù)器都能被劃分為組.在各分組內(nèi)可以采用基于RS的方法為所有分組成員確定位于階段j-1的一組下一跳服務(wù)器.這樣，分組的數(shù)量和下一階段新增的新增服務(wù)器數(shù)量剛好相等.這些新增服務(wù)器和階段j-1的原有發(fā)送端構(gòu)成了該階段的全部服務(wù)器集合.階段j的輸出數(shù)據(jù)流將在聚合服務(wù)器處融合，階段j-1的輸出數(shù)據(jù)流數(shù)量等于位于該階段的服務(wù)器總量.受此啟發(fā)，我們把基于RS的方法應(yīng)用到其他k種路由符號(hào)ej的設(shè)置上，得到相應(yīng)的另外k個(gè)處于階段j-1的服務(wù)器集合.至此，我們只需要從k+1個(gè)候選的服務(wù)器集合中選擇最小的服務(wù)器集.ej的設(shè)置被標(biāo)記為階段j中所有k+1個(gè)候選者中最好的選擇.在這種方式下，從階段j輸出的數(shù)據(jù)流在相鄰的階段j-1可以獲得最大的網(wǎng)內(nèi)聚合增益.

一旦推定出階段j-1的最小服務(wù)器集合，則可進(jìn)一步求得該階段路由符號(hào)ej-1的最佳選擇，并進(jìn)而求得相鄰階段j-2的最小服務(wù)器集合.最后，所有k+2個(gè)階段的各自服務(wù)器集合和相鄰階段間的有向路徑組成一棵incast樹，同時(shí)也可確定對(duì)應(yīng)的路由序列.這種方法稱為基于ARS的incast樹構(gòu)建方法.

我們用一個(gè)例子來(lái)闡述基于ARS方法的好處.考慮圖3中的incast傳輸，如圖3(b)所示在e2=0時(shí)，位于階段2的所有服務(wù)器被劃分為3組，分別為{5}，{9,10,11}和{14}，而位于階段1的服務(wù)器集合為{2,4,8,12}.但在e2=1的設(shè)定下，如圖3(c)所示，位于階段2的所有服務(wù)器被分為3組，分別是{5,9},{10,14}和{11}，而位于階段1的服務(wù)器集合是{1,2,3}.因此，為階段2選擇路由符號(hào)e2=1，為階段1選擇服務(wù)器集{1,2,3}.結(jié)果表明，圖3(c)所示的incast樹的代價(jià)要明顯低于圖3(b)所示的incast樹的代價(jià).

定理2. 給定BCube(n,k)中的有m個(gè)發(fā)送端的incast傳輸，基于ARS的incast樹構(gòu)造方法的時(shí)間復(fù)雜度是O(m×(logN)2)，其中N=nk+1表示BCube(n,k)中服務(wù)器的數(shù)量.

證明. 考慮到我們的方法最多在k個(gè)階段上執(zhí)行(階段k+1到階段2)，根據(jù)定理 1可知當(dāng)給定路由符號(hào)ek+1時(shí)，其在階段k+1的計(jì)算開銷是O(m).而在基于ARS的構(gòu)建方法中，我們?cè)谒衚+1種ek+1設(shè)置下執(zhí)行了相同的操作，因此以O(shè)((k+1)×m)的計(jì)算開銷作代價(jià)為階段k共生成k+1個(gè)服務(wù)器集合.另外，從k+1個(gè)路由符號(hào)中確定最小服務(wù)器集合的計(jì)算代價(jià)為O((k+1)×m).總之，在階段k+1分別運(yùn)行的incast樹構(gòu)造方法的代價(jià)計(jì)算復(fù)雜度是O((k+1)×m).

由于ek+1已占有集合{1,2,…,k+1}中的某個(gè)值，則基于ARS的方法實(shí)際上是從k個(gè)路由符號(hào)中確定階段k-1的最小服務(wù)器集，所以其最終計(jì)算開銷是O(k×m).綜上所述，基于ARS的構(gòu)造方法的總計(jì)算開銷是O(k(k+3)×m2).定理2得證.

證畢.

3.3發(fā)送端動(dòng)態(tài)行為的處理方法

已知發(fā)送端集合為{s1,s2,…,sm}，接收端為r的incast傳輸，當(dāng)額外的新發(fā)送端sm+1加入時(shí)已經(jīng)構(gòu)造好的incast樹得到更新以涵蓋這個(gè)新發(fā)送端.一種方法是針對(duì)新的發(fā)送端s1s2…smsm+1，重新運(yùn)行3.2節(jié)提出的方法構(gòu)造一棵新的incast樹.然而，這種方式產(chǎn)生了O(k2×m)的額外計(jì)算開銷.

因此，我們更傾向于用增量式方法來(lái)更新已有的incast樹.首先，incast管理器維持著路由序列與當(dāng)前incast樹的聯(lián)系.一旦一個(gè)新的發(fā)送端sm+1加入已有的incast傳輸中，通過(guò)調(diào)用傳統(tǒng)的基于RS的方法，能夠以O(shè)(k)的計(jì)算開銷推導(dǎo)出一條從sm+1到r的單播路徑.此單播路徑和先前的incast樹組合構(gòu)成新的incast樹.為了確保incast樹中所有的服務(wù)器都知道這個(gè)改變，incast管理器只需將單播路徑結(jié)構(gòu)廣播給沿路的各個(gè)服務(wù)器.通過(guò)這種方式，新incast樹中的每臺(tái)服務(wù)器都知道以其自身為根且能夠進(jìn)行網(wǎng)內(nèi)數(shù)據(jù)流聚合的子樹結(jié)構(gòu).此時(shí)，先前發(fā)送端到接收端r的路徑?jīng)]有任何改變.

當(dāng)發(fā)送端sj退出原有的某個(gè)incast傳輸時(shí)，incast樹也應(yīng)該更新以應(yīng)對(duì)這一變化.首先，在原有incast樹中，incast管理器會(huì)移除從發(fā)送端sj到接收端r的單播路徑.需要注意的是，為即將離開的發(fā)送端提取單播路徑需要將原有incast樹的相關(guān)邊的權(quán)值減去1，權(quán)值為0的邊將從樹中移除，如此一來(lái)，我們得到了新的incast樹.為確保新incast樹中所有服務(wù)器都知道這個(gè)改變，incast管理器只需將單播路徑結(jié)構(gòu)擴(kuò)散給沿路的各個(gè)服務(wù)器，這種方式同樣不會(huì)改變剩余發(fā)送端到接收端的路徑.

綜上所述，我們的incast樹構(gòu)造方法可以靈活地處理發(fā)送端的動(dòng)態(tài)行為.例如在MapReduce中主服務(wù)器常會(huì)安排某個(gè)空閑服務(wù)器去替換失敗的map任務(wù).這種過(guò)程便是由即將離開的發(fā)送端和即將加入的發(fā)送端所構(gòu)成.

3.4接收端的動(dòng)態(tài)行為

在實(shí)際應(yīng)用中，每個(gè)incast傳輸?shù)慕邮斩藃也可能會(huì)被新的接收端取代，我們用rn表示.例如，在一個(gè)MapReduce作業(yè)中，主服務(wù)器將會(huì)安排另一個(gè)服務(wù)器去替代失敗的reduce任務(wù).在這種情況下，incast管理器會(huì)采用基于ARS的方法生成一棵新的incast樹，然而這種方法導(dǎo)致過(guò)大的計(jì)算開銷為O(k2×m).

因此，我們更傾向于以增量方式更新incast樹.incast管理器為先前的incast傳輸維持著路由序列e1e2…ej…ekek+1與incast傳播樹之間的映射關(guān)系.給定原有的接收端r和新的接收端rn，我們逐維比較二者的標(biāo)識(shí)符.若標(biāo)識(shí)符只有ej維不同，則以r和rn為根的2棵incast樹從階段k+1到階段j是相同的，而從階段j到階段0出現(xiàn)差異.換句話說(shuō)，這2棵incast樹上從階段k+1到階段j的服務(wù)器集合和跨2個(gè)相鄰階段的有向路徑都是相同的.

因此，incast管理器只需重新計(jì)算從階段j到階段0的樹結(jié)構(gòu)即可.給定路由符號(hào)e1,e2,…,ej以及ej階段的服務(wù)器集合，從階段j到階段0的incast樹結(jié)構(gòu)可以用基于RS的方法獲得.

如果rn出現(xiàn)在先前的以r為根的incast樹中，其在先前incast樹中的子樹仍存在于以rn為根的incast樹中，但在新的incast樹中應(yīng)該從階段0開始.

可以斷定j越小上述方法越有效.如果rn剛好是r在e1維的一個(gè)鄰居，incast管理器只需調(diào)整從階段1到階段0的有向路徑.給定以r為根，路由序列為e1e2…ej…ekek+1的incast樹，不難發(fā)現(xiàn)如果接收端r需要被替換，r在e1維的所有n-1個(gè)鄰居是最好的替代者.如果這些替代者都不空閑，incast管理器將會(huì)從r在e2維的n-1個(gè)鄰居中選一個(gè)空閑的作為替代，以此類推.通過(guò)這種方式，我們可以最大化已有incast樹的重用效果，極大地減少更新接收端所帶來(lái)的二次計(jì)算開銷.而且，由于中間節(jié)點(diǎn)已緩存了最初incast最小代價(jià)樹的許多數(shù)據(jù)，這些數(shù)據(jù)也能在新的incast最小代價(jià)樹中得到重用.

4其他相關(guān)問(wèn)題的討論

本節(jié)中我們將進(jìn)一步討論其他一些重要設(shè)計(jì)因素對(duì)流量網(wǎng)內(nèi)聚合方法的影響.

4.1通用Incast傳輸模式

此前為便于理解，我們假設(shè)incast傳輸中發(fā)送端和接收端之間的最大海明距離為k+1.但是，基于RS和基于ARS的incast樹構(gòu)造方法可以通過(guò)擴(kuò)展支持更通用的incast傳輸.設(shè)d表示發(fā)送端和接收端間的最大海明距離,若d

在這種情況下，定義2可修改為：設(shè)e1e2…ej…ed表示由d個(gè)路由符號(hào)構(gòu)成的一個(gè)路由序列，其是d! 種排列中的一種.而incast樹的階段j和路由符號(hào)ej(1≤j≤d)相關(guān)聯(lián).從而基于RS和基于ARS的構(gòu)造方法能夠很好地適用于更通用的incast傳輸.

4.2其他數(shù)據(jù)中心結(jié)構(gòu)下的Incast傳輸模式

如2.1節(jié)所述，現(xiàn)存的以交換機(jī)為核心的網(wǎng)絡(luò)拓?fù)溆捎谄毡槭褂脗鹘y(tǒng)交換機(jī)，因而不具備充足的數(shù)據(jù)包緩存和可編程能力.也就是說(shuō)，以交換機(jī)為核心的數(shù)據(jù)中心目前并不能實(shí)現(xiàn)流間的網(wǎng)內(nèi)數(shù)據(jù)聚合.然而，隨著技術(shù)的發(fā)展，例如Cisco ASIC 和arista的應(yīng)用交換機(jī)已經(jīng)能夠提供可編程數(shù)據(jù)平面.若未來(lái)數(shù)據(jù)中心采用此種新型交換機(jī)，則能自然地支持流間的網(wǎng)內(nèi)數(shù)據(jù)聚合.

雖然第3節(jié)以BCube為背景研究了以服務(wù)器為核心結(jié)構(gòu)的incast樹構(gòu)造方法，但本文提出的方法也可被應(yīng)用到其他以服務(wù)器為核心的結(jié)構(gòu)中，如DCell[13],BCN[16],FiConn[19],SWD[20]和Scafida[21]，區(qū)別在于incast樹的構(gòu)建方法將有所差異.我們將其他以服務(wù)器為核心的數(shù)據(jù)中心內(nèi)流間數(shù)據(jù)聚合的研究留待后續(xù).

另外，本文提出的方法也能夠直接應(yīng)用于FBFLY和HyperX這2種以交換機(jī)為核心的網(wǎng)絡(luò)結(jié)構(gòu)中.其原因在于BCube拓?fù)浣Y(jié)構(gòu)的實(shí)質(zhì)是廣義超級(jí)立方體，與FBFLY和HyperX拓?fù)浣Y(jié)構(gòu)本質(zhì)上相同.若FBFLY和HyperX中采用上述新型交換機(jī)，則我們的構(gòu)造方法幾乎不需修改便可直接使用.同樣地，我們將以交換機(jī)為核心的數(shù)據(jù)中心內(nèi)流間網(wǎng)內(nèi)聚合留待后續(xù)研究.

4.3作業(yè)特征對(duì)Incast網(wǎng)內(nèi)聚合性質(zhì)影響

Facebook上的MapReduce集群擁有600個(gè)結(jié)點(diǎn)，統(tǒng)計(jì)發(fā)現(xiàn)83%的作業(yè)平均含有少于271個(gè)map任務(wù)和30個(gè)reduce任務(wù)[32].相似地，在一個(gè)由3 000臺(tái)服務(wù)器構(gòu)成的雅虎數(shù)據(jù)中心中也得到體現(xiàn).另外，文獻(xiàn)[33-34]曾證實(shí)，2個(gè)生產(chǎn)集群(由上千臺(tái)機(jī)器構(gòu)成Facebook的Hadoop集群和微軟Bing搜索引擎的Dryad集群)中，作業(yè)的輸入數(shù)據(jù)大小符合長(zhǎng)尾分布.作業(yè)的大小(輸入數(shù)據(jù)的大小和任務(wù)的數(shù)量)實(shí)際上遵循冪律分布，也就是說(shuō)，工作負(fù)載由大量的小作業(yè)和相對(duì)少量的大作業(yè)組成.

我們提出的網(wǎng)內(nèi)數(shù)據(jù)聚合模型非常適用于小型作業(yè)，因?yàn)槊總€(gè)聚合服務(wù)器都有充足的緩存空間來(lái)緩存數(shù)據(jù)包，而且對(duì)于大部分MapReduce作業(yè)來(lái)說(shuō)，運(yùn)行在每個(gè)聚合服務(wù)器上的函數(shù)都具有關(guān)聯(lián)性和可互換性.而文獻(xiàn)[35]曾提出如何將非可互換和非關(guān)聯(lián)的函數(shù)以及用戶自定義的函數(shù)轉(zhuǎn)換成可互換和關(guān)聯(lián)函數(shù).因此，每個(gè)聚合服務(wù)器接收到部分?jǐn)?shù)據(jù)包后即可執(zhí)行網(wǎng)內(nèi)聚合操作.因此，為聚合函數(shù)分配的存儲(chǔ)空間通常是充足的，可用來(lái)緩存所需要的數(shù)據(jù)包.

5性能評(píng)估

本節(jié)首先介紹實(shí)驗(yàn)的設(shè)置，并在此基礎(chǔ)上分別評(píng)估在不同數(shù)據(jù)中心規(guī)模、incast傳輸規(guī)模、incast聚合率和incast成員分布的情況下，關(guān)聯(lián)性流量網(wǎng)內(nèi)聚合方法的性能.

5.1原型實(shí)現(xiàn)

原型系統(tǒng)的平臺(tái)由以太網(wǎng)連接的8臺(tái)服務(wù)器虛擬出的81臺(tái)虛擬機(jī)(VMs)構(gòu)成.每臺(tái)服務(wù)器配備有2個(gè)8核超線程的Intel Xeon E5620 2.40 GHz處理器、24 GB內(nèi)存和1TB的SATA硬盤，運(yùn)行內(nèi)核版本為2.6.18的CentOS 5.6.其中，7臺(tái)服務(wù)器每臺(tái)運(yùn)行10個(gè)虛擬機(jī)，用作Hadoop的虛擬從節(jié)點(diǎn)，另有1臺(tái)服務(wù)器運(yùn)行10個(gè)虛擬從節(jié)點(diǎn)和1個(gè)主節(jié)點(diǎn).每個(gè)虛擬從節(jié)點(diǎn)支持4個(gè)map任務(wù)和1個(gè)reduce任務(wù).通過(guò)擴(kuò)展Hadoop使其能支持任意shuffle傳輸?shù)木W(wǎng)內(nèi)聚合.每臺(tái)物理服務(wù)器上的所有虛擬機(jī)通過(guò)一個(gè)虛擬交換機(jī)共享主機(jī)的網(wǎng)卡.我們對(duì)Hadoop的設(shè)置進(jìn)行了擴(kuò)展，從而能夠支持?jǐn)?shù)據(jù)流的網(wǎng)內(nèi)緩存和數(shù)據(jù)聚合.

為模擬實(shí)現(xiàn)incast傳輸，實(shí)驗(yàn)使用了Hadoop 0.21.0內(nèi)置的字?jǐn)?shù)統(tǒng)計(jì)作業(yè).該作業(yè)的發(fā)送端(map任務(wù))和接收端(reduce任務(wù))的數(shù)目被分別設(shè)置為320和1.實(shí)驗(yàn)給每個(gè)map任務(wù)分配10個(gè)輸入文件，每個(gè)文件64 MB.在shuffle工作階段，從發(fā)送端到接收端的平均數(shù)據(jù)量在每個(gè)發(fā)送端處進(jìn)行聚合后大約為1 MB.

考慮BCube(n,k)(3≤k≤9)數(shù)據(jù)中心內(nèi)的incast傳輸，每個(gè)發(fā)送端和唯一的接收端被隨機(jī)地分配一個(gè)k+1維BCube標(biāo)識(shí)符.我們?cè)谠撎摂M平臺(tái)上通過(guò)如下方式模擬了BCube數(shù)據(jù)中心內(nèi)的incast傳輸過(guò)程，并分別生成基于ARS的incast樹和單播incast樹.

為在BCube中部署incast傳輸，我們?cè)O(shè)計(jì)了下述從incast樹節(jié)點(diǎn)到測(cè)試平臺(tái)的映射方式.其中，主虛擬機(jī)發(fā)揮incast管理器的作用；4個(gè)發(fā)送端、一個(gè)可能的接收端以及一些incast樹的內(nèi)部節(jié)點(diǎn)被映射到30個(gè)從虛擬機(jī)中.通過(guò)這種方式，我們把每個(gè)虛擬機(jī)抽象為虛擬機(jī)代理(VMAs)，每一個(gè)虛擬機(jī)代理對(duì)應(yīng)incast樹中的一個(gè)節(jié)點(diǎn).我們要求映射到同一個(gè)虛擬機(jī)上的所有節(jié)點(diǎn)不能包含任何incast樹中橫跨相鄰階段的鄰居對(duì).例如，圖3(c)中的節(jié)點(diǎn)v5和v9可以出現(xiàn)在相同的虛擬機(jī)中，但是這個(gè)虛擬機(jī)不能容納節(jié)點(diǎn)v1.因此，在進(jìn)行incast傳輸期間，同一個(gè)虛擬機(jī)上的虛擬機(jī)代理間將不會(huì)產(chǎn)生局部通信.實(shí)際上，對(duì)于任何虛擬機(jī)代理，其incast樹中的下一階段的鄰居VMA將出現(xiàn)在不同的虛擬機(jī)上，這些虛擬機(jī)處于相同或不同的物理服務(wù)器.因此，incast樹中的每條邊都被映射到2個(gè)虛擬機(jī)間的虛擬鏈路或者測(cè)試平臺(tái)中服務(wù)器之間的網(wǎng)絡(luò)物理鏈路.

實(shí)驗(yàn)將基于ARS的incast樹構(gòu)造算法分別與典型Steiner樹算法、單播驅(qū)動(dòng)incast樹算法以及其他算法從4個(gè)方面進(jìn)行性能比較.這4個(gè)性能指標(biāo)分別為所產(chǎn)生的網(wǎng)絡(luò)流量、占用的鏈路數(shù)量、緩存服務(wù)器的數(shù)量以及接收端輸入數(shù)據(jù)的大小.其中，網(wǎng)絡(luò)流量指的是incast樹中所有鏈路上的流量總和.

實(shí)驗(yàn)中所使用的Steiner樹算法來(lái)自文獻(xiàn)[36]，其優(yōu)勢(shì)在于計(jì)算速度較快.具體作法是：1)依據(jù)incast成員生成虛擬完全圖；2)在該圖上計(jì)算最小生成樹;3)虛擬完全圖中的虛擬鏈路被最初拓?fù)浣Y(jié)構(gòu)中任意2個(gè)incast成員的最短路徑取代，并刪除不必要的路徑.

5.2數(shù)據(jù)中心規(guī)模對(duì)聚合增益的影響

實(shí)驗(yàn)在測(cè)試平臺(tái)BCube(6,k)子網(wǎng)上部署了一個(gè)有320個(gè)發(fā)送端的incast傳輸，并構(gòu)造了基于ARS的incast樹.經(jīng)過(guò)大量實(shí)驗(yàn)，我們收集了不同性能指標(biāo)的平均取值，圖4展示了我們的方法與其他3種方法在4種性能指標(biāo)上的差異.

從圖4可以看出，與現(xiàn)有方法相比，基于ARS方法和單播驅(qū)動(dòng)方法能平均節(jié)省38%和18%的網(wǎng)絡(luò)流量.這是因?yàn)榍罢叩木酆戏?wù)器數(shù)量隨著k的增加而增加；但后者的聚合服務(wù)器數(shù)量則隨著k的增加而減少.此外，基于ARS的方法構(gòu)造出的incast樹占用的鏈路數(shù)目也較少，這意味著所使用的服務(wù)器和網(wǎng)絡(luò)設(shè)備也較少.而從圖4(d)可以看出，基于ARS的方法極大地減少了接收端輸入數(shù)據(jù)的規(guī)模.

Fig. 4　Changing trends of four metrics for incast transfers with 320 senders in BCube(6,k) when 3≤k≤9.圖4　發(fā)送端為320的incast傳輸在不同的BCube(6,k)的4項(xiàng)指標(biāo)的變化情況

Fig. 5　Changing trends of two metrics along with the increase of senders in an incast transfer in BCube(8,5).圖5　在BCube(8,5)中incast傳輸?shù)?種指標(biāo)隨發(fā)送端規(guī)模的增加而變化

同時(shí)，基于ARS的方法在一定程度上要優(yōu)于Steiner樹算法的性能.這是因?yàn)槿舨豢紤]數(shù)據(jù)中心規(guī)模，在二者鏈路數(shù)目相似的情況下，基于ARS的方法用到了比Steiner樹算法更多的聚合服務(wù)器.綜上所述，不論數(shù)據(jù)中心的規(guī)模如何，基于ARS的incast樹構(gòu)造方法總是遠(yuǎn)遠(yuǎn)優(yōu)于另外2種方法.

5.3Incast傳輸規(guī)模對(duì)聚合增益的影響

實(shí)際應(yīng)用中，MapReduce往往包含有幾百甚至上千的map任務(wù).然而，由于測(cè)試平臺(tái)的資源有限，不能進(jìn)行如此大規(guī)模的作業(yè).因此我們利用模擬實(shí)驗(yàn)進(jìn)一步論證上述方法的擴(kuò)展性，用Java實(shí)現(xiàn)BCube數(shù)據(jù)中心網(wǎng)絡(luò)架構(gòu)，并參考Hadoop的wordcounter作業(yè)產(chǎn)生所需的incast的傳輸.具體而言，分別創(chuàng)建了擁有m(m∈{100,200,…,3900,4000})個(gè)發(fā)送端的incast組播傳輸，該作業(yè)為每個(gè)發(fā)送端提供用Hadoop內(nèi)置的RandomTeextWriter，隨機(jī)產(chǎn)生64 MB的輸入數(shù)據(jù).從每個(gè)發(fā)送端到接收端的數(shù)據(jù)流量被控制在1 MB.圖5展示了BCube(8,5)中，2種方法在不同規(guī)模incast傳輸下產(chǎn)生的網(wǎng)絡(luò)流量和占用的鏈路數(shù)的變化情況.

圖5表明，隨著m從100變化到4 000，基于ARS的方法和單播驅(qū)動(dòng)方法能最多節(jié)省59%的網(wǎng)絡(luò)流量，平均節(jié)省27%.即使在大規(guī)模的incast傳輸中，依然能夠獲得較大的網(wǎng)內(nèi)數(shù)據(jù)聚合增益;基于ARS的方法占用的鏈路數(shù)目明顯少于單播驅(qū)動(dòng)方法，故使用的服務(wù)器和網(wǎng)絡(luò)設(shè)備也較少.

5.4聚合率對(duì)聚合增益的影響

此前我們?cè)僭O(shè)經(jīng)聚合后得到的新數(shù)據(jù)流的大小等同于聚合服務(wù)器輸入流中最大的一個(gè).也就是說(shuō)，所有輸入流的主鍵集合是其中最大輸入流主鍵的子集.本節(jié)中我們將在更通用的incast傳輸下評(píng)估基于ARS的方法.

給定incast傳輸中有s個(gè)數(shù)據(jù)流，令fi(1≤i≤s)表示第i個(gè)數(shù)據(jù)流的大小，δ(0≤δ≤1)表示任意數(shù)據(jù)流之間的聚合比.s個(gè)數(shù)據(jù)流經(jīng)聚合后獲得的新數(shù)據(jù)流的大小為

上述分析建立在δ=0的前提下，此時(shí)網(wǎng)內(nèi)數(shù)據(jù)聚合達(dá)到最大增益.而當(dāng)δ=1時(shí)，s中的任意2個(gè)數(shù)據(jù)流由于沒(méi)有共享主鍵使得網(wǎng)內(nèi)數(shù)據(jù)聚合不能獲得任何收益.這種情況下，基于單播的方法與其他方法等價(jià).此處，我們將在0≤δ≤1的情形下評(píng)估我們提出的基于ARS的方法.

以BCube(8,5)網(wǎng)絡(luò)拓?fù)錇楸尘?，?dāng)δ的范圍從0變化到1時(shí)分別評(píng)估基于ARS、單播和其他方法所生成的網(wǎng)絡(luò)流量.實(shí)驗(yàn)結(jié)果表明，與其他2種方法相比，基于ARS的方法總是能夠產(chǎn)生更少的網(wǎng)絡(luò)流量.假設(shè)隨機(jī)變量δ的值遵循統(tǒng)一的分布，則與其他2種方法相比，基于ARS的方法在當(dāng)incast傳輸分別包含500和4 000個(gè)發(fā)送端時(shí)分別節(jié)約了24%和40%的網(wǎng)絡(luò)流量.從圖6可知，隨聚合率的增加，incast傳輸時(shí)間也隨之變化；無(wú)論聚合率的值為多少，基于ARS的方法都優(yōu)于其他2種方法.

Fig. 6　Resultant network traffic under different aggregation factors and incast transfers in BCube(8,5).圖6　網(wǎng)絡(luò)流量隨著聚合率增加的變化趨勢(shì)

5.5Incast成員分布對(duì)聚合增益的影響

實(shí)際應(yīng)用中incast傳輸成員可能位于整個(gè)數(shù)據(jù)中心內(nèi)的空閑服務(wù)器上，這使得發(fā)送端和接收端位置的分布接近于隨機(jī)分布.然而，這種隨機(jī)分布使得incast傳輸占用了更多的數(shù)據(jù)中心資源，也產(chǎn)生了更多的網(wǎng)絡(luò)流量.此處，我們將研究不同的incast成員分布模型對(duì)網(wǎng)內(nèi)流量聚合增益的影響.

首先，此問(wèn)題的關(guān)鍵在于尋找BCube(n,k)中的最小子網(wǎng)Bcube(n,k1)，以使得該子網(wǎng)能夠滿足所有incast成員的傳輸要求.在這種情況下，incast傳輸?shù)乃袀魉驼吆徒邮斩碎g的海明距離滿足k1+1≤k+1，且基于ARS的incast樹在Bcube(n,k1)的范圍內(nèi)最多存在k1+1個(gè)階段.理論上，與之前BCube(n,k)范圍內(nèi)的基于ARS的incast樹相比，它占用了更少的數(shù)據(jù)中心資源以及更少的網(wǎng)絡(luò)流量.

為此，考慮30個(gè)shuffle傳輸，其中每個(gè)傳輸有500個(gè)發(fā)送端以及不同數(shù)量的接收端，接收端數(shù)量在1～30之間.對(duì)每個(gè)shuffle傳輸，在BCube(8,5)中，我們對(duì)它的所有incast傳輸應(yīng)用2種分布方式以計(jì)算累計(jì)網(wǎng)絡(luò)流量.圖7展示了2種不同的成員部署方案下shuffle傳輸所產(chǎn)生的網(wǎng)絡(luò)流量.我們可以看到，與隨機(jī)分布方案相比，可控分布方案產(chǎn)生的網(wǎng)絡(luò)流量更少；在可控分布和隨機(jī)分布這2個(gè)方案下與其他方法相比，基于ARS的方法分別節(jié)省了62%和24%的網(wǎng)絡(luò)流量，這也意味著基于ARS的方法在可控分布下能實(shí)現(xiàn)更大的增益.

Fig. 7　Network traffic under different distributions of shuffle member with 500 senders in BCube(8,5).圖7　BCube(8,5)拓?fù)湎戮W(wǎng)絡(luò)流量隨shuffle成員分布的變化

6相關(guān)工作

最近，Costa等人構(gòu)建了Camdoop[37]系統(tǒng)，該系統(tǒng)與MapReduce有相似之處但運(yùn)行在新型數(shù)據(jù)中心網(wǎng)絡(luò)結(jié)構(gòu)CamCube上.在Camdoop上，Costa等人嘗試了shuffle階段對(duì)流量進(jìn)行網(wǎng)內(nèi)聚合從而減少網(wǎng)絡(luò)流量，并研究了CamCube服務(wù)器轉(zhuǎn)發(fā)流量的性質(zhì).CamCube采用3維torus拓?fù)浣Y(jié)構(gòu)，即每臺(tái)服務(wù)器直接和6個(gè)鄰居服務(wù)器相連.因此，與其他典型的以服務(wù)器為核心的網(wǎng)絡(luò)結(jié)構(gòu)相比，如BCube,DCell,FBFLY和HyperX，CamCube表現(xiàn)出了更長(zhǎng)的網(wǎng)絡(luò)直徑和更高的通信延遲.

然而，如何將Camdoop的基本原理應(yīng)用到其他數(shù)據(jù)中心拓?fù)浣Y(jié)構(gòu)中仍是未知的，本文提出的聚合方法并不適合于其他同類的網(wǎng)絡(luò)結(jié)構(gòu).針對(duì)此問(wèn)題，本文首先分別探討了以服務(wù)器為核心和以交換機(jī)為核心的數(shù)據(jù)中心網(wǎng)內(nèi)數(shù)據(jù)聚合的增益和可行性.在此基礎(chǔ)上，將網(wǎng)內(nèi)數(shù)據(jù)聚合問(wèn)題抽象為可以應(yīng)用到任意結(jié)構(gòu)數(shù)據(jù)中心上的incast最小代價(jià)樹問(wèn)題.

incast最小代價(jià)樹問(wèn)題與著名的Steiner樹問(wèn)題相似；所不同的是邊的權(quán)重在最小Steiner樹問(wèn)題中是給定且不可更改的，而在incast最小代價(jià)樹問(wèn)題中卻是不確定和可變的.事實(shí)上，incast最小代價(jià)樹中每條邊的權(quán)重取決于從所有發(fā)送端到給定接收端的樹結(jié)構(gòu).最小Steiner樹問(wèn)題在普通圖(general graph)中是NP難的且有很多近似算法[38-39].然而，這些算法不能有效解決incast最小代價(jià)樹問(wèn)題，第5節(jié)實(shí)驗(yàn)部分的評(píng)估進(jìn)一步驗(yàn)證了這一結(jié)論.此外，大部分算法的時(shí)間復(fù)雜度為O(m×N2)，其中m表示incast傳輸成員數(shù)目，N表示數(shù)據(jù)中心內(nèi)服務(wù)器總數(shù).顯然，該算法的復(fù)雜度過(guò)高，不能滿足數(shù)據(jù)中心內(nèi)incast最小代價(jià)樹的構(gòu)建要求.為此，在充分挖掘數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)涮卣鞯幕A(chǔ)上，我們提出了2種近似的incast樹構(gòu)造方法，分別是基于RS的和基于ARS的方法，且這2種方法的時(shí)間復(fù)雜度分別為O(m×logN)，O(m×(logN)2).

7結(jié)束語(yǔ)

類似MapReduce的大型分布式計(jì)算系統(tǒng)在相鄰處理階段之間傳輸大量的中間運(yùn)算結(jié)果.本文旨在傳輸階段進(jìn)行流間的網(wǎng)內(nèi)數(shù)據(jù)聚合，從而降低造成的網(wǎng)絡(luò)流量，減少對(duì)網(wǎng)絡(luò)資源的消耗.該問(wèn)題被進(jìn)一步抽象為incast最小代價(jià)樹的構(gòu)造問(wèn)題.在此基礎(chǔ)上，我們提出基于ARS的方法為任何incast傳輸構(gòu)造一棵高效的incast樹.我們進(jìn)一步討論了如何以增量式方法來(lái)解決incast樹的動(dòng)態(tài)性問(wèn)題.最后，通過(guò)構(gòu)建原型和大規(guī)模模擬評(píng)估了我們方法的性能.結(jié)果表明我們的方法和其他方法相比能極大地減少網(wǎng)絡(luò)流量、節(jié)省數(shù)據(jù)中心資源.

參考文獻(xiàn)

[1]Condie T, Conway N, Alvaro P, et al. MapReduce online[C]Proc of USENIX NSDI’10. Berkeley, CA: USENIX Association, 2010: 313-328

[2]Yu Yuan, Isard M, Fetterly D, et al. DryadLINQ: A system for general-purpose distributed data-parallel computing using a high-level language[C]Proc of USENIX OSDI’08. Berkeley, CA: USENIX Association, 2008: 1-14

[3]Murray D G, Schwarzkopf M, Smowton C, et al. CIEL: A universal execution engine for distributed data-flow computing[C]Proc of USENIX NSDI’11. Berkeley, CA: USENIX Association, 2011

[4]Malewicz G, Austern M H, Bik A J C, et al. Pregel: A system for large-scale graph processing[C]Proc of ACM SIGMOD’10. New York: ACM, 2010: 135-146

[5]Zaharia M, Chowdhury M, Franklin M J, et al. Spark: Cluster computing with working sets[J]. Book of Extremes, 2010, 15(1): 1765-1773

[6]Chowdhury M, Zaharia M, Ma J, et al. Managing data transfers in computer clusters with orchestra[C]Proc of ACM SIGCOMM’11. New York: ACM, 2011: 98-109

[7]Al-Fares A, Loukissas A, Vahdat A. A scalable, commodity data center network architecture[C]Proc of ACM SIGCOMM’08. New York: ACM, 2008: 63-74

[8]Greenberg A, Jain N, Kandula S, et al. VL2: A scalable and flexible data center network[C]Proc of ACM SIGCOMM’09. New York: ACM, 2009: 51-62

[9]Mysore R, Pamboris A, Farrington N. PortLand: A scalable fault-tolerant layer 2 data center network fabric[C]Proc of ACM SIGCOMM’09. New York: ACM, 2009: 39-50

[10]Abts D, Marty M A, Wells P M, et al. Energy proportional datacenter networks[C]Proc of ACM ISCA’10. New York: ACM, 2010: 338-347

[11]Ahn J H, Binkert N L, Davis A, et al. HyperX: Topology, routing, and packaging of efficient large-scale networks[C]Proc of ACMIEEE Conf on High Performance Computing (SC’09). New York: IEEEACM, 2009: 1-11

[12]Singla A, Hong C Y, Popa L, et al. Jellyfish: Networking data centers randomly[C]Proc of USENIX NSDI’12. Berkeley, CA: USENIX Association, 2012: 225-238

[13]Guo Chuanxiong, Wu Haitao, Tan Kun, et al. DCell: A scalable and fault-tolerant network structure for data centers[C]Proc of ACM SIGCOMM’08. New York: ACM, 2008: 75-86

[14]Guo Chuanxiong, Lu Guohan, Li Dan, et al. BCube: A high performance, server-centric network architecture for modular data centers[J]. ACM SIGCOMM, 2009, 39(4): 63-74

[15]Abu-Libdeh H, Costa P, Rowstron A, et al. Symbiotic routing in future data centers[J]. ACM SIGCOMM, 2010, 40(4): 51-62

[16]Guo Deke, Chen Tao, Li Dan, et al. BCN: Expansible network structures for data centers using hierarchical compound graphs[C]Proc of IEEE INFOCOM’11. Piscataway, NJ: IEEE, 2011: 61-65

[17]Guo Deke, Chen Tao, Li Dan, et al. Expansible and cost-effective network structures for data centers using dual-port servers[J]. IEEE Trans on Computers, 2012, 62(7): 1303-1317

[18]Bhuyan L N, Agrawal D P. Generalized hypercube and hyperbus structures for a computer network[J]. IEEE Trans on Computers, 1984, 33(4): 323-333

[19]Li Dan, Guo Chuanxiong, Wu Haitao, et al. Scalable and cost-effective interconnection of data-center servers using dual server ports[J]. IEEEACM Trans on Networking, 2011, 19(1): 102-114

[20]Shin J Y, Wong B, Sirer E G. Small-world datacenters[C]Proc of ACM SoCC’11. New York: ACM, 2011: 2-14

[21]Gyarmati L, Trinh T. Scafida: A scale-free network inspired data center architecture[J]. ACM SIGCOMM Computer Communication Review, 2010, 40(5): 4-12

[22]Condie T, Conway N, Alvaro P, et al. Online aggregation and continuous query support in MapReduce[C]Proc of ACM SIGMOD’10. New York: ACM, 2010: 1115-1118

[23]Pansare N, Borkar V R, Jermaine C, et al. Online aggregation for large MapReduce jobs[J]. PVLDB, 2011, 4(11): 1135-1145

[24]Casado M, Freedman M J, Pettit J, et al. Ethane: Taking control of the enterprise[C]Proc of ACM SIGCOMM’07. New York: ACM, 2007: 1-12

[25]McKeown N, Anderson T, Balakrishnan H, et al. Openflow: Enabling innovation in campus networks[J]. Computer Communication Review, 2008, 38(2): 69-74

[26]Curtis A R, Mogul J C, Tourrilhes J, et al. Devoflow: Scaling flow management for high-performance networks[C]Proc of ACM SIGCOMM’11. New York: ACM, 2011: 254-265

[27]Han Sangjin, Jang K, Park K S, et al. PacketShader: A GPU-accelerated software router[C]Proc of ACM SIGCOMM’10. New York: ACM, 2010: 195-206

[28]Naous J, Gibb G, Bolouki S, et al. Netfpga: Reusable router architecture for experimental research[C]Proc of ACM PRESTO’08. New York: ACM, 2008: 1-7

[29]Lu Guohan, Guo Chuanxiong, Li Yulong, et al. Serverswitch: A programmable and high performance platform for data center networks[C]Proc of USENIX NSDI’11. Berkeley, CA: USENIX Association, 2011

[30]Cao Jiaxin, Guo Chuanxiong, Lu Guohan, et al. Datacast: A scalable and efficient reliable group data delivery service for data centers[C]Proc of ACM CoNEXT’13. New York: ACM, 2013: 37-48

[31]Kwon Y C, Balazinska M, Home B, et al. Skewtune: Mitigating skew in MapReduce applications[C]Proc of ACM SIGMOD’12. New York: ACM, 2012: 25-36

[32]Zaharia M, Borthakur D, Sarma J S, et al. Delay scheduling: A simple technique for achieving locality and fairness in cluster scheduling[C]Proc of ACM EuroSys’10. New York: ACM, 2010: 265-278

[33]Ananthanarayanan G, Ghodsi A, Wang A, et al. Pacman: Coordinated memory caching for parallel jobs[C]Proc of USENIX NSDI’12. Berkeley, CA: USENIX Association, 2012: 267-280

[34]Chen Yanpei, Alspaugh S, Borthakur D, et al. Energy efficiency for large-scale mapreduce workloads with significant interactive analysis[C]Proc of EuroSys’12. New York: ACM, 2012: 43-56

[35]Yu Yuan, Gunda P K, Isard M. Distributed aggregation for data-parallel computing: Interfaces and implementations[C]Proc of ACM SOSP’09. New York: ACM, 2009: 247-260

[36]Guo Deke, Wu Jie, Chen Honghui, et al. The dynamic bloom filters[J]. IEEE Trans on Knowledge and Data Engineering, 2010, 22(1): 120-133

[37]Costa P, Donnelly A, OShea A R G. Camdoop: Exploiting in-network aggregation for big data applications[C]Proc of USENIX NSDI’12. Berkeley, CA: USENIX Association, 2012: 29-42

[38]Robins G, Zelikovsky A. Tighter bounds for graph Steiner tree approximation[J]. SIAM Journal on Discrete Mathematics, 2005, 19(1): 122-134

[39]Zaharia M, Borthakur D, Sarma J S, et al. Delay scheduling: A simple technique for achieving locality and fairness in cluster scheduling[C]Proc of ACM EuroSys’10. New York: ACM, 2010: 265-278

Guo Deke, born 1980. Received his BS degree in industry engineering from Beijing University of Aeronautic and Astronautic, Beijing, China, in 2001, and received his PhD degree in management science and engineering from National University of Defense Technology, Changsha, China, in 2008. Associate professor at the College of Information System and Management, National University of Defense Technology, Changsha, China. Member of ACM and IEEE. His main research interests include distributed systems, software-defined network, data center network, wireless and mobile systems, and interconnection networks.

Luo Lailong, born in 1991. Received his MS degree in management science and engineering from National University of Defense Technology, Changsha, China, in 2015. PhD candidate in the College of Information System and Management, National University of Defense Technology, Changsha, China. His main research interests include software-defined network and data center network.

Li Yan, born in 1992. Received her BS degree in management science and engineering from National University of Defense Technology, Changsha, China, in 2014. MS candidate in the College of Information System and Management, National University of Defense Technology, Changsha, China. Her main research interests include data center network and traffic schedule.

Hu Zhiyao, born in 1992. Received his BS degree in information countermeasure techniques from Beijing Institute of Technology, Beijing, China, in 2014. MS candidate in the College of Information System and Management, National University of Defense Technology, Changsha, China. His main research interests include software-defined network and data center network.

Ren Bangbang, born in 1994. Received his BS degree in management science and engineering from National University of Defense Technology, Changsha, China, in 2015. MS candidate in the College of Information System and Management, National University of Defense Technology, Changsha, China. His main research interests include software-defined network and data center network.

中圖法分類號(hào)TP391

基金項(xiàng)目：國(guó)家自然科學(xué)基金優(yōu)秀青年科學(xué)基金項(xiàng)目(61422214)

收稿日期：2015-07-15；修回日期：2015-11-09

This work was supported by the National Natural Science Foundation for Excellent Young Scholars of China (61422214).