TY - GEN

T1 - On optimal routing in overloaded parallel queues

AU - Li, Bin

AU - Eryilmaz, Atilla

AU - Srikant, R.

AU - Tassiulas, Leandros

PY - 2013

Y1 - 2013

N2 - We consider the problem of routing Bernoulli arrivals to parallel queues, where each queue provides service according to an independent Bernoulli process. We assume that the total arrival rate exceeds the sum of the service rates of the queues. Since such a queueing system is unstable, the vector of queue lengths does not have a well-defined stationary distribution. However, one metric which can be used to compare routing policies is the amount of unused service in the system. To lower-bound the cumulative unused service in the system, we present a "queue reversal" theorem for a single-server queue with independent and identically distributed (i.i.d.) arrivals and i.i.d. services: Assuming that the queue is initially empty, the expected cumulative unused service is equal to the expected queue length in a queue where the arrivals and services are reversed. Thus, the expected cumulative unused service in the unstable system is equal to the expected queue length in a stable system, which can be calculated. Using this result for a single-server queue, we obtain a lower bound on the expected unused service in the parallel queueing system for any feasible routing policy.We then compare this lower bound to the performance of two simple routing policies: Randomized and Join-the-Shortest Queue Routing.

AB - We consider the problem of routing Bernoulli arrivals to parallel queues, where each queue provides service according to an independent Bernoulli process. We assume that the total arrival rate exceeds the sum of the service rates of the queues. Since such a queueing system is unstable, the vector of queue lengths does not have a well-defined stationary distribution. However, one metric which can be used to compare routing policies is the amount of unused service in the system. To lower-bound the cumulative unused service in the system, we present a "queue reversal" theorem for a single-server queue with independent and identically distributed (i.i.d.) arrivals and i.i.d. services: Assuming that the queue is initially empty, the expected cumulative unused service is equal to the expected queue length in a queue where the arrivals and services are reversed. Thus, the expected cumulative unused service in the unstable system is equal to the expected queue length in a stable system, which can be calculated. Using this result for a single-server queue, we obtain a lower bound on the expected unused service in the parallel queueing system for any feasible routing policy.We then compare this lower bound to the performance of two simple routing policies: Randomized and Join-the-Shortest Queue Routing.

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

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

U2 - 10.1109/CDC.2013.6759892

DO - 10.1109/CDC.2013.6759892

M3 - Conference contribution

AN - SCOPUS:84902329276

SN - 9781467357173

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 262

EP - 267

BT - 2013 IEEE 52nd Annual Conference on Decision and Control, CDC 2013

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 52nd IEEE Conference on Decision and Control, CDC 2013

Y2 - 10 December 2013 through 13 December 2013

ER -