Computationally Efficient Simulation of Queues: The R Package queuecomputer

Anthony Ebert, Paul Wu, Kerrie L. Mengersen, Fabrizio RuggeriJ. Stat. Softw 2020 · OpenReview

TL;DR

This paper introduces queuecomputer, an R package that implements a novel, computationally efficient algorithm (Queue Departure Computation - QDC) for simulating complex queueing systems. The QDC algorithm achieves remarkable speedups of over two orders of magnitude compared to existing discrete event simulation (DES) packages, making it ideal for applications like Approximate Bayesian Computation where rapid simulation is crucial.

What Problem Does This Paper Address?

Many real-world systems, from IT infrastructure like MapReduce clusters and web servers to service systems like hospitals, call centers, and airports, can be modeled as queueing networks. Accurately modeling these systems often requires inferring parameters from data. However, simulating complex queueing networks with existing tools can be computationally prohibitive, hindering parameter inference, especially within methods like Approximate Bayesian Computation (ABC). This paper addresses the need for a faster, more efficient simulation method that can handle general queueing systems and networks.

Methods

The core of the paper is the introduction of the Queue Departure Computation (QDC) algorithm. Unlike traditional Discrete Event Simulation (DES) approaches that track system state and event lists, QDC focuses on efficiently calculating departure times. For a fixed number of servers (K), QDC sorts arrival and service times and maintains a K-length vector representing when each server becomes free. It iteratively determines the earliest available server for each arriving customer and calculates their departure time. This approach is O(nK) for n customers and K servers, significantly more efficient than some older O(n²) methods.

The paper also extends QDC to handle dynamic queueing systems where the number of servers can change over time (K(t)). Two algorithms are presented: a conditional approach for step-function changes in server availability and an unconditional approach for more general server availability patterns. These algorithms are implemented in the queuecomputer R package.

Datasets

The paper does not introduce new datasets. Instead, it uses synthetic data generated for simulation purposes to validate its methods and compare performance against existing packages. For example, it simulates M/M/2 and M/M/3 queueing systems with varying numbers of customers. A synthetic dataset of passengers for an airport terminal scenario is also used to demonstrate the package's capabilities in modeling complex networks.

Key Insights and Ideas

  • Decoupling Sampling and Computation: A major advantage of queuecomputer is that it "decouples" the statistical sampling of arrival and service times from the queue computation. Users can generate these times using any method they prefer, and queuecomputer then deterministically simulates the queue. This is a significant departure from packages like simmer and simpy where sampling is integrated into the simulation loop.
  • Computational Efficiency is Paramount for ABC: The paper strongly emphasizes that the speed of QDC is crucial for enabling Approximate Bayesian Computation (ABC) for complex queueing models. ABC relies on repeated simulations to estimate parameters, and the efficiency of queuecomputer makes this feasible for previously intractable problems.
  • Simplicity and Modularity: The QDC algorithm is presented as conceptually simpler and more memory-efficient than some existing methods. The queuecomputer package is designed to be modular and integrates well with other R packages like dplyr, facilitating the construction of complex queueing networks.

Key Results

  • Massive Speedups: The queuecomputer package demonstrates speedups of 35x to 1000x compared to simpy and 50x to 300x compared to simmer for simulating M/M/2 queues with up to 10⁶ customers. For 10⁷ customers, queuecomputer can simulate in under a second.
  • Accurate Replication: The package successfully replicates exact departure times from simmer and simpy for a M/M/2 queue, validating its accuracy. It also accurately reproduces theoretical equilibrium results for M/M/2 and M/M/3 queues.
  • Generalizability: The QDC algorithm can simulate a very general class of queueing systems: G(t)/G(t)/K(t)/∞/n/FCFS, meaning it can handle time-varying arrival and service processes, a variable number of servers, and general distributions.
  • Modular Network Simulation: The paper demonstrates how queuecomputer can be combined with dplyr to easily build and simulate complex queueing networks, including tandem, parallel, and fork/join topologies, as shown in the airport terminal example.

Limitations and Future Work

  • Condition for Dynamic Server Changes: Algorithm 2 for changing server numbers has a condition (si < min(x_{l+1} - x_l)) that limits the duration of service times relative to epoch changes. If this condition doesn't hold, a less efficient unconditional algorithm (Algorithm 4) must be used.
  • Future Work: The authors explicitly mention that future work will address embedding queue simulations within ABC algorithms. They also suggest that the speedups observed are likely to hold for other arrival and service distribution types due to the nature of how non-negative random variables can be decomposed.

Summary updated

Abstract

Large networks of queueing systems model important real-world systems such as MapReduce clusters, web-servers, hospitals, call centers and airport passenger terminals. To model such systems accurately, we must infer queueing parameters from data. Unfortunately, for many queueing networks there is no clear way to proceed with parameter inference from data. Approximate Bayesian computation could offer a straightforward way to infer parameters for such networks if we could simulate data quickly enough. We present a computationally efficient method for simulating from a very general set of queueing networks with the R package queuecomputer. Remarkable speedups of more than 2 orders of magnitude are observed relative to the popular DES packages simmer and simpy. We replicate output from these packages to validate the package. The package is modular and integrates well with the popular R package dplyr. Complex queueing networks with tandem, parallel and fork/join topologies can easily be built with these two packages together. We show how to use this package with two examples: a call center and an airport terminal.
BibTeX
@article{ebert2020computationally,
  author = {Anthony Ebert and Paul Wu and Kerrie L. Mengersen and Fabrizio Ruggeri},
  title = {{Computationally Efficient Simulation of Queues: The R Package queuecomputer}},
  journal = {J. Stat. Softw.},
  year = {2020},
  url = {https://openreview.net/forum?id=yfbM5Fx3je},
}
Figure