Enforcing time-constraints effectively for QoS-aware servers

ABSTRACT

One of the relevant Quality-of-Service (QoS) issues in web service provider infrastructures (Web-servers, web-services and backend database-servers) is how well they are able to handle congestion, while still meeting time-constraints for accepted transactions. There are many works proposing admission control mechanisms, but their focus is on throughput maximization under miss ratio constraints. These metrics are misleading -- at maximum service rate, throughput can only be improved by accepting small transactions while starving long ones. In this paper we investigate whether admission control based on time-constraints may be a more suitable solution, and analyze the hypothesis by means of simulation. We show that time-based control works well. These conclusions are a basis for our future work within the Adapt-DB project on: alternative time-bounding based control approaches; effective control of starving with best throughput; and especially on SLA-targets tracking and feedback control, all of them using timing control as a basis.

REFERENCES

• 1: Robert K. Abbott , Hector Garcia-Molina, Scheduling real-time transactions: a performance evaluation, ACM Transactions on Database Systems (TODS), v.17 n.3, p.513-560, Sept. 1992 [doi>10.1145/132271.132276]
• 2: Mohamed Noureddine Bennani , Daniel Menasce, Autonomic computing through analytic performance models, George Mason University, Fairfax, VA, 2006
• 3: Bhatti N. and R. Friedrich. Web server support for tiered services. IEEE Network, Vol. 13(5) (1999) 64--71.
• 4: Bhoj, Rmanathan, and Singhal. Web2K: Bringing QoS to Web servers. Tech. Rep. HPL-2000-61, HP Labs, (2000).
• 5: Xiangping Chen , Prasant Mohapatra , Huamin Chen, An admission control scheme for predictable server response time for web accesses, Proceedings of the 10th international conference on World Wide Web, p.545-554, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372156]
• 6: Ludmila Cherkasova , Peter Phaal, Session-Based Admission Control: A Mechanism for Peak Load Management of Commercial Web Sites, IEEE Transactions on Computers, v.51 n.6, p.669-685, June 2002 [doi>10.1109/TC.2002.1009151]
• 7: 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]
• 8: Kyoung-Don Kang , Sang H. Son , John A. Stankovic, Managing Deadline Miss Ratio and Sensor Data Freshness in Real-Time Databases, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1200-1216, October 2004 [doi>10.1109/TKDE.2004.61]
• 9: Kyoung-Don Kang , John A. Stankovic , Sang H. Son, Qos-aware real-time data management, University of Virginia, Charlottesville, VA, 2003
• 10: Kyoung-Don Kang , Sang H. Son , John A. Stankovic , Tarek F. Abdelzaher, A QoS-Sensitive Approach for Timeliness and Freshness Guarantees in Real-Time Databases, Proceedings of the 14th Euromicro Conference on Real-Time Systems, p.203, June 19-21, 2002
• 11: Haritsa, J., Livny and M. Carey:"Earliest Deadline Scheduling for Real-Time Database Systems", Proc. IEEE Real-Time Syst. Symp, pp 232--242, IEEE, Los Alamitos, CA, 1991.
• 12: Hans-Ulrich Heiss , Roger Wagner, Adaptive Load Control in Transaction Processing Systems, Proceedings of the 17th International Conference on Very Large Data Bases, p.47-54, September 03-06, 1991
• 13: Kanodia V. and E. W. Knightly. Ensuring latency targets in multiclass Web servers. IEEE Requests on Parallel and Distributed Systems, Vol. 13(10) (2002).
• 14: Little, J. D. C. "A Proof of the Queueing Formula L = λ W" Operations Research, 9, 383--387 (1961).
• 15: Krishna C., Shin, Kang, "Real-Time Systems", McGraw-Hill 1997, ISBN 0-07-057043-4.
• 16: Chenyang Lu , John A. Stankovic , Sang H. Son , Gang Tao, Feedback Control Real-Time Scheduling: Framework, Modeling, and Algorithms*, Real-Time Systems, v.23 n.1-2, p.85-126, July-September 2002 [doi>10.1023/A:1015398403337]
• 17: Menasce, Bennani, "On the Use of Performance Models to Design Self-Managing Computer Systems", Proc. 2003 Comp. Measur. Group Conf., Dallas, TX, Dec. 7--12, 2003.
• 18: Jeffrey C. Mogul , K. K. Ramakrishnan, Eliminating receive livelock in an interrupt-driven kernel, ACM Transactions on Computer Systems (TOCS), v.15 n.3, p.217-252, Aug. 1997 [doi>10.1145/263326.263335]
• 19: Pang H., Livny M., Carey M.: "Transaction Scheduling in Multiclass Real-Time Database Systems", Proc. IEEE Real-Time Systems Symposium, pp 22--34, IEEE, Los Alamitos, CA, (1992).
• 20: Pradhan P., R. Tewari, S. Sahu, A. Chandra, and P. Shenoy. An observation-based approach towards self managing Web servers. In International Workshop on Quality of Service, Miami Beach, FL, (2002).
• 21: Bianca Schroeder , Mor Harchol-Balter , Arun Iyengar , Erich Nahum , Adam Wierman, How to Determine a Good Multi-Programming Level for External Scheduling, Proceedings of the 22nd International Conference on Data Engineering, p.60, April 03-07, 2006 [doi>10.1109/ICDE.2006.78]
• 22: Stankovic J., C. Lu, S. Son, and G. Tao, The Case for Feedback Control Real-Time Scheduling, EuroMicro Conference on Real-Time Systems (1999).
• 23: TPCC: www.tpc.org.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

General Terms:
Algorithms, Performance

Keywords:
QoS, algorithms, deadlines, real-time, transactions