TY - GEN

T1 - Large deviations of queues under qos scheduling algorithms

AU - Stolyar, Aleksandr

PY - 2006/1/1

Y1 - 2006/1/1

N2 - We consider a model where multiple queues are served by a server whose capacity varies randomly and asynchronously with respect to different queues. The problem is to optimally control large deviations of the queues in the following sense: find a scheduling rule maximizing min i h lim n!1 1 n log P (aiQi n) i , (1) where Qi is the length of i-th queue in a stationary regime, and ai 0 are parameters. Thus, we seek to maximize the minimum of the exponential decay rates of the tails of distributions of weighted queue lengths aiQi. We give a characterization of the upper bound on (1) under any scheduling rule, and of the lower bound on (1) 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 not asymptotically 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.

AB - We consider a model where multiple queues are served by a server whose capacity varies randomly and asynchronously with respect to different queues. The problem is to optimally control large deviations of the queues in the following sense: find a scheduling rule maximizing min i h lim n!1 1 n log P (aiQi n) i , (1) where Qi is the length of i-th queue in a stationary regime, and ai 0 are parameters. Thus, we seek to maximize the minimum of the exponential decay rates of the tails of distributions of weighted queue lengths aiQi. We give a characterization of the upper bound on (1) under any scheduling rule, and of the lower bound on (1) 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 not asymptotically 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.

UR - http://www.scopus.com/inward/record.url?scp=84940654094&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84940654094&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84940654094

T3 - 44th Annual Allerton Conference on Communication, Control, and Computing 2006

SP - 96

EP - 105

BT - 44th Annual Allerton Conference on Communication, Control, and Computing 2006

PB - University of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering

T2 - 44th Annual Allerton Conference on Communication, Control, and Computing 2006

Y2 - 27 September 2006 through 29 September 2006

ER -