QDSL: a queuing model for systems with differential service levels

ABSTRACT

A feature exhibited by many modern computing systems is their ability to improve the quality of output they generate for a given input by spending more computing resources on processing it. Often this improvement comes at the price of degraded performance in the form of reduced throughput or increased response time. We formulate QDSL, a class of constrained optimization problems defined in the context of a queueing server equipped with multiple levels of service. Solutions to QDSL provide rules for dynamically varying the service level to achieve desired trade-offs between output quality and performance. Our approach involves reducing restricted versions of such systems to Markov Decision Processes. We find two variants of such systems worth studying: (i) VarSL, in which a single request may be serviced using a combination of multiple levels during its lifetime and (ii) FixSL in which the service level may not change during the lifetime of a request. Our modeling indicates that optimal service level selection policies in these systems correspond to very simple rules that can be implemented very efficiently in realistic, online systems. We find our policies to be useful in two response-time-sensitive real-world systems: (i) qSecStore, an iSCSI-based secure storage system that has access to multiple encryption functions, and (ii) qPowServer, a server with DVFS-capable processor. As a representative result, in an instance of qSecStore serving disk requests derived from the well-regarded TPC-H traces, we are able to improve the fraction of requests using more reliable encryption functions by 40-60%, while meeting performance targets. In a simulation of qPowServer employing realistic DVFS parameters, we are able to improve response times significantly while only violating specified server-wide power budgets by less than 5W.

REFERENCES

• 1: S. Keshav A. Demers and S. Shenker. Analysis and simulation of a fair queuing algorithm. In Journal of Internetworking Research and Experience, 1990.
• 2: F. Bellosa. Process cruise control: Throttling memory access in a soft real-time environment. In Technical Report TR-14-97-02, Univ of Erlangen-Nuernberg, IMMD IV, 1997.
• 3: N. Bhatti and R. Friedrich. Web Server Support for Tiered Services. In IEEE Network, 1999.
• 4: John Bruno , Eran Gabber , Banu Özden , Abraham Silberschatz, The eclipse operating system: providing quality of service via reservation domains, Proceedings of the annual conference on USENIX Annual Technical Conference, p.20-20, June 15-19, 1998, New Orleans, Louisiana
• 5: Shiva Chaitanya , Kevin Butler , Anand Sivasubramaniam , Patrick McDaniel , Murali Vilayannur, Design, implementation and evaluation of security in iSCSI-based network storage systems, Proceedings of the second ACM workshop on Storage security and survivability, October 30-30, 2006, Alexandria, Virginia, USA [doi>10.1145/1179559.1179564]
• 6: D. Chen and P. K. Varshney. QoS support in wireless sensor networks: A survey. In Proceedings of the International Conference on Wireless
• 7: J. Chuang and M. Sirbu. Distributed Network Storage with Quality-Of-Service Gaurantees. In Journal of Network and Computer Applications, 2000.
• 8: Thomas B. Crabill. Optimal Control of a Service Facility with Variable Exponential Service Times and Constant Arrival Rate. In Management Science, May 1972.
• 9: CSIM. http://www.mesquite.com/.
• 10: Dirk Grunwald , Charles B. Morrey, III , Philip Levis , Michael Neufeld , Keith I. Farkas, Policies for dynamic clock scheduling, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.6-6, October 22-25, 2000, San Diego, California
• 11: Ejasent. Utility Computing White Paper. November 2001.
• 12: D. McNamee et al. Control challenges in multi-level adaptive video streaming. In Proceedings of 39th IEEE Conference on Decision and Control, 2000.
• 13: 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
• 14: Y. Bernet et al. A Framework for differentiated services. In Internet draft: draft-ietf-diffserv-framework-02.txt, 1999.
• 15: Xu-Dong Zhang , Tie-Yan Liu , Kwok-Tung Lo , Jian Feng, Dynamic selection and effective compression of key frames for video abstraction, Pattern Recognition Letters, v.24 n.9-10, p.1523-1532, 01 June 2003 [doi>10.1016/S0167-8655(02)00391-4]
• 16: E.A Feinberg. Optimal control of average reward constrained continuous-time finite markov decision processes. In Proceedings of the 41st IEEE Conference on Decision and Control, 2002.
• 17: 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
• 18: Jennifer M. George , J. Michael Harrison, Dynamic Control of a Queue with Adjustable Service Rate, Operations Research, v.49 n.5, p.720-731, September 2001 [doi>10.1287/opre.49.5.720.10605]
• 19: R A Howard. Dynamic probabilistic systems. vol. ii: Semi-markov and decision processes. In Series in Decision and Control, 1971.
• 20: Cynthia Irvine , Tim Levin, Toward a Taxonomy and Costing Method for Security Services, Proceedings of the 15th Annual Computer Security Applications Conference, p.183, December 06-10, 1999
• 21: F. P. Kelly. Charging and Rate Control for Elastic Traffic. In European Transactions on Telecommunications, 1997.
• 22: L. Kleinrock. Queueing Systems, Volume 1: Theory. 1975.
• 23: Chandra Krintz , Brad Calder, Reducing Delay with Dynamic Selection of Compression Formats, Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing, p.266, August 07-09, 2001
• 24: K. Li and S. Jamin. A Measurement-based Admission Controlled Web Server. In Proceedings of IEEE INFOCOM, 2000.
• 25: Jacob R. Lorch , Alan Jay Smith, Improving dynamic voltage scaling algorithms with PACE, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.50-61, June 2001, Cambridge, Massachusetts, United States
• 26: Mootaz Elnozahy , Michael Kistler , Ramakrishnan Rajamony, Energy conservation policies for web servers, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.8-8, March 26-28, 2003, Seattle, WA
• 27: E. Elnozahy T. Keller M. Kistler C. Lefurgy R. Rajamony F. Rawson P. Bohrer, D. Cohn and E. Hensbergen. Energy conservation for servers. In Proceedings of the IEEE Workshop on Power Management for Real-Time and Embedded Systems, 2001.
• 28: Pawan Goyal , Harrick M. Vin , Haichen Cheng, Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.690-704, Oct. 1997 [doi>10.1109/90.649569]
• 29: Qinru Qiu , Massoud Pedram, Dynamic power management based on continuous-time Markov decision processes, Proceedings of the 36th ACM/IEEE conference on Design automation, p.555-561, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309997]
• 30: Erik Riedel , Mahesh Kallahalla , Ram Swaminathan, A Framework for Evaluating Storage System Security, Proceedings of the Conference on File and Storage Technologies, p.15-30, January 28-30, 2002
• 31: O. Rose. Estimation of the hurst parameter of long-range dependent time series. 1996.
• 32: V. Rykov and D. Efrosinin. Numerical Analysis of Optimal Control Policies for Queueing Systems with Heterogeneous Servers. In Kalashnikov Memorial Seminar, 2002.
• 33: Christopher M. Sadler , Margaret Martonosi, Data compression algorithms for energy-constrained devices in delay tolerant networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182834]
• 34: Linn I. Sennott. Average Cost Optimal Stationary Policies in Infinite State Markov Decision Processes with Unbounded Costs. In Operations Research, volume 37, 1989.
• 35: W. Smith. Tpc-w: Benchmarking an ecommerce solution.
• 36: Sychron. Sychron Enterprise Manager. 2001.
• 37: TPC-H. http://www.tpc.org/tpch.
• 38: Vivek Sharma , Arun Thomas , Tarek Abdelzaher , Kevin Skadron , Zhijian Lu, Power-aware QoS Management in Web Servers, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.63, December 03-05, 2003
• 39: C. Wang and W. A. Wulf. Towards a framework for security measurement. In Proceedings of the National Information Systems Security Conference, 1997.
• 40: Richard Weber and Shaler Stidham. Optimal Control of Service Rates in Networks of Queues. In Advances in Applied Probability, volume 19, 1987.
• 41: Charles P. Wright, Michael C. Martino, and Erez Zadok. Ncryptfs: A secure and convenient cryptographic file system. In Proceedings of the USENIX 2003 Annual Technical Conference, 2003.
• 42: Tao Yu , Kwei-Jay Lin, Service Selection Algorithms for Web Services with End-to-End QoS Constraints, Proceedings of the IEEE International Conference on E-Commerce Technology, p.129-136, July 06-09, 2004
• 43: Shlomo Zilberstein. Using anytime algorithms in intelligent systems. In American Association for Artificial Intelligence, 1996.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Stochastic analysis; Simulation

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
differential service levels, dynamic voltage frequency scaling, markov decision process, secure storage