Cyclic Bernoulli Polling

Cyclic Bernoulli Polling

0.00 Avg rating0 Votes
Article ID: iaor19942023
Country: Germany
Volume: 38
Start Page Number: 55
End Page Number: 76
Publication Date: Jan 1993
Journal: Mathematical Methods of Operations Research (Heidelberg)
Authors: ,
Abstract:

The authors introduce, analyse and optimize the class of Bernoulli random polling systems. The server moves cyclically among N channels (queues), but Change-over times between stations are composed of walking times required to ‘move’ from one channel to another and switch-in times that are incurred only when the server actually enters a station to render service. The server uses a Bernoulli random mechanism to decide whether to serve a queue or not: upon arrival to channel i, it switches in with probability equ1 or moves on to the next queue equ2 without serving any customer (e.g. packet or job). The Cyclic Bernoulli Polling (CBP) scheme is independent of the service regime in any particular station, and may be applied to any service discipline. In this paper the authors analyse three different service disciplines under the CBP scheme: Gated, Partially Exhaustive and Fully Exhaustive. For each regime they derive expressions for (i) the generating functions and moments of the number of customers (jobs) at the various queues at polling instants, (ii) the expected number of jobs that an arbitrary departing job leaves behind it, and (iii) the LST and expectation of the waiting time of a customer at any given queue. The fact that these measures of performance can be explicitly obtained under the CBP is an advantage over all ‘parameterized’ cyclic polling schemes (such as the k-limited discipline) that have been studied in the literature, and for which explicit measures of performance are hard to obtain. The choice of the equ3 in the CBP allows for fine tuning and optimization of performance measures, as well as prioritization between stations (this being achieved at a low computational cost). For this purpose, the authors develop a Pseudo-conservation law for a mixed system comprised of channels from all three service disciplines, and define a Mathematical Program to find the optimal values of the probabilities equ4 so as to minimize the expected amount of unfinished work in the system. Any CBP scheme for which the optimal p i 's are not all equal to one, yields a smaller amount of the expected unfinished work in the system than that in the standard cyclic polling procedure with equivalent parameters. The authors conclude by showing that even in the case of a single queue, it is not always true that equ5 is the best strategy, and derive conditions under which it is optimal to have equ6.

Reviews

Required fields are marked *. Your email address will not be published.