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. (Wireless systems
are the primary motivation.)
The problem is to find a
scheduling rule maximizing the minimum of the exponential decay rates
of the distributions of weighted queue lengths a_i Q_i in stationary
regime. (Q_i are queue lengths and a_i>0 are parameters.) We prove
optimality of the "EXP" scheduling rule, for arbitrary number of queues.
The
EXP rule is 'not' invariant with respect to scaling of the queues,
which complicates its large deviations analysis. To overcome this, we
introduce a refined sample path large deviations principle; and work
with local fluid limits, in addition to "conventional" fluid limits.