ANALYSIS OF NETWORK OF QUEUES WITH FINITE CAPACITIES AND BLOCKING

Abstract

Queueing Network Models (QNMs) with Finite Capacity provide powerful and realistic tools for the performance evaluation and prediction of discrete flow systems such as computer systems, communication networks and flexible manufacturing systems. Over recent years, there has been a great deal of progress towards the analysis and application of QNMs with finite capacity, and high quality research work has appeared in diverse scientific journals of learning and conference proceedings in the fields of Operations Research, Computer Science, Telecommunication Networks, Management and Industrial Engineering. However, there are still many important and interesting finite capacity queues and QNMs to be resolved, such as those involving multiple-job classes, bounds and theoretical properties, exact analysis, numerical solutions and approximate methods, as well as application studies to computer and distributed systems, high-speed networks and production systems. Finite capacity queueing network models (QNMs) also play an important role towards effective congestion control and quality of service (QoS) protection of modern discrete flow networks. Blocking in such networks arises because the traffic of jobs through one queue may be momentarily halted if the destination queue has reached its capacity. Exact closed-form solutions for QNMs with blocking are not generally attainable except for some special cases such as two-station cyclic ivqueues and ‘reversible’ queueing networks. As a consequence, numerical techniques and analytic approximations have been proposed for the study of arbitrary QNMs with non-Markovian (external) inter- arrival and service times under various types of blocking mechanisms. This research mainly focuses on: i) To develop and validate cost effective analytical models for arbitrary QNMs with blocking and multiple job classes. ii) To use the analytical models to evaluate the performance of QNMs under various blocking mechanisms applicable to flexible manufacturing systems and high speed telecommunication networks. iii) To develop approximate analytical algorithms for arbitrary QNMs consisting of G/G/1/N censored-type queues with arbitrary arrival and service processes, single server under Partial Buffer Sharing (PBS) and Complete Buffer Partitioning (CBP) schemes stipulating a sequence of buffer thresholds {N=N1,N2,...,NR,0< Ni ≤ Ni-1 , i=1,2,...,R} and buffer partitioning with FCFS service discipline. {chapter 4 and 5} iv) Validation of these algorithms (iii) using QNAP simulation package. v) Extension of the above algorithms for multiple servers and its validation using simulation. Determining a performance distribution via classical queueing theory may prove to be an infeasible task even for systems of queues with moderate complexity. Hence, the principle of entropy maximization may be applied to characterize useful information theoretic approximations of performance distributions of queueing systems and queueing network models (QNMs). vFocusing on an arbitrary open QNM, the ME solution for the joint state probability, subject to marginal mean value constraints, can be interpreted as a product-form approximation. Thus, the principle of ME implies a decomposition of a complex QNM into individual queues each of which can be analyzed separately with revised inter arrival and service times. Moreover, the marginal ME state probability of a single queue, in conjunction with suitable formulae for the first two moments of the effective flow, can play the role of a cost-effective analytic building block towards the computation of the performance metrics for the entire network.