research-article

QDSL: a queuing model for systems with differential service levels

Authors:

Shiva Chaitanya,

Bhuvan Urgaonkar,

Anand SivasubramaniamAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 36, Issue 1

Pages 289 - 300

https://doi.org/10.1145/1384529.1375490

Published: 02 June 2008 Publication History

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.

Digital Library

[4]

J. Bruno, E. Gabber, B. Ozden, and A. Silberschatz. The eclipse operating system: Providing quality of service via reservation domains. In Proceedings of the USENIX Annual Technical Conference, 1998.

Digital Library

[5]

S. Chaitanya, K. Butler, A. Sivasubramaniam, P. McDaniel, and M. Vilayannur. Design, implementation and evaluation of security in iscsi based network storage systems. In Proceedings of the Workshop on Storage Security and Survivability, 2006.

Digital Library

[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]

P. Lewis D. Grunwald and K. I Farkas. Policies for dynamic clock scheduling. In Proceedings of the Usenix Symposium on Operating Systems Design and Implementation, 2000.

Digital Library

[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]

J. Chase et al. Managing Energy and Server Resources in Hosting Centers. In Proceedings of the ACM Symposium on Operating System Principles, 2001.

Digital Library

[14]

Y. Bernet et al. A Framework for differentiated services. In Internet draft: draft-ietf-diffserv-framework-02.txt, 1999.

[15]

Zhang et al. Dynamic selection and effective compression of key frames for video abstraction. In Pattern Recognition Letters, 2003.

Digital Library

[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]

P. Drushel G. Banga and J. Mogul. Resource containers: A new facility for resource management in server systems. In Proceedings of the Usenix Symposium on Operating Systems Design and Implementation, 1999.

Digital Library

[18]

Jennifer M. George and J. Michael Harrison. Dynamic Control of a Queue with Adjustable Service Rate. In Operations Research, 2001.

Digital Library

[19]

R A Howard. Dynamic probabilistic systems. vol. ii: Semi-markov and decision processes. In Series in Decision and Control, 1971.

[20]

C. Irvine and T. Levin. Toward a Taxonomy and Costing Method for Security Services. In Proceedings of the Annual Computer Security Applications Conference, 1999.

Digital Library

[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 and Brad Calder. Reducing delay with dynamic selection of compression formats. In HPDC, 2001.

Digital Library

[24]

K. Li and S. Jamin. A Measurement-based Admission Controlled Web Server. In Proceedings of IEEE INFOCOM, 2000.

[25]

J. R Lorch and A. J Smith. Improving dynamic voltage scheduling algorithms with pace. In Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, 2001.

Digital Library

[26]

M. Kistler M. Elnozahy and R. Rajamony. Energy conservation policies for web servers. In Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems, 2003.

Digital Library

[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]

H. Vin P. Goyal and H. Cheng. Start-time fair queuing: a scheduling algorithm for integrated services packet switching networks. In IEEE/ACM Transactions on Networks, 1997.

Digital Library

[29]

Q. Qiu and M. Pedram. Dynamic power management based on continuous-time markov decision processes. In Proceedings of the Design Automation Conference, 1999.

Digital Library

[30]

Erik Riedel, Mahesh Kallahala, and Ram Swaminathan. A framework for evaluating storage system security. In Proceedings of the FAST 2002 conference on File and Storage Technology, 2002.

Digital Library

[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 and Margaret Martonosi. Data compression algorithms for energy-constrained devices in delay tolerant networks. In Proceedings of the 4th international conference on Embedded networked sensor systems, 2006.

Digital Library

[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]

T. Abdelzaher K. Skadron V. Sharma, A. Thomas and Zhijjan Lu. Power-aware qos management in web servers. In Proceedings of the 24th IEEE Real-Time Systems Symposium, 2003.

Digital Library

[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]

T. Yu and K. J. Lin. Service Selection Algorithms for Web Services with End-to-End QoS Constraints. In Proceedings of the IEEE International conference on E-Commerce Technology, 2004.

Digital Library

[43]

Shlomo Zilberstein. Using anytime algorithms in intelligent systems. In American Association for Artificial Intelligence, 1996.

Cited By

Berg BHarchol-Balter M(2021)Optimal Scheduling of Parallel Jobs With Unknown Service RequirementsHandbook of Research on Methodologies and Applications of Supercomputing10.4018/978-1-7998-7156-9.ch003(18-40)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-7156-9.ch003
Berg BDorsman JHarchol-Balter M(2017)Towards Optimality in Parallel SchedulingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/31544991:2(1-30)Online publication date: 19-Dec-2017
https://dl.acm.org/doi/10.1145/3154499
Muppala SChen GZhou X(2014)Multi-tier service differentiation by coordinated learning-based resource provisioning and admission controlJournal of Parallel and Distributed Computing10.1016/j.jpdc.2014.01.00474:5(2351-2364)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1016/j.jpdc.2014.01.004
Show More Cited By

Recommendations

QDSL: a queuing model for systems with differential service levels
SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

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 ...
Energy efficient scheduling of real-time tasks on multi-core processors with voltage islands

This paper studies energy efficient scheduling of periodic real-time tasks on multi-core processors with voltage islands, in which cores are partitioned into multiple blocks (termed voltage islands) and each block has its own power source to supply ...
System-level power management using online learning

In this paper, we propose a novel online-learning algorithm for system-level power management. We formulate both dynamic power management (DPM) and dynamic voltage-frequency scaling problems as one of workload characterization and selection and solve ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 36, Issue 1

SIGMETRICS '08

June 2008

469 pages

ISSN:0163-5999

DOI:10.1145/1384529

Issue’s Table of Contents

SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems
June 2008
486 pages
ISBN:9781605580050
DOI:10.1145/1375457
General Chair:
Zhen Liu
IBM T. J. Watson Research Center, USA
,
Program Chairs:
Vishal Misra
Columbia University, USA
,
Prashant Shenoy
University of Massachusetts, USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 June 2008

Published in SIGMETRICS Volume 36, Issue 1

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
355
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Berg BHarchol-Balter M(2021)Optimal Scheduling of Parallel Jobs With Unknown Service RequirementsHandbook of Research on Methodologies and Applications of Supercomputing10.4018/978-1-7998-7156-9.ch003(18-40)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-7156-9.ch003
Berg BDorsman JHarchol-Balter M(2017)Towards Optimality in Parallel SchedulingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/31544991:2(1-30)Online publication date: 19-Dec-2017
https://dl.acm.org/doi/10.1145/3154499
Muppala SChen GZhou X(2014)Multi-tier service differentiation by coordinated learning-based resource provisioning and admission controlJournal of Parallel and Distributed Computing10.1016/j.jpdc.2014.01.00474:5(2351-2364)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1016/j.jpdc.2014.01.004
Muppala SZhou XChen G(2012)Multi-tier Service DifferentiationProceedings of the 2012 IEEE 18th International Conference on Parallel and Distributed Systems10.1109/ICPADS.2012.20(69-76)Online publication date: 17-Dec-2012
https://dl.acm.org/doi/10.1109/ICPADS.2012.20
Balsamo SMarin AStojic I(2014)Optimisation of Servers with Different Quality of ServicesProceedings of the 2014 IEEE 22nd International Symposium on Modelling, Analysis & Simulation of Computer and Telecommunication Systems10.1109/MASCOTS.2014.26(142-151)Online publication date: 9-Sep-2014
https://dl.acm.org/doi/10.1109/MASCOTS.2014.26
Govindan SChoi JUrgaonkar BSivasubramaniam ABaldini ASchröder-Preikschat WWilkes JIsaacs R(2009)Statistical profiling-based techniques for effective power provisioning in data centersProceedings of the 4th ACM European conference on Computer systems10.1145/1519065.1519099(317-330)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1145/1519065.1519099
Kumar PDesai M(2009)Learning based address mapping for improving the performance of memory subsystems2009 IEEE International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems10.1109/MASCOT.2009.5366234(1-9)Online publication date: Sep-2009
https://doi.org/10.1109/MASCOT.2009.5366234
Kumar DOlshefski DLi Zhang (2009)Connection and performance model driven optimization of pageview response time2009 IEEE International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems10.1109/MASCOT.2009.5366184(1-10)Online publication date: Sep-2009
https://doi.org/10.1109/MASCOT.2009.5366184

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents