EUVIMEDEUVIMED entdecken
Crossref

Exponential Tail Bounds on Queues: A Confluence of Non- Asymptotic Heavy Traffic and Large Deviations

Prakirt Raj Jhunjhunwala, Daniela Hurtado-Lange, Siva Theja Maguluri

ACM SIGMETRICS Performance Evaluation Review · 22.02.2024 · 51 (4) · 18-19

DOI: 10.1145/3649477.3649488 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM SIGMETRICS Performance Evaluation Review, online erschienen am 23.02.2024. Verfasst von Prakirt Raj Jhunjhunwala und 2 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 3 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In general, obtaining the exact steady-state distribution of queue lengths is not feasible. Therefore, we focus on establishing bounds for the tail probabilities of queue lengths. We examine queueing systems under Heavy Traffic (HT) conditions and provide exponentially decaying bounds for the probability P(∈q > x), where ∈ is the HT parameter denoting how far the load is from the maximum allowed load. Our bounds are not limited to asymptotic cases and are applicable even for finite values of ∈, and they get sharper as ∈ - 0. Consequently, we derive non-asymptotic convergence rates for the tail probabilities. Furthermore, our results offer bounds on the exponential rate of decay of the tail, given by -1/2 log P(∈q > x) for any finite value of x. These can be interpreted as non-asymptotic versions of Large Deviation (LD) results. To obtain our results, we use an exponential Lyapunov function to bind the moment-generating function of queue lengths and apply Markov's inequality. We demonstrate our approach by presenting tail bounds for a continuous time Join-the-shortest queue (JSQ) system.

Zitieren

APA

Jhunjhunwala, P. R., Hurtado-Lange, D., & Maguluri, S. T. (2024). Exponential Tail Bounds on Queues: A Confluence of Non- Asymptotic Heavy Traffic and Large Deviations. ACM SIGMETRICS Performance Evaluation Review, 51(4), 18-19. https://doi.org/10.1145/3649477.3649488

Vancouver

Jhunjhunwala PR, Hurtado-Lange D, Maguluri ST. Exponential Tail Bounds on Queues: A Confluence of Non- Asymptotic Heavy Traffic and Large Deviations. ACM SIGMETRICS Performance Evaluation Review. 2024;51(4):18-19. doi:10.1145/3649477.3649488

BibTeX
@article{Jhunjhunwala2024,
  author = {Jhunjhunwala, Prakirt Raj and Hurtado-Lange, Daniela and Maguluri, Siva Theja},
  title = {Exponential Tail Bounds on Queues: A Confluence of Non- Asymptotic Heavy Traffic and Large Deviations},
  journal = {ACM SIGMETRICS Performance Evaluation Review},
  year = {2024},
  volume = {51},
  number = {4},
  pages = {18--19},
  doi = {10.1145/3649477.3649488}
}
Kostenlos starten →