Xen and co.: communication-aware CPU scheduling for consolidated xen-based hosting platforms

ABSTRACT

Recent advances in software and architectural support for server virtualization have created interest in using this technology in the design of consolidated hosting platforms. Since virtualization enables easier and faster application migration as well as secure co-location of antagonistic applications, higher degrees of server consolidation are likely to result in such virtualization-based hosting platforms (VHPs). We identify a key shortcoming in existing virtual machine monitors (VMMs) that proves to be an obstacle in operating hosting platforms, such as Internet data centers, under conditions of such high consolidation: CPU schedulers that are agnostic to the communication behavior of modern, multi-tier applications. We develop a new communication-aware CPU scheduling algorithm to alleviate this problem. We implement our algorithm in the Xen VMM and build a prototype VHP on a cluster of servers. Our experimental evaluation with realistic Internet server applications and benchmarks demonstrates the performance/cost benefits and the wide applicability of our algorithms. For example, the TPC-W benchmark exhibited improvements in average response times of up to 35% for a variety of consolidation scenarios. A streaming media server hosted on our prototype VHP was able to satisfactorily service up to 3.5 times as many clients as one running on the default Xen.

REFERENCES

• 1: Micah Adler , Ying Gong , Arnold L. Rosenberg, Optimal sharing of bags of tasks in heterogeneous clusters, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777414]
• 2: Amazon Elastic Compute Cloud. http://www.nature.com/.
• 3: Andrea Carol Arpaci-Dusseau, Implicit coscheduling: coordinated scheduling with implicit information in distributed systems, ACM Transactions on Computer Systems (TOCS), v.19 n.3, p.283-331, Aug. 2001 [doi>10.1145/380749.380764]
• 4: A. Arpaci-Dusseau and D.E. Culler. Extending Proportional-Share Scheduling to a Network of Workstations. In Proceedings of Parallel and Distributed Processing Techniques and Applications (PDPTA'97), Las Vegas, NV, June 1997.
• 5: Gaurav Banga , Peter Druschel , Jeffrey C. Mogul, Resource containers: a new facility for resource management in server systems, Proceedings of the third symposium on Operating systems design and implementation, p.45-58, February 1999, New Orleans, Louisiana, United States
• 6: 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
• 7: Mohamed N. Bennani , Daniel A. Menasce, Resource Allocation for Autonomic Data Centers using Analytic Performance Models, Proceedings of the Second International Conference on Automatic Computing, p.229-240, June 13-16, 2005 [doi>10.1109/ICAC.2005.50]
• 8: Daniel A. Menasce , Mohamed N. Bennani, Autonomic Virtualized Environments, Proceedings of the International Conference on Autonomic and Autonomous Systems, p.28, July 19-21, 2006 [doi>10.1109/ICAS.2006.13]
• 9: Abhishek Chandra , Micah Adler , Pawan Goyal , Prashant Shenoy, Surplus fair scheduling: a proportional-share CPU scheduling algorithm for symmetric multiprocessors, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.4-4, October 22-25, 2000, San Diego, California
• 10: Yiyu Chen , Amitayu Das , Anand Sivasubramaniam , Qian Wang , R. Harper , M. Bland, Consolidating clients on back-end servers with co-location and frequency control, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 11: 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
• 12: Credit Based Scheduler. http://wiki.xensource.com/xenwiki/CreditScheduler.
• 13: Ronald P. Doyle , Jeffrey S. Chase , Omer M. Asad , Wei Jin , Amin M. Vahdat, Model-based resource provisioning in a web service utility, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.5-5, March 26-28, 2003, Seattle, WA
• 14: Kenneth J. Duda , David R. Cheriton, Borrowed-virtual-time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.261-276, December 12-15, 1999, Charleston, South Carolina, United States
• 15: R. Goldberg. Survey of Virtual Machine Research. IEEE Computer, pages 34--45, June 1974.
• 16: S. Govindan, A. Nath, A. Das, B. Urgaonkar, and A. Sivasubramaniam. Communication-aware CPU Management in Consolidated Virtualization-based Hosting Platforms. Technical report, Department of Computer Science and Engineering, The Pennsylvania State University, October 2006.
• 17: D. Gupta, L. Cherkasova, R. Gardner, and A. Vahdat. Enforcing Performance Isolation Across Virtual Machines in Xen. In Proceedings of the Seventh International Middleware Conference, Melbourne, Australia, November-December 2006.
• 18: D. Gupta, R. Gardner, and L. Cherkasova. XenMon: QoS Monitoring and Performance Profiling Tool. Technical Report HPL-2005-187, HP Labs, 2005.
• 19: Intel VT. http://www.intel.com/technology/itj/2006/v10i3/foreword.htm.
• 20: The JBoss Application Server. http://www.jboss.org.
• 21: Michael B. Jones , Daniela Roşu , Marcel-Cătălin Roşu, CPU reservations and time constraints: efficient, predictable scheduling of independent activities, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.198-211, October 05-08, 1997, Saint Malo, France
• 22: Scott T. Leutenegger , Mary K. Vernon, The performance of multiprogrammed multiprocessor scheduling algorithms, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.226-236, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 23: Jiuxing Liu , Wei Huang , Bulent Abali , Dhabaleswar K. Panda, High performance VMM-bypass I/O in virtual machines, Proceedings of the Annual Technical Conference on USENIX'06 Annual Technical Conference, p.3-3, May 30-June 03, 2006, Boston, MA
• 24: Aravind Menon , Alan L. Cox , Willy Zwaenepoel, Optimizing network virtualization in Xen, Proceedings of the Annual Technical Conference on USENIX'06 Annual Technical Conference, p.2-2, May 30-June 03, 2006, Boston, MA
• 25: MySQL. http://www.mysql.com.
• 26: Shailabh Nagar , Ajit Banerjee , Anand Sivasubramaniam , Chita R. Das, A closer look at coscheduling approaches for a network of workstations, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.96-105, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305630]
• 27: Michael Nelson , Beng-Hong Lim , Greg Hutchins, Fast transparent migration for virtual machines, Proceedings of the USENIX Annual Technical Conference 2005 on USENIX Annual Technical Conference, p.25-25, April 10-15, 2005, Anaheim, CA
• 28: Jason Nieh , Monica S. Lam, A SMART scheduler for multimedia applications, ACM Transactions on Computer Systems (TOCS), v.21 n.2, p.117-163, May 2003 [doi>10.1145/762483.762484]
• 29: Steven Osman , Dinesh Subhraveti , Gong Su , Jason Nieh, The design and implementation of Zap: a system for migrating computing environments, 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.1060323]
• 30: Constantine P. Sapuntzakis , Ramesh Chandra , Ben Pfaff , Jim Chow , Monica S. Lam , Mendel Rosenblum, Optimizing the migration of virtual computers, 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.1060324]
• 31: 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]
• 32: Sameer Shende , Allen D. Malony , Janice Cuny , Peter Beckman , Steve Karmesin , Kathleen Lindlan, Portable profiling and tracing for parallel, scientific applications using C++, Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, p.134-145, August 03-04, 1998, Welches, Oregon, United States [doi>10.1145/281035.281049]
• 33: J. E. Smith and R. Nair. Virtual Machines: Architectures, Implementations and Applications. Morgan Kauffmann, New York, 2004.
• 34: W. Smith. TPC--W: Benchmarking An Ecommerce Solution. http://www.tpc.org/information/other/techarticles.asp.
• 35: Patrick Sobalvarro , William E. Weihl, Demand-Based Coscheduling of Parallel Jobs on Multiprogrammed Multiprocessors, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.106-126, April 25, 1995
• 36: Mark S. Squillante , Yanyong Zhang , Anand Sivasubramaniam , Natarajan Gautam , Hubertus Franke , Jose Moreira, Modeling and analysis of dynamic coscheduling in parallel and distributed environments, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 37: NYU TPC-W. http://www.cs.nyu.edu/pdsg/.
• 38: Bhuvan Urgaonkar , Giovanni Pacifici , Prashant Shenoy , Mike Spreitzer , Asser Tantawi, An analytical model for multi-tier internet services and its applications, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 39: 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]
• 40: VMware. http://www.vmware.com/.
• 41: Carl A. Waldspurger, Memory resource management in VMware ESX server, 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.1060307]
• 42: Carl A. Waldspurger , William E. Weihl, Lottery scheduling: flexible proportional-share resource management, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.1-es, November 14-17, 1994, Monterey, California
• 43: Andrew Whitaker , Marianne Shaw , Steven D. Gribble, Scale and performance in the Denali isolation kernel, 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.1060308]
• 44: XenSource Press Release. http://www.xensource.com/news/pressreleases.html.
• 45: Improving Parallel Job Scheduling by Combining Gang Scheduling and Backfilling Techniques, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.133, May 01-05, 2000
• 46: Yanyong Zhang , Anand Sivasubramaniam , Jose Moreira , Hubertus Franke, A simulation-based study of scheduling mechanisms for a dynamic cluster environment, Proceedings of the 14th international conference on Supercomputing, p.100-109, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335241]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Network communication

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
CPU scheduler, multi-tier application, virtual machine monitor, xen