【博士论文】大规模数据中心带宽分配与流量调度技术研究

2020 年 12 月 15 日 专知

来自大连理工大学李文信的博士论文，入选2020年度“CCF优秀博士学位论文奖”初评名单！

https://www.ccf.org.cn/Focus/2020-12-03/717578.shtml

大规模数据中心带宽分配与流量调度技术研究

随着互联网和计算机技术的发展,基于互联网提供的各种应用和服务也越来越多了。作为这些应用服务载体的数据中心,其建设需求也在不断增加。然而,在数据中心发展的过程中,还面临着诸多亟待解决的关键科学问题和挑战。本论文主要关注大规模数据中心中带宽资源受限、带宽资源分散、流量总量巨大、流量时空变化这四类挑战,在总结现有方法和研究成果的基础之上,围绕数据中心内的流量、数据中心间的流量、以及用户服务请求这三个研究主体,展开对带宽分配和流量调度这两类问题的研究,具体的研究内容和贡献如下:

在数据中心内部,集群计算应用触发的流量显著增加,从而使得链路带宽经常成为稀缺资源。为此,本文针对多种集群计算框架共享同一数据中心网络所引发的链路带宽倾斜使用、带宽资源非弹性使用、以及应用完成时间被延长这三方面的后果,研究跨集群计算框架的带宽分配和流量调度问题,以实现高链路带宽利用率和低应用完成时间的双重目标。在带宽分配方面,本文提出了虚拟链路组抽象模型,以构建虚拟带宽资源共享池,并据此设计了三层带宽分配方法,从而保障应用的网络性能,并实现带宽资源在集群计算框架间的弹性共享。在流量调度方面,本文设计了虚拟链路组依赖关系图,并提出了一个近似比为3/2的链路选择算法,从而实现负载均衡化的流量调度,并同时缓解链路带宽倾斜使用的情况。实验结果表明本文所提出的方法能够大幅降低应用完成时间,且提高链路带宽资源利用率。

在数据中心间,本文主要围绕成本和性能两个目标来展开针对数据中心间流量的带宽分配和流量调度问题研究。首先,在成本方面,本文发现Internet服务供应商(Internet Service Provider,ISP)对数据中心间流量所采用的比例计费模型中存在着相当多的免费时间间隙:在这些时间间隙上传输的流量不影响整体传输成本。为此,本文提出了基于李雅普诺夫优化(Lyapunov Optimization)技术的带宽分配和流量调度方法,以利用比例计费模型中的免费时间间隙进行流量传输,从而减少流量传输成本。实验结果表明本文所提出的方法能够大幅减少流量传输成本。其次,在性能方面,本文发现在进行带宽分配和流量调度时,灵活地放置网络流的端点能够显著地减少跨数据中心传输的Coflow的完成时间。为此,本文研究流量端点放置、带宽分配和流量调度的联合优化问题,以最小化跨数据中心运行的Coflow的平均完成时间。为了解决该问题,本文首先提出针对单个Coflow的端点放置、带宽分配和流量调度算法,然后将此算法扩展到多个Coflow的场景。实验结果表明本文所提出的方法能够大幅减少Coflow的平均完成时间。最后,在兼顾成本和性能方面,本文研究了针对数据中心间流量的带宽分配和流量调度问题,并提出了基于交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)的分布式带宽分配和流量调度算法,从而最小化供应商的网络带宽成本,并同时为数据中心间流量提供带宽保障。实验结果表明本文所提出的方法能够大幅减少供应商的网络带宽成本,并同时还能为数据中心间流量提供带宽保障。

在面向用户服务方面,本文主要研究带宽分配和用户请求流量调度两个子问题。在带宽分配方面,本文首先提出了“数据中心间的网络即服务”模型,以将用户在Internet上传输的流量引入到了大公司(如Google和Microsoft)的私有广域网中,并且重点研究该模型下的多用户多供应商的带宽分配问题。本文设计了基于两阶段斯塔尔伯格博弈(Stackelberg Game)理论的带宽分配方法,实验结果表明本文所提出的带宽分配方法能够同时保证供应商和用户的利益。在用户请求流量调度方面,本文研究了供应商带宽资源效率和用户延迟联合优化的用户服务请求调度问题,并提出了基于对数平滑技术的请求调度算法。实验结果表明,本文提出的请求调度算法能够大幅提高数据中心带宽资源利用率,且还能明显减少用户的延迟。