Modelling queueing networks with blocking using probability mass fitting
In this thesis, we are interested in the modelling of queueing networks with finite buffers and with general service time distributions. Queueing networks models have shown to be very useful tools to evaluate the performance of complex systems in many application fields (manufacturing, communication networks, traffic flow, etc.). In order to analyze such networks, the original distributions are most often transformed into tractable distributions, so that the Markov theory can then be applied. Our main originality lies in this step of the modelling process. We propose to discretize the original distributions by probability mass fitting (PMF). The PMF discretization is simple: the probability masses on regular intervals are computed and aggregated on a single value in the corresponding interval. PMF has the advantage to be simple, refinable, and to conserve the shape of the distribution. Moreover, we show that it does not require more phases, and thus more computational effort, than concurrent methods.
From the distributions transformed by PMF, the evolution of the system can then be modelled by a discrete Markov chain, and the performance of the system can be evaluated from the chain. This global modelling method leads to various interesting results. First, we propose two methodologies leading to bounds on the cycle time of the system. In particular, a tight lower bound on the cycle time can be computed. Second, probability mass fitting leads to accurate approximation of the performance measures (cycle time, work-in-progress, flow time, etc.). Together with the bounds, the approximations allow to get a good grasp on the exact measure with certainty. Third, the cycle time distribution can be computed in the discretized time and shows to be a good approximation of the original cycle time distribution. The distribution provides more information on the behavior of the system, compared to the isolated expectation (to which other methods are limited). Finally, in order to be able to analyze larger networks, the decomposition technique can be applied after PMF. We show that the accuracy of the performance evaluation is still good, and that the ability of PMF to accurately estimate the distributions brings an improvement in the application of the decomposition. In conclusion, we believe that probability mass fitting can be considered as a valuable alternative in order to build tractable distributions for the analytical modelling of queueing networks.
School:Université catholique de Louvain
Source Type:Master's Thesis
Keywords:discretization queueing networks performance evaluation production distributions bounds
Date of Publication:03/18/2009