Multi-Queue Request Scheduling for Profit Maximization in IaaS Clouds

[EN] In cloud computing, service providers rent heterogeneous servers from cloud providers, i.e., Infrastructure as a Service (IaaS), to meet requests of consumers. The heterogeneity of servers and impatience of consumers pose great challenges to service providers for profit maximization. In this article, we transform this problem into a multi-queue model where the optimal expected response time of each queue is theoretically analyzed. A multi-queue request scheduling algorithm framework is proposed to maximize the total profit of service providers, which consists of three components: request stream splitting, requests allocation, and server assignment. A request stream splitting algorithm is designed to split the arriving requests to minimize the response time in the multi-queue system. An allocation algorithm, which adopts a one-step improvement strategy, is developed to further optimize the response time of the requests. Furthermore, an algorithm is developed to determine the appropriate number of required servers of each queue. After statistically calibrating parameters and algorithm components over a comprehensive set of random instances, the proposed algorithms are compared with the state-of-the-art over both simulated and real-world instances. The results indicate that the proposed multi-queue request scheduling algorithm outperforms the other algorithms with acceptable computational time.This work was supported in part by the National Key Research and Development Program of China under Grant 2017YFB1400800, in part by the National Natural Science Foundation of China under Grants 61872077 and 61832004, and in part by the Collaborative InnovationCenter of Wireless Communications Technology. The work of Quan Z. Sheng was supported in part by Australian Research Council Future Fellowship under Grant FT140101247 and in part by Discovery Project under Grant DP180102378. The work of Ruben Ruiz was supported in part by the Spanish Ministry of Science, Innovation, and Universities through the project OPTEP-Port Terminal Operations Optimization under Grant RTI2018-094940-B-I00 financed with FEDER fundsWang, S.; Li, X.; Sheng, QZ.; Ruiz García, R.; Zhang, J.; Beheshti, A. (2021). Multi-Queue Request Scheduling for Profit Maximization in IaaS Clouds. IEEE Transactions on Parallel and Distributed Systems. 32(11):2838-2851. https://doi.org/10.1109/TPDS.2021.307525428382851321