Large Deviations of Queues Sharing a Randomly Time-varying Server

We consider a model where multiple queues, each with its own exogenous arrival process, are served by a server whose capacity varies randomly and asynchronously with respect to different queues. This model is primarily motivated by the problem of efficient scheduling of transmissions of multiple data flows sharing a wireless channel. We address the following problem of controlling large deviations of the queues: find a scheduling rule, which is optimal in the sense of maximizing r = min_i [lim_{n->infinity} (1/n) log P(a_i Q_i > n)], where $Q_i$ is the length of i-th queue in a stationary regime, and a_i>0 are parameters. Thus, we seek to maximize the minimum of the exponential decay rates of the tails of distributions of weighted queue lengths a_i Q_i. We give a characterization of the upper bound on r under any scheduling rule, and of the lower bound on r under the 'exponential' (EXP) rule. For the case of two queues, we prove that the two bounds match, thus proving optimality of EXP rule in this case. The EXP rule is very parsimonious in that it does not require any "pre-computation" of its parameters, and uses only current state of the queues and of the server. The EXP rule is not invariant with respect to scaling of the queues, which complicates its analysis in large deviations regime. To overcome this, we introduce and prove a refined sample path large deviations principle, or refined Mogulsky theorem, which is of independent interest. This report is a revised and extended version of report ITD-06-47050R