On the Tradeoff Of Average Delay, Average Service Cost, and Average Utility for Single Server Queues with Monotone Policies

Abstract

In this thesis, we study the tradeoff of average delay with average service cost and average utility for both continuous time and discrete time single server queueing models without and with admission control. The continuous time and discrete time queueing models that we consider are motivated by cross-layer models for point-to-point links with random packet arrivals and fading at slow and fast time scales. Our studies are motivated by the need to optimally tradeoff the average delay of the packets (a network layer performance measure) with the average service cost of transmitting the packets, e.g. the average power required for transmission (a physical layer performance measure) under a lower bound constraint on the average throughput, in various point-to-point communication scenarios. The tradeoff problems are studied for a class of monotone and stationary scheduling policies and under the assumption that the service cost rate and utility rate are respectively convex and concave functions of the service rate and arrival rate. We also consider the problem of optimally trading off the average delay and average error rate of randomly arriving message symbols which are transmitted over a noisy point-to-point link, in which case the service cost function is non-convex. The solutions to the tradeoff problems that we address in the thesis are asymptotic in nature, and are similar in spirit to the Berry-Gallager asymptotic bounds. It is intuitive that to keep a queue stable under a lower bound constraint on the average utility a minimum number of customers have to be served per unit time. This in turn implies that queue stability requires a minimum average service cost expenditure. In the thesis we obtain an asymptotic characterization of the minimum average delay for monotone stationary policies subject to an upper bound constraint on the average service cost and a lower bound constraint on the average utility, in the asymptotic regime where the average service cost constraint is made arbitrarily close to the above minimum average service cost. In the thesis, we obtain asymptotic lower bounds on the minimum average delay for the cases for which lower bounds were previously not known. The asymptotic characterization of the minimum average delay for monotone stationary policies, for both continuous time and discrete time models, is obtained via geometric bounds on the stationary probability of the queue length, in the above asymptotic regime. The restriction to monotone stationary policies enables us to obtain an intuitive explanation for the behaviour of the asymptotic lower bounds using the above geometric bounds on the stationary probability distribution of the queue length. The geometric bounds on the stationary probability of the queue length also lead to a partial asymptotic characterization of the structure of any optimal monotone stationary policy, in the above asymptotic regime, which was not available in previous work. Furthermore, the geometric bounds on the stationary probability can be extended to analyse the tradeoff problem in other scenarios, such as for other continuous time queueing models, multiple user communication models, queueing models with service time control, and queueing models with general holding costs. Usually, queueing models with integer valued queue evolution, are approximated by queueing models with real valued queue evolution and strictly convex service cost functions for analytical tractability. Using the asymptotic bounds, we show that for some cases the average delay does not grow to infinity in the asymptotic regime, although the approximate model suggests that the average delay does grow to infinity. In other cases where the average delay does grow to infinity in the asymptotic regime, our results illustrate that the tradeoff behaviour of the approximate model is different from that of the original integer valued queueing model unless the service cost function is modelled as the piecewise linear lower convex envelope of the service cost function for the original model.