Integrated resource management for cluster-based Internet services

ABSTRACT

Client request rates for Internet services tend to be bursty and thus it is important to maintain efficient resource utilization under a wide range of load conditions. Network service clients typically seek services interactively and maintaining reasonable response time is often imperative for such services. In addition, providing differentiated service qualities and resource allocation to multiple service classes can also be desirable at times. This paper presents an integrated resource management framework (part of Neptune system) that provides flexible service quality specification, efficient resource utilization, and service differentiation for cluster-based services. This framework introduces the metric of quality-aware service yield to combine the overall system efficiency and individual service response time in one flexible model. Resources are managed through a two-level request distribution and scheduling scheme. At the cluster level, a fully decentralized request distribution architecture is employed to achieve high scalability and availability. Inside each service node, an adaptive scheduling policy maintains efficient resource utilization under a wide range of load conditions. Our trace-driven evaluations demonstrate the performance, scalability, and service differentiation achieved by the proposed techniques.

REFERENCES

• 1: T. F. Abdelzaher and N. Bhatti. Web Server QoS Management by Adaptive Content Delivery. In International Workshop on Quality of Service, London, UK, June 1999.
• 2: J. Almeida, M. Dabu, A. Manikutty, and P. Cao. Providing Differentiated Levels of Service in Web Content Hosting. In Proc. of SIGMETRICS Workshop on Internet Server Performance, Madison, WI, June 1998.
• 3: 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
• 4: M. Aron, D. Sanders, P. Druschel, and W. Zwaenepoel. Scalable Content-aware Request Distribution in Cluster-based Network Services. In Proc. of the 2000 USENIX Annual Technical Conf., San Diego, CA, June 2000.
• 5: Ask jeeves search, http://www.ask.com.
• 6: 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
• 7: N. Bhatti and R. Friedrich. Web Server Support for Tiered Services. IEEE Network, 13(5):64--71, September 1999.
• 8: J. Bruno, E. Gabber, B. Ozden, and A. Silberschatz. The Eclipse Operating System: Providing Quality of Service via Reservation Domains. In Proc. of USENIX Annual Technical Conf., pages 235--246, Orleans, LA, June 1998.
• 9: S. Chandra, C. S. Ellis, and A. Vahdat. Differentiated Multimedia Web Services Using Quality Aware Transcoding. In Proc. of IEEE INFOCOM'2000, TelAviv, Israel, March 2000.
• 10: Jeffrey S. Chase , Darrell C. Anderson , Prachi N. Thakar , Amin M. Vahdat , Ronald P. Doyle, Managing energy and server resources in hosting centers, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 11: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 12: Constantinos Dovrolis , Dimitrios Stiliadis , Parameswaran Ramanathan, Proportional differentiated services: delay differentiation and packet scheduling, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.109-120, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 13: Peter Druschel , Gaurav Banga, Lazy receiver processing (LRP): a network subsystem architecture for server systems, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.261-275, October 29-November 01, 1996, Seattle, Washington, United States
• 14: J. Postel Ed. Transmission Control Protocol Specification. SRI International, Menlo Park, CA, September 1981. RFC-793.
• 15: A. Feldmann. Characteristics of TCP Connection Arrivals. Technical report, AT&T Labs Research, 1998.
• 16: Armando Fox , Eric A. Brewer, Harvest, Yield, and Scalable Tolerant Systems, Proceedings of the The Seventh Workshop on Hot Topics in Operating Systems, p.174, March 28-30, 1999
• 17: 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
• 18: Google search, http://www.google.com.
• 19: S. D. Gribble, E. A. Brewer, J. M. Hellerstein, and D. Culler. Scalable, Distributed Data Structures for Internet Service Construction. In Proc. of the 4th USENIX Symposium on Operating Systems Design and Implementation, San Diego, CA, October 2000.
• 20: S. D. Gribble, M. Welsh, E. A. Brewer, and D. Culler. The MultiSpace: An Evolutionary Platform for Infrastructural Services. In Proc. of the USENIX Annual Technical Conf., Monterey, CA, June 1999.
• 21: Mor Harchol-Balter , Allen B. Downey, Exploiting process lifetime distributions for dynamic load balancing, ACM Transactions on Computer Systems (TOCS), v.15 n.3, p.253-285, Aug. 1997 [doi>10.1145/263326.263344]
• 22: Jayant R. Haritsa , Michael J. Carey , Miron Livny, Value-based scheduling in real-time database systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.2, April 1993
• 23: J. Huang, J. Stankovic, D. Towsley, and K. Ramamritham. Experimental Evaluation of Real-Time Transaction Processing. In Proc. of the Tenth IEEE Real-Time System Symposium, pages 144--153, Santa Monica, CA, 1989.
• 24: 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
• 25: R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85--103, March 1972.
• 26: Jim Kurose, Open issues and challenges in providing quality of service guarantees in high-speed networks, ACM SIGCOMM Computer Communication Review, v.23 n.1, p.6-15, Jan. 1993 [doi>10.1145/173942.173943]
• 27: K. Li and S. Jamin. A Measurement-Based Admission-Controlled Web Server. In Proc. of IEEE INFOCOM'2000, pages 651--659, Tel-Aviv, Israel, March 2000.
• 28: Zhen Liu , Mark S. Squillante , Joel L. Wolf, On maximizing service-level-agreement profits, Proceedings of the 3rd ACM conference on Electronic Commerce, p.213-223, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501185]
• 29: J. Mogul and K. K. Ramakrishnan. Eliminating Receive Livelock in an Interrupt-driven Kernel. In Proc. of USENIX Annual Technical Conf., San Diego, CA, January 1996.
• 30: Sue Nagy , Azer Bestavros, Admission Control for Soft-Transactions in ACCORD, Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97), p.160, June 09-11, 1997
• 31: Vivek S. Pai , Mohit Aron , Gaurov Banga , Michael Svendsen , Peter Druschel , Willy Zwaenepoel , Erich Nahum, Locality-aware request distribution in cluster-based network servers, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.205-216, October 02-07, 1998, San Jose, California, United States
• 32: Raju Pandey , J. Fritz Barnes , Ronald Olsson, Supporting quality of service in HTTP servers, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.247-256, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277742]
• 33: 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
• 34: Kai Shen , Tao Yang , Lingkun Chu, Cluster Load Balancing for Fine-Grain Network Services, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.93, April 15-19, 2002
• 35: K. Shen, T. Yang, L. Chu, J. L. Holliday, D. A. Kuschner, and H. Zhu. Neptune: Scalable Replication Management and Programming Support for Cluster-based Network Services. In Proc. of the 3rd USENIX Symposium on Internet Technologies and Systems, pages 197--208, San Francisco, CA, March 2001.
• 36: David C. Steere , Ashvin Goel , Joshua Gruenberg , Dylan McNamee , Calton Pu , Jonathan Walpole, A feedback-driven proportion allocator for real-rate scheduling, Proceedings of the third symposium on Operating systems design and implementation, p.145-158, February 1999, New Orleans, Louisiana, United States
• 37: I. Stoica and H. Zhang. LIRA: An Approach for Service Differentiation in the Internet. In Proc. of Nossdav, June 1998.
• 38: D. G. Sullivan and M. I. Seltzer. Isolation with Flexibility: A Resource Management Framework for Central Servers. In Proc. of the 2000 USENIX Annual Technical Conf., San Diego, CA, June 2000.
• 39: Thiemo Voigt , Renu Tewari , Douglas Freimuth , Ashish Mehra, Kernel Mechanisms for Service Differentiation in Overloaded Web Servers, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.189-202, June 25-30, 2001
• 40: C. A. Waldspurger and W. E. Weihl. Lottery Scheduling: Flexible Proportional-Share Resource Management. In Proc. of USENIX Operating Systems Design and Implementation Symposium, pages 1--11, Monterey, CA, November 1994.
• 41: H. Zhu, H. Tang, and T. Yang. Demand-driven Service Differentiation for Cluster-based Network Servers. In Proc. of IEEE INFOCOM'2001, Anchorage, AK, April 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
      D.4.7 Organization and Design
          Subjects: Distributed systems
      D.4.8 Performance
          Subjects: Modeling and prediction

General Terms:
Design, Management