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

Abstract

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