zbMATH — the first resource for mathematics

Sample path large deviations and intree networks. (English) Zbl 0844.60066
Summary: Using the contraction principle, we derive a set of closure properties for sample path large deviations. These properties include sum, reduction, composition and reflection mapping. Using these properties, we show that the exponential decay rates of the steady state queue length distributions in an intree network with routing can be derived by a set of recursive equations. The solution of this set of equations is related to the recently developed theory of effective bandwidth for high speed digital networks, especially ATM networks. We also prove a conditional limit theorem that illustrates how a queue builds up in an intree network.

60K20 Applications of Markov renewal processes (reliability, queueing networks, etc.)
60F10 Large deviations
Full Text: DOI
[1] V. Anantharam, How large delays build up in a GI/G/1 queue, Queueing Systems 5 (1988) 345-368. · Zbl 0695.60092 · doi:10.1007/BF01225324
[2] V. Anantharam, P. Heidelberger and P. Tsoucas, Analysis of rare events in continuous time Markov chains via time reversal and fluid approximation, IBM RC 16280 (1990).
[3] M. Avriel,Nonlinear Programming: Analysis and Methods (Prentice-Hall, 1976).
[4] F. Baccelli and P. Bremaud,Elements of Queueing Theory (Springer, New York, 1990).
[5] P. Billingsley,Convergence of Probability Measures (Wiley, New York, 1968). · Zbl 0172.21201
[6] C.S. Chang, Stability, queue length and delay of deterministic and stochastic queueing networks, IEEE Trans. Aut. Contr. 39 (1994) 913-931. · Zbl 0818.90050 · doi:10.1109/9.284868
[7] C.S. Chang, Approximations of ATM networks: effective bandwidths and traffic descriptors, IBM RC 18954 (1993)
[8] C.S. Chang, P. Heidelberger, S. Juneja and P. Shahabuddin, Effective bandwidth and fast simulation of ATM intree networks, Perform. Eval. 20 (1994) 45-66. · doi:10.1016/0166-5316(94)90005-1
[9] A. Dembo and O. Zeitouni,Large Deviations Techniques and Applications (Jones and Barlett, Boston, 1992).
[10] A. Dembo and Tim Zajic, Large deviations from empirical mean and measure to partial sums processes, to appear in Stoch. Proc. Appl. · Zbl 0838.60026
[11] R. Ellis, Large deviations for a general class of random vectors, Ann. Prob. 12 (1984) 1-12. · Zbl 0534.60026 · doi:10.1214/aop/1176993370
[12] A.I. Elwalid and D. Mitra, Effective bandwith of general Markovian traffic sources and admission control of high speed networks, IEEE/ACM Trans. Networking 1 (1993) 329-343. · doi:10.1109/90.234855
[13] M.R. Frater, T.M. Lennon and B.D.O. Anderson, Optimally efficient estimation of the statistics of rare events in queueing networks, IEEE Trans. Aut. Contr. 36 (1991) 1395-1405. · Zbl 0739.60080 · doi:10.1109/9.106155
[14] J. Gärtner, On large deviations from invariant measure, Th. Prob. Appl. 22 (1977) 24-39. · Zbl 0375.60033 · doi:10.1137/1122003
[15] R.J. Gibbens and P.J. Hunt, Effective bandwidths for the multi-type UAS channel, Queueing Systems 9 (1991) 17-28. · Zbl 0738.90028 · doi:10.1007/BF01158790
[16] P.W. Glynn and W. Whitt, Logarithmic asymptotics for steady-state tail probabilities in a single-server queue, J. Appl. Prob. 31A (1994) 131-156. · Zbl 0805.60093 · doi:10.2307/3214953
[17] P.W. Glynn and W. Whitt, Large deviations behavior of counting processes and their inverses, Queueing Systems 17 (1994) 107-128. · Zbl 0805.60023 · doi:10.1007/BF01158691
[18] R. Guérin, H. Ahmadi and M. Naghshineh, Equivalent capacity and its application to bandwidth allocation in high-speed networks, IEEE J. Select. Areas Commun. 9 (1991) 968-981. · doi:10.1109/49.103545
[19] I. Iscoe, P. Ney and E. Nummelin, Large deviations of uniformly recurrent Markov Additive Processes, Adv. Appl. Math. 6 (1985) 373-412. · Zbl 0602.60034 · doi:10.1016/0196-8858(85)90017-X
[20] P. Heidelberger, Fast simulation of rare events in queueing and reliability models, IBM RC 19028 (1993).
[21] F.P. Kelly,Reversibility and Stochastic Networks (Wiley, New York, 1979).
[22] F.P. Kelly, Effective bandwidths at multi-class queues, Queueing Systems 9 (1991) 5-16. · Zbl 0737.60084 · doi:10.1007/BF01158789
[23] G. Kesidis and J. Walrand, Traffic policing and enforcement of effective bandwidth constraints in ATM networks, preprint. · Zbl 0842.68112
[24] G. Kesidis, J. Walrand and C.S. Chang, Effective bandwidths for multiclass Markov fluids and other ATM sources, IEEE/ACM Trans. Networking 1 (1993) 424-428. · doi:10.1109/90.251894
[25] R.M. Loynes, The stability of a queue with non-independent inter-arrival and service times, Proc. Camb. Phil. Soc. 58 (1962) 497-520. · Zbl 0203.22303 · doi:10.1017/S0305004100036781
[26] H.D. Miller, A convexity property in the theory of random variables defined on a finite Markov chain, Ann. Math. Stat. 32 (1961) 1260-1270. · Zbl 0108.15101 · doi:10.1214/aoms/1177704865
[27] A.A. Mogulskii, Large deviations for trajectories of multidimensional random walk, Th. Prob. Appl. 21 (1976) 300-315. · Zbl 0366.60031 · doi:10.1137/1121035
[28] R. Nagarajan, J. Kurose and D. Towsley, Local allocation of end-to-end quality-of-service in high speed networks, preprint.
[29] S. Parekh and J. Walrand, A quick simulation method for excessive backlogs in networks of queues, IEEE Trans. Aut. Contr. 34 (1989) 54-66. · Zbl 0661.60110 · doi:10.1109/9.8649
[30] R.T. Rochafellar,Convex Analysis (Princeton University Press, Princeton, 1970).
[31] D. Stoyan,Comparison Methods for Queues and Other Stochastic Models (Wiley, Berlin, 1983). · Zbl 0536.60085
[32] J. Walrand,An Introduction to Queueing Networks (Prentice-Hall, New Jersey, 1988). · Zbl 0854.60090
[33] W. Whitt, Some useful functions for functional limit theorems, Math. Oper. Res. 5 (1980) 67-85. · Zbl 0428.60010 · doi:10.1287/moor.5.1.67
[34] W. Whitt, Comparing counting processes and queues, Adv. Appl. Prob. 13 (1981) 207-220. · Zbl 0449.60064 · doi:10.2307/1426475
[35] W. Whitt, Tail probability with statistical multiplexing and effective bandwidths in multiclass queues, Telecom. Syst. 2 (1993) 71-107. · doi:10.1007/BF02109851
[36] G. De. Veciana and J. Walrand, Effective Bandwidths: call admission, traffic policing & filtering for ATM networks, submitted to IEEE/ACM Trans. Networking (1993). · Zbl 0847.90055
[37] G. De. Veciana, C. Courcoubetis and J. Walrand, Decoupling bandwidths for networks: a decomposition approach to resource management, submitted to IEEE/ACM Trans. Networking (1993).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.