A scalable application placement controller for enterprise data centers

ABSTRACT

Given a set of machines and a set of Web applications with dynamically changing demands, an online application placement controller decides how many instances to run for each application and where to put them, while observing all kinds of resource constraints. This NP hard problem has real usage in commercial middleware products. Existing approximation algorithms for this problem can scale to at most a few hundred machines, and may produce placement solutions that are far from optimal when system resources are tight. In this paper, we propose a new algorithm that can produce within 30seconds high-quality solutions for hard placement problems with thousands of machines and thousands of applications. This scalability is crucial for dynamic resource provisioning in large-scale enterprise data centers. Our algorithm allows multiple applications to share a single machine, and strivesto maximize the total satisfied application demand, to minimize the number of application starts and stops, and to balance the load across machines. Compared with existing state-of-the-art algorithms, for systems with 100 machines or less, our algorithm is up to 134 times faster, reduces application starts and stops by up to 97%, and produces placement solutions that satisfy up to 25% more application demands. Our algorithm has been implemented and adopted in a leading commercial middleware product for managing the performance of Web applications.

REFERENCES

• 1: WebSphere Extended Deployment, http://www-306.ibm.com/software/webservers/appserv/extend/.
• 2: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 3: K. Appleby, S. Fakhouri, L. Fong, G. Goldszmidt, M. Kalantar, S. Krishnakumar, D. Pazel, J. Pershing, and B. Rochwerger. Oceano SLA based management of a computing utility. In Proceedings of the International Symposium on Integrated Network Management, pages 1418, Seattle, WA, May 2001.
• 4: Armando Fox , Steven D. Gribble , Yatin Chawathe , Eric A. Brewer , Paul Gauthier, Cluster-based scalable network services, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.78-91, October 05-08, 1997, Saint Malo, France
• 5: Galen C. Hunt , Michael L. Scott, The Coign automatic distributed partitioning system, Proceedings of the third symposium on Operating systems design and implementation, p.187-200, February 1999, New Orleans, Louisiana, United States
• 6: A. Karve , T. Kimbrel , G. Pacifici , M. Spreitzer , M. Steinder , M. Sviridenko , A. Tantawi, Dynamic placement for clustered web applications, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135865]
• 7: H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. SpringerVerlag, 2004.
• 8: T. Kimbrel, M. Steinder, M. Sviridenko, and A. N. Tantawi. Dynamic Application Placement Under Service and Memory Constraints. In International Workshop on E.cient and Experimental Algorithms, 2005.
• 9: R. Levy, J. Nagarajarao, G. Paci.ci, M. Spreitzer, A. N. Tantawi, and A. Youssef. Performance management for cluster based web services. In Proceedings of the International Symposium on Integrated Network Management, 2003.
• 10: G. Pacifici, W. Segmuller, M. Spreitzer, M. Steinder, A. Tantawi, and A. Youssef. Managing the response time for multi-tiered web applications. Technical Report RC 23651, IBM, 2005.
• 11: Giovanni Pacifici , Wolfgang Segmuller , Mike Spreitzer , Asser Tantawi, Dynamic estimation of CPU demand of web traffic, Proceedings of the 1st international conference on Performance evaluation methodolgies and tools, October 11-13, 2006, Pisa, Italy [doi>10.1145/1190095.1190128]
• 12: H. Shachnai and T. Tamir. Noah's bagels -- some combinatorial aspects. In Proc. 1st Int. Conf. on Fun with Algorithms, 1998.
• 13: H. Shachnai and T. Tamir. On two class-constrained versions of the multiple knapsack problem. Algorithmica, 29(3):442467, 2001.
• 14: Kai Shen , Hong Tang , Tao Yang , Lingkun Chu, Integrated resource management for cluster-based internet services, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060311]
• 15: Christopher Stewart , Kai Shen, Performance modeling and system management for multi-component online services, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.71-84, May 02-04, 2005
• 16: Chunqiang Tang , Rong N. Chang , Edward So, A Distributed Service Management Infrastructure for Enterprise Data Centers Based on Peer-to-Peer Technology, Proceedings of the IEEE International Conference on Services Computing, p.52-59, September 18-22, 2006 [doi>10.1109/SCC.2006.2]
• 17: Bhuvan Urgaonkar , Prashant Shenoy , Timothy Roscoe, Resource overbooking and application profiling in shared hosting platforms, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060312]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.4 System Management
          Subjects: Quality assurance

General Terms:
Algorithms, Management, Performance

Keywords:
application placement, performance management