Mehdi Dehghan Takht Fooladi, Mona Naghdehforoushh, Mohammad Hossein Rezvani, Mohammad Mehdi Gilanian Sadeghi

BLMDP: A new bi-level Markov decision process approach to joint bidding and task-scheduling in cloud spot market

In the cloud computing market (CCM), computing services are traded between cloud providers and consumers in the form of the computing capacity of virtual machines (VMs). The Amazon spot market is one of the most well-known markets in which the surplus capacity of data centers is auctioned off in the form of VMs at relatively low prices. For each submitted task, the user can offer a price that is higher than the current price. However, uncertainty in the market environment confronts the user with challenges such as the variable price of VMs and the variable number of users. An appropriate strategy should both maximize the user’s utility and determine the best bid for him/her. In this paper, we aim to solve the problem of joint minimizing the cost of processing tasks and maximizing user satisfaction. Our proposed method, which we call bi-level Markov decision-making process (BLMDP), works on two levels. At the top level, it selects the most appropriate user bids and adjusts the spot price to minimize the cost of VMs on the cloud provider side. At a low level, it decides to admit tasks in such a way as to maximize the user side satisfaction. Performance evaluation based on real data collected from Amazon web services shows that BLMDP manages to minimize cloud provider’s costs and maximize user gain more effectively compared to heuristic methods.

PDF

___

[1] Mukherjee A, Sundarraj R, Dutta K. Time-preference-based on-spot bundled cloud-service provisioning. Decision Support Systems 2021.
[2] Zhu Z, Peng J, Liu K, Zhang X. A game-based resource pricing and allocation mechanism for profit maximization in cloud computing. Soft Computing 2020; 24 (6): 4191-4203.
[3] Amazon Web Services Amazon EC2 spot instances pricing. https://aws.amazon.com/ec2/spot/pricing/. Accessed 01 May 2017.
[4] Teylo L, Arantes L, Sens P. Drummond LMDA. Scheduling Bag-of-Tasks in Clouds using spot and Burstable Virtual Machines. arXiv preprint arXiv 2020; 05042.
[5] Besharati R, Rezvani MH, Gilanian Sadeghi MM. An Incentive-Compatible Offloading Mechanism in Fog-Cloud Environments Using Second-Price Sealed-Bid Auction, Journal of Grid Computing 2021.
[6] Ivashko EE, Ivashko AA, Safonov GR, Tchernykh A. Cost-Efficient Strategy in Clouds with spot Price Uncertainty. Automation and Remote Control 2020; 81 (4).
[7] Kumar D, Baranwal G, Raza Z, Vidyarthi DP. A Survey on spot pricing in Cloud Computing. J. Network Syst 2018; Manage, 809–856.
[8] Song J, Guérin R. Pricing (and bidding) strategies for delay differentiated cloud services. ACM Transactions on Economics and Computation (TEAC) 2020; 8 (2):1-58.
[9] Fabra J, Ezpeleta J, Álvarez P. Reducing the price of resource provisioning using EC2 spot instances with prediction models, Future Generation Computer Systems 2019; 96: 48-367.
[10] Kamiński B, Szufel P. On optimization of simulation execution on Amazon EC2 spot market. Simulation Modelling Practice and Theory 2015; 58: 172-187.
[11] Cong P, Xu G, Wei T, Li K. A survey of profit optimization techniques for cloud providers. ACM Computing Surveys (CSUR) 2020; 53 (2):1-35,dio:10.1145/3376917
[12] Islam MT, Srirama SN, Karunasekera S, Buyya R. Cost-efficient dynamic scheduling of big data applications in apache spark on cloud. Journal of Systems and Software 2020; 162: 110515.
[13] Yang G, Hou L, He X, He D, Chan S, Guizani M. Offloading Time Optimization via Markov Decision Process in Mobile-Edge Computing. IEEE Internet of Things Journal 2020; 8 (4): 2483-2493.
[14] Liu D, Cai Z, Li X. Hidden markov model based spot price prediction for cloud computing. In 2017 IEEE International symposium on parallel and distributed processing with applications and 2017 IEEE international conference on ubiquitous computing and communications (ISPA/IUCC) 2017; 996-1003.
[15] Garí Y, Monge D.A, Mateos C, Garino C.G. Markov Decision Process to Dynamically Adapt spots Instances Ratio on the Autoscaling of Scientific Workflows in the Cloud. In Latin American High Performance Computing Conference 2017; 353-369.
[16] Surya K, Rajam VMA. Prediction of resource contention in cloud using second order Markov model. Computing 2021; 1-22,
[17] Cong P, Zhou J, Chen M, Wei T. Personality-guided cloud pricing via reinforcement learning. IEEE Transactions on Cloud Computing 2020.
[18] Cai Z, Li X, Ruiz R, Li Q. Price forecasting for spot instances in Cloud computing. Future Generation Computer Systems 2018; 79, 38-53.
[19] Tang S, Yuan J, Wang C,Li XY. A framework for amazon ec2 bidding strategy under sla constraints. IEEE Transactions on Parallel and Distributed Systems 2013; 25, 2-11.
[20] Xie H, Lui JC. A Reinforcement Learning Approach to Price Cloud Resources With Provable Convergence Guarantees. IEEE Transactions on Neural Networks and Learning Systems 2021.
[21] Hidayat T, Franky DST, Mahardiko R. Forecast Analysis of Research Chance on AES Algorithm to Encrypt during Data Transmission on Cloud Computing. In 2020 2nd International Conference on Broadband Communications, Wireless Sensors and Powering (BCWSP) 2020; 163-166.
[22] Deng S, Xiang Y, Nan B, Tian H, Sun Z. A hybrid model of dynamic time wrapping and hidden Markov model for forecasting and trading in crude oil market. Soft Computing 2020; 24 (9): 6655-6672.
[23] Bakhtiari H, Zhong J, Alvarez M. Predicting the stochastic behavior of uncertainty sources in planning a standalone renewable energy-based microgrid using Metropolis–coupled Markov chain Monte Carlo simulation. Applied Energy 2021; 290, 116719.
[24] Floyd S, Jacobson V. Random Early Detection (RED) gateways for Congestion Avoidance. IEEE/ACM Transactions on Networking 1993; 1 (4): 397–413.
[25] Kumar D, Baranwal G, Raza M. A Systematic Study of Double Auction Mechanisms in Cloud Computing. The Journal of Systems and Software 2017.
[26] Portella GJ, Nakano E, Rodrigues GN, Melo CMA. Utility-based Strategy for Balanced Cost and Availability at the Cloud spot Market. IEEE 12th International Conference on Cloud Computing (CLOUD) 2019.
[27] Chen W, Xie G, Li R, Li K. Execution cost minimization scheduling algorithms for deadline constrained parallel applications on heterogeneous clouds. Cluster Computing 2020.
[28] Hassan AJ, Hammad M. spot Hopping: Increasing Reliability and Reducing Cost. International Journal of Computing and Digital Systems 2020; 9, 6.
[29] Pal P,Hui P. Economic models for cloud service markets: Pricing and Capacity planning. The journal of theoretical computer science, 2012; 113-124.
[30] Chang H,Fard P. Multitime scale Markov decision processes. IEEE Transactions on Automatic Control, 2003; 48, 976-987.