research-article

On the online fault-tolerant server consolidation problem

Authors:

Khuzaima Daudjee,

Shahin Kamali,

Alejandro López-OrtizAuthors Info & Claims

SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures

Pages 12 - 21

https://doi.org/10.1145/2612669.2612686

Published: 21 June 2014 Publication History

Get Access

Abstract

In the server consolidation problem, the goal is to minimize the number of servers needed to host a set of clients. The clients appear in an online manner and each of them has a certain load. The servers have uniform capacity and the total load of clients assigned to a server must not exceed this capacity. Additionally, to have a fault-tolerant solution, the load of each client should be distributed between at least two different servers so that failure of one server avoids service interruption by migrating the load to the other servers hosting the respective second loads. In a simple setting, upon receiving a client, an online algorithm needs to select two servers and assign half of the load of the client to each server. We analyze the problem in the framework of competitive analysis. First, we provide upper and lower bounds for the competitive ratio of two well known heuristics which are introduced in the context of tenant placement in the cloud. In particular, we show their competitive ratios are no better than 2. We then present a new algorithm called Horizontal Harmonic and show that it has an improved competitive ratio which converges to 1.59. The simplicity of this algorithm makes it a good choice for use by cloud service providers. Finally, we prove a general lower bound that shows any online algorithm for the online fault-tolerant server consolidation problem has a competitive ratio of at least 1.42.

References

[1]

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

Digital Library

Google Scholar

[2]

E. G. Coffman, M. R. Garey, and D. S. Johnson. Approximation algorithms for bin packing: A survey. In D. Hochbaum, editor, Approximation algorithms for NP-hard Problems. PWS Publishing Co., 1997.

Digital Library

Google Scholar

[3]

E. G. Coffman Jr., J. Csirik, G. Galambos, S. Martello, and D. Vigo. Bin packing approximation algorithms: survey and classification. In P. M. Pardalos, D.-Z. Du, and R. L. Graham, editors, Handbook of Combinatorial Optimization, pages 455--531. Springer, 2013.

Google Scholar

[4]

CyrusOne executive report. Build vs. buy: Addressing capital constraints in the data center. 2013.

Google Scholar

[5]

A. J. Elmore, S. Das, A. Pucher, D. Agrawal, A. El Abbadi, and X. Yan. Characterizing tenant behavior for placement and crisis mitigation in multitenant dbmss. In ACM SIGMOD '13, pages 517--528, 2013.

Digital Library

Google Scholar

[6]

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the theory of of NP-Completeness. Freeman and Company, 1979.

Digital Library

Google Scholar

[7]

R. Gupta, S. K. Bose, S. Sundarrajan, M. Chebiyam, and A. Chakrabarti. A two stage heuristic algorithm for solving the server consolidation problem with item-item and bin-item incompatibility constraints. In IEEE SCC'98, pages 39--46, 2008.

Digital Library

Google Scholar

[8]

D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput., 3:256--278, 1974.

Digital Library

Google Scholar

[9]

C. C. Lee and D. T. Lee. A simple online bin packing algorithm. J. ACM, 32:562--572, 1985.

Digital Library

Google Scholar

[10]

J. Schaffner, T. Januschowski, M. Kercher, T. Kraska, H. Plattner, M. J. Franklin, and D. Jacobs. RTP: Robust tenant placement for elastic in-memory database clusters. In ACM SIGMOD '13, pages 773--784, 2013.

Digital Library

Google Scholar

[11]

S. S. Seiden. On the online bin packing problem. J. ACM, 49:640--671, 2002.

Digital Library

Google Scholar

[12]

D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28:202--208, 1985.

Digital Library

Google Scholar

[13]

B. Speitkamp and M. Bichler. A mathematical programming approach for server consolidation problems in virtualized data centers. IEEE T. Services Comput., 3(4):266--278, 2010.

Digital Library

Google Scholar

[14]

C. Subramanian, A. Vasan, and A. Sivasubramaniam. Reducing data center power with server consolidation: Approximation and evaluation. In HiPC '10, pages 1--10, 2010.

Crossref

Google Scholar

Cited By

View all

Li BWu BShen MPeng HLi WZhang HGan JTian ZXu G(2024)Algorithms for online fault tolerance server consolidationDigital Communications and Networks10.1016/j.dcan.2024.06.007Online publication date: Jun-2024
https://doi.org/10.1016/j.dcan.2024.06.007
Xia RDai HZheng JGu RWang XWang WChen G(2023)SAFE: Service Availability via Failure Elimination Through VNF ScalingIEEE/ACM Transactions on Networking10.1109/TNET.2022.323348831:5(2042-2057)Online publication date: Oct-2023
https://doi.org/10.1109/TNET.2022.3233488
Li BWu B(2023)Online Robust Bin Packing for Resource Allocation in Cloud Computing2023 26th International Conference on Computer Supported Cooperative Work in Design (CSCWD)10.1109/CSCWD57460.2023.10152004(1063-1068)Online publication date: 24-May-2023
https://doi.org/10.1109/CSCWD57460.2023.10152004
Show More Cited By

Index Terms

On the online fault-tolerant server consolidation problem
1. Theory of computation

Recommendations

On the Fault-Tolerant Online Bin Packing Problem
Algorithmic Aspects of Cloud Computing
Abstract
We study the fault-tolerant variant of the online bin packing problem. Similar to the classic online bin packing problem, an online sequence of items of various sizes should be packed into a minimum number of bins of uniform capacity. For ...
Online Bin Packing with Advice of Small Size

In this paper, we study the advice complexity of the online bin packing problem. In this well-studied setting, the online algorithm is supplemented with some additional information concerning the input. We improve upon both known upper and lower bounds ...
The online k-server problem with rejection

In this work we investigate the online k-server problem where each request has a penalty and it is allowed to reject the requests. The goal is to minimize the sum of the total distance moved by the servers and the total penalty of the rejected requests. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures

June 2014

356 pages

ISBN:9781450328210

DOI:10.1145/2612669

General Chair:
Guy Blelloch
Carnegie Mellon University, USA
,
Program Chair:
Peter Sanders
Karlsruhe Institute of Technology, Germany

Permission to make digital or hard copies of all or part 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 components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 June 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPAA '14

Sponsor:

SPAA '14: 26th ACM Symposium on Parallelism in Algorithms and Architectures

June 23 - 25, 2014

Prague, Czech Republic

Acceptance Rates

SPAA '14 Paper Acceptance Rate 30 of 122 submissions, 25%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
234
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Li BWu BShen MPeng HLi WZhang HGan JTian ZXu G(2024)Algorithms for online fault tolerance server consolidationDigital Communications and Networks10.1016/j.dcan.2024.06.007Online publication date: Jun-2024
https://doi.org/10.1016/j.dcan.2024.06.007
Xia RDai HZheng JGu RWang XWang WChen G(2023)SAFE: Service Availability via Failure Elimination Through VNF ScalingIEEE/ACM Transactions on Networking10.1109/TNET.2022.323348831:5(2042-2057)Online publication date: Oct-2023
https://doi.org/10.1109/TNET.2022.3233488
Li BWu B(2023)Online Robust Bin Packing for Resource Allocation in Cloud Computing2023 26th International Conference on Computer Supported Cooperative Work in Design (CSCWD)10.1109/CSCWD57460.2023.10152004(1063-1068)Online publication date: 24-May-2023
https://doi.org/10.1109/CSCWD57460.2023.10152004
Li BXu GWu BDong YPalesi MTumeo AGoumas GAlmudever C(2021)An efficient fault tolerant cloud market mechanism for profit maximizationProceedings of the 18th ACM International Conference on Computing Frontiers10.1145/3457388.3458669(169-177)Online publication date: 11-May-2021
https://dl.acm.org/doi/10.1145/3457388.3458669
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 BTang XWu B(2021)A Robust Algorithm for Multi-tenant Server ConsolidationWireless Algorithms, Systems, and Applications10.1007/978-3-030-86137-7_60(566-573)Online publication date: 9-Sep-2021
https://doi.org/10.1007/978-3-030-86137-7_60
Abdel Raouf AAbo‐alian ABadr N(2021) A predictive replication for multi‐tenant databases using deep learning Concurrency and Computation: Practice and Experience10.1002/cpe.622633:13Online publication date: 12-Feb-2021
https://doi.org/10.1002/cpe.6226
Xia RDai HZheng JGu RWang XChen G(2019)SAFEProceedings of the 48th International Conference on Parallel Processing10.1145/3337821.3337832(1-10)Online publication date: 5-Aug-2019
https://dl.acm.org/doi/10.1145/3337821.3337832
Hou WZhang RQi WLu KWang JGuo L(2018)A Provident Resource Defragmentation Framework for Mobile Cloud ComputingIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2015.24777786:1(32-44)Online publication date: Jan-2018
https://doi.org/10.1109/TETC.2015.2477778
Berndt SJansen KKlein K(2018)Fully dynamic bin packing revisitedMathematical Programming10.1007/s10107-018-1325-xOnline publication date: 1-Sep-2018
https://doi.org/10.1007/s10107-018-1325-x
Show More Cited By

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

On the Fault-Tolerant Online Bin Packing Problem

Online Bin Packing with Advice of Small Size

The online k-server problem with rejection