Efficient Visit Frequencies of Polling Tables: Minimization of Waiting Cost

摘要

Polling systems have been used as a central model for the modeling and analysisof many communication systems. Examples include the Token Ring network and a communications switch. The common property of these systems is the need to efficiently share a single resource (server) among N entitites (stations). In spite of the massive research effort in this area, very little work has been devoted to the issue of how to efficiently operate these systems. This problem, namely how to efficiently allocate the server's attention among the N stations, is addressed. A framework in which a predetermined fixed visit order (polling table) is used to establish the order by which the server visits the stations is considered and the problem of how to construct an efficient (optimal) polling table is addressed. In selecting a polling table, the objective is to minimize the mean waiting cost of the system, a weighted sum of the mean delays with arbitrary cost parameters. Since the optimization problem involved is very hard an approximate approach is used. Using two independent analyses, based on a lower bound and on mean delay approximations, very simple rules for the determination of efficient polling tables are derived. The two rules are very similar and even coincide in most cases. Extensive numerical examination shows that the rules perform well and that in most cases the system operates very close to its optimal operation point.