QDSL: A queuing model for systems with differential service levels

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. Coovriaht 2008 ACM.