research-article

Engineering resource management middleware for optimizing the performance of clouds processing mapreduce jobs with deadlines

Authors:

Shikharesh Majumdar,

Peter Ashwood-SmithAuthors Info & Claims

ICPE '14: Proceedings of the 5th ACM/SPEC international conference on Performance engineering

Pages 161 - 172

https://doi.org/10.1145/2568088.2576796

Published: 22 March 2014 Publication History

Abstract

This paper focuses on devising efficient resource management techniques used by the resource management middleware in clouds that handle MapReduce jobs with end-to-end service level agreements (SLAs) comprising an earliest start time, execution time, and a deadline. This research and development work, performed in collaboration with our industrial partner, presents the formulation of the matchmaking and scheduling problem for MapReduce jobs as an optimization problem using: Mixed Integer Linear Programming (MILP) and Constraint Programming (CP) techniques. In addition to the formulations devised, our experience in implementing the MILP and CP models using various open source as well as commercial software packages is described. Furthermore, a performance evaluation of the different approaches used to implement the formulations is conducted using a variety of different workloads.

References

[1]

Buyya, R., Yeo, C.S., Venugopal, S., Broberg, J., and Brandic, I. 2009. Cloud computing and emerging IT platforms: Vision, hype, and reality for delivering computing as the 5th utility. Future Generation Computer Systems. 25, 6 (June 2009), 599--616.

Digital Library

[2]

Heinz, S., and Beck, J.C. 2011. Solving resource allocation/scheduling problems with constraint integer programming. In Proc. of Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems (COPLAS) (12--13 June 2011). 23--30.

[3]

Hooker, J.N. 2005. Planning and scheduling to minimize tardiness. In van Beek, P., ed., Principles and Practice of Constraint Programming. Vol. 3709 of LNCS (2005). 314--327.

[4]

Verma, A., Cherkasova, L., Kumar, V.S., and Campbell, R.H. 2012. Deadline-based workload management for MapReduce environments: Pieces of the performance puzzle. In Proc. of Network Operations and Management Symposium (NOMS) (16--20 April 2012). 900--905.

[5]

Dean, J. and Ghemawat, S. 2004. MapReduce: Simplified data processing on large clusters. International Symposium on Operating System Design and Implementation (December 2004). 137--150.

Digital Library

[6]

The Apache Software Foundation. Hadoop. Available: http://hadoop.apache.org.

[7]

Apache. Hadoop Wiki. Available: http://wiki.apache.org/hadoop/PoweredBy

[8]

Kc, K., and Anyanwu, K. 2010. Scheduling Hadoop Jobs to Meet Deadlines. In Proc. of International Conference on Cloud Computing Technology and Science (CloudCom) (Nov. 30 2010-Dec. 3 2010). 388--392.

Digital Library

[9]

Dong, X., Wang, Y., and Liao, H. 2011. Scheduling Mixed Real-Time and Non-real-Time Applications in MapReduce Environment. In Proc. of International Conference on Parallel and Distributed Systems (ICPADS) (7--9 Dec. 2011). 9--16.

Digital Library

[10]

Chang, H., Kodialam, M., Kompella, R.R., Lakshman, T.V. Lee, M., and Mukherjee, S. 2011. Scheduling in mapreduce-like systems for fast completion time. In Proc. of IEEE INFOCOM (10--15 April 2011). 3074--3082.

[11]

Bosch, R. and Trick, M. 2005. Integer programming. Search Methodologies. Springer US (2005). 69--95.

[12]

Chinneck, J.W. 2004. Chapter 13: Binary and Mixed-Integer Linear Programming. Practical Optimization: a Gentle Introduction (2004). Available: http://www.sce.carleton.ca/faculty/chinneck/po.html

[13]

Rossi, F., Beek, P., and Walsh, T. 2008. Chapter 4: Constraint Programming. Handbook of Knowledge Representation (2008). 181--211.

[14]

Lindo Systems Inc. Lindo Systems -- Optimization Software. Available: http://www.lindo.com/.

[15]

NICTA. MiniZinc and FlatZinc. Available: http://www.MiniZinc.org/.

[16]

Gecode. Generic Constraint Development Environment. Available: http://www.gecode.org/.

[17]

IBM. IBM ILOG CPLEX Optimization Studio. Available: http://www-03.ibm.com/software/products/us/en/ ibmilogcpleoptistud

[18]

Lustig, I. J., and Puget, J.-F. 2001. Program Does Not Equal Program: Constraint Programming and Its Relationship to Mathematical Programming. INTERFACES. 31, 6 (Nov.-Dec. 2001). 29--53.

Digital Library

[19]

Refalo, P. 2000. Linear formulation of constraint programming models and hybrid solvers. Principles and Practice of Constraint Programming-CP 2000. Springer Berlin Heidelberg (2000). 369--383.

Digital Library

[20]

Beldiceanu, N. and Demassey, S. Global Constraint Catalog. Available: http://www.emn.fr/z-info/sdemasse/gccatold/ Ccumulative.html.

[21]

Udupi, Y. and Dutta, D. Business Rules and Policies driven Constraints-based Smart Resource Placement in Openstack. White Paper. Cisco.

[22]

Van den Akker, J. M., Hurkens, C., and Savelsbergh, M. 2000. Time-indexed formulations for machine scheduling problems: Column generation. INFORMS Journal on Computing. 12.2 (2000). 111--124.

Digital Library

[23]

LINDO Systems Inc. 2011. LINGO 13.0: User's Guide.

[24]

Marriott, K., Stuckey, P.J., Koninck, L.D., and Samulowitz, H. 2012. An Introduction to MiniZinc Version 1.6.

[25]

IBM. 2009. IBM ILOG OPL Language Reference Manual. White Paper. IBM Corporation (2009).

[26]

IBM. 2010. Detailed Scheduling in IBM ILOG CPLEX Optimization Studio with IBM ILOG CPLEX CP Optimizer. White Paper. IBM Corporation (2010).

[27]

Dong, T. 2009. Efficient modeling with the IBM ILOG OPL-CPLEX Development Bundles. White Paper. IBM Corporation (December 2009).

Cited By

Alrefai TIndrusiak LPalesi MPalermo GGraves CArima E(2020)Management of container-based genetic algorithm workloads over cloud infrastructureProceedings of the 17th ACM International Conference on Computing Frontiers10.1145/3387902.3394031(229-232)Online publication date: 11-May-2020
https://dl.acm.org/doi/10.1145/3387902.3394031
Patil CPatwardhan M(2020)Visual Question GenerationACM Computing Surveys10.1145/338346553:3(1-22)Online publication date: 28-May-2020
https://dl.acm.org/doi/10.1145/3383465
Zeng XGarg SBarika MZomaya AWang LVillari MChen DRanjan R(2020)SLA Management for Big Data Analytical Applications in CloudsACM Computing Surveys10.1145/338346453:3(1-40)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3383464
Show More Cited By

Index Terms

Engineering resource management middleware for optimizing the performance of clouds processing mapreduce jobs with deadlines

Recommendations

A Constraint Programming Based Hadoop Scheduler for Handling MapReduce Jobs with Deadlines on Clouds
ICPE '15: Proceedings of the 6th ACM/SPEC International Conference on Performance Engineering

A novel MapReduce constraint programming based matchmaking and scheduling algorithm (MRCP) that can handle MapReduce jobs with deadlines and achieve high system performance is devised. The MRCP algorithm is incorporated into Hadoop, which is a widely ...
A Constraint Programming-Based Resource Management Technique for Processing MapReduce Jobs with SLAs on Clouds
BRACIS '14: Proceedings of the 2014 Brazilian Conference on Intelligent Systems

Clouds that are rapidly gaining in popularity require an effective resource manager that can harness the power of the underlying resource pool, and provide resources on demand to its users. This paper focuses on resource management on clouds for ...
A Constraint Programming Based Energy Aware Resource Management Middleware for Clouds Processing MapReduce Jobs with Deadlines
ICPE '16 Companion: Companion Publication for ACM/SPEC on International Conference on Performance Engineering

This paper concerns guarantees on system performance through Service Level Agreement (SLA) compliance and focuses on devising energy aware resource management techniques based on Dynamic Voltage and Frequency Scaling (DVFS) used by resource management ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ICPE '14: Proceedings of the 5th ACM/SPEC international conference on Performance engineering

March 2014

310 pages

ISBN:9781450327336

DOI:10.1145/2568088

General Chairs:
Klaus-Dieter Lange
Hewlett-Packard Company, USA
,
John Murphy
University College Dublin, Ireland
,
Program Chairs:
Walter Binder
University of Lugano, Switzerland
,
José Merseguer
Universidad de Zaragoza, Spain

Copyright © 2014 ACM.

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]

Sponsors

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation
SIGSOFT: ACM Special Interest Group on Software Engineering
SPEC: SPEC Research Group

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 March 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICPE'14

Sponsor:

ICPE'14: ACM/SPEC International Conference on Performance Engineering

March 22 - 26, 2014

Dublin, Ireland

Acceptance Rates

ICPE '14 Paper Acceptance Rate 21 of 78 submissions, 27%;

Overall Acceptance Rate 252 of 851 submissions, 30%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
231
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Alrefai TIndrusiak LPalesi MPalermo GGraves CArima E(2020)Management of container-based genetic algorithm workloads over cloud infrastructureProceedings of the 17th ACM International Conference on Computing Frontiers10.1145/3387902.3394031(229-232)Online publication date: 11-May-2020
https://dl.acm.org/doi/10.1145/3387902.3394031
Patil CPatwardhan M(2020)Visual Question GenerationACM Computing Surveys10.1145/338346553:3(1-22)Online publication date: 28-May-2020
https://dl.acm.org/doi/10.1145/3383465
Zeng XGarg SBarika MZomaya AWang LVillari MChen DRanjan R(2020)SLA Management for Big Data Analytical Applications in CloudsACM Computing Surveys10.1145/338346453:3(1-40)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3383464
Hashem IAnuar NMarjani MAhmed EChiroma HFirdaus AAbdullah MAlotaibi FAli WYaqoob IGani A(2018)MapReduce scheduling algorithms: a reviewThe Journal of Supercomputing10.1007/s11227-018-2719-5Online publication date: 10-Dec-2018
https://doi.org/10.1007/s11227-018-2719-5
Majumdar S(2018)Leveraging Cloud Computing and Sensor-Based Devices in the Operation and Management of Smart SystemsHandbook of Smart Cities10.1007/978-3-319-97271-8_3(55-80)Online publication date: 16-Nov-2018
https://doi.org/10.1007/978-3-319-97271-8_3
Biran YPasricha SCollins GDubow J(2017)Clean Energy Use for Cloud Computing Federation WorkloadsAdvances in Science, Technology and Engineering Systems Journal10.25046/aj0206012:6(1-12)Online publication date: Aug-2017
https://doi.org/10.25046/aj020601
Lim NMajumdar SAshwood-Smith P(2017)MRCP-RMIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.261732428:5(1375-1389)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1109/TPDS.2016.2617324
Yasmin SSritha S(2017)A constraint programming-based resource allocation and scheduling of map reduce jobs with service level agreement2017 International Conference on Energy, Communication, Data Analytics and Soft Computing (ICECDS)10.1109/ICECDS.2017.8390131(3589-3594)Online publication date: Aug-2017
https://doi.org/10.1109/ICECDS.2017.8390131
Gregory AMajumdar SAvritzer AIosup AZhu XBecker S(2016)A Constraint Programming Based Energy Aware Resource Management Middleware for Clouds Processing MapReduce Jobs with DeadlinesCompanion Publication for ACM/SPEC on International Conference on Performance Engineering10.1145/2859889.2859892(15-20)Online publication date: 12-Mar-2016
https://dl.acm.org/doi/10.1145/2859889.2859892
Biran YPasricha SCollins GDubow J(2016)Enabling green content distribution network by cloud orchestration2016 3rd Smart Cloud Networks & Systems (SCNS)10.1109/SCNS.2016.7870553(1-8)Online publication date: Dec-2016
https://doi.org/10.1109/SCNS.2016.7870553
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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten