面向效用最大化的数据中心动态资源分配

Maximizing utilities in data center with dynamic resource allocation

传统数据中心的负载均衡只追求资源利用的最大化,而忽略了不同类型任务对完成时间的需求是不同的,使得系统总体服务质量无法达到最佳。针对不同任务的需求差异,引入时间效用函数以表征不同类型任务的完成时间与服务质量的关系,并形式化定义了面向效用最大化的动态资源分配问题。由于该问题是NP难的,设计了一个利用任务优先关系的调度机制,其主要思想为将原问题分解为若干同构的小规模子问题,并利用任务间的优先关系,决策为哪个任务优先分配资源。通过理论分析可以证明,当并行的任务的完成时间满足一定的序列性质时,该算法可以取得全局最优解。实验显示,该算法产生的收益是常用的先进先出公平调度机制产生收益1.5倍到2倍,并且比当前最新的算法2DFQ(多租户二维公平排队算法)的总效用高约17%。

In a data center,load balancing is used for resource scheduling to maximize the resource utilization of servers.However,since the requirement of completion time is different across different tasks,traditional load balance methods typically ignore such heterogeneity,leading to enormous decrease in the quality of service.This paper introduced a time-utility function(TUF)to express the utility according to the completion time of a task.With TUF,this paper studied how to maximize the total utility of all active tasks by resource allocation,which could be proved to be NP hard.It designed a scheduling algorithm to allocate resources properly for tasks.The main idea was to decompose the original problem into a number of isomorphic small-scale subproblems,and used the precedence relationship between tasks to decide which task to allocate resource first.The performance of this proposed algorithm could be proved to be very close to the optimal results by theoretical analysis.Experiments show that the overall utility generated by precedence relation scheduling algorithm is about 1.5x to 2x of that generated by FIFO fair scheduling mechanism.In addition,this algorithm outperforms the state of art 2DFQ by a significant margin of 17%.