### 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 language | English (US) |
---|---|

Title of host publication | 2013 IEEE 52nd Annual Conference on Decision and Control, CDC 2013 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 262-267 |

Number of pages | 6 |

ISBN (Print) | 9781467357173 |

DOIs | |

State | Published - Jan 1 2013 |

Event | 52nd IEEE Conference on Decision and Control, CDC 2013 - Florence, Italy Duration: Dec 10 2013 → Dec 13 2013 |

### Publication series

Name | Proceedings of the IEEE Conference on Decision and Control |
---|---|

ISSN (Print) | 0191-2216 |

### Other

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

Country | Italy |

City | Florence |

Period | 12/10/13 → 12/13/13 |

### Fingerprint

### ASJC Scopus subject areas

- Control and Systems Engineering
- Modeling and Simulation
- Control and Optimization

### Cite this

*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