Computable exponential bounds for intree networks with routing
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 197-204 vol.1
- https://doi.org/10.1109/infcom.1995.515877
Abstract
In this paper, we refine the calculus proposed previously by Chang et al. (1994). The new calculus, including network operations for multiplexing, input-output relation, and routing, allows us to compute tighter exponential bounds for the tail distributions of queue lengths in intree networks with routing. In particular, if external arrival processes and routing processes are either Markov arrival processes or autoregressive processes, the stationary queue length at a local node is stochastically bounded above by the sum of a constant and an Erlang random variable. The decay rate of the Erlang random variable is not greater than (in some cases equal to) the decay rate of the tail distribution of the stationary queue length. The number of stages of the Erlang random variable is the number of external arrival processes and routing processes contributing to its queue length. For the single queue case, both the lower and upper-bounds are derived.Keywords
This publication has 20 references indexed in Scilit:
- Exponential bounds with applications to call admissionJournal of the ACM, 1997
- Logarithmic asymptotics for steady-state tail probabilities in a single-server queueJournal of Applied Probability, 1994
- Tail probabilities with statistical multiplexing and effective bandwidths in multi-class queuesTelecommunication Systems, 1993
- Effective bandwidth of general Markovian traffic sources and admission control of high speed networksIEEE/ACM Transactions on Networking, 1993
- Effective bandwidths for the multi-type UAS channelQueueing Systems, 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
- Large Deviations for a General Class of Random VectorsThe Annals of Probability, 1984
- On Large Deviations from the Invariant MeasureTheory of Probability and Its Applications, 1977
- The stability of a queue with non-independent inter-arrival and service timesMathematical Proceedings of the Cambridge Philosophical Society, 1962