ROBUST BOUNDS AND THROUGHPUT GUARANTEES FOR CLOSED MULTICLASS QUEUING-NETWORKS

To use queueing theory for analyzing real computing systems, we may ma ke assumptions that are strictly speaking untrue. The problem is espec ially severe for multiclass systems with widely differing service time s. This paper provides an exact analysis for bounds for systems with g reatly relaxed assumptions. Service times can have arbitrary NBUE dist ributions, different by class even at FIFO nodes. Routing can be arbit rary, including dependencies along the route, provided the number of v isits to a device per response cycle is random with a known expectatio n. Only the mean service time and mean visit rates at nodes need to be specified. A new lower throughput bound is found which gives a minimu m guaranteed throughput for each class. together with the familiar mul ticlass asymptotic upper bounds they give a convex feasible region in a multidimensional throughput space. A detailed analysis is given for queueing network models of systems with infinite-server nodes as well as queueing nodes with various service disciplines: FIFO, processor sh aring, and priority (preemptive as well as non-preemptive) scheduling. Because the feasible region may be a complicated shape which is diffi cult to visualize, the results can be re-interpreted as a set of bound s on the separate throughputs. This is equivalent to a circumscribed r ectangular region called the ''robust box bounds''. Computation of the se bounds is carried out by a novel technique based on interval arithm etic as implemented in BNR Prolog language. A method for computing app roximate system throughput from the box bounds is also proposed in the paper. Using Little's law and utilization law with the bounds on thro ughput bounds on response times and device utilizations are obtained. These analytic techniques can be effectively utilized for analyzing th e performance of distributed systems as well as other types of computi ng systems. (C) 1998 Elsevier Science B.V.