Approximating queue size and waiting time distributions in general polling systems

Polling system models are extensively used to model a large variety of computer and communication networks as well as production and service systems in which multiple customer classes or a number of distinct items compete for the capacity of a common server or production facility. In this paper the authors describe an efficient approximation method for the steady state distributions of the queue size and waiting times. This method is highly accurate as demonstrated by an extensive numerical study. In addition, it is highly adaptable to a variety of arrival patterns and switching protocols, including exhaustive and gated regimes, simple cyclical systems as well as general polling tables. For a system with N stations, one finds the first K probability density function values of the steady state queue size in any given station in O(max(N,K²)) time only. When executed on an IBM system RSz.drule;6000, the authors have observed an average CPU time of less than 1 second for systems with as many as 50 stations over a large variety of parameter settings.