Awi Federgruen

Approximating queue size and waiting time distributions in general polling systems

Coauthor(s): Ziv Katalan.

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 we describe an efficient approximation method for the steady state distributions of the queue sizes 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, K2) time only. When executed on an IBM system RS/6000, we 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.

Source: Queueing Systems
Exact Citation:
Federgruen, Awi, and Ziv Katalan. "Approximating queue size and waiting time distributions in general polling systems." Queueing Systems 18, no. 3-4 (September 1994): 353-386.
Volume: 18
Number: 3-4
Pages: 353-386
Date: 9 1994