On optimal routing in overloaded parallel queues

Bin Li, Atilla Eryilmaz, R. Srikant, Leandros Tassiulas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2013 IEEE 52nd Annual Conference on Decision and Control, CDC 2013
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages262-267
Number of pages6
ISBN (Print)9781467357173
DOIs
StatePublished - Jan 1 2013
Event52nd IEEE Conference on Decision and Control, CDC 2013 - Florence, Italy
Duration: Dec 10 2013Dec 13 2013

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0191-2216

Other

Other52nd IEEE Conference on Decision and Control, CDC 2013
CountryItaly
CityFlorence
Period12/10/1312/13/13

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint Dive into the research topics of 'On optimal routing in overloaded parallel queues'. Together they form a unique fingerprint.

  • Cite this

    Li, B., Eryilmaz, A., Srikant, R., & Tassiulas, L. (2013). On optimal routing in overloaded parallel queues. In 2013 IEEE 52nd Annual Conference on Decision and Control, CDC 2013 (pp. 262-267). [6759892] (Proceedings of the IEEE Conference on Decision and Control). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2013.6759892