Dynamic scheduling of parallel queues: queue-length asymptotics under heavy-tailed traffic

Abstract:

We consider the problem of scheduling a single server to N parallel queues. We analyze the impact of heavy-tailed traffic on the performance of various scheduling policies. As metric of performance we use the tail coefficient of the steady-state queue-lengths, i.e., the maximum order of finite moments. Determining the tail coefficient gives the rough asymptotic behavior of the steady-state queue-lengths.

First, we show that any nonpreemptive scheduling policy induces the worst possible tail coefficient on all steady-state queue-lengths. Under a preemptive priority policy, we show that the queues corresponding to arrivals with the heavier tails should be lower on the priority list. If the arrival rates are fairly `balanced', then round-robin provides a fair and immune to heavy tails candidate policy. This conclusion may be reversed if the arrival rates are `unbalanced'. The celebrated Max-Weight policy, similar to nonpreemptive policies, induces the worst possible tail coefficient on all steady-state queue-lengths. Finally, we compute the tail coefficients induced by Max-Weight-alpha, and show that this policy provides only partial remedy to the shortcomings of Max-Weight.

Joint work with Krishna Jagannathan, Eytan Modiano, and John Tsitsiklis

Biography:

Mihalis Markakis was born in Athens, Greece. He received the BS degree from the National Technical University of Athens, in 2005, and the MS degree from the University of Southern California, in 2008, both in electrical engineering. He is currently a graduate student at LIDS, MIT, working towards his PhD, under the supervision of professors Eytan Modiano and John Tsitsiklis. His research interests are in identifying and analyzing heavy-tailed phenomena on stochastic models, with particular focus on the impact of heavy-tailed traffic on queueing networks.