Home Journal of Computer Science and Technology Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Abstract
Keywords
Electronic Supplementary Material
References
Show full outline
Hide outline
Regular Paper

An Online Algorithm Based on Replication for Using Spot Instances in IaaS Clouds

School of Software, Shandong University, Jinan 250101, China
Show Author Information

Abstract

Infrastructure-as-a-Service (IaaS) cloud platforms offer resources with diverse buying options. Users can run an instance on the on-demand market which is stable but expensive or on the spot market with a significant discount. However, users have to carefully weigh the low cost of spot instances against their poor availability. Spot instances will be revoked when the revocation event occurs. Thus, an important problem that an IaaS user faces now is how to use spot instances in a cost-effective and low-risk way. Based on the replication-based fault tolerance mechanism, we propose an online termination algorithm that optimizes the cost of using spot instances while ensuring operational stability. We prove that in most cases, the cost of our proposed online algorithm will not exceed twice the minimum cost of the optimal offline algorithm that knows the exact future a priori. Through a large number of experiments, we verify that our algorithm in most cases has a competitive ratio of no more than 2, and in other cases it can also reach the guaranteed competitive ratio.

Keywords

Infrastructure-as-a-Service (IaaS) cloudcost managementcompetitive analysisonline algorithmspot instance

Electronic Supplementary Material

Download File(s)
JCST-2104-11535-Highlights.pdf (414.7 KB)

References

[1]

Neto J P A, Pianto D M, Ralha C G. MULTS: A multi-cloud fault-tolerant architecture to manage transient servers in cloud computing. Journal of Systems Architecture, 2019, 101: 101651. DOI: 10.1016/j.sysarc.2019.101651.

Crossref Google Scholar
[2]

Calatrava A, Romero E, Moltó G, Caballer M, Alonso J M. Self-managed cost-efficient virtual elastic clusters on hybrid Cloud infrastructures. Future Generation Computer Systems, 2016, 61: 13–25. DOI: 10.1016/j.future.2016.01.018.

Crossref Google Scholar
[3]
Yi S, Kondo D, Andrzejak A. Reducing costs of spot instances via checkpointing in the Amazon Elastic Compute Cloud. In Proc. the 3rd IEEE International Conference on Cloud Computing, Jul. 2010, pp.236–243. DOI: 10.1109/CLOUD.2010.35.
Crossref
[4]

Jangjaimon I, Tzeng N F. Effective cost reduction for elastic clouds under spot instance pricing through adaptive checkpointing. IEEE Trans. Computers, 2015, 64(2): 396–409. DOI: 10.1109/TC.2013.225.

Crossref Google Scholar
[5]

Poola D, Ramamohanarao K, Buyya R. Fault-tolerant workflow scheduling using spot instances on clouds. Procedia Computer Science, 2014, 29: 523–533. DOI: 10.1016/j.procs.2014.05.047.

Crossref Google Scholar
[6]

Sampaio A M, Barbosa J G. Constructing reliable computing environments on top of Amazon EC2 spot instances. Algorithms, 2020, 13(8): 187. DOI: 10.3390/a1308 0187.

Crossref Google Scholar
[7]
Sampaio A M, Barbosa J G. Enhancing reliability of compute environments on Amazon EC2 spot instances. In Proc. the 2019 International Conference on High Performance Computing & Simulation, Jul. 2019, pp.708–715. DOI: 10.1109/HPCS48598.2019.9188116.
Crossref
[8]
Subramanya S, Guo T, Sharma P, Irwin D, Shenoy P. SpotOn: A batch computing service for the spot market. In Proc. the 6th ACM Symposium on Cloud Computing, Aug. 2015, pp.329–341. DOI: 10.1145/2806777.2806851.
Crossref
[9]

Domanal S G, Reddy G R M. An efficient cost optimized scheduling for spot instances in heterogeneous cloud environment. Future Generation Computer Systems, 2018, 84: 11–21. DOI: 10.1016/j.future.2018.02.003.

Crossref Google Scholar
[10]

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: 348–367. DOI: 10.1016/j.future.2019.01.025.

Crossref Google Scholar
[11]
Ben-Yehuda O A, Ben-Yehuda M, Schuster A, Tsafrir D. Deconstructing Amazon EC2 spot instance pricing. In Proc. the 3rd IEEE International Conference on Cloud Computing Technology and Science, Nov. 29–Dec. 1, 2011, pp.304–311. DOI: 10.1109/CloudCom.2011.48.
Crossref
[12]
Wallace R M, Turchenko V, Sheikhalishahi M, Turchenko I, Shults V, Vazquez-Poletti J L, Grandinetti L. Applications of neural-based spot market prediction for cloud computing. In Proc. the 7th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems, Sept. 2013, pp.710–716. DOI: 10.1109/IDAACS.2013.6663017.
Crossref
[13]
Gong Y F, He B S, Zhou A C. Monetary cost optimizations for MPI-based HPC applications on Amazon clouds: Checkpoints and replicated execution. In Proc. the 2015 International Conference for High Performance Computing, Networking, Storage and Analysis, Nov. 2015, Article No. 32. DOI: 10.1145/2807591.2807612.
Crossref
[14]
Song Y, Zafer M, Lee K W. Optimal bidding in spot instance market. In Proc. the 2012 IEEE INFOCOM, Mar. 2012, pp.190–198. DOI: 10.1109/INFCOM.2012.6195567.
Crossref
[15]

Dubois D J, Casale G. OptiSpot: Minimizing application deployment cost using spot cloud resources. Cluster Computing, 2016, 19(2): 893–909. DOI: 10.1007/s10586-016-0568-7.

Crossref Google Scholar
[16]

Fleischer R. On the Bahncard problem. Theoretical Computer Science, 2001, 268(1): 161–174. DOI: 10.1016/S0304- 3975(00)00266-8.

Crossref Google Scholar
[17]
Yang S S, Pan L, Wang Q Y, Liu S J. To sell or not to sell: Trading your reserved instances in Amazon EC2 marketplace. In Proc. the 38th IEEE International Conference on Distributed Computing Systems, Jul. 2018, pp.939–948. DOI: 10.1109/ICDCS.2018.00095.
Crossref
[18]
Zhang S, Yuan D, Pan L, Liu S J, Cui L Z, Meng X X. Selling reserved instances through pay-as-you-go model in cloud computing. In Proc. the 2017 IEEE International Conference on Web Services, Jun. 2017, pp.130–137. DOI: 10.1109/ICWS.2017.25.
Crossref
[19]

Wang W, Liang B, Li B C. Optimal online multi-instance acquisition in IaaS clouds. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(12): 3407–3419. DOI: 10.1109/TPDS.2014.2385697.

Crossref Google Scholar
[20]
Wang C, Liang Q L, Urgaonkar B. An empirical analysis of Amazon EC2 spot instance features affecting cost-effective resource procurement. In Proc. the 8th ACM/SPEC on International Conference on Performance Engineering, Apr. 2017, pp.63–74. DOI: 10.1145/3030207.3030210.
Crossref
[21]
Nicolae B, Cappello F. BlobCR: Efficient checkpoint-restart for HPC applications on IaaS clouds using virtual disk image snapshots. In Proc. the 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, Nov. 2011, Article No. 34. DOI: 10.1145/2063384.2063429.
Crossref
[22]

Hochreiter S, Schmidhuber J. Long short-term memory. Neural Computation, 1997, 9(8): 1735–1780. DOI: 10.1162/ neco.1997.9.8.1735.

Crossref Google Scholar
[23]
Borodin A, El-Yaniv R. Online Computation and Competitive Analysis. Cambridge University Press, 2005.
Journal of Computer Science and Technology
Volume 39 Issue 1,
January 2024
Pages 103-115
DOI: 10.1007/s11390-023-1535-4
Cite this article:
Xu Z-W, Pan L, Liu S-J. An Online Algorithm Based on Replication for Using Spot Instances in IaaS Clouds. Journal of Computer Science and Technology, 2024, 39(1): 103-115. https://doi.org/10.1007/s11390-023-1535-4
Metrics & Citations  
Article History
Copyright
Return