Numerical Solution of Polling Systems for Analyzing Networks on Chips
This paper introduces a numerical solution method for a class of discrete-time polling systems by relying on the power method, Kronecker matrix representations and the shuffle algorithm. The class of polling models considered consists of several infinite pseudo queues, deterministic service times, Bernoulli service and Markovian routing and includes exhaustive, 1-limited and k-limited service as special cases. A truncated, large finite state Markov chain is obtained by solving a series of finite state Markov chains with increasing size. The model is motivated by the analysis of networks on chips and its superiority over other existing approximation methods in terms of the accuracy and computation times is demonstrated.