郭得科　罗来龙　李　妍　胡智尧　任棒棒

(信息系统工程国防科技重点实验室(国防科学技术大学)　长沙　410073)

(dekeguo@nudt.edu.cn)



数据中心内Incast流量的网内聚合研究

郭得科罗来龙李妍胡智尧任棒棒

(信息系统工程国防科技重点实验室(国防科学技术大学)长沙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等分布式计算系统应用在数据中心内产生了严重的东西向流量，其中以incast和shuffle为代表的关联性流量占相当大的比重，进而严重影响到上层应用的性能.这促使研究者们考虑在这些关联性流量的网内传输阶段尽可能早而不是仅在流量的接收端进行流间数据聚合.首先以新型数据中心网络结构为背景讨论流间数据聚合的可行性和增益，为最大化该增益，为incast传输建立最小代价树模型.为解决该模型，提出了2种近似的incast树构造方法，其能够仅基于incast成员的位置和数据中心拓扑结构生成一个有效的incast树，进一步解决了incast树的动态和容错问题.最后，采用原型系统和大规模仿真的方法评估了incast流量的网内聚合方法，实验结果证明该方法能大幅降低incast流量造成的传输开销，能节约数据中心的网络资源.同时，提出的模型和解决方法也适用于其他类型的数据中心网络结构.

关键词网内聚合；数据中心；incast传输；shuffle传输；网络流量

大规模数据中心不仅服务于各类在线云应用，而且还直接服务于大规模分布式计算系统，如MapReduce[1]，Dryad[2]，CIEL[3]，Pregel[4]和Spark[5]等.这些分布式计算系统向数据中心提交大量处理作业，每项作业都可能需要使用数据中心内大量的服务器.这些计算系统普遍遵从流计算模式，即在相邻处理阶段间需要传递大量的中间计算结果.这种类型的数据传输为数据中心贡献了大约80%的东西向流量[5]，因此对分布式应用的性能和数据中心的运营产生了严重影响.

我们观察到，上述很多计算系统的作业在接收端采用了多种聚合操作以降低其输出数据的规模.例如，在MapReduce作业的shuffle阶段，每一个reducer被分配一个map阶段输出值域空间的唯一子空间；然后reducer从每个mapper的输出中提取其负责的部分内容，并在获取后进行reduce操作.对于大多数的reduce函数，如MIN,MAX,SUM,COUNT,TOP-K和KNN来说，其涉及到的数据流之间具有较高的关联性和很好的聚合效益.以Facebook的MapReduce作业为例，每个reducer聚合后的输出数据规模比其输入数据规模平均减少了81.7%[6].该观测结果促使我们思考，是否可在上述关联性流量的网内传输过程中尽可能早地实施数据聚合操作，而不是仅仅在接收端开展.如果网内数据聚合能够实现，则数据中心内的东西流量将会大幅度降低，并且reducer端输入数据量的降低也会加速作业的处理速度.

本研究旨在通过管理和优化关联性流量的协同传输以实现流量的网内聚合.本研究重点关注多对一的incast传输模式[5].当前incast传输模式普遍被分解为一系列单播来实现，并不考虑其关联性数据流的潜在聚合行为.

对于incast传输，只有参与聚合的相关数据流能够在传播路径的某些交汇点上进行网内缓存和网内处理时，网内聚合增益才能实现.在以交换机为核心的数据中心互联结构[7-12]中，传统交换机的计算能力和缓存空间不足，因此这类互联结构支持incast流量网内聚合的能力非常有限.但是从技术发展趋势看，业界已提出许多以服务器为核心的数据中心互联结构[13-17].在这些结构中，主要的互联和路由功能由服务器承担，交换机只提供简单的纵横式交换功能，因此具备网内缓存和数据包的深度处理能力.另外，由于任意2台服务器间存在多条不相交的路由路径，易于主动构造出尽可能多的交汇点以支持网内聚合，因此为管理incast传输带来了机会.

本文中，我们首先以服务器为核心的数据中心网络结构为背景，探讨incast传输网内聚合的可行性及潜在增益.为方便研究，incast传输的流量聚合问题被建模成incast最小聚合树的构建问题.我们进而提出了2种近似的incast聚合树构建方法，分别为基于RS(routing symbol)的方法和基于ARS(advanced routing symbol)的方法.在此基础上进一步考虑了incast树构造的动态性和容错问题，并提出渐进式解决方案.

最后通过原型实现评估我们提出的方法，实验结果表明我们的方法能显著减少网络流量、节约数据中心的网络资源、加快作业的完成时间.基于ARS的方法能为数据中心BCube(6,k)(3≤k≤9)内一个有320个发送端的incast传输平均降低了38%的网络流量.在容纳262 144个服务器的数据中心BCube(8,5)中，为包含100～4 000个发送端的incast传输平均节省了58%的网络流量.如果对每个incast传输的发送端和接收方的部署位置进行优化，则能节省更多的网络流量.

1背景知识

1.1数据中心的网络互联结构

在数据中心内，大量服务器和交换机通过特定的网络互联结构连接起来.传统数据中心中网络设备被组织成树型结构，服务器挂接在网络设备的预留端口上.近年来，学术界为数据中心提出了许多新型网络互联结构，大致可分为2类：

1) 以交换机为核心的网络结构.该结构将交换机组织成树型之外的其他特定结构，并将网络互联和路由功能放到交换机上.典型代表包括Fat-Tree[7],VL2[8]和PortLand[9]等Clos网络互联结构，其本质上是传统树型结构的变种.为进一步优化现有的互联结构，出现了以交换机为核心的扁平化互联结构——FBFLY[10]和HyperX[11].在这2种互联结构中，大量的多端口通用交换机被互联为广义超级立方体结构[18]，而服务器挂接在网络设备的剩余端口.所有链路和交换机都被平等均衡地使用，因此不存在设备或链路上的性能瓶颈，其整体性能要优于树型及Clos等结构.

2) 以服务器为核心的网络结构.其中,主要的互联和路由功能交由服务器承担，交换机只提供简单的纵横式(crossbar)交换功能.DCell[13],BCube[14],CamCube[15],BCN[16],FiConn[19],SWD[20]和Scafida[21]均属于这类结构.其中，FiConn和BCN 重点关注数据中心内基于双端口服务器的低成本网络互联结构；SWD和Scafida将小世界和无标度网络理论引进到数据中心网络结构中.

在这些新型数据中心结构中，FBFLY和BCube(k-aryn-flat flattened butterfly)是上述2类中最具代表性的网络结构.

1) FBFLY.FBFLY充分利用了高端口交换机的特性，是一种可拓展的网络结构，具有较小的网络直径.其基本思想是用广义超级立方体结构来互连所有交换机.每个维度的所有交换机都彼此全互联，每个交换机用剩余的端口连接服务器.在FBFLY中，任何服务器对之间都不直接相连，且服务器只能与一个交换机相连.例如，对于c=2的4-ary 3-flat FBFLY，有c×kn-1=2×42=32个服务器和kn-1=16个8口交换机，每个交换机与c=2个服务器相连.若c=1，则FBFLY就只能容纳16个服务器.

2) BCube.BCube是广义超级立方体互联结构的变形.BCube0是n个服务器连到一个n端口交换机的整体表示.BCubek(k≥1)是由n个BCubek-1和nk个n端口交换机构成，其中BCubek的每台服务器均有k+1个端口.多NIC端口的服务器与多层交换机相连，但交换机间不能直接相连.图1为BCube(4,1)的网络互联结构，其由nk+1=16个服务器和2层共nk×(k+1)=8个交换机组成.

Fig. 1　Structure of BCube(4,1).图1　BCube(4,1)结构

虽然新型网络互联结构之间存在很大的差异，但也存在3个共同点：1)数据中心设计的趋势是尽可能采用低成本的通用服务器和交换机来替换原来的专用服务器和网络设备;2)这些网络互联结构拥有高链路密度，为任意一对服务器之间提供多条平行路由路径;3)这些网络结构的构造方式简单易行.这些趋势给管理和聚合数据流量带来了新的机会和挑战.

1.2数据中心内的shuffle传输

我们以MapReduce为例简要介绍数据中心内普遍存在的shuffle传输.一个MapReduce作业包含2个连续的处理阶段，即map阶段和reduce阶段.在map阶段，mapper任务对输入的数据执行map操作，产生一个键值对的序列;在reduce阶段，reducer任务对输入的数据执行用户定义的reduce操作，通常是聚合操作.

每个reducer任务被分配一个mapper输出的值域区间的一个唯一划分，在shuffle阶段从每个mapper的输出中被动提取出分配给它的键值对.所有mapper到同一reducer的数据流之间高度关联，因为每个mapper输出的值域区间和划分策略相同.最近，研究人员提出数据管道技术对shuffle传输的过程进行优化，至此一旦某个mapper任务完成，其会主动将中间运算结果向对应的reducer进行推送[21-23].

不管MapReduce作业采用数据提取还是数据推送机制，shuffle传输都普遍存在于map和reduce阶段之间.Dryad,CIEL,Pregel和Spark等数据中心中其他分布式计算框架，都拥有类似的多阶段处理架构.一般来说，shuffle传输包含m个发送端和n个接收端，任意一对发送端和接收端之间形成一条数据流. incast传输则由m个发送端和其中一个接收端形成，每个发送端都向同一接收端发送数据流.

2Incast传输中的数据聚合

由于shuffle 传输可以分解为一组彼此独立的incast传输，因此本研究重点探讨incast传输的网内数据聚合.本节中，我们首先研究incast流间数据聚合的可行性.在此基础上，进一步探索如何构造incast最小代价传播树以及如何在传播树上执行流间的数据聚合操作.

2.1Incast数据流间聚合的可行性

我们发现incast传输中的诸多数据流存在内在的高度关联性，其主要原因在于对所有mapper来说其运算结果的值域和划分规则是相同的，这些数据流的数据(一系列键值对)共享分配给相同接收端的同一个值域区间.如图2所示，对于incast传输的某个数据流来说，其键值序列与其他数据流具有相同的键值序列.

Fig. 2　An example of incast aggregation.图2　关于incast传输的网内聚合示意图

本文的研究工作基于2个发现来开展:1)在incast传输中，接收端普遍对其所有输入数据流运用聚合函数进行处理，如MIN,MAX,SUM,COUNT,TOP-K和KNN;2)虽然发送端在将其运算结果传递给接收端之前采用combine操作，接收端已经能发挥部分聚合效应，但不同流之间还存在相当大的数据聚合机会.这促使我们考虑能否在传输阶段尽可能早地对数据流进行聚合操作，而不仅仅在接收端执行该操作.如果这种流间数据聚合能得以应用，则能极大地减少网内流量以及shuffle阶段传输的数据量，并且不会损害接收端计算结果的正确性.关联性数据流的网络聚合要求参与的流量在传播过程中遇到一些交汇节点，同时这些交汇节点应能支持流量报文的缓存和聚合.在以交换机为核心的数据中心中，由于传统交换机的缓存空间和包处理能力有限，因此不支持数据流的网内聚合功能能力，而网内流量聚合则可以在以服务器为核心的数据中心内得到自然支持.但是，随着技术的发展，SDN技术体制下交换机的可编程成为可能[24-26].当前，Cisco和Arista已研制开发了具有可编程数据平面的应用交换机数据平面[27-28]，使得在以交换机为核心的数据中心中开展流间数据聚合成为可能.

在以服务器为核心的数据中心内，多端口商业服务器不仅作为终端主机，同时也可作为交换机使用.实际应用中，服务器通过千兆可编程交换板卡ServerSwitch来定制报文转发功能[29].由于交换芯片和服务器的CPU之间存在高吞吐量以及低延时通道等优势，ServerSwitch可调用服务器的CPU来进行网内数据分析处理.如先前的研究工作[29-30]所言，配备ServerSwitch的服务器能支持新型网络设备，如网内包缓存.因此，以服务器为核心的数据中心网络结构为实现流间数据聚合带来了可能.

2.2Incast最小代价树

令图G=(V,E)代表一个数据中心，其中V为点集，E为边集.图中的点v代表数据中心内的交换机或服务器，边(u,v)代表点u到v的链路，u,v∈V.

本节旨在通过对网内相关流量进行网内数据聚合，最小化incast传输过程产生的总流量.对于任意一项incast传输，其中接收端为r，发送端为{s1,s2,…,sm}，我们要在图G=(V,E)中为其生成一棵incast聚合树.每个发送端的数据流沿着生成的聚合树传送到相同的接收端r.在BCube和FBFLY等数据中心中，对于每个incast传输而言存在大量该类incast聚合树.难题在于如何寻找一棵incast聚合树，其网内数据聚合后产生最少的网络流量.

对于任意incast聚合树而言，如果其中某节点支持网内缓存并且接收到至少2个输入流，则该节点能实现网内数据聚合.这样的节点称为聚合节点(aggregating nodes)，其他节点称为非聚合节点.需要注意的是，节点自身生成的数据流也可被看作其输入流.在每个聚合节点上，多个数据流被最终聚合为一条新的数据流.为便于表述，我们假设经聚合后产生的新数据流的大小等于所有输入中的最大数据流大小.在实验部分，我们将探讨更通用的incast传输配置.在非聚合节点，由于其不支持网内缓存及数据包处理，输出数据流的大小为输入数据流大小的总和.

对于给定的incast聚合树，其代价被定义为完成incast传输而引发的网络流量总和.更准确地说，incast聚合树的代价是其所有边权重的总和，即incast聚合树中除接收端以外的所有节点输出流量的总和.我们假设所有发送端生成的流量均为1 MB，由此incast聚合树的代价便可标准化.此时，聚合节点输出链路的权值为1.

对于incast传输来说，最小代价聚合树问题是在G(V,E)中找到一个覆盖所有incast成员且代价最小的连通子图.因此，问题转化为如何为数据中心中的incast传输构建一棵incast最小代价树.

2.3基于Incast树的流间数据聚合实现

对于incast传输而言，为其构造出最小代价incast聚合树之后，相关管理器可据此实现其传输过程.

首先，incast管理器通过广播的方式将生成的incast聚合树拓扑结构通知给树内所有服务器，则涉及到的服务器将会知道其父服务器和子树的结构.若某个服务器有一个以上的子服务器或其本身就是发送端且有一个子服务器，则该服务器为聚合服务器.如图3(c)所示，服务器v0,v1,v2都是聚合服务器.在此基础上，管理器将一些数据聚合任务配置到这些聚合服务器上，聚合服务器在向下转发数据流之前首先对其输入数据进行聚合运算.

若发送端的数据已经准备好，并且其本身并非聚合服务器，则该发送端将数据流沿着incast聚合树传递给接收端.数据流一旦到达聚合服务器，所有的包都会被缓存.若来自该聚合服务器所有后续服务器的数据流都已到达，则聚合服务器将按照下面的方式进行网内数据聚合.首先按照数据流键值对的键值对其分组，然后分别对每组使用聚合函数，最终产生一条新流取代原来所有的输入流.

Fig. 3　Different incast trees for an incast transfer in a BCube(4,1).图3　Bcube(4,1)拓扑结构中不同的incast聚合树

聚合服务器也可以在数据流到达时立即进行聚合操作.该机制避免了等待所有输入流所产生的延迟.在incast传播树的唯一接收端对其所有输入流使用reduce函数进行聚合.图2描述了一个基于incast树的流间数据聚合示例.从图2可以看出，数据流1和数据流2汇合成了数据流5，数据流3和4被聚合成数据流6，数据流5和流6被转发到接收端并聚合成数据流7.

相关研究发现，类似MapReduce的分布式系统面临计算偏斜的影响[31].其中，map任务偏斜程度最大，其运行时间不只取决于输入数据的规模，而且受随机因素的影响较大.此时，一些map任务要花费比其他任务更长的时间去处理输入数据，这就减缓了整个作业的处理过程.因此，其他发送端将在最慢的发送端完成之前沿incast树传递各自的输出数据流.最后一条数据流成功到达接收端的完成时间即为incast传输在shuffle阶段的总耗时.其中，最后一条数据流在其传播路径上的每个聚合服务器处都需要耗费一定的计算时间.然而，对于数据流来说，其所经过的聚合服务器总数最大为该树的深度减去1，例如在BCube(n,k)网络中最多为k.这种额外时间代价与map或reduce阶段的计算时间相比，对整个作业完成时间影响很小.因此，这类额外时间对像MapReduce这样的批处理系统而言可以承受.

3高效Incast聚合树的构建

本节我们首先提出2种incast聚合树的近似构建方法，即基于RS的方法和基于ARS的方法.在此基础上优化incast聚合树的构造问题，提出高效的构建策略，并探讨了incast聚合树的动态性和容错问题.

3.1Incast聚合树的构建方法

为了满足大量发送端的incast聚合树的快速构建需求，我们深入挖掘数据中心的网络拓扑特征，进而设计了一种近似的构造方法.

在数据中心网络中，任意服务器对之间有多条可用平行路径.在BCube(n,k)中，如果任意一对服务器的标识符在k+1个维度上不同，则二者之间有k+1条平行不相交路径.incast最小代价树问题的一种直观解决方法就是，每个发送端独立选择其中一条单播路径将其数据传输给接收端.这种单播驱动的incast树由源自全体发送端的单播路径混合而成.不足之处在于，这种方法可获得的网内流量聚合增益并不大.

图3(a)给出了BCube(4,1)中单播驱动的incast树的示意图.唯一的接收端是v0，发送端集合是{v2,v5,v9,v10,v11,v14}.产生的incast树由18条链路构成，总代价为22，没有聚合节点.但是，如果依据图3(c)所示的方式来构造incast的传播树，则该incast传播树只有12条链路，总代价是16，而且其中有2个聚合节点v1和v2.

incast网内聚合功能需要集中式的管理器负责最小传播树的构造，MapReduce架构中的JobTracker可以承担该角色.当所有incast成员的标识符给定之后，incast管理器可以通过挖掘数据中心的网络拓扑性质，高效计算出传播代价尽可能小的incast树.

数据中心的网络互联结构BCube(n,k)可被抽象为k+1维n-ary的广义超级立方体[18].在BCube(n,k)和广义超级立方体中，一对服务器xkxk-1…x1x0和ykyk-1…y1y0被互称为维j的1跳邻居，当且仅当二者的标识符在维j不同.因此不难得出任意一台服务器在每个维度上都有n-1个1跳邻居.BCube(n,k)和广义超级立方体之间的差别仅在于，广义超级立方体中的服务器可以直接相连，而BCube(n,k) 中的服务器却需要通过交换机相连.也就是说，每台服务器和它同维度的所有邻居都通过一个共同的交换机间接地连在一起.以此类推，若2个服务器的标识符在j个维度存在差异，则二者互为j跳邻居.

考虑BCube(n,k)中的某个incast传输，其中接收端为r，发送端的集合为{s1,s2,…,sm}.令接收端的标识符为rkrk-1…r1r0，发送端的标识符为sksk-1…s1s0.为不失一般性，我们假设incast传输中接收端和发送端的最大海明距离为k+1，更一般的场景将在后续进行讨论.所有发送端到接收端的最短路径可被扩展为阶段k+2的多级有向图.其中，只有接收端位于阶段0，而位于阶段j的服务器必须是接收端的j跳邻居.另外，必须有一组交换机作为2个相邻阶段的中继，因为在BCube(n,k)中服务器不能直连.

需要注意的是，若某个发送端是接收端的j跳邻居，则其必然出现在阶段j.如图3所示，发送端v5,v9,v10,v11和v14都位于阶段2，但另一个发送端v2却位于阶段1.然而，只有这些发送端和接收端不足以形成包含所有incast成员的连通子图.因此，问题被转化为如何为每个阶段增添最少数目的额外服务器，以及如何在相邻阶段之间选择交换机以构成incast最小代价树.

定义1. 对于incast树中阶段j-1的服务器集合A以及阶段j的服务器集合B，A包含B当且仅当B中的每台服务器都存在一条有向链路从其自身到A中的服务器.如果A的任何子集都不包含B，我们就称A严格包含B.

考虑到交换机标识符可由与其相连的2个服务器推断得出，因此我们可以只关注每个阶段新增服务器的选取.定义 1旨在保证源自阶段j服务器的数据流都能被准确送往阶段j-1的服务器.

我们从阶段k+1开始为每阶段确定除发送端以外的新增服务器，直至阶段1.构建过程必须满足一个限制条件，即阶段j-1的服务器严格包含阶段j的服务器(1≤j≤k+1).给定阶段j的服务器集合，通过利用BCube(n,k)的拓扑特征推断在满足上述约束条件下阶段j-1的服务器.值得注意的是，这种阶段j-1服务器集合并非是唯一的.这是由于在BCube(n,k)中阶段j的每台服务器在j维有一个共同的阶段j-1的邻居，只不过当前服务器和接收端的标识符在j维存在差异.在此基础上，我们为incast传输引入路由序列的概念：

定义2. 令e1e2…ej…ekek+1为包含k+1个路由符号的路由序列，是(k+1)!个组合中的一个.一棵incast树的阶段j与一个路由符号ej相关联.对于阶段j的服务器X=xk…xj…x1x0和接收端r，我们有：

1) 若2个标识符的维ej不同，则将服务器X在ej维的n-1个邻居的标识符与接收端的标识符对比，选择ej维标识符相同而其他j-1维标识符不同的邻居.

依照上述规则，服务器X的邻居服务器将出现在incast树中的阶段j-1.给定incast传输及相关的路由序列e1e2…ej…ekek+1，可通过下述方法生成对应的incast聚合树.

我们从k+2个阶段中的任意阶段j开始.为不失一般性，假设j=k+1.一旦阶段j的服务器给定，我们把这些服务器划分成一个个分组，以便每个分组内的服务器都互为维度ej上的1跳邻居.在每个分组中，每台服务器和接收端的标识符在维度j上不同，即它们是接收端的j跳邻居.在任意分组中，每台服务器通往接收端的下一跳服务器的标识符在维度j-1不同，并出现在阶段j-1.需要注意的是，任意分组中的每一个服务器关于通往接收端的下一跳服务器都有j种选择.这里，我们要求它们在阶段j-1共用相同的下一跳服务器.

为此，我们可根据定义2为所有分组中服务器各自选择下一跳的新增服务器，并且，组中所有服务器和它们的共同下一跳服务器的标识符除了ej维外都相同.实际上，共同的下一跳服务器和接收端的标识符在维度ej相同.如图3(b)所示，位于阶段2的所有服务器根据路由符号e2=0被划分为3组，分别为{5}，{9,10,11}和{14}.据此，可以推断3个分组位于阶段1的下一跳服务器分别为4,8和12.在这种方式下，如图3(b)所示从每组到接收端的数据流在阶段j-1能实现所期望的网内数据聚合；否则，如图3(a)所示，在阶段j-1没有机会实现网内聚合的机会.

阶段j的其他节点分组采用同样的方法进行处理，至此阶段j-1的服务器集合严格包含了j阶段的服务器集合.需要注意的是，一些发送端可能原本就位于阶段j-1,因此，阶段j-1的服务器集合是发送端和其他新增服务器的并集.在此基础上，运用上述方法可推断出应该出现在阶段j-2的新增服务器.以此类推，所有k+2个阶段的服务器集合和相邻阶段间的有向路径形成最终的incast树，其被称作基于路由序列的incast树，简写为基于RS的incast树构造方法.

定理1. 对于BCube(n,k)中有m个发送端的incast传输来说，基于RS的incast树构建方法的时间复杂度为O(m×logN)，其中N=nk+1表示BCube(n,k)中服务器的数量.

证明. 我们的方法最多需要分别考虑k个阶段.其中，根据ej将阶段j的所有服务器分组的过程可以简化为如下方法.对处于阶段j的已有服务器，我们提取它除ej维以外的标识符，得到的标识符表征这个服务器所在的组；然后将这个服务器加到这个分组中，推断出组里所有服务器共同的下一跳服务器.阶段j的计算开销与该阶段的服务器数量成比例.由于每阶段的服务器数量不会超过m，所以其时间复杂度为O(m).考虑到算法最多运行k个阶段，因此综上所述该方法的时间复杂度是O(m×k).定理1得证.

证毕.

3.2Incast最小代价树的构造方法

路由序列e1e2…ej…ekek+1可以为BCube(n,k)中任意incast传输产生一棵基于RS的incast传播树.对incast传输来说，最多存在(k+1)!种这样的路由序列.不同的路由序列产生的incast传播树可获得的网内聚合增益和额外代价都不同.例如，我们可由路由序列e1e2=10构造出如图3(b)所示的incast树，也可以路由序列e1e2=01构造出图3(c)所示的另一棵incast树.

因此，本文所面临的难题在于，如何从(k+1)!个路由序列中挑选出某个路由序列，据此构造的incast树的聚合增益最大.一种简单的方法是，对所有(k+1)!种路由序列分别应用基于RS的方法生成所有可能的incast树，然后计算每棵incast树的代价，从中挑选出代价最少的incast树.这种方法带来非常高的计算开销，其计算复杂度是O((k+1)!×k×m).

为此，我们提出如下更高效的方法来构造incast最小代价树.从阶段j=k+1开始，在定义了路由符号ej(0≤j≤k)后，阶段j的所有服务器都能被划分为组.在各分组内可以采用基于RS的方法为所有分组成员确定位于阶段j-1的一组下一跳服务器.这样，分组的数量和下一阶段新增的新增服务器数量刚好相等.这些新增服务器和阶段j-1的原有发送端构成了该阶段的全部服务器集合.阶段j的输出数据流将在聚合服务器处融合，阶段j-1的输出数据流数量等于位于该阶段的服务器总量.受此启发，我们把基于RS的方法应用到其他k种路由符号ej的设置上，得到相应的另外k个处于阶段j-1的服务器集合.至此，我们只需要从k+1个候选的服务器集合中选择最小的服务器集.ej的设置被标记为阶段j中所有k+1个候选者中最好的选择.在这种方式下，从阶段j输出的数据流在相邻的阶段j-1可以获得最大的网内聚合增益.

一旦推定出阶段j-1的最小服务器集合，则可进一步求得该阶段路由符号ej-1的最佳选择，并进而求得相邻阶段j-2的最小服务器集合.最后，所有k+2个阶段的各自服务器集合和相邻阶段间的有向路径组成一棵incast树，同时也可确定对应的路由序列.这种方法称为基于ARS的incast树构建方法.

我们用一个例子来阐述基于ARS方法的好处.考虑图3中的incast传输，如图3(b)所示在e2=0时，位于阶段2的所有服务器被划分为3组，分别为{5}，{9,10,11}和{14}，而位于阶段1的服务器集合为{2,4,8,12}.但在e2=1的设定下，如图3(c)所示，位于阶段2的所有服务器被分为3组，分别是{5,9},{10,14}和{11}，而位于阶段1的服务器集合是{1,2,3}.因此，为阶段2选择路由符号e2=1，为阶段1选择服务器集{1,2,3}.结果表明，图3(c)所示的incast树的代价要明显低于图3(b)所示的incast树的代价.

定理2. 给定BCube(n,k)中的有m个发送端的incast传输，基于ARS的incast树构造方法的时间复杂度是O(m×(logN)2)，其中N=nk+1表示BCube(n,k)中服务器的数量.

证明. 考虑到我们的方法最多在k个阶段上执行(阶段k+1到阶段2)，根据定理 1可知当给定路由符号ek+1时，其在阶段k+1的计算开销是O(m).而在基于ARS的构建方法中，我们在所有k+1种ek+1设置下执行了相同的操作，因此以O((k+1)×m)的计算开销作代价为阶段k共生成k+1个服务器集合.另外，从k+1个路由符号中确定最小服务器集合的计算代价为O((k+1)×m).总之，在阶段k+1分别运行的incast树构造方法的代价计算复杂度是O((k+1)×m).

由于ek+1已占有集合{1,2,…,k+1}中的某个值，则基于ARS的方法实际上是从k个路由符号中确定阶段k-1的最小服务器集，所以其最终计算开销是O(k×m).综上所述，基于ARS的构造方法的总计算开销是O(k(k+3)×m2).定理2得证.

证毕.

3.3发送端动态行为的处理方法

已知发送端集合为{s1,s2,…,sm}，接收端为r的incast传输，当额外的新发送端sm+1加入时已经构造好的incast树得到更新以涵盖这个新发送端.一种方法是针对新的发送端s1s2…smsm+1，重新运行3.2节提出的方法构造一棵新的incast树.然而，这种方式产生了O(k2×m)的额外计算开销.

因此，我们更倾向于用增量式方法来更新已有的incast树.首先，incast管理器维持着路由序列与当前incast树的联系.一旦一个新的发送端sm+1加入已有的incast传输中，通过调用传统的基于RS的方法，能够以O(k)的计算开销推导出一条从sm+1到r的单播路径.此单播路径和先前的incast树组合构成新的incast树.为了确保incast树中所有的服务器都知道这个改变，incast管理器只需将单播路径结构广播给沿路的各个服务器.通过这种方式，新incast树中的每台服务器都知道以其自身为根且能够进行网内数据流聚合的子树结构.此时，先前发送端到接收端r的路径没有任何改变.

当发送端sj退出原有的某个incast传输时，incast树也应该更新以应对这一变化.首先，在原有incast树中，incast管理器会移除从发送端sj到接收端r的单播路径.需要注意的是，为即将离开的发送端提取单播路径需要将原有incast树的相关边的权值减去1，权值为0的边将从树中移除，如此一来，我们得到了新的incast树.为确保新incast树中所有服务器都知道这个改变，incast管理器只需将单播路径结构扩散给沿路的各个服务器，这种方式同样不会改变剩余发送端到接收端的路径.

综上所述，我们的incast树构造方法可以灵活地处理发送端的动态行为.例如在MapReduce中主服务器常会安排某个空闲服务器去替换失败的map任务.这种过程便是由即将离开的发送端和即将加入的发送端所构成.

3.4接收端的动态行为

在实际应用中，每个incast传输的接收端r也可能会被新的接收端取代，我们用rn表示.例如，在一个MapReduce作业中，主服务器将会安排另一个服务器去替代失败的reduce任务.在这种情况下，incast管理器会采用基于ARS的方法生成一棵新的incast树，然而这种方法导致过大的计算开销为O(k2×m).

因此，我们更倾向于以增量方式更新incast树.incast管理器为先前的incast传输维持着路由序列e1e2…ej…ekek+1与incast传播树之间的映射关系.给定原有的接收端r和新的接收端rn，我们逐维比较二者的标识符.若标识符只有ej维不同，则以r和rn为根的2棵incast树从阶段k+1到阶段j是相同的，而从阶段j到阶段0出现差异.换句话说，这2棵incast树上从阶段k+1到阶段j的服务器集合和跨2个相邻阶段的有向路径都是相同的.

因此，incast管理器只需重新计算从阶段j到阶段0的树结构即可.给定路由符号e1,e2,…,ej以及ej阶段的服务器集合，从阶段j到阶段0的incast树结构可以用基于RS的方法获得.

如果rn出现在先前的以r为根的incast树中，其在先前incast树中的子树仍存在于以rn为根的incast树中，但在新的incast树中应该从阶段0开始.

可以断定j越小上述方法越有效.如果rn刚好是r在e1维的一个邻居，incast管理器只需调整从阶段1到阶段0的有向路径.给定以r为根，路由序列为e1e2…ej…ekek+1的incast树，不难发现如果接收端r需要被替换，r在e1维的所有n-1个邻居是最好的替代者.如果这些替代者都不空闲，incast管理器将会从r在e2维的n-1个邻居中选一个空闲的作为替代，以此类推.通过这种方式，我们可以最大化已有incast树的重用效果，极大地减少更新接收端所带来的二次计算开销.而且，由于中间节点已缓存了最初incast最小代价树的许多数据，这些数据也能在新的incast最小代价树中得到重用.

4其他相关问题的讨论

本节中我们将进一步讨论其他一些重要设计因素对流量网内聚合方法的影响.

4.1通用Incast传输模式

此前为便于理解，我们假设incast传输中发送端和接收端之间的最大海明距离为k+1.但是，基于RS和基于ARS的incast树构造方法可以通过扩展支持更通用的incast传输.设d表示发送端和接收端间的最大海明距离,若d

在这种情况下，定义2可修改为：设e1e2…ej…ed表示由d个路由符号构成的一个路由序列，其是d! 种排列中的一种.而incast树的阶段j和路由符号ej(1≤j≤d)相关联.从而基于RS和基于ARS的构造方法能够很好地适用于更通用的incast传输.

4.2其他数据中心结构下的Incast传输模式

如2.1节所述，现存的以交换机为核心的网络拓扑由于普遍使用传统交换机，因而不具备充足的数据包缓存和可编程能力.也就是说，以交换机为核心的数据中心目前并不能实现流间的网内数据聚合.然而，随着技术的发展，例如Cisco ASIC 和arista的应用交换机已经能够提供可编程数据平面.若未来数据中心采用此种新型交换机，则能自然地支持流间的网内数据聚合.

虽然第3节以BCube为背景研究了以服务器为核心结构的incast树构造方法，但本文提出的方法也可被应用到其他以服务器为核心的结构中，如DCell[13],BCN[16],FiConn[19],SWD[20]和Scafida[21]，区别在于incast树的构建方法将有所差异.我们将其他以服务器为核心的数据中心内流间数据聚合的研究留待后续.

另外，本文提出的方法也能够直接应用于FBFLY和HyperX这2种以交换机为核心的网络结构中.其原因在于BCube拓扑结构的实质是广义超级立方体，与FBFLY和HyperX拓扑结构本质上相同.若FBFLY和HyperX中采用上述新型交换机，则我们的构造方法几乎不需修改便可直接使用.同样地，我们将以交换机为核心的数据中心内流间网内聚合留待后续研究.

4.3作业特征对Incast网内聚合性质影响

Facebook上的MapReduce集群拥有600个结点，统计发现83%的作业平均含有少于271个map任务和30个reduce任务[32].相似地，在一个由3 000台服务器构成的雅虎数据中心中也得到体现.另外，文献[33-34]曾证实，2个生产集群(由上千台机器构成Facebook的Hadoop集群和微软Bing搜索引擎的Dryad集群)中，作业的输入数据大小符合长尾分布.作业的大小(输入数据的大小和任务的数量)实际上遵循幂律分布，也就是说，工作负载由大量的小作业和相对少量的大作业组成.

我们提出的网内数据聚合模型非常适用于小型作业，因为每个聚合服务器都有充足的缓存空间来缓存数据包，而且对于大部分MapReduce作业来说，运行在每个聚合服务器上的函数都具有关联性和可互换性.而文献[35]曾提出如何将非可互换和非关联的函数以及用户自定义的函数转换成可互换和关联函数.因此，每个聚合服务器接收到部分数据包后即可执行网内聚合操作.因此，为聚合函数分配的存储空间通常是充足的，可用来缓存所需要的数据包.

5性能评估

本节首先介绍实验的设置，并在此基础上分别评估在不同数据中心规模、incast传输规模、incast聚合率和incast成员分布的情况下，关联性流量网内聚合方法的性能.

5.1原型实现

原型系统的平台由以太网连接的8台服务器虚拟出的81台虚拟机(VMs)构成.每台服务器配备有2个8核超线程的Intel Xeon E5620 2.40 GHz处理器、24 GB内存和1TB的SATA硬盘，运行内核版本为2.6.18的CentOS 5.6.其中，7台服务器每台运行10个虚拟机，用作Hadoop的虚拟从节点，另有1台服务器运行10个虚拟从节点和1个主节点.每个虚拟从节点支持4个map任务和1个reduce任务.通过扩展Hadoop使其能支持任意shuffle传输的网内聚合.每台物理服务器上的所有虚拟机通过一个虚拟交换机共享主机的网卡.我们对Hadoop的设置进行了扩展，从而能够支持数据流的网内缓存和数据聚合.

为模拟实现incast传输，实验使用了Hadoop 0.21.0内置的字数统计作业.该作业的发送端(map任务)和接收端(reduce任务)的数目被分别设置为320和1.实验给每个map任务分配10个输入文件，每个文件64 MB.在shuffle工作阶段，从发送端到接收端的平均数据量在每个发送端处进行聚合后大约为1 MB.

考虑BCube(n,k)(3≤k≤9)数据中心内的incast传输，每个发送端和唯一的接收端被随机地分配一个k+1维BCube标识符.我们在该虚拟平台上通过如下方式模拟了BCube数据中心内的incast传输过程，并分别生成基于ARS的incast树和单播incast树.

为在BCube中部署incast传输，我们设计了下述从incast树节点到测试平台的映射方式.其中，主虚拟机发挥incast管理器的作用；4个发送端、一个可能的接收端以及一些incast树的内部节点被映射到30个从虚拟机中.通过这种方式，我们把每个虚拟机抽象为虚拟机代理(VMAs)，每一个虚拟机代理对应incast树中的一个节点.我们要求映射到同一个虚拟机上的所有节点不能包含任何incast树中横跨相邻阶段的邻居对.例如，图3(c)中的节点v5和v9可以出现在相同的虚拟机中，但是这个虚拟机不能容纳节点v1.因此，在进行incast传输期间，同一个虚拟机上的虚拟机代理间将不会产生局部通信.实际上，对于任何虚拟机代理，其incast树中的下一阶段的邻居VMA将出现在不同的虚拟机上，这些虚拟机处于相同或不同的物理服务器.因此，incast树中的每条边都被映射到2个虚拟机间的虚拟链路或者测试平台中服务器之间的网络物理链路.

实验将基于ARS的incast树构造算法分别与典型Steiner树算法、单播驱动incast树算法以及其他算法从4个方面进行性能比较.这4个性能指标分别为所产生的网络流量、占用的链路数量、缓存服务器的数量以及接收端输入数据的大小.其中，网络流量指的是incast树中所有链路上的流量总和.

实验中所使用的Steiner树算法来自文献[36]，其优势在于计算速度较快.具体作法是：1)依据incast成员生成虚拟完全图；2)在该图上计算最小生成树;3)虚拟完全图中的虚拟链路被最初拓扑结构中任意2个incast成员的最短路径取代，并删除不必要的路径.

5.2数据中心规模对聚合增益的影响

实验在测试平台BCube(6,k)子网上部署了一个有320个发送端的incast传输，并构造了基于ARS的incast树.经过大量实验，我们收集了不同性能指标的平均取值，图4展示了我们的方法与其他3种方法在4种性能指标上的差异.

从图4可以看出，与现有方法相比，基于ARS方法和单播驱动方法能平均节省38%和18%的网络流量.这是因为前者的聚合服务器数量随着k的增加而增加；但后者的聚合服务器数量则随着k的增加而减少.此外，基于ARS的方法构造出的incast树占用的链路数目也较少，这意味着所使用的服务器和网络设备也较少.而从图4(d)可以看出，基于ARS的方法极大地减少了接收端输入数据的规模.

Fig. 4　Changing trends of four metrics for incast transfers with 320 senders in BCube(6,k) when 3≤k≤9.图4　发送端为320的incast传输在不同的BCube(6,k)的4项指标的变化情况

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传输的2种指标随发送端规模的增加而变化

同时，基于ARS的方法在一定程度上要优于Steiner树算法的性能.这是因为若不考虑数据中心规模，在二者链路数目相似的情况下，基于ARS的方法用到了比Steiner树算法更多的聚合服务器.综上所述，不论数据中心的规模如何，基于ARS的incast树构造方法总是远远优于另外2种方法.

5.3Incast传输规模对聚合增益的影响

实际应用中，MapReduce往往包含有几百甚至上千的map任务.然而，由于测试平台的资源有限，不能进行如此大规模的作业.因此我们利用模拟实验进一步论证上述方法的扩展性，用Java实现BCube数据中心网络架构，并参考Hadoop的wordcounter作业产生所需的incast的传输.具体而言，分别创建了拥有m(m∈{100,200,…,3900,4000})个发送端的incast组播传输，该作业为每个发送端提供用Hadoop内置的RandomTeextWriter，随机产生64 MB的输入数据.从每个发送端到接收端的数据流量被控制在1 MB.图5展示了BCube(8,5)中，2种方法在不同规模incast传输下产生的网络流量和占用的链路数的变化情况.

图5表明，随着m从100变化到4 000，基于ARS的方法和单播驱动方法能最多节省59%的网络流量，平均节省27%.即使在大规模的incast传输中，依然能够获得较大的网内数据聚合增益;基于ARS的方法占用的链路数目明显少于单播驱动方法，故使用的服务器和网络设备也较少.

5.4聚合率对聚合增益的影响

此前我们曾假设经聚合后得到的新数据流的大小等同于聚合服务器输入流中最大的一个.也就是说，所有输入流的主键集合是其中最大输入流主键的子集.本节中我们将在更通用的incast传输下评估基于ARS的方法.

给定incast传输中有s个数据流，令fi(1≤i≤s)表示第i个数据流的大小，δ(0≤δ≤1)表示任意数据流之间的聚合比.s个数据流经聚合后获得的新数据流的大小为

上述分析建立在δ=0的前提下，此时网内数据聚合达到最大增益.而当δ=1时，s中的任意2个数据流由于没有共享主键使得网内数据聚合不能获得任何收益.这种情况下，基于单播的方法与其他方法等价.此处，我们将在0≤δ≤1的情形下评估我们提出的基于ARS的方法.

以BCube(8,5)网络拓扑为背景，当δ的范围从0变化到1时分别评估基于ARS、单播和其他方法所生成的网络流量.实验结果表明，与其他2种方法相比，基于ARS的方法总是能够产生更少的网络流量.假设随机变量δ的值遵循统一的分布，则与其他2种方法相比，基于ARS的方法在当incast传输分别包含500和4 000个发送端时分别节约了24%和40%的网络流量.从图6可知，随聚合率的增加，incast传输时间也随之变化；无论聚合率的值为多少，基于ARS的方法都优于其他2种方法.

Fig. 6　Resultant network traffic under different aggregation factors and incast transfers in BCube(8,5).图6　网络流量随着聚合率增加的变化趋势

5.5Incast成员分布对聚合增益的影响

实际应用中incast传输成员可能位于整个数据中心内的空闲服务器上，这使得发送端和接收端位置的分布接近于随机分布.然而，这种随机分布使得incast传输占用了更多的数据中心资源，也产生了更多的网络流量.此处，我们将研究不同的incast成员分布模型对网内流量聚合增益的影响.

首先，此问题的关键在于寻找BCube(n,k)中的最小子网Bcube(n,k1)，以使得该子网能够满足所有incast成员的传输要求.在这种情况下，incast传输的所有传送者和接收端间的海明距离满足k1+1≤k+1，且基于ARS的incast树在Bcube(n,k1)的范围内最多存在k1+1个阶段.理论上，与之前BCube(n,k)范围内的基于ARS的incast树相比，它占用了更少的数据中心资源以及更少的网络流量.

为此，考虑30个shuffle传输，其中每个传输有500个发送端以及不同数量的接收端，接收端数量在1～30之间.对每个shuffle传输，在BCube(8,5)中，我们对它的所有incast传输应用2种分布方式以计算累计网络流量.图7展示了2种不同的成员部署方案下shuffle传输所产生的网络流量.我们可以看到，与随机分布方案相比，可控分布方案产生的网络流量更少；在可控分布和随机分布这2个方案下与其他方法相比，基于ARS的方法分别节省了62%和24%的网络流量，这也意味着基于ARS的方法在可控分布下能实现更大的增益.

Fig. 7　Network traffic under different distributions of shuffle member with 500 senders in BCube(8,5).图7　BCube(8,5)拓扑下网络流量随shuffle成员分布的变化

6相关工作

最近，Costa等人构建了Camdoop[37]系统，该系统与MapReduce有相似之处但运行在新型数据中心网络结构CamCube上.在Camdoop上，Costa等人尝试了shuffle阶段对流量进行网内聚合从而减少网络流量，并研究了CamCube服务器转发流量的性质.CamCube采用3维torus拓扑结构，即每台服务器直接和6个邻居服务器相连.因此，与其他典型的以服务器为核心的网络结构相比，如BCube,DCell,FBFLY和HyperX，CamCube表现出了更长的网络直径和更高的通信延迟.

然而，如何将Camdoop的基本原理应用到其他数据中心拓扑结构中仍是未知的，本文提出的聚合方法并不适合于其他同类的网络结构.针对此问题，本文首先分别探讨了以服务器为核心和以交换机为核心的数据中心网内数据聚合的增益和可行性.在此基础上，将网内数据聚合问题抽象为可以应用到任意结构数据中心上的incast最小代价树问题.

incast最小代价树问题与著名的Steiner树问题相似；所不同的是边的权重在最小Steiner树问题中是给定且不可更改的，而在incast最小代价树问题中却是不确定和可变的.事实上，incast最小代价树中每条边的权重取决于从所有发送端到给定接收端的树结构.最小Steiner树问题在普通图(general graph)中是NP难的且有很多近似算法[38-39].然而，这些算法不能有效解决incast最小代价树问题，第5节实验部分的评估进一步验证了这一结论.此外，大部分算法的时间复杂度为O(m×N2)，其中m表示incast传输成员数目，N表示数据中心内服务器总数.显然，该算法的复杂度过高，不能满足数据中心内incast最小代价树的构建要求.为此，在充分挖掘数据中心网络拓扑特征的基础上，我们提出了2种近似的incast树构造方法，分别是基于RS的和基于ARS的方法，且这2种方法的时间复杂度分别为O(m×logN)，O(m×(logN)2).

7结束语

类似MapReduce的大型分布式计算系统在相邻处理阶段之间传输大量的中间运算结果.本文旨在传输阶段进行流间的网内数据聚合，从而降低造成的网络流量，减少对网络资源的消耗.该问题被进一步抽象为incast最小代价树的构造问题.在此基础上，我们提出基于ARS的方法为任何incast传输构造一棵高效的incast树.我们进一步讨论了如何以增量式方法来解决incast树的动态性问题.最后，通过构建原型和大规模模拟评估了我们方法的性能.结果表明我们的方法和其他方法相比能极大地减少网络流量、节省数据中心资源.

参考文献

[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.

中图法分类号TP391

基金项目：国家自然科学基金优秀青年科学基金项目(61422214)

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

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