数据中心网络高效数据汇聚传输算法

摘要：

在数据中心中，类 MapReduce 的分布式计算系统在数据的混洗阶段产生巨大流量，令数据中心的东西向网络资源成为瓶颈．将这些高度相关的数据流在接收端进行聚合是分布式计算的通用处理方式，为了降低网络通信量并有效利用带宽，文中采用网内关联性流量的汇聚传输策略，将混洗和汇聚并行化，达到进一步降低东西向网络资源消耗、缩短混洗阶段延迟的目的．目前提出的 IRS-based 算法在适用场景上有一定局限性，为了解决这一问题，文中首先在以服务器为中心的代表结构 BCube 上建立 incast 最小树模型，分别提出 MIB-based 算法和MC-based 算法，仅根据已知拓扑结构和发送节点编号即可快速生成一棵近似的最小代价 incast 树．MIB-based 算法针对发送节点强关联的情况，使高层发送节点尽可能汇聚到已有的低层发送节点构建 incast 树；MC-based 算法针对发送节点松散关联的情况，将节点进行最大程度上的聚合，通过增加最少的汇聚点完成 incast 树的构建．随后将上述两种算法结合起来进一步提出适用于各种场景的 M2-based 算法，通过推算时间复杂度证明该算法能够满足在线构建 incast 树的需求．最后，详细分析了 M2-based 算法对其他数据中心网络结构的适应性以及网内汇聚传输能够减少作业完成时间的原理．小规模实验结果表明，在不同网络规模下，M2-based 比 IRS-based 节省了网络中约3％的数据量，整个作业在混洗和 Reduce 阶段的等待时间比不采用网内汇聚缩短约2／3；在不同传输节点规模下，M2-based 比 IRS-based 节省了网络中约19％的数据量，整个作业在混洗和 Reduce 阶段的等待时间比不采用网内汇聚缩短约3／4．

关键词：数据中心、数据汇聚、网内聚合、混洗传输、incast树

所属期刊栏目：39

分类号：TP393(计算技术、计算机技术)

资助基金：国家“九七三”重点基础研究发展规划项目青年科学家专题项目2014CB347800;国家自然科学基金优秀青年基金61422214;国家自然科学基金91430214;国家“八六三”高技术研究发展计划项目基金2013AA01A213资助．

在线出版日期：2016-10-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共13页

页码：1750-1762