Computing transient and steady-state distributions in polling models by numerical transform inversion

Abstract

We show that probability distributions of performance measures in a large class of polling models can be effectively computed by numerically inverting transforms (generating functions and Laplace transforms). We develop new efficient iterative algorithms for computing the transform values and then use the Fourier-series method to perform the inversion. We also use this approach to compute moments. The algorithms apply to the transient behavior of stationary or nonstationary models as well as to the steady-state behavior of stationary models. Our main focus is on computing exact tail probabilities, but even for mean waiting times, our algorithm is faster than previous algorithms for large models. The computational complexity of our algorithm is O(N/sup /spl alpha//) for computing performance measures at one queue and O(N/sup 1+/spl alpha//) for computing performance measures at all queues, where N is the number of queues and /spl alpha/ is typically between 0.6 and 0.8. We demonstrate effectiveness by computing performance measures in an asymmetric 1000-queue system.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 23 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.