一种通用云计算资源调度问题的快速近似算法

A Fast Approximation Algorithm for the General Resource Placement Problem in Cloud Computing Platform

在分布式云计算平台中,面向大规模用户的在线应用需处理针对海量资源的用户需求,在给定的资源预算下,服务提供商需确定最优资源放置位置,以最大程度地满足用户需求,通常需求用给定时间段内均值表示.然而真实场景中用户需求是高度动态和随机的,采用随机需求模型以考虑更多需求细节,资源利用率可得到进一步优化.但相比均值调度方法,随机需求模型会导致很高的计算复杂度.已有的最优解求解算法的时间复杂度和资源总量成正比,无法满足海量资源在线调度的效率要求.基于非线性规划理论,提出了一个快速资源分配算法,该算法可将计算复杂度降低至最优解算法的1‰,并逼近最优解效果的99%,因此可用于在线应用场景中海量资源的高效调度.

There are regionally distributed demands for various resources in cloud based large-scale online services.Given fixed resource budget,the service providers need to decide where to place resources to satisfy massive demands from all regions,where demands are usually represented by mean value in given time span.However,in scenarios with a large number of resources,demands are dynamic and stochastic,considering fine-grained demands and adopting stochastic model will further improve resource utilization.Compared with mean demand-based algorithm,considering demand stochasticity in algorithm will increase resource utilization ratio,but also leads to high time complexity.The time complexity of optimal algorithm is linear to total amount of resources,thus may be inefficient when dealing with a large number of resources.Based on nonlinear programming theory,we propose Fast Resource Placement（FRP）,an effective resource placement method of high efficiency.In the algorithm,optimal solution is represented by continuous functions of input,and we construct approximation functions to reduce the computation complexity. The preliminary experiments show that in scenarios with general settings,compared with optimal algorithm,FRP can reduce the computation time by three orders of magnitude,and can achieve 99% effect of optimal solution.Therefore,FRP can be used to schedule large number of resources efficiently in time-tense scheduling scenarios.