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

DOI10.1007/S11134-014-9401-2zbMATH Open1309.60085arXiv1403.2400OpenAlexW3103465943MaRDI QIDQ475139FDOQ475139

Authors: Jinho Baik, Raj Rao Nadakuditi 

Publication date: 25 November 2014

Published in: Queueing Systems (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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)