Stability, Queue Length, and Delay of Deterministic and Stochastic Queueing Networks

Having been motivated by recent development in high speed networks, in this paper we present two types of stability problems: i) conditions for queueing networks that render bounded queue lengths and bounded delay for customers, and ii) conditions for queueing networks in which the queue length distribution of a queue has an exponential tail with rate θ. To answer these two types of stability problems, we introduce two new notions of traffic characterization: minimum envelope rate (MER) and MER with respect to θ. Based on these two new notions of traffic characterization, we develop a set of rules for network operations such as superposition, input-output relation of a single queue, and routing. Specifically, we show that i) the MER of a superposition process is less than or equal to the sum of the MER of each process, ii) a queue is stable in the sense of bounded queue length if the MER of the input traffic is smaller than the capacity, iii) the MER of a departure process from a stable queue is less than or equal to that of the input process, and iv) the MER of a routed process from a departure process is less than or equal to the MER of the departure process multiplied by the MER of the routing process. Similar results hold for MER with respect to 0 under a further assumption of independence. These rules provide a natural way to analyze feedforward networks with multiple classes of customers. For single class networks with nonfeedforward routing, we provide a new method to show that similar stability results hold for such networks under the first come, first served policy. Moreover, when restricting to the family of two-state Markov modulated arrival processes, the notion of MER with respect to θ is shown to be equivalent to the recently developed notion of effective bandwidth in communication networks. © 1994 IEEE