Large deviations without principle: join the shortest queue
type: Item
instance of: scholarly article
title: Large deviations without principle: join the shortest queue
zbMATH Open document ID: 1084.60058
author: A. Ridder
author: Adam Shwartz
published in: Mathematical Methods of Operations Research
publication date: 2006-01-23T00:00:00Z
full work available at URL: 05003.pdf
review text: Let \(y_n = (y_n (t):t \in [0,T])\) for \(n = 0,1,\dots\) be stochastic processes with sample paths in \(D([0,T],R_+^K)\) (right continuous functions \([0,T] \to R_ + ^K \) with left limits; the space is equipped with the Skorokhod metric). The sequence \(\{ y_n \} \) is said to satisfy the large deviation principle with rate function \(I( \cdot )\) if \(I\) is nonnegative, lower semicontinuous, and for all \(x \in R_ + ^K \) and for all closed \(C \subset D([0,T],R_+^K)\): \[ \lim \sup_{n \to \infty } \frac{1} {n}\log P_x (y_n \in C) \leqslant -\inf_{\varphi \in C:\varphi (0) = x} I(\varphi ), \] and for all \(x \in R_+^K \) and for all open \(G \subset D([0,T],R_+^K)\): \[ \lim \inf_{n \to \infty } \frac{1} {n}\log P_x (y_n \in G) \geqslant -\inf_{\varphi \in G:\varphi (0) = x} I(\varphi ). \] (The subscript \(x\) means conditioning on \(y_n (0)\) so that \(\lim_{n \to \infty } y_n (0) = x\)). The paper studies a system of queues with exponential servers, which share an arrival stream. Arrivals are routed to the (weighted) shortest queue. The goal is to derive large deviation type estimates for the most likely behavior, the most likely path to overflow and the probability of overflow.
reviewed by: Oleg K. Zakusilo
Mathematics Subject Classification ID: 60K25
Mathematics Subject Classification ID: 90B22
Mathematics Subject Classification ID: 90B18
zbMATH DE Number: 5000143
zbMATH Keywords: most likely behavior
zbMATH Keywords: large deviation principle
MaRDI profile type: Publication
OpenAlex ID: W2123381698
Wikidata QID: Q59313615
cites work: Large deviations and queueing networks: Methods for rate function identification
cites work: Large deviations analysis of the generalized processor sharing policy
cites work: Sample path large deviations and intree networks
cites work: Large deviations for subsampling from individual sequences
cites work: The Large Deviation Principle for a General Class of Queueing Systems I
cites work: Join the shortest queue: Stability and exact asymptotics
cites work: A large deviation principle with queueing applications
cites work: Big queues.
cites work: Large deviations for processes with discontinuous statistics
cites work: Rare event analysis of the state frequencies of a large number of Markov chains
cites work: Optimal trajectory to overflow in a queue fed by a large number of sources
cites work: Q4895173
cites work: Functional Large Deviation Principles for Waiting and Departure Processes
cites work: Q4865050
cites work: Large Deviations with Diminishing Rates
cites work: Control of end-to-end delay tails in a multiclass network: LWDF discipline optimality
cites work: Largest weighted delay first scheduling: Large deviations and optimality
cites work: Sample path large deviations for queues with many inputs
cites work: A new technique for analyzing large traffic systems
DBLP publication ID: journals/mmor/RidderS05
DOI: 10.1007/S00186-005-0037-1
Recommended article: A Large Deviation Principle for Join the Shortest Queue
Recommended article: Large deviations for join the shorter queue
Recommended article: Many-server asymptotics for join-the-shortest-queue: large deviations and rare events
Recommended article: Join the shortest queue: Stability and exact asymptotics
Recommended article: A large deviation principle with queueing applications
Recommended article: Join the shortest queue among \(k\) parallel queues: tail asymptotics of its stationary distribution
Recommended article: Join-the-shortest queue diffusion limit in Halfin-Whitt regime: tail asymptotics and scaling of extrema
Recommended article: Join the Shortest Queue with Many Servers. The Heavy-Traffic Asymptotics
description: scientific article; zbMATH DE number 5000143