Batch latency analysis and phase transitions for a tandem of queues with exponentially distributed service times

DOI10.1007/S11134-014-9401-2MaRDI QIDQ475139zbMATH OpenOpenAlexFDO

Authors Jinho Baik, Raj Rao Nadakuditi

Publication date 25 November 2014

Published in Queueing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.2400

zbMATH Keywords

random matrix theoryphase transitionstandem queuesmulti-hop networksdirected last passage percolationlatency analysis

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Zero-one laws (60F20) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Abstract: We analyze the latency or sojourn time L(m,n) for the last customer in a batch of n customers to exit from the m-th queue in a tandem of m queues in the setting where the queues are in equilibrium before the batch of customers arrives at the first queue. We first characterize the distribution of L(m,n) exactly for every m and n, under the assumption that the queues have unlimited buffers and that each server has customer independent, exponentially distributed service times with an arbitrary, known rate. We then evaluate the first two leading order terms of the distributions in the large m and n limit and bring into sharp focus the existence of phase transitions in the system behavior. The phase transition occurs due to the presence of either slow bottleneck servers or a high external arrival rate. We determine the critical thresholds for the service rate and the arrival rate, respectively, about which this phase transition occurs; it turns out that they are the same. This critical threshold depends, in a manner we make explicit, on the individual service rates, the number of customers and the number of queues but not on the external arrival rate.

Recommendations

• Response Time Distribution in a Tandem Pair of Queues with Batch Processing
• Tandem queueing system with infinite and finite intermediate buffers and generalized phase-type service time distribution
• Tandem queues with subexponential service times and finite buffers
• Multi-server tandem queue with Markovian arrival process, phase-type service times, and finite buffers
• Bounds for the expected delays in some tandem queues

Cites work

• scientific article; zbMATH DE number 5943539 (Why is no real title available?)
• scientific article; zbMATH DE number 3117699 (Why is no real title available?)
• scientific article; zbMATH DE number 2046376 (Why is no real title available?)
• scientific article; zbMATH DE number 1789872 (Why is no real title available?)
• scientific article; zbMATH DE number 2162775 (Why is no real title available?)
• scientific article; zbMATH DE number 2174437 (Why is no real title available?)
• scientific article; zbMATH DE number 2212219 (Why is no real title available?)
• A remark on a theorem of Chatterjee and last passage percolation
• A scaling limit for queues in series
• A universality property for last-passage percolation paths close to the axis
• Airy kernel with two sets of parameters in directed percolation and random matrix theory
• Applied asymptotic analysis
• Asymptotic results on infinite tandem queueing networks
• Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
• Batch queues, reversibility and first-passage percolation
• Bounds for the expected delays in some tandem queues
• Current fluctuations for the totally asymmetric simple exclusion process
• Departures from many queues in series
• Eigenvalues of large sample covariance matrices of spiked population models
• Fluctuations of the extreme eigenvalues of finite rank deformations of random matrices
• Heavy tails in last-passage percolation
• Infinite wedge and random partitions
• Level-spacing distributions and the Airy kernel
• On the comparison of waiting times in tandem queues
• On the distribution of the largest eigenvalue in principal components analysis
• On the numerical evaluation of Fredholm determinants
• On the numerical evaluation of distributions in random matrix theory: a review
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Production systems engineering
• Queues, stores, and tableaux
• Random matrix theory
• Reduction Methods for Tandem Queuing Systems
• Scaling limit for the space-time covariance of the stationary totally asymmetric simple exclusion process
• Scaling properties of statistical end-to-end bounds in the network calculus.
• Shape fluctuations and random matrices
• Simple Bounds for Finite Single-Server Exponential Tandem Queues
• Spectral analysis of large dimensional random matrices
• The Distributions of Random Matrix Theory and their Applications
• The Kardar-Parisi-Zhang equation and universality class
• The Optimal Order of Service in Tandem Queues
• The diffusion approximation for tandem queues in heavy traffic
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• The interchangeability of ·/M/1 queues in series
• Tracy-Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices
• Waiting Times When Queues are in Tandem

Cited in

(1)

• Fluctuations at the edges of the spectrum of the full rank deformed GUE

This page was built for publication: Batch latency analysis and phase transitions for a tandem of queues with exponentially distributed service times

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q475139)