We use cookies to improve your experience with our site.
Advanced Search
Volume 39 Issue 1
January  2024
Turn off MathJax
Article Contents
Abstract
Conflict of Interest
References
Related Articles
Supplements
Xu ZW, Pan L, Liu SJ. An online algorithm based on replication for using spot instances in IaaS clouds. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 39(1): 103−115 Jan. 2024. DOI: 10.1007/s11390-023-1535-4.
Citation: Xu ZW, Pan L, Liu SJ. An online algorithm based on replication for using spot instances in IaaS clouds. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 39(1): 103−115 Jan. 2024. DOI: 10.1007/s11390-023-1535-4.
shu

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

  • Zhi-Wei Xu (许志伟) Student Member, CCF, 
  • Li Pan,  (潘丽) Member, CCF, IEEE, 
  • Shi-Jun Liu (刘士军) Senior Member, CCF, IEEE

  • School of Software, Shandong University, Jinan 250101, China

Funds: This work was supported by the National Key Research and Development Program of China under Grant No. 2018YFB1404501.
More Information
  • Author Bio:

    Zhi-Wei Xu received his B.S. degree in software engineering from Qingdao University, Qingdao, in 2019. He is currently pursuing his M.S. degree in software engineering from the School of Software, Shandong University, Jinan. His research interests include cloud computing and service computing

    Li Pan received her Ph.D. degree in computer software and theory from Shandong University, Jinan, in 2011. She is currently a professor of the School of Software, Shandong University, Jinan. Her main research interests include service computing and cloud computing

    Shi-Jun Liu received his B.S. degree in oceanography from the Ocean University of China, Qingdao, and his M.S. and Ph.D. degrees in computer science from Shandong University, Jinan. He is currently a professor from Shandong University, Jinan. His current research interests include services computing, enterprise services computing, and services system for manufacturing

  • Corresponding author:

    panli@sdu.edu.cn

  • Received Date: April 22, 2021
  • Accepted Date: April 17, 2023
    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.

    • FullText(HTML)
    • References (23)
  • [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.
    [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.
    [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.
    [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.
    [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.
    [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.
    [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.
    [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.
    [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.
    [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.
    [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.
    [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.
    [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.
    [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.
    [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.
    [16]
    Fleischer R. On the Bahncard problem. Theoretical Computer Science, 2001, 268(1): 161–174. DOI: 10.1016/S0304- 3975(00)00266-8.
    [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.
    [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.
    [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.
    [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.
    [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.
    [22]
    Hochreiter S, Schmidhuber J. Long short-term memory. Neural Computation, 1997, 9(8): 1735–1780. DOI: 10.1162/ neco.1997.9.8.1735.
    [23]
    Borodin A, El-Yaniv R. Online Computation and Competitive Analysis. Cambridge University Press, 2005.
    • Relative Articles

  • Related Articles

    [1]Mansoor Davoodi, Esmaeil Delfaraz, Sajjad Ghobadi, Mahtab Masoori. Algorithms for Handoff Minimization in Wireless Networks[J]. Journal of Computer Science and Technology, 2019, 34(4): 887-900. DOI: 10.1007/s11390-019-1948-2
    [2]Chao Shao, Lin-Mei Hu, Juan-Zi Li, Zhi-Chun Wang, Tonglee Chung, Jun-Bo Xia. RiMOM-IM:A Novel Iterative Framework for Instance Matching[J]. Journal of Computer Science and Technology, 2016, 31(1): 185-197. DOI: 10.1007/s11390-016-1620-z
    [3]Cheng-Liang Tian, Wei Wei, Dong-Dai Lin. Solving Closest Vector Instances Using an Approximate Shortest Independent Vectors Oracle[J]. Journal of Computer Science and Technology, 2015, 30(6): 1370-1377. DOI: 10.1007/s11390-015-1604-4
    [4]Duksan Ryu, Jong-In Jang, Jongmoon Baik. A Hybrid Instance Selection Using Nearest-Neighbor for Cross-Project Defect Prediction[J]. Journal of Computer Science and Technology, 2015, 30(5): 969-980. DOI: 10.1007/s11390-015-1575-5
    [5]Chun-Lin Xin, Wei-Min Ma, Lei Yang. Competitive Analysis of Two Special Online Device Replacement Problems[J]. Journal of Computer Science and Technology, 2008, 23(2): 203-213.
    [6]Yi-Wei Jiang, Yong He. Semi-Online Algorithms for Scheduling with Machine Cost[J]. Journal of Computer Science and Technology, 2006, 21(6): 984-988.
    [7]HAO Jie, LI Xing. Word Spotting Based on a posterior Measure of Keyword Confidence[J]. Journal of Computer Science and Technology, 2002, 17(4).
    [8]SUI Yuefei. Two Online Algorithms for the Ambulance Systems[J]. Journal of Computer Science and Technology, 2001, 16(2).
    [9]WU Jigang, JI Yongchang, CHEN Guoliang. An Optimal Online Algorithm for Half Plane Intersection[J]. Journal of Computer Science and Technology, 2000, 15(3): 295-299.
    [10]Tai Juwei, Wang Jue, Chen Xin. A Syntactic-Semantic Approach for Pattern Recognition and Knowledge Representation[J]. Journal of Computer Science and Technology, 1988, 3(3): 161-172.
    • Supplements (3)

  • Others

Catalog

    Get Citation
    PDF
    XML
    Read Online
    Article views (233) PDF downloads (46) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return