Transitory Queueing Networks

Harsha Honnappa, Rahul JainarXiv 2017 · DOI · arXiv

Introduction

Classical queueing theory, epitomized by Jackson networks, has long relied on two fundamental assumptions: stationarity and Markovian dynamics. Stationarity assumes that a system eventually reaches a steady state over an infinite time horizon, while Markovian dynamics utilize memoryless processes, such as Poisson arrivals, to simplify mathematical modeling. However, many real-world operational environments—ranging from a four-hour manufacturing shift to a specific computing task or a hospital clinic's daily operation—do not conform to these assumptions. These systems are "transitory," characterized by time-varying arrival and service rates and a finite number of jobs processed over a fixed horizon.

In such settings, the "bottleneck" of the system is rarely fixed; it shifts between nodes as the workload evolves. Analyzing these networks is mathematically challenging because standard steady-state tools are inapplicable. This paper introduces a rigorous framework for "transitory queueing networks," providing fluid and diffusion approximations to analyze the "number-in-system" metric for non-stationary, non-Markovian environments.

Methodology: Population Acceleration Scaling

To analyze these complex dynamics, the authors employ a technique known as population acceleration scaling. This approach considers a sequence of networks where the number of external arrivals ($n$) scales toward infinity, while the service processes are accelerated proportionally. This scaling allows for the derivation of two primary limits:

  1. Fluid Limit (FSLLN): Using the Functional Strong Law of Large Numbers, the authors derive a deterministic "fluid" model that describes the average behavior of queue lengths. This provides a first-order approximation of the system's trajectory.
  2. Diffusion Limit (FCLT): Using the Functional Central Limit Theorem, the authors capture the stochastic variability, or "noise," around the fluid average. This second-order approximation is essential for understanding performance fluctuations and reliability.

A significant mathematical contribution of this work is the application of Directional Derivative Oblique Reflection Maps. While standard models use simple reflection maps to ensure queue lengths remain non-negative, transitory networks with time-varying rates require a more sophisticated approach to handle complex boundaries. Furthermore, the authors generalize one-dimensional Brownian bridges into multidimensional versions to accurately model the arrival processes of a finite job pool.

Key Insights: The Shifting Bottleneck and State-Space Collapse

One of the paper's most salient findings is the formalization of the shifting bottleneck. In stationary systems, a bottleneck is a static property of the network's capacity. In transitory networks, a node may act as a bottleneck for a specific duration before "clearing" and passing the congestion downstream.

The research demonstrates a phenomenon known as state-space collapse. Under specific conditions, the behavior of a complex network mathematically simplifies to resemble a much smaller system dominated by its current bottleneck. This simplification is crucial for real-time operational monitoring.

The authors also address topological challenges. Standard convergence (the $J_1$ topology) often fails in transitory models because limit processes can exhibit unmatched discontinuities. By utilizing the more flexible $M_1$ topology, the authors successfully establish convergence for tandem (series) networks, providing a robust mathematical foundation for their approximations.

Results and Operational Implications

The paper successfully establishes the FSLLN and FCLT for transitory networks without requiring Markovian assumptions. For tandem networks with unimodal traffic distributions, the authors explicitly identify how the bottleneck process evolves. They prove that the distribution of the total sojourn time—the time a job spends in the system—is asymptotically equal to the delay at the bottleneck nodes.

From an operational perspective, this work provides a formal definition of a "transitory bottleneck" based on whether the diffusion workload process is non-zero. This allows managers to predict when and where congestion will occur, enabling more precise resource allocation in time-critical environments.

Limitations and Future Directions

While the paper makes significant strides, several challenges remain:

  • General Topology: Proving full process-level convergence for arbitrary network topologies (beyond tandem networks) remains difficult due to the complexity of directional derivatives.
  • Polling Systems: Future research could extend these results to polling networks, where a single server moves between multiple queues.
  • Percolation Theory: The authors suggest a potential link between transitory models and "last passage percolation," which could offer novel insights into manufacturing line performance.
  • Traffic Correlation: The current model assumes certain independence in arrival counts; future work could explore the impact of "strong negative association" in specific traffic models.

By bridging the gap between theoretical queueing models and the realities of finite-horizon operations, this paper provides a vital toolkit for analyzing the next generation of dynamic service and manufacturing systems.

Summary updated

Abstract

Queueing networks are notoriously difficult to analyze sans both Markovian and stationarity assumptions. Much of the theoretical contribution towards performance analysis of time-inhomogeneous single class queueing networks has focused on Markovian networks, with the recent exception of work in Liu and Whitt (2011) and Mandelbaum and Ramanan (2010). In this paper, we introduce transitory queueing networks as a model of inhomogeneous queueing networks, where a large, but finite, number of jobs arrive at queues in the network over a fixed time horizon. The queues offer FIFO service, and we assume that the service rate can be time-varying. The non-Markovian dynamics of this model complicate the analysis of network performance metrics, necessitating approximations. In this paper we develop fluid and diffusion approximations to the number-in-system performance metric by scaling up the number of external arrivals to each queue, following Honnappa et al. (2014). We also discuss the implications for bottleneck detection in tandem queueing networks.
BibTeX
@misc{honnappa2017transitory,
  author = {Harsha Honnappa and Rahul Jain},
  title = {{Transitory Queueing Networks}},
  year = {2017},
  eprint = {1708.05921},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1708.05921},
}
Figure