Learning Deep Generative Models for Queuing Systems

César Ojeda, Kostadin Cvejoski, Bogdan Georgiev, Christian Bauckhage, Jannis Schuecker, Ramsés J. SánchezAAAI 2021 · OpenReview

Abstract: Modern society is heavily dependent on large scale client-server systems with applications ranging from Internet and Communication Services to sophisticated logistics and deployment of goods. To maintain and improve such a system, a careful study of client and server dynamics is needed – e.g. response/service times, average number of clients at given times, etc. To this end, one traditionally relies, within the queuing theory formalism, on parametric analysis and explicit distribution forms. However, parametric forms limit the model’s expressiveness and could struggle on extensively large datasets. We propose a novel data-driven approach towards queuing systems: the Deep Generative Service Times. Our methodology delivers a flexible and scalable model for service and response times. We leverage the representation capabilities of Recurrent Marked Point Processes for the temporal dynamics of clients, as well as Wasserstein Generative Adversarial Network techniques, to learn deep generative models which are able to represent complex conditional service time distributions. We provide extensive experimental analysis on both empirical and synthetic datasets, showing the effectiveness of the proposed models.

Introduction

Queuing theory is the mathematical study of waiting lines, essential for optimizing everything from ride-sharing platforms to web server clusters. Traditionally, researchers have relied on parametric models, such as Poisson processes, to describe customer arrivals and service durations. While mathematically elegant, these classical models often struggle with the complexities of real-world data. They are frequently too rigid to capture multi-modal distributions or "heavy tails" (rare but extremely long delays), and they often fail to scale to the millions of data points generated by modern digital services.

Presented at AAAI-21, this research introduces Deep Generative Service Times (DGST), a non-parametric framework that bridges classical queuing theory and modern deep learning. By moving away from rigid mathematical assumptions, DGST captures the "messy" behavior of real-world systems while maintaining scalability and context-awareness.

Methodology: RPP and RAS

The authors decouple the queuing problem into two distinct but interconnected stages: modeling when requests arrive and modeling how long they take to be serviced.

1. Arrival Times Modeling

The system uses a Recurrent Point Process (RPP) to encode the history of customer arrivals into a hidden state ($h^a_i$). This hidden state effectively captures the current "tempo" or load of the system—distinguishing between periods of high-intensity bursts and quiet lulls.

2. Service Times Modeling (RAS)

To model service duration, the authors introduce Recurrent Adversarial Service Times (RAS). This is a generative model based on a Wasserstein GAN (WGAN) that incorporates three primary inputs: the hidden state from the arrival model (representing system history), covariates (specific request metadata like GPS coordinates), and random noise. By utilizing a Recurrent Neural Network (RNN) within the generator, the model accounts for non-Markovian effects, where current service times are influenced by how previous requests were handled.

The architecture of the proposed RPP and RAS models compared to simpler neural service (NS) and adversarial service (AS) variants.

Experimental Evaluation

The model was evaluated on several massive real-world datasets to test its versatility:

  • Stackoverflow: 20 million questions, measuring the delay until an accepted answer is provided.
  • Github: 1.5 million issues, measuring the time from creation to closure.
  • New York City Taxi: 11 million trips, where service time is the ride duration.

Key Results and Insights

The RAS model consistently outperformed both classical parametric baselines and non-recurrent adversarial models across all metrics. A key finding was that conditioning service times on arrival history significantly improves accuracy; if arrivals are accelerating, the system's response behavior typically shifts.

Distribution Accuracy

In Kolmogorov-Smirnov (KS) tests, which measure the distance between two probability distributions, RAS achieved significantly better fits. For the NY Taxi dataset, RAS achieved a KS score of 0.030, vastly outperforming the best parametric baseline's 0.154.

Qualitative Fit

As shown in the Q-Q plots below, the RAS model is uniquely capable of capturing both the "head" and the "long tail" of service distributions. Standard models often sacrifice accuracy in one area to fit the other, but the generative nature of RAS allows it to learn the true shape of the data directly.

Empirical results across three datasets (Github, Stackoverflow, NY Taxi). The top row shows frequency distributions, while the bottom row provides Q-Q plots comparing model predictions against ground truth.

Conclusion and Future Work

DGST represents a significant step forward in making queuing theory applicable to modern, large-scale data. While the current model assumes an infinite-server ($G/G/\infty$) environment, it provides a foundation for more complex scheduling policies. Future work may involve using Graph Neural Networks to better encode geographic or social relationships and improving the interpretability of these "black-box" deep learning models for system stakeholders.

Summary updated

Abstract

Modern society is heavily dependent on large scale client-server systems with applications ranging from Internet and Communication Services to sophisticated logistics and deployment of goods. To maintain and improve such a system, a careful study of client and server dynamics is needed – e.g. response/service times, aver-age number of clients at given times, etc. To this end, one traditionally relies, within the queuing theory formalism,on parametric analysis and explicit distribution forms.However, parametric forms limit the model’s expressiveness and could struggle on extensively large datasets. We propose a novel data-driven approach towards queuing systems: the Deep Generative Service Times. Our methodology delivers a flexible and scalable model for service and response times. We leverage the representation capabilities of Recurrent Marked Point Processes for the temporal dynamics of clients, as well as Wasserstein Generative Adversarial Network techniques, to learn deep generative models which are able to represent complex conditional service time distributions. We provide extensive experimental analysis on both empirical and synthetic datasets, showing the effectiveness of the proposed models
BibTeX
@inproceedings{ojeda2021learning,
  author = {César Ojeda and Kostadin Cvejoski and Bogdan Georgiev and Christian Bauckhage and Jannis Schuecker and Ramsés J. Sánchez},
  title = {{Learning Deep Generative Models for Queuing Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=U_VjbsRmU2},
}

Loading related content...

Figure