On Gaussian Limits and Large Deviations for Queues Fed by High Intensity Randomly Scattered Traffic

Peter W. Glynn, Harsha HonnappaarXiv 2017 · DOI · arXiv

TL;DR

This paper introduces a new traffic model called "random scattering" for analyzing queues, particularly in high-intensity scenarios. It provides powerful mathematical tools (Gaussian limits and large deviations) to understand queue behavior, offering a more realistic and simplified approach to analyzing workload dynamics compared to existing methods.

What Problem Does This Paper Address?

The paper tackles the challenge of accurately modeling and analyzing queueing systems, specifically when a large number of customers arrive at random, independent times. Traditional queueing models often rely on renewal processes, which assume arrivals are independent and identically distributed over time, but don't fully capture the nuances of "random scattering" traffic. This type of traffic, where customers make independent decisions about when to join a queue (like website subscribers or cafeteria patrons), can lead to complex correlations and behaviors that aren't well-represented by simpler models. The authors aim to bridge this gap by developing mathematical tools to analyze the workload in such systems, especially under high-intensity conditions where the system is heavily utilized.

Methods

The paper employs two primary analytical techniques:

  • Gaussian Process Approximations: The authors derive approximations for the workload process using Gaussian processes. This is done under a "high intensity" asymptotic scale, meaning they consider scenarios where the number of customers (n) becomes very large. They then analyze the transient (time-dependent) distribution of these Gaussian approximations.
  • Large Deviations Principles: The paper investigates "rare event paths" of the workload, which are extreme deviations from the typical behavior. They prove a large deviations principle for the workload in the same high-intensity regime, allowing them to understand the probability of these rare, but potentially significant, events.

Additionally, they provide exact asymptotics for the Gaussian approximations, which helps to validate and refine their models. The analysis is extended to both a single-period model and a periodic high-intensity traffic model.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on mathematical modeling and analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Random Scattering Traffic is Distinct: The paper highlights that "random scattering" traffic, due to its inherent negative correlations, exhibits performance behaviors qualitatively different from conventional renewal-type traffic.
  • Gaussian Limits Offer Tractability: By approximating the workload with Gaussian processes, the authors make complex queueing dynamics more mathematically tractable, especially in high-intensity regimes.
  • Rare Events Have Non-Linear Paths: The "rare event" paths associated with large workload exceedances are shown to be non-linear, a significant departure from piecewise linear paths seen in conventional models.
  • Uniform Scattering Simplifies Analysis: The uniform distribution of arrival times, while having practical applications (e.g., concert arrival games, distributed sensor networks), also simplifies the mathematical derivation of Gaussian limits, leading to a reflected Gaussian process.
  • Periodic Traffic Extends the Model: The paper successfully extends the analysis to periodic high-intensity traffic, demonstrating the robustness of their methods.

Key Results

  • Gaussian Approximations: The paper establishes Gaussian process approximations for the workload in RS/G/1 queues under high intensity.
  • Large Deviations for Rare Events: A large deviations principle is proven for the workload, quantifying the probability of extreme workload events.
  • Exact Asymptotics: Exact asymptotic formulas are derived for the Gaussian approximations, providing precise characterizations of queue behavior.
  • Transient Distribution Computations: For specific cases (like uniform scattering), the transient distribution of the workload is computed.
  • Characterization of Steady-State Distributions: The paper characterizes steady-state distributions under different conditions for service requirements and service rates, showing that they can be translated Weibull distributions, unlike the negative exponential distribution seen in some G/G/1 queues.

Limitations and Future Work

  • "Near Balanced" Case: While the paper discusses general approximations, some specific results are derived for the "near balanced" case where the service effort is close to the offered load. The authors note that exact balance is infrequent in real-world scenarios.
  • Complexity of General Drift: Deriving the transient distribution for a general reflected Brownian Bridge process with a time-varying drift function is noted as non-trivial and outside the scope of the current paper.
  • Generalization to Multi-Period Models: The paper mentions that Section 7 discusses the generalization to equilibrium analysis of the multi-period version of the RS/G/1 model, suggesting this as a direction for future work.
  • Practical Calibration: While the authors suggest their models can be calibrated to real-world data, the paper itself focuses on theoretical development rather than demonstrating this calibration.

Summary updated

Abstract

We study a single server FIFO queue that offers general service. Each of n customers enter the queue at random time epochs that are inde- pendent and identically distributed. We call this the random scattering traffic model, and the queueing model RS/G/1. We study the workload process associated with the queue in two different settings. First, we present Gaussian process approximations in a high intensity asymptotic scale and characterize the transient distribution of the approximation. Second, we study the rare event paths of the workload by proving a large deviations principle in the same high intensity regime. We also obtain exact asymptotics for the Gaussian approximations developed prior. This analysis significantly extends and simplifies recent work in [1] on uniform population acceleration asymptotics to the queue length and workload in the RS/G/1 queue.
BibTeX
@misc{glynn2017gaussian,
  author = {Peter W. Glynn and Harsha Honnappa},
  title = {{On Gaussian Limits and Large Deviations for Queues Fed by High Intensity Randomly Scattered Traffic}},
  year = {2017},
  eprint = {1708.05584},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1708.05584},
}
Figure