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

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^α) for computing performance measures at one queue and O(N^1+α) for computing performance measures at all queues, where N is the number of queues and α is typically between 0.6 and 0.8. We demonstrate effectiveness by computing performance measures in an asymmetric 1000-queue system