COMPUTING DISTRIBUTIONS AND MOMENTS IN POLLING MODELS BY NUMERICAL TRANSFORM INVERSION

We show that probability distributions and moments of performance meas ures in many polling models can be effectively computed by numerically inverting transforms (generating functions and Laplace transforms), W e develop new efficient iterative algorithms for computing the transfo rm values and then use our recently developed variant of the Fourier-s eries method to perform the inversion, We also show how to use this ap proach to compute moments and asymptotic parameters of the distributio ns, We compute a two-term asymptotic expansion of the tail probabiliti es, which turns our to be remarkably accurate for small tail probabili ties. The tail probabilities are especially helpful in understanding t he performance of different polling disciplines, For instance, it is k nown that the exhaustive discipline produces smaller mean steady-state waiting times than the gated discipline, but we show that the reverse tends to be true for small tail probabilities. The algorithms apply t o describe the transient behavior of stationary or non-stationary mode ls as well as the steady-state behavior of stationary models. We demon strate effectiveness by analyzing the computational complexity and by doing several numerical examples for the gated and exhaustive service disciplines, with both zero and non-zero switchover times. We also sho w that our approach applies to other polling models. Our main focus is on computing exact tail probabilities and asymptotic approximations t o them, which seems not to have been done before. However, even for me an waiting times, our algorithm is faster than previous algorithms for large models. The computational complexity of our algorithm is O(N-al pha) for computing performance measures at one queue and O(N-1+alpha) for computing performance measures at all queues, where N is the numbe r of queues and cr is typically between 0.6 and 0.8.