We propose throughput and cost optimal job scheduling algorithms in cloud computing platforms offering Infrastructure as a Service. We first consider online migration and propose job scheduling algorithms to minimize job migration and server running costs. We consider algorithms that assume knowledge of job-size on arrival of jobs. We characterize the optimal cost subject to system stability. We develop a drift-plus-penalty framework based algorithm that can achieve optimal cost arbitrarily closely. Specifically this algorithm yields a trade-off between delay and costs. We then relax the job-size knowledge assumption and give an algorithm that uses readily offered service to the jobs. We show that this algorithm gives order-wise identical cost as the job size based algorithm. Later, we consider offline job migration that incurs migration delays. We again present throughput optimal algorithms that minimize server running cost. We illustrate the performance of the proposed algorithms and compare these to the existing algorithms via simulation.
翻译:我们提出云计算平台的吞吐量和成本最佳工作时间安排算法,将基础设施作为服务提供。我们首先考虑在线迁移,并提出工作时间安排算法,以尽量减少工作迁移和服务器运行成本。我们首先考虑假设工作规模知识的算法,然后考虑工作抵达时的计算法。我们根据系统稳定性来确定最佳成本。我们开发了基于漂流加惩罚框架的算法,可以任意地实现最佳成本。具体地说,这种算法可以平衡延迟成本和成本之间的平衡。我们随后放松了工作规模知识假设,并给出了使用随时提供的工作服务的算法。我们显示,这种算法提供了与基于工作规模的算法相同的顺序成本。我们随后考虑造成迁移延误的离线外工作迁移。我们再次提出将服务器运行成本最小化的最佳算法。我们通过模拟来说明拟议算法的运作情况,并将这些算法与现有的算法进行比较。