### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | 44th Annual Allerton Conference on Communication, Control, and Computing 2006 |

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

Pages | 96-105 |

Number of pages | 10 |

ISBN (Electronic) | 9781604237924 |

State | Published - Jan 1 2006 |

Externally published | Yes |

Event | 44th Annual Allerton Conference on Communication, Control, and Computing 2006 - Monticello, United States Duration: Sep 27 2006 → Sep 29 2006 |

### Publication series

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

Volume | 1 |

### Other

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

Country | United States |

City | Monticello |

Period | 9/27/06 → 9/29/06 |

### Fingerprint

### ASJC Scopus subject areas

- Computer Science Applications
- Computer Networks and Communications

### Cite this

*44th Annual Allerton Conference on Communication, Control, and Computing 2006*(pp. 96-105). (44th Annual Allerton Conference on Communication, Control, and Computing 2006; Vol. 1). University of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering.