面向广域云服务的计算、数据和网络的协同调度研究

As current trends in cloud computing shows an increasing number of geographically distributed datacenters and wide-area stored data, there is an urgent need for automated mechanisms to schedule data-intensive applications across these datacenters. The scheduling algorithm must deal with constraints such as datacenter capacity limits, geographic locations, data locations and WAN bandwidth costs, while also maximizing the efficiency of job processing. In this research, we consider two basic problems in wide-area cloud scheduling: improving the time-efficiency and cost-efficiency of data-intensive applications. Because either job execution time or economic cost comprises computing cost and wide-area network transmission cost, and because computing cost relies on the selected virtual machines while network transmission cost depends on the amount of data, bandwidth and routing path, the scheduling is further complicated by the issues of VM sizing and placement, data placement and replica selection, and routing control. We will present collaborative scheduling algorithms, which jointly schedule computing, data and network links for orchestrating the data staging, job execution and routing. In particular, we will formulate the problem of minimizing job execution time and economic cost. Based on the analysis of its difficulty, we will devise approximation algorithms or heuristics if the problem is proved to be NP-Complete. Our proposals will fit for situations of offline scheduling and online scheduling, and also scale to the size of wide-area cloud systems by studying distributed scheduling model and algorithms. We will theoretically and empirically evaluate the algorithms, and deploy them on a real scheduling prototype system designed for astronomical data processing. The success of our research will enable the fast and cost-efficient data processing for astronomers, and further promoting the development of geo-distributed cloud services.

云计算的发展正呈现出两个特征：数据中心建设和大量数据及副本存储的泛地域化。面向广域云的数据密集型任务处理受数据中心的计算存储能力、地理位置、数据及副本的存储位置和广域网带宽的影响变得更加复杂困难。针对该问题，为提高数据密集型任务的处理效率，本项目拟开展广域云环境下的资源调度研究。综合考虑虚拟机实例选择与安置、数据副本选择与安置和网络路由控制技术，提出以“计算、数据和网络的协同调度”为核心，解决跨数据中心的数据密集型任务的时间效率优化和收益效率优化两个基本问题。具体的，本项目研究将针对离线调度、在线调度以及分布式调度情境设计协同调度算法，并对算法作理论分析和仿真实验评估。研究成果将应用部署到广域天文数据分析中，有望提高天文数据分析的运行效率，为广域云计算产业的发展提供理论和实践支持。

云计算的快速发展推动了各种类型的云服务不断涌现。为满足持续增长的用户需求，并提高云服务在广域范围内的利用效率，支撑云服务的超大规模数据中心的建设逐步走向泛地域化。与此同时，数据的规模也持续增加，数据的发布、存储和数据密集型应用均呈现出广域分布的特点。如何协同利用广域云环境下的多个数据中心，高效地分析处理同为广域分布的大量数据成为云计算面临的新挑战。本课题将设计面向广域云环境的计算、数据和网络的协同调度算法，综合考虑各数据中心弹性计算能力、数据及其副本选择和网络路由选择因素，提高任务执行的时间效率和成本效率。课题研究成果拟结合天文数据分析的应用背景，通过实际系统验证其有效性。..课题开展过程中，对广域环境下的任务调度问题作了完整的数学建模，并针对不同应用场景设计实现了多个调度算法以提高广域云环境下任务执行的效率。首先，为提高任务运行的时间效率，本课题设计提出了三个算法：基于超图分割的HPS算法适用于任务负载较高（资源需求量超过数据中心的可用资源量）的情况；基于数据本地性最优的贪婪算法适合任务负载较低（资源需求量远小于数据中心可用资源量）的情况；基于社区发现的CDS算法在其他场景下（资源请求量与资源可用量相差较小）的表现优于以上两个算法。课题在以上工作的基础上，进一步优化设计了改进的基于超图分割的HPS+算法，实验结果表明HPS+算法的调度结果相比以上算法，可降低数据的广域传输量达45%以上，缩短最终完成时间33%以上。其次，为提高广域计算任务的成本效率，本课题设计了基于扩展拉格朗日乘子法的ALMM调度算法。该算法可以给出多数据中心下任务调度的最低成本调度解。然后由于其求解过程较慢（150个任务和5个数据中心问题规模下的求解时间超过10分钟），因此，本课题同时设计了求解速度更快的DVDS算法。相比ALMM算法，DVDS算法在增加计算成本不超过10%的前提下，远远提高了求解的时间效率。