Stability, queue length and delay. I. Deterministic queueing networks
- 24 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 999-1004
- https://doi.org/10.1109/cdc.1992.371570
Abstract
Conditions for deterministic queueing networks that render bounded delays for customers are identified. These conditions are referred to as stability conditions for deterministic queues. Parallel to the three classical stability conditions, stationarity, ergodicity, and the traffic condition, for queues with random inputs, the notions of envelope process, subadditivity, and the traffic condition are used as the stability conditions for deterministic queues. It is shown that the delay in a single queue is bounded under a work-conservative scheduling policy if the minimum envelope rate, which is the average rate of the smallest envelope process, is less than the capacity. Moreover, the delay cannot be bounded if the minimum envelope rate is larger than the capacity. Similar results are extended to multiclass networks with feedforward routing. For networks with nonfeedforward routing, it is shown that the stability result holds for networks with a single class of customers under the first come first served (FCFS) policy. Various scheduling policies that stabilize multiclass networks with nonfeedforward routing are discussed, and a sufficient condition for the stability under the FCFS policy is given.Keywords
This publication has 12 references indexed in Scilit:
- Optimal scheduling control in a multi-class fluid networkPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Congestion-free transmission of real-time traffic in packet networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On computing per-session performance bounds in high-speed multi-hop computer networksPublished by Association for Computing Machinery (ACM) ,1992
- Distributed scheduling based on due dates and buffer prioritiesIEEE Transactions on Automatic Control, 1991
- A calculus for network delay. II. Network analysisIEEE Transactions on Information Theory, 1991
- A calculus for network delay. I. Network elements in isolationIEEE Transactions on Information Theory, 1991
- Network delay considerations for packetized voicePerformance Evaluation, 1989
- Monotonicity of throughput in non-Markovian networksJournal of Applied Probability, 1989
- Stable, distributed, real-time scheduling of flexible manufacturing/assembly/diassembly systemsIEEE Transactions on Automatic Control, 1989
- Stochastic Processes in Queueing TheoryPublished by Springer Nature ,1976