The main objective of this dissertation is to analyze the performance of two finite-capacity polling systems from which we investigate the behavior of two well-known media assess protocols in local area networks: the token ring and the slotted ring.
First, we analyze the performance of a general asymmetric polling system where each station has a finite-capacity buffer and exhaustive service discipline. The system is a generalized analytic model of the token ring. Since it is very difficult to describe the exact behavior of the finite-buffer polling system, we introduce a model system named as the virtual buffer model which yields the same performance of the original system. In the virtual buffer model, we assume that each station has a temporary virtual buffer with infinite capacity attached to the real buffer while the server is unavailable to the station. The virtual buffer stores all those packets which are forced to be lost due to the limitation of the real buffer capacity.
Choosing as imbedded points the instants when the server visits each station (called polling instants), we build a Markov chain whose state consists of the queue lengths of all stations. We note that in the exhaustive service discipline the server leaves a station only when there are no waiting packets in the buffer. Thus, from the marginal queue length distribution of the station at each polling instant, we readily derive the intervisit time distribution of the station. Then, we obtain the performance measures of the station such as the waiting time distribution, the blocking probability, and the cycle time distribution, using the known results for a single M/G/1/K queueing system with multiple vacations.
Next, we present an analysis of a high-speed slotted ring where each station has a single-packet buffer. Since we consider a high-speed network, the slot size is assumed to be large enough to hold a whole packet. Assuming that distances between stations affect the network performance only by the sum of themselves, we introduce a model system called the lumped model in which stations are located at a single point on the ring with their relative positions preserved.
We choose imbedded Markov points as the instants when each slot visits the aggregated point of the lumped model. Then, we develop two Markov chains named as the full state model and the reduced state model according to the degree of considering the state of buffers and slots. At each imbedded point, in the full state model we describe exactly the behavior of buffers and slots, whereas in the reduced state model we consider only the number of packets in buffers and slots. From the steady state probabilities of each Markov chain, we obtain the mean waiting time and the blocking probability of each station.