An invariant distribution for the G/G/1 queueing operator

Nicholas Bambos, Jean WalrandAdvances 1990 · DOI

Abstract

We consider the $G/G/1$ queue as an operator that maps inter-arrival times to inter-departure times of points, given the service times. For arbitrarily fixed statistics of service times, we are interested in the existence of distributions of inter-arrival times that induce identical distributions on the inter-departure times. In this note we prove, by construction, the existence of one of such distribution.

Introduction

In the study of queueing systems, a central question is how the statistical properties of arrival processes are transformed by the queueing mechanism. A landmark result in this field is Burke’s Theorem, which demonstrates that for an $M/M/1$ queue—characterized by Poisson arrivals and exponential service times—the departure process is also a Poisson process with the same rate. This "transparency" is vital for analyzing networks of queues, as it ensures that the output of one node remains a tractable input for the next.

However, the question remains: does such an invariant distribution exist for the more general $G/G/1$ queue? Given an arbitrary service time distribution, can we find an inter-arrival distribution that is preserved by the queueing operator? This paper provides a constructive proof that such a distribution exists for any fixed service time statistics.

The Queueing Operator and Lindley’s Equations

The $G/G/1$ queue can be viewed as a mathematical operator that maps a sequence of inter-arrival times $\tau$ to a sequence of inter-departure times $\tau^*$, mediated by a sequence of service times $\sigma$. The relationship between these variables is governed by Lindley’s equations, which track the waiting times and idle periods of the server. The goal is to find a fixed point for this operator—a distribution $P_\tau$ such that $P_\tau = P_{\tau^*}$.

Methodology: A Constructive Proof

Rather than relying on abstract existence theorems, the authors employ a constructive approach to identify the invariant distribution. The proof follows a sequence of logical steps involving tandem queues and limit processes:

  1. Tandem Queue Construction: Imagine an infinite sequence of queues arranged in tandem. Each queue has independent and identically distributed (i.i.d.) service times drawn from the fixed distribution $P_\sigma$.
  2. The Saturated Initial State: The system is initialized by assuming the first queue in the sequence is "saturated" or "heavy-headed," meaning it is never idle and always has a customer waiting to be served.
  3. Pathwise Evolution: The inter-departure times from the first queue serve as the inter-arrival times for the second, and so on. The authors track the evolution of these inter-departure times as they pass through successive stages of the tandem.
  4. Monotonicity and Convergence: The authors demonstrate that the inter-departure times change monotonically as they progress through the infinite series of queues. This monotonicity ensures that the sequence of distributions converges to a stable limit.

Key Insights

The Critical State

The invariant distribution identified by this construction corresponds to a queue operating at its "critical" limit. In this state, the arrival rate exactly matches the service rate. This is a significant finding, as it characterizes the boundary between stable and unstable queueing behavior.

Pathwise Convergence

A notable aspect of the proof is its reliance on pathwise limits. For a specific realization of service times, the sequence of inter-departure times settles into a specific value as it passes through the infinite tandem. This suggests a robust relationship between the input and output processes at the limit.

Dependencies in the Process

While the $M/M/1$ case is famous for producing independent inter-departure times, the authors note that in the general $G/G/1$ case, the invariant distribution may involve complex dependencies between successive inter-arrival times. Even if the service times are i.i.d., the resulting invariant process is not necessarily a simple renewal process.

Conclusion and Future Directions

This research successfully proves that for any service time distribution, an invariant inter-arrival distribution exists and can be constructed via the limit of a saturated tandem queue.

However, several questions remain open. The authors acknowledge that the finiteness of the resulting inter-arrival times requires further investigation under specific service time constraints. Furthermore, the study focuses on the critical case where the arrival rate equals the service rate. The paper concludes with a conjecture: for any stationary and ergodic service time sequence and any arrival rate lower than the service rate, there should exist a unique stationary arrival process that remains invariant. Proving this conjecture remains a significant challenge for future work in queueing theory.

Summary updated

Abstract

We consider the G/G /1 queue as an operator that maps inter-arrival times to inter-departure times of points, given the service times. For arbitrarily fixed statistics of service times, we are interested in the existence of distributions of inter-arrival times that induce identical distributions on the inter-departure times. In this note we prove, by construction, the existence of one of such distribution.
BibTeX
@inproceedings{bambos1990invariant,
  author = {Nicholas Bambos and Jean Walrand},
  title = {{An invariant distribution for the <i>G</i>/<i>G</i>/1 queueing operator}},
  booktitle = {Advances},
  year = {1990},
  doi = {10.2307/1427610},
}
Figure