abstract

Online Virtual Machine Allocation with Lifetime and Load Predictions

Authors:

Joseph (Seffi) NaorAuthors Info & Claims

SIGMETRICS '21: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

Pages 9 - 10

https://doi.org/10.1145/3410220.3456278

Published: 06 June 2021 Publication History

Get Access

Abstract

The cloud computing industry has grown rapidly over the last decade, and with this growth there is a significant increase in demand for compute resources. Demand is manifested in the form of Virtual Machine (VM) requests, which need to be assigned to physical machines in a way that minimizes resource fragmentation and efficiently utilizes the available machines. This problem can be modeled as a dynamic version of the bin packing problem with the objective of minimizing the total usage time of the bins (physical machines). Motivated by advances in Machine Learning that provide good estimates of workload characteristics, this paper studies the effect of having extra information about future (total) demand. We show that the competitive factor can be dramatically improved with this additional information; in some cases, we achieve constant competitiveness, or even a competitive factor that approaches 1. Along the way, we design new offline algorithms with improved approximation ratios for the dynamic bin-packing problem.

Supplementary Material

MP4 File (SIGMETRICS21-sigmet276.mp4)

Presentation video - Online Virtual Machine Allocation with Lifetime and Load Predictions

Download
184.18 MB

References

[1]

Mansoor Alicherry and Randeep Bhatia. 2003. Line system design and a generalized coloring problem. In European Symposium on Algorithms. Springer, 19--30.

Crossref

Google Scholar

[2]

Yossi Azar and Danny Vainstein. 2019. Tight Bounds for Clairvoyant Dynamic Bin Packing. ACM Trans. Parallel Comput., Vol. 6, 3 (2019), 15:1--15:21.

Digital Library

Google Scholar

[3]

Eli Cortez, Anand Bonde, Alexandre Muzio, Mark Russinovich, Marcus Fontoura, and Ricardo Bianchini. 2017. Resource central: Understanding and predicting workloads for improved resource management in large cloud platforms. In Proceedings of the 26th Symposium on Operating Systems Principles. 153--167.

Digital Library

Google Scholar

[4]

Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Hadas Shachnai, Mordechai Shalom, Tami Tamir, and Shmuel Zaks. 2010. Minimizing total busy time in parallel scheduling with application to optical networks. Theoretical Computer Science, Vol. 411, 40--42 (2010), 3553--3562.

Digital Library

Google Scholar

[5]

David S Johnson. 1973. Near-optimal bin packing algorithms. Ph.D. Dissertation. Massachusetts Institute of Technology.

Google Scholar

[6]

Vijay Kumar and Atri Rudra. 2005. Approximation Algorithms for Wavelength Assignment. In FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 25th International Conf., Proceedings (Lecture Notes in Computer Sc., Vol. 3821), Ramaswamy Ramanujam and Sandeep Sen (Eds.). Springer, 152--163.

Google Scholar

[7]

Chan C Lee and Der-Tsai Lee. 1985. A simple on-line bin-packing algorithm. Journal of the ACM (JACM), Vol. 32, 3 (1985), 562--572.

Digital Library

Google Scholar

[8]

Yusen Li, Xueyan Tang, and Wentong Cai. 2014. On dynamic bin packing for resource allocation in the cloud. In 26th ACM SPAA, 2014 . 2--11.

Digital Library

Google Scholar

[9]

Runtian Ren and Xueyan Tang. 2016. Clairvoyant Dynamic Bin Packing for Job Scheduling with Minimum Server Usage Time. In 28th ACM SPAA, 2016. 227--237.

Digital Library

Google Scholar

Cited By

View all

Liu MTang X(2024)Tight Bounds for Dynamic Bin Packing with PredictionsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/37004378:3(1-28)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1145/3700437
Mellou KMolinaro MZhou R(2024)The Power of Migrations in Dynamic Bin PackingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/37004358:3(1-28)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1145/3700435
Chugh TKandula SKrishnamurthy AMahajan RMenache I(2023)Anticipatory Resource Allocation for ML TrainingProceedings of the 2023 ACM Symposium on Cloud Computing10.1145/3620678.3624669(410-426)Online publication date: 30-Oct-2023
https://dl.acm.org/doi/10.1145/3620678.3624669
Show More Cited By

Index Terms

Online Virtual Machine Allocation with Lifetime and Load Predictions
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms

Recommendations

Online Virtual Machine Allocation with Lifetime and Load Predictions
SIGMETRICS '21

The cloud computing industry has grown rapidly over the last decade, and with this growth there is a significant increase in demand for compute resources. Demand is manifested in the form of Virtual Machine (VM) requests, which need to be assigned to ...
On dynamic bin packing for resource allocation in the cloud
SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures

Dynamic Bin Packing (DBP) is a variant of classical bin packing, which assumes that items may arrive and depart at arbitrary times. Existing works on DBP generally aim to minimize the maximum number of bins ever used in the packing. In this paper, we ...
Dynamic Bin Packing with Predictions
SIGMETRICS '23

The MinUsageTime Dynamic Bin Packing (DBP) problem aims to minimize the accumulated bin usage time for packing a sequence of items into bins. It is often used to model job dispatching for optimizing the busy time of servers, where the items and bins ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGMETRICS '21: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

May 2021

97 pages

ISBN:9781450380720

DOI:10.1145/3410220

General Chair:
Longbo Huang
Tsinghua University, China
,
Program Chairs:
Anshul Gandhi
Stony Brook University, USA
,
Negar Kiyavash
EPFL, Switzerland
,
Jia Wang
AT&T Labs Research, USA

ACM SIGMETRICS Performance Evaluation Review Volume 49, Issue 1
SIGMETRICS '21
June 2021
80 pages
ISSN:0163-5999
DOI:10.1145/3543516
Editor:
Nidhi Hegde
Borealis AI
Issue’s Table of Contents

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2021

Check for updates

Author Tags

Qualifiers

Abstract

Funding Sources

Conference

SIGMETRICS '21

Sponsor:

SIGMETRICS

SIGMETRICS '21: ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

June 14 - 18, 2021

Virtual Event, China

Acceptance Rates

Overall Acceptance Rate 459 of 2,691 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
430
Total Downloads

Downloads (Last 12 months)74
Downloads (Last 6 weeks)8

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liu MTang X(2024)Tight Bounds for Dynamic Bin Packing with PredictionsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/37004378:3(1-28)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1145/3700437
Mellou KMolinaro MZhou R(2024)The Power of Migrations in Dynamic Bin PackingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/37004358:3(1-28)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1145/3700435
Chugh TKandula SKrishnamurthy AMahajan RMenache I(2023)Anticipatory Resource Allocation for ML TrainingProceedings of the 2023 ACM Symposium on Cloud Computing10.1145/3620678.3624669(410-426)Online publication date: 30-Oct-2023
https://dl.acm.org/doi/10.1145/3620678.3624669
Liu MTang X(2022)Dynamic Bin Packing with PredictionsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35706056:3(1-24)Online publication date: 8-Dec-2022
https://dl.acm.org/doi/10.1145/3570605
Liu MTang X(2022)Busy-Time Scheduling on Heterogeneous Machines: Algorithms and AnalysisIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.317666533:12(3942-3958)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1109/TPDS.2022.3176665
Przybylski BZuk PRzadca K(2022)Divide (CPU Load) and Conquer: Semi-Flexible Cloud Resource Allocation2022 22nd IEEE International Symposium on Cluster, Cloud and Internet Computing (CCGrid)10.1109/CCGrid54584.2022.00022(129-139)Online publication date: May-2022
https://doi.org/10.1109/CCGrid54584.2022.00022
Cho YKo Y(2022)Power- and QoS-Aware Job Assignment With Dynamic Speed Scaling for Cloud Data Center ComputingIEEE Access10.1109/ACCESS.2022.316556610(38284-38298)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3165566
Booba BJoshphin Jasaline Anitha XMohan CS J(2024)Hybrid approach for virtual machine allocation in cloud computingSustainable Computing: Informatics and Systems10.1016/j.suscom.2023.10092241(100922)Online publication date: Jan-2024
https://doi.org/10.1016/j.suscom.2023.100922
Parvez MParikh PAqlan FNoor-e-Alam M(2024)An online dynamic dual bin packing with lookahead approach for server-to-cell assignment in computer server industryComputers & Industrial Engineering10.1016/j.cie.2024.110404(110404)Online publication date: Jul-2024
https://doi.org/10.1016/j.cie.2024.110404
Mazied ENikolopoulos DHanafy YMidkiff S(2023)Auto-scaling edge cloud for network slicingFrontiers in High Performance Computing10.3389/fhpcp.2023.11671621Online publication date: 9-Jun-2023
https://doi.org/10.3389/fhpcp.2023.1167162

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Online Virtual Machine Allocation with Lifetime and Load Predictions

On dynamic bin packing for resource allocation in the cloud

Dynamic Bin Packing with Predictions