abstract

Brief Announcement: Towards Fault-Tolerant Bin Packing for Online Cloud Resource Allocation

Authors:

Chuanyou Li,

Xueyan TangAuthors Info & Claims

SPAA '17: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures

Pages 231 - 233

https://doi.org/10.1145/3087556.3087596

Published: 24 July 2017 Publication History

Get Access

Abstract

We consider an online fault-tolerant bin packing problem that models the reliable resource allocation in cloud-based systems. In this problem, any feasible packing algorithm must satisfy an exclusion constraint and a space constraint. The exclusion constraint is generalized from the fault-tolerance requirement and the space constraint comes from the capacity planning. The target of bin packing is to minimize the number of bins used. We first derive a lower bound on the number of bins needed by any feasible packing algorithm. Then we study two heuristic algorithms mirroring and shifting. The mirroring algorithm has a low utilization of the bin capacity. Compared with the mirroring algorithm, the shifting algorithm requires fewer numbers of bins. However, in online packing, the process of opening bins by the shifting algorithm is not smooth. It turns out that even for packing a few items, the shifting algorithm needs to quickly open a large number of bins. We therefore propose a new heuristic algorithm named mixing which can gradually open new bins for incoming items. We prove that the mixing algorithm is feasible and show that it balances the number of bins used and the process of opening bins.

References

[1]

J. Balogh, J. Békési, and G. Galambos. 2012. New lower bounds for certain classes of bin packing algorithms. Theor. Comput. Sci. 440--441 (2012), 1--13.

Google Scholar

[2]

O. Beaumont, L. Eyraud-Dubois, and H. Larchevêque. 2013. An Availability-on-Demand Mechanism for Datacenters. In Proc. of the 27th IEEE International Symposium on Parallel and Distributed Processing (IPDPS). 55--66.

Google Scholar

[3]

E. G. Coffman, J. Csirik, G. Galambos, S. Martello, and D. Vigo. 2013. Bin packing approximation algorithms: Survey and classification. Handbook of Combinatorial Optimization (second edition) (2013), 455--531.

Google Scholar

[4]

K. Daudjee, S. Kamali, and A. Lopez-Ortiz. 2014. On the online fault-tolerant server consolidation problem. In Proc. of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 12--21.

Digital Library

Google Scholar

[5]

G. Galambos and G. J. Woeginger. 1995. On-line bin packing - A restricted survey. Math. Meth. of OR 42, 1 (1995), 25--45.

Crossref

Google Scholar

[6]

M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. x0--7167--1044--7

Google Scholar

[7]

M. R. Korupolu and R. Rajaraman. 2016. Robust and Probabilistic Failure-Aware Placement. In Proc. of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 213--224.

Digital Library

Google Scholar

[8]

L. Lamport. 1998. The Part-Time Parliament. ACM Trans. Comput. Syst. 16, 2 (1998), 133--169.

Digital Library

Google Scholar

[9]

Y. Li, X. Tang, and W. Cai. 2014. On dynamic bin packing for resource allocation in the cloud. In Proc. of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 2--11.

Digital Library

Google Scholar

[10]

R. Ren and X. Tang. 2016. Clairvoyant Dynamic Bin Packing for Job Scheduling with Minimum Server Usage Time. In Proc. of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 227--237.

Digital Library

Google Scholar

[11]

J. Schaffner, T. Januschowski, M. Kercher, T. Kraska, H. Plattner, M. J. Franklin, and D. Jacobs. 2013. RTP: Robust tenant placement for elastic in-momory database clusters. In Proc. of the ACM International Conference on Management of Data (SIGMOD). 773--784.

Digital Library

Google Scholar

[12]

S. S. Seiden. 2002. On the online bin packing problem. Journal of the ACM 49, 5 (2002), 640--671.

Digital Library

Google Scholar

[13]

S. Shen, A. Iosup, A. Israel, W. Cirne, D. Raz, and D. H. J. Epema. 2015. An Availability-on-Demand Mechanism for Datacenters. In Proc. of the 15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid). 495--504.

Digital Library

Google Scholar

[14]

H. Yanagisawa, T. Osogami, and R. Raymond. 2013. Dependable virtual machine allocation. In Proc. of the 32nd Annual IEEE International Conference on Computer Communications (INFOCOM). 629--637.

Crossref

Google Scholar

Cited By

View all

Kamali SNikbakht P(2021)On the Fault-Tolerant Online Bin Packing ProblemAlgorithmic Aspects of Cloud Computing10.1007/978-3-030-93043-1_1(1-17)Online publication date: 10-Dec-2021
https://doi.org/10.1007/978-3-030-93043-1_1
Li CTang X(2020)On Fault-Tolerant Bin Packing for Online Resource AllocationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2019.294832731:4(817-829)Online publication date: 1-Apr-2020
https://doi.org/10.1109/TPDS.2019.2948327

Index Terms

Brief Announcement: Towards Fault-Tolerant Bin Packing for Online Cloud Resource Allocation
1. Hardware
  1. Robustness
    1. Fault tolerance
      1. Redundancy
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms

Recommendations

Online bin packing problem with buffer and bounded size revisited

In this paper we study the online bin packing with buffer and bounded size, i.e., there are items with size within $$(\alpha ,1/2]$$(ź,1/2] where $$0 \le \alpha < 1/2 $$0≤ź<1/2, and there is a buffer with constant size. Each time when a new item is given,...
Resource augmentation for online bounded space bin packing

We study online bounded space bin packing in the resource augmentation model of competitive analysis. In this model, the online bounded space packing algorithm has to pack a list L of items in (0, 1] into a small number of bins of size b ≥ 1. Its ...
Online bin packing with arbitrary release times

We study a new variant of the online bin-packing problem, in which each item a"i is associated with a size a"i and also a release time r"i so that it must be placed at least r"i above the bottom of a bin. Items arrive in turn and must be assigned ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '17: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures

July 2017

392 pages

ISBN:9781450345934

DOI:10.1145/3087556

General Chair:
Christian Scheideler
Paderborn University, Germany
,
Program Chair:
Mohammad Hajiaghayi
University of Maryland at College Park, USA

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: 24 July 2017

Check for updates

Author Tags

Qualifiers

Abstract

Funding Sources

This work is supported by Singapore Ministry of Education Academic Research Fund

Conference

SPAA '17

Sponsor:

SPAA '17: 29th ACM Symposium on Parallelism in Algorithms and Architectures

July 24 - 26, 2017

DC, Washington, USA

Acceptance Rates

SPAA '17 Paper Acceptance Rate 31 of 127 submissions, 24%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
146
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kamali SNikbakht P(2021)On the Fault-Tolerant Online Bin Packing ProblemAlgorithmic Aspects of Cloud Computing10.1007/978-3-030-93043-1_1(1-17)Online publication date: 10-Dec-2021
https://doi.org/10.1007/978-3-030-93043-1_1
Li CTang X(2020)On Fault-Tolerant Bin Packing for Online Resource AllocationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2019.294832731:4(817-829)Online publication date: 1-Apr-2020
https://doi.org/10.1109/TPDS.2019.2948327

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 bin packing problem with buffer and bounded size revisited

Resource augmentation for online bounded space bin packing

Online bin packing with arbitrary release times