Bounding Blocking Probabilities and Throughput in Queueing Networks With Buffer Capacity Constraints

this paper, we propose a new technique for estimating the performance of queueing networks with buffer capacity constraints i.e, queueing networks in which some of the buffers have finite capacity. Two performance measures of interest for such systems are the throughput and the blocking probabilities of various customer classes. Our technique allows us to obtain upper and lower bounds on such performance measures for a wide variety of systems. The proposed technique extends the technique of obtaining bounds on the mean delay and throughput of queueing networks described in [10]. It can be described as follows. Assuming the existence of a steady state, we study the evolution of multinomials of the state of the system in steady state. Knowing that such multinomials, if integrable with respect to the invariant measure, cannot evolve in the mean, we obtain constraints on the possible behavior of the system. Using these constraints, with a suitable choice of variables, we obtain linear programs whose values upper and lower bound the performance measures of interest, namely throughput or blocking probabilities. This differs from [10] in that the performance measures on which bounds are obtained are probabilities, and in that multinomials rather than quadratics are used. The main advantage of this new technique is that the computational complexity does not increase with the size of the finite buffers. Also, the technique is applicable to systems in which some buffers have infinite capacity. In some cases the bounds obtained are asymptotically exact, i.e., they approach the exact value as the degree of the multinomial considered increases. Another advantage of the method is that the main computation involved is the solution of a linear program which is rather routine with curre..