论文部分内容阅读
近年来,云计算产业飞速发展。数据中心作为云计算的基础设施,在云计算的发展过程中起着至关重要的作用。在当今数据中心中,如何对网络资源高效调度是学术界和工业界共同关注的难题。研究发现,数据中心中任务的网络传输时间占据了总完成时间的50%,因此对于网络资源的管理和优化对缩短任务的完成时间非常重要。早期对数据中心中网络调度的研究主要集中在流级,然而流级抽象无法捕获数据中心中两组主机之间的通信语义。Coflow抽象是人们向应用感知网络调度迈出的重要一步。Coflow的引入使应用层的通信语义更加容易地传递到网络层。本文主要研究如何调度数据中心中单阶段任务和多阶段任务的Coflow以最小化总任务完成时间。对单阶段任务,本文主要关注多播(Multicast)通信模式。高效的多播算法可以大大提高数据中心中应用程序的性能。众所周知,由于网络管理的原因,数据中心中链路层和网络层多播通常被网络管理员禁用,所以本文主要研究应用层多播算法。对于数据中心中应用层多播,主要面临两个挑战:首先,如何准确地推测出网络的拓扑结构?其次,在准确地推测出网络的拓扑结构的前提下,如何设计一个高效的多播算法?本文通过层次聚类的思想,即使在有线和无线混合的数据中心网络架构中也可以准确地推测出数据中心的层次拓扑。利用数据中心网络的层次拓扑信息,本文提出了机架间传输优先多播算法IRFM。实验证明IRFM在纯有线数据中心网络中比其它多播算法快3.7~11.2倍,而在有线和无线混合的数据中心网络中比其它多播算法快4.8~14.6倍。对于多阶段任务Coflow调度问题,Coflow之间存在依赖关系。Coflow完成时间和任务完成时间之间存在很大差异。截至目前,本文是第一篇系统地研究如何调度多阶段任务中具有依赖关系的Coflow,以最小化总加权任务完成时间的论文。本文首先将多阶段任务Coflow调度问题形式化并证明该问题为强NP难问题。然后提出了可以在多项式时间内解决该问题的近似算法MCS。MCS算法在一般情况下的近似比为(2M+1),其中M为机器的数量,而在特殊情况下的近似比仅为3。由于目前数据中心网络大多采用具有收缩比的网络架构,这种网络架构不利于问题抽象和分析,因此现有的理论工作都没有考虑这种情况。而本文考虑了MCS算法在具有收缩比的网络架构中的适用情况,将MCS算法扩展到具有收缩比的网络架构中。最后分别在真机实验和大规模仿真中评估了MCS算法。在真机实验测试平台中,本文设计并实现了一个应用层调度框架。与纯DCTCP相比,本文提出的MCS算法将任务完成时间降低了81.65%。在大规模仿真中,本文使用一个基于事件的流级仿真器,并与目前两个经典的算法Aalo和LP-OV-LS进行了比较。与多阶段Coflow调度系统Aalo相比,本文提出的MCS算法将任务完成时间降低了33.48%;与最优的Coflow调度近似算法LP-OV-LS相比,本文提出的MCS算法将任务完成时间降低了83.58%。真机实验结果和大规模仿真实验结果均表明,本文提出的MCS算法和其理论下界之间的最大差距仅为9.14%。