Entropy: a consolidation manager for clusters

ABSTRACT

Clusters provide powerful computing environments, but in practice much of this power goes to waste, due to the static allocation of tasks to nodes, regardless of their changing computational requirements. Dynamic consolidation is an approach that migrates tasks within a cluster as their computational requirements change, both to reduce the number of nodes that need to be active and to eliminate temporary overload situations. Previous dynamic consolidation strategies have relied on task placement heuristics that use only local optimization and typically do not take migration overhead into account. However, heuristics based on only local optimization may miss the globally optimal solution, resulting in unnecessary resource usage, and the overhead for migration may nullify the benefits of consolidation.

In this paper, we propose the Entropy resource manager for homogeneous clusters, which performs dynamic consolidation based on constraint programming and takes migration overhead into account. The use of constraint programming allows Entropy to find mappings of tasks to nodes that are better than those found by heuristics based on local optimizations, and that are frequently globally optimal in the number of nodes. Because migration overhead is taken into account, Entropy chooses migrations that can be implemented efficiently, incurring a low performance overhead.

REFERENCES

• 1: Paul Barham , Boris Dragovic , Keir Fraser , Steven Hand , Tim Harris , Alex Ho , Rolf Neugebauer , Ian Pratt , Andrew Warfield, Xen and the art of virtualization, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 2: F. Benhamou, N. Jussien, and B. O'Sullivan, editors. Trends in Constraint Programming. ISTE, London, UK, May 2007.
• 3: N. Bobroff, A. Kochut, and K. Beaty. Dynamic placement of virtual machines for managing SLA violations. Integrated Network Management, 2007. IM '07. 10th IFIP/IEEE International Symposium on, pages 119--128, May 2007.
• 4: Raphaël Bolze , Franck Cappello , Eddy Caron , Michel Daydé , Frédéric Desprez , Emmanuel Jeannot , Yvon Jégou , Stephane Lanteri , Julien Leduc , Noredine Melab , Guillaume Mornet , Raymond Namyst , Pascale Primet , Benjamin Quetier , Olivier Richard , El-Ghazali Talbi , Iréa Touche, Grid'5000: A Large Scale And Highly Reconfigurable Experimental Grid Testbed, International Journal of High Performance Computing Applications, v.20 n.4, p.481-494, November 2006 [doi>10.1177/1094342006070078]
• 5: Christopher Clark , Keir Fraser , Steven Hand , Jacob Gorm Hansen , Eric Jul , Christian Limpach , Ian Pratt , Andrew Warfield, Live migration of virtual machines, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.273-286, May 02-04, 2005
• 6: E. G. Coffman, Jr. , M. R. Garey , D. S. Johnson, Approximation algorithms for bin packing: a survey, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 7: Olivier Delannoy , FranceNahid Emad , Serge Petiton, Workflow Global Computing with YML, Proceedings of the 7th IEEE/ACM International Conference on Grid Computing, p.25-32, September 28-29, 2006 [doi>10.1109/ICGRID.2006.310994]
• 8: Michael Frumkin , Rob F. Van der Wijngaart, NAS Grid Benchmarks: A Tool for Grid Space Exploration, Cluster Computing, v.5 n.3, p.247-255, July 2002 [doi>10.1023/A:1015669003494]
• 9: Laura Grit , David Irwin , Aydan Yumerefendi , Jeff Chase, Virtual Machine Hosting for Networked Clusters: Building the Foundations for "Autonomic" Orchestration, Proceedings of the 2nd International Workshop on Virtualization Technology in Distributed Computing, p.7, November 17-17, 2006 [doi>10.1109/VTDC.2006.17]
• 10: R. Haralick and G. Elliott. Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14(3):263--313, October 1980.
• 11: David Irwin , Jeffrey Chase , Laura Grit , Aydan Yumerefendi , David Becker , Kenneth G. Yocum, Sharing networked resources with brokered leases, Proceedings of the annual conference on USENIX '06 Annual Technical Conference, p.18-18, May 30-June 03, 2006, Boston, MA
• 12: N. Jussien, G. Rochart, and X. Lorca. The CHOCO constraint programming solver. In CPAIOR'08 workshop on Open-Source Software for Integer and Contraint Programming (OSSICP'08), Paris, France, June 2008.
• 13: G. Khanna, K. Beaty, G. Kar, and A. Kochut. Application performance management in virtualized server environments. Network Operations and Management Symposium, 2006. NOMS 2006. 10th IEEE/IFIP, pages 373--381, 2006.
• 14: Ripal Nathuji , Karsten Schwan, VirtualPower: coordinated power management in virtualized enterprise systems, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 15: Ripal Nathuji , Karsten Schwan, Vpm tokens: virtual machine-aware power budgeting in datacenters, Proceedings of the 17th international symposium on High performance distributed computing, June 23-27, 2008, Boston, MA, USA [doi>10.1145/1383422.1383438]
• 16: Francesca Rossi , Peter van Beek , Toby Walsh, Handbook of Constraint Programming (Foundations of Artificial Intelligence), Elsevier Science Inc., New York, NY, 2006
• 17: Paul Ruth , Xuxian Jiang , Dongyan Xu , Sebastien Goasguen, Virtual Distributed Environments in a Shared Infrastructure, Computer, v.38 n.5, p.63-69, May 2005 [doi>10.1109/MC.2005.175]
• 18: P. Ruth , Junghwan Rhee , Dongyan Xu , R. Kennell , S. Goasguen, Autonomic Live Adaptation of Virtual Computational Environments in a Multi-Domain Infrastructure, Proceedings of the 2006 IEEE International Conference on Autonomic Computing, p.5-14, June 12-16, 2006 [doi>10.1109/ICAC.2006.1662376]
• 19: P. Shaw. A constraint for bin packing. In Principles and Practice of Constraint Programming (CP'04), volume 3258 of Lecture Notes in Computer Science, pages 648--662. Springer, 2004.
• 20: M. Trick. A dynamic programming approach for consistency and propagation for knapsack constraints. In Proceedings of the Third International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR-01), pages 113--124, 2001.
• 21: A. Verma, P. Ahuja, and A. Neogi. pmapper: Power and migration cost aware application placement in virtualized systems. Technical report, IBM, 2008.
• 22: Akshat Verma , Puneet Ahuja , Anindya Neogi, Power-aware dynamic placement of HPC applications, Proceedings of the 22nd annual international conference on Supercomputing, June 07-12, 2008, Island of Kos, Greece [doi>10.1145/1375527.1375555]
• 23: T. Wood, P. J. Shenoy, A. Venkataramani, and M. S. Yousif. Black-box and gray-box strategies for virtual machine migration. In Proceedings of the 4th ACM/USENIX Symposium on Networked Systems Design and Implementation (NSDI '07), 2007.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Algorithms, Design

Keywords:
cluster, dynamic consolidation, migration, reconfiguration, virtualization