Large Deviations of Queues Sharing a Randomly Time-Varying Server |
| |
Authors: | Alexander L Stolyar |
| |
Institution: | (1) Bell Labs, Alcatel-Lucent, 600 Mountain Ave., 2C-322, MurrayHill, NJ 07974, USA |
| |
Abstract: | We consider a discrete-time 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
|
(0.1) |
where Q
i
is the length of the 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 (0.1) under any scheduling rule, and of the lower bound on (0.1) under
the exponential (EXP) rule. We prove that the two bounds match, thus proving optimality of the EXP rule. 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 the large deviations
regime. To overcome this, we introduce and prove a refined sample path large deviations principle, or refined Mogulskii theorem, which is of independent interest.
|
| |
Keywords: | Queueing networks Dynamic scheduling Sample path large deviations principle Refined Mogulskii theorem Local fluid limit Time-varying server Quality of service Exponential (EXP) rule |
本文献已被 SpringerLink 等数据库收录! |
|