Many-sources delay asymptotics with applications to priority queues

Sanjay Shakkottai, R. Srikant

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper, we study discrete-time priority queueing systems fed by a large number of arrival streams. We first provide bounds on the actual delay asymptote in terms of the virtual delay asymptote. Then, under suitable assumptions on the arrival process to the queue, we show that these asymptotes are the same. As an application of this result, we then consider a priority queueing system with two queues. Using the earlier result, we derive an upper bound on the tail probability of the delay. Under certain assumptions on the rate function of the arrival process, we show that the upper bound is tight. We then consider a system with Markovian arrivals and numerically evaluate the delay tail probability and validate these results with simulations.

Original languageEnglish (US)
Pages (from-to)183-200
Number of pages18
JournalQueueing Systems
Volume39
Issue number2-3
DOIs
StatePublished - Oct 2001

Keywords

  • Large deviations waiting time
  • Many-sources scaling
  • Priority queues

ASJC Scopus subject areas

  • Statistics and Probability
  • Computer Science Applications
  • Management Science and Operations Research
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Many-sources delay asymptotics with applications to priority queues'. Together they form a unique fingerprint.

Cite this