Analysis of a time-limited polling system with Markovian arrival process and phase-type service.

摘要

Polling systems have been the subject of many studies and are of interest in the analysis of communication systems, operating systems scheduler, traffic intersections, and manufacturing systems. For communication and operating systems, the time-limited service discipline is very important since it allows one to limit the time the server is away from a particular queue. Nevertheless, it has received little attention, whereas, the exhaustive and gated service discipline have been studied extensively. In addition, most of the available results ignore correlation between arrivals.;In this thesis, we have modeled the Fair Share Scheduler as a discrete time polling system. In this polling system, each queue is visited according to the exhaustive time-limited service discipline, customers arrive according to the Markovian arrival process and their service time has a phase type distribution. Both cyclic and table polling are considered. In addition, we consider, separately, the case when all the queues have infinite buffer capacity and when all the queues have finite buffer capacity. Our solution is based on the decomposition approach. Thus, for the infinite buffer capacity case, each queue in the polling system is treated as a MAP/PH/1 with vacation periods and is analyzed using the matrix-analytic approach. On the other hand, for the finite buffer capacity case, each queue is considered as a MAP/PH/1/K with vacation periods, for which the queue length distribution is obtained using the block Gauss-Seidel iterative procedure.;The results of the MAP/PH/1 or the MAP/PH/1/K are then incorporated into an iterative procedure to obtain the mean waiting time for each queue in a polling system. Because of the time-limited service discipline, the vacation and visit period distributions are represented by discrete-time phase distribution in the case of cyclic polling. However, for table polling, since the type of vacation the server takes depends on its position in the polling table, the vacation period looks like the convolution of discrete phase distributions and is represented by a MAP. In order to incorporate the correlation between the vacation and visit period distributions, the vacation period is obtained as the sum of an independent and a dependent part. The independent part is the convolution of the visit period of the queues visited while the server is on vacation. The dependent part is computed using an approach similar to that of Lee and Sengupta. The convergence of the iterative procedure is proved for the cyclic polling case using stochastic dominance. We have also proved that if we start with a stable system, then the iterative procedure is stable (for cyclic polling). Comparison between the iterative results and the simulation results shows that the iterative procedure provides reasonable results over a wide range of input parameters.;However, the computational time increases as the dimension of the vacation period becomes large. In our case, the dimension of the vacation period distribution depends on (1) the number of queues in the polling system, (2) the time threshold for the queues visited while the server is on vacation, and (3) the number of visits in the case of table polling. In order to reduce the computational time, the dimension of each phase type vacation period distribution is reduced using the moments matching approach. Comparison between the original and reduced MAP shows that the error in the probability mass function and the coefficient of correlation is very small.