|
ABSTRACT
In this article, we present techniques for provisioning CPU and network resources in shared Internet hosting platforms running potentially antagonistic third-party applications. The primary contribution of our work is to demonstrate the feasibility and benefits of overbooking resources in shared Internet platforms. Since an accurate estimate of an application's resource needs is necessary when overbooking resources, we present techniques to profile applications on dedicated nodes, possibly while in service, and use these profiles to guide the placement of application components onto shared nodes. We then propose techniques to overbook cluster resources in a controlled fashion. We outline an empirical appraoch to determine the degree of overbooking that allows a platform to achieve improvements in revenue while providing performance guarantees to Internet applications. We show how our techniques can be combined with commonly used QoS resource allocation mechanisms to provide application isolation and performance guarantees at run-time. We implement our techniques in a Linux cluster and evaluate them using common server applications. We find that the efficiency (and consequently revenue) benefits from controlled overbooking of resources can be dramatic. Specifically, we find that overbooking resources by as little as 1% we can increase the utilization of the cluster by a factor of two, and a 5% overbooking yields a 300--500% improvement, while still providing useful resource guarantees to applications.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
 |
2
|
Jennifer M. Anderson , Lance M. Berc , Jeffrey Dean , Sanjay Ghemawat , Monika R. Henzinger , Shun-Tak A. Leung , Richard L. Sites , Mark T. Vandevoorde , Carl A. Waldspurger , William E. Weihl, Continuous profiling: where have all the cycles gone?, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.1-14, October 05-08, 1997, Saint Malo, France
|
| |
3
|
Appleby, K., Fakhouri, S., Fong, L., Goldszmidt, M. K. G., Krishnakumar, S., Pazel, D., Pershing, J., and Rochwerger, B. 2001. Oceano—SLA-based management of a computing utility. In Proceedings of the IFIP/IEEE Symposium on Integrated Network Management. IEEE Computer Society Press, Los Alamitos, CA.
|
 |
4
|
Mohit Aron , Peter Druschel , Willy Zwaenepoel, Cluster reserves: a mechanism for resource management in cluster-based network servers, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.90-101, June 18-21, 2000, Santa Clara, California, United States
|
 |
5
|
|
 |
6
|
|
| |
7
|
|
 |
8
|
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
|
| |
9
|
|
| |
10
|
Berger, E., Kaplan, S., Urgaonkar, B., Sharma, P., Chandra, A., and Shenoy, P. 2003. Scheduler-aware virtual memory management. In Poster at the 19th ACM Symposium on Operating Systems Principles (SOSP 2003). ACM, New York.
|
| |
11
|
Blanquer, J., Bruno, J., McShea, M., Ozden, B., Silberschatz, A., and Singh, A. 1999. Resource management for QoS in Eclipse/BSD. In Proceedings of the FreeBSD'99 Conference.
|
| |
12
|
Boorstyn, R., Burchard, A., Liebeherr, J., and Oottamakorn, C. 2000. Statistical service assurances for traffic scheduling algorithms. IEEE J. Select. Areas Commun. 18, 12, 2651--2664.
|
| |
13
|
|
| |
14
|
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
|
 |
15
|
|
| |
16
|
Chandra, A., Goyal, P., and Shenoy, P. 2003b. Quantifying the benefits of resource multiplexing in on-demand data centers. In Proceedings of the 1st Workshop on Algorithms and Architectures for Self-Managing Systems.
|
| |
17
|
|
| |
18
|
|
 |
19
|
Yiyu Chen , Amitayu Das , Wubi Qin , Anand Sivasubramaniam , Qian Wang , Natarajan Gautam, Managing server energy and operational costs in hosting centers, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
|
 |
20
|
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
|
| |
21
|
Cherkasova, L. and Phaal, P. 1999. Session based admission control: A mechanism for improving performance of commercial web sites. In Proceedings of the 7th International Workshop on Quality of Service. IEEE Computer Society Press, Los Alamitos, CA.
|
| |
22
|
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
|
| |
23
|
Ira Cohen , Moises Goldszmidt , Terence Kelly , Julie Symons , Jeffrey S. Chase, Correlating instrumentation data to system states: a building block for automated diagnosis and control, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.16-16, December 06-08, 2004, San Francisco, CA
|
| |
24
|
|
| |
25
|
Corba 2006. Corba documentation. http://www.omg.org/.
|
| |
26
|
|
| |
27
|
Davis, P. 1994. Airline ties profitability to yield management. SIAM News.
|
| |
28
|
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
|
 |
29
|
|
| |
30
|
Edmonds, J. 1965. Maximum matching and a polyhedron with 0,1 - Vertices. J. Rese. NBS 69B.
|
 |
31
|
Sameh Elnikety , Erich Nahum , John Tracey , Willy Zwaenepoel, A method for transparent admission control and request scheduling in e-commerce web sites, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA
[doi> 10.1145/988672.988710]
|
 |
32
|
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
|
| |
33
|
|
 |
34
|
Kinshuk Govil , Dan Teodosiu , Yongqiang Huang , Mendel Rosenblum, Cellular Disco: resource management using virtual clusters on shared-memory multiprocessors, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.154-169, December 12-15, 1999, Charleston, South Carolina, United States
|
 |
35
|
Sriram Govindan , Arjun R. Nath , Amitayu Das , Bhuvan Urgaonkar , Anand Sivasubramaniam, Xen and co.: communication-aware CPU scheduling for consolidated xen-based hosting platforms, Proceedings of the 3rd international conference on Virtual execution environments, June 13-15, 2007, San Diego, California, USA
[doi> 10.1145/1254810.1254828]
|
 |
36
|
Pawan Goyal , Xingang Guo , Harrick M. Vin, A hierarchial CPU scheduler for multimedia operating systems, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.107-121, October 29-November 01, 1996, Seattle, Washington, United States
|
 |
37
|
Pawan Goyal , Harrick M. Vin , Haichen Chen, Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.157-168, August 28-30, 1996, Palo Alto, California, United States
|
| |
38
|
GridForum02b 2002. Global grid forum: Scheduling and resource management working group. http://www-unix.mcs.anl.gov/schopf/ggf-sched/.
|
 |
39
|
|
| |
40
|
|
| |
41
|
Atsushi Hori , Hiroshi Tezuka , Yutaka Ishikawa , Noriyuki Soda , Hiroki Konaka , Munenori Maeda, Implementation of Gang-Scheduling on Workstation Cluster, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.126-139, April 16, 1996
|
| |
42
|
Iyer, R., Tewari, V., and Kant, K. 2000. Overload control mechanisms for web servers. In Proceedings of the Workshop on Performance and QoS of Next Generation Networks.
|
| |
43
|
Jamjoom, H., Reumann, J., and Shin, K. 2000. QGuard: Protecting internet servers from overload. Tech. Rep. CSE-TR-427-00, Department of Computer Science, University of Michigan.
|
 |
44
|
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
|
| |
45
|
Kamra, A., Misra, V., and Nahum, E. 2004. Yaksha: A controller for managing the performance of 3-tiered websites. In Proceedings of the 12th International Workshop on Quality of Service (IWQoS). IEEE Computer Society Press, Los Alamitos, CA.
|
| |
46
|
Kanodia, V. and Knightly, E. 2000. Multi-class latency-bounded web servers. In Proceedings of International Workshop on Quality of Service (IWQoS'00). IEEE Computer Society Press, Los Alamitos, CA.
|
| |
47
|
Kelly, T., Cohen, I., Goldszmidt, M., and Keeton, K. 2004. Inducing models of black-box storage arrays. Tech. Rep. HPL-2004, HP Labs.
|
| |
48
|
Knightly, E. and Shroff, N. 1999. Admission control for statistical QoS: Theory and practice. IEEE Network 13, 2. 20--29.
|
| |
49
|
Kournev, S. and Buchmann, A. 2003. Performance modeling and evaluation of large-scale J2EE applications. In Proceedings of the International Conference of the Computer Measurement Group.
|
| |
50
|
|
| |
51
|
Leslie, I., McAuley, D., Black, R., Roscoe, T., Barham, P., Evers, D., Fairbairns, R., and Hyden, E. 1996. The design and implementation of an operating system to support distributed multimedia applications. IEEE J. Selected Areas in Communication, 14, 7, 1280--1297.
|
| |
52
|
Levy, R., Nagarajarao, J., Pacifici, G., Spreitzer, M., Tantawi, A., and Youssef, A. 2003. Performance management for cluster based web services. In Proceedings of the IFIP/IEEE 8th International Symposium on Integrated Network Management. IEEE Computer Society Press, Los Alamitos, CA, Vol. 246. 247--261.
|
| |
53
|
Li, S. and Jamin, S. 2000. A measurement-based admission-controlled web server. In Proceedings of the 9th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2000). IEEE Computer Society Press, Los Alamitos, CA.
|
| |
54
|
|
| |
55
|
Litzkow, M., Livny, M., and Mutka, M. 1988. Condor—A hunter of idle workstations. In Proceedings of the 8th International Conference of Distributed Computing Systems. 104--111.
|
| |
56
|
Liu, T.-K., Kumaran, S., and Luo, Z. 2001. Layered queueing models for Enterprise Java Beans Applications. Tech. rep., IBM. June.
|
| |
57
|
LTT02. The linux toolkit project page. http://www.opensys.com/LTT.
|
| |
58
|
|
| |
59
|
|
| |
60
|
|
 |
61
|
Aravind Menon , Jose Renato Santos , Yoshio Turner , G. (John) Janakiraman , Willy Zwaenepoel, Diagnosing performance overheads in the xen virtual machine environment, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA
[doi> 10.1145/1064979.1064984]
|
| |
62
|
|
| |
63
|
Papoulis, A. and Pillai, S. 2002. Probability, Random Variables and Stochastic Processes. McGraw-Hill, Englewood Cliffs, NJ.
|
| |
64
|
pgbench 2002. The pgbench man page, postgresql software distribution.
|
| |
65
|
Pradhan, P., Tewari, R., Sahu, S., Chandra, A., and Shenoy, P. 2002. An observation-based approach towards self-managing web servers. In Proceedings of the 10th International Workshop on Quality of Service (IWQoS 2002). IEEE Computer Society Press, Los Alamitos, CA.
|
| |
66
|
Ranjan, S., Rolia, J., Fu, H., and Knightly, E. 2002. QoS-driven server migration for internet data centers. In Proceedings of the 10th International Workshop on Quality of Service (IWQoS). IEEE Computer Society Press, Los Alamitos, CA.
|
| |
67
|
|
 |
68
|
|
 |
69
|
Yasushi Saito , Brian N. Bershad , Henry M. Levy, Manageability, availability and performance in Porcupine: a highly scalable, cluster-based mail service, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.1-15, December 12-15, 1999, Charleston, South Carolina, United States
|
 |
70
|
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]
|
| |
71
|
Sgi99 1999. React: Irix real-time extensions. http://www.sgi.com/software/react.
|
 |
72
|
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]
|
 |
73
|
|
| |
74
|
Slothouber, L. 1996. A model of web server performance. In Proceedings of the 5th International World Wide Web Conference.
|
| |
75
|
Smith, B. C., Leimkuhler, J. F., and Darrow, R. M. 1992. Yield management at American Airlines. Interfaces, 22, 1, 8--31.
|
| |
76
|
SPECWeb99. The Standard Performance Evaluation Corporation (SPEC). http://www.spec.org/.
|
| |
77
|
|
| |
78
|
Sun98b 1998. Solaris resource manager 1.0: Controlling system resources effectively. http://www.sun.com/software/white-papers/wp-srm.
|
 |
79
|
Vijay Sundaram , Abhishek Chandra , Pawan Goyal , Prashant Shenoy , Jasleen Sahni , Harrick Vin, Application performance in the QLinux multimedia operating system, Proceedings of the eighth ACM international conference on Multimedia, p.127-136, October 2000, Marina del Rey, California, United States
[doi> 10.1145/354384.354448]
|
| |
80
|
Tang, P. and Tai, T. 1999. Network traffic characterization using token bucket model. In Proceedings of IEEE Infocom'99. IEEE Computer Society Press, Los Alamitos, CA.
|
 |
81
|
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
|
 |
82
|
|
| |
83
|
|
| |
84
|
|
 |
85
|
|
 |
86
|
Ben Verghese , Anoop Gupta , Mendel Rosenblum, Performance isolation: sharing and isolation in shared-memory multiprocessors, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.181-192, October 02-07, 1998, San Jose, California, United States
|
| |
87
|
|
 |
88
|
|
| |
89
|
Villela, D., Pradhan, P., and Rubenstein, D. 2004. Provisioning servers in the application tier for e-commerce systems. In Proceedings of the 12th International Workshop on Quality of Service (IWQoS). IEEE Computer Society Press, Los Alamitos, CA.
|
 |
90
|
H. Vin , P. Goyal , A. Goyal, A statistical admission control algorithm for multimedia servers, Proceedings of the second ACM international conference on Multimedia, p.33-40, October 15-20, 1994, San Francisco, California, United States
[doi> 10.1145/192593.192616]
|
| |
91
|
|
 |
92
|
|
| |
93
|
|
| |
94
|
|
 |
95
|
|
| |
96
|
|
| |
97
|
wsla. Web service level agreements (wsla) project. http://www.research.ibm.com/wsla.
|
 |
98
|
|
| |
99
|
Xu, W., Bodik, P., and Patterson, D. 2004. A flexible architecture for statistical learning and data mining from system log streams. In Proceedings of Workshop on Temporal Data Mining: Algorithms, Theory and Applications at the 4th IEEE International Conference on Data Mining (ICDM'04).
|
 |
100
|
Jianyong Zhang , Anand Sivasubramaniam , Alma Riska , Qian Wang , Erik Riedel, An interposed 2-Level I/O scheduling framework for performance virtualization, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
|
| |
101
|
Jianyong Zhang , Anand Sivasubramaniam , Qian Wang , Alma Riska , Erik Riedel, Storage Performance Virtualization via Throughput and Latency Control, Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.135-142, September 27-29, 2005
[doi> 10.1109/MASCOT.2005.71]
|
INDEX TERMS
Primary Classification:
D.
Software
D.4
OPERATING SYSTEMS
D.4.7
Organization and Design
Subjects:
Distributed systems
Additional Classification:
D.
Software
D.4
OPERATING SYSTEMS
D.4.8
Performance
Subjects:
Measurements;
Modeling and prediction;
Stochastic analysis
I.
Computing Methodologies
I.6
SIMULATION AND MODELING
I.6.4
Model Validation and Analysis
I.6.5
Model Development
Subjects:
Modeling methodologies
General Terms:
Design,
Experimentation,
Measurement,
Performance
Keywords:
Internet application,
capsule,
dedicated hosting platform,
high percentile,
placement,
profile,
quality-of-service,
resource overbooking,
shared hosting platform,
yield management
|