Networks with cascading overloads

Jesse Collingwood; Robert D. Foley; David R. McDonald

doi:10.3934/jimo.2012.8.877

Article Contents

2012, Volume 8, Issue 4: 877-894. Doi: 10.3934/jimo.2012.8.877

This issue Previous Article On the optimal and equilibrium retrial rates in an unreliable retrial queue with vacations Next Article Analysis of customers' impatience in an M/M/1 queue with working vacations

Networks with cascading overloads

1.
Department of Mathematics and Statistics, University of Ottawa, 585 King Edward Avenue, Ottawa, Ontario K1N 6M8
2.
Industrial and Systems Engineering, Georgia Institute of Technology, Groseclose Building, Room 428, Atlanta GA 30332-0205

Received: August 31, 2011

Revised: June 30, 2012

Published: September 2012

Abstract Related Papers Cited by

Abstract

Here we study large deviations in networks that are more likely to result from the accumulation of many slightly unusual events. We are particularly interested in analyzing large deviations where the most probable path changes direction. These deviations arise when a large deviation in one part of the system cascades across the network to produce a large deviation in another part of the network. Our technique involves the construction of an approximate time reversal. We also use this approximate time reversal to do rare event simulation.

Keywords:

Mathematics Subject Classification: Primary: 60J20, 60K20.

Citation:

Related Papers

Cited by

References

[1]	I. Adan, R. D. Foley and D. R. McDonald, Exact asymptotics for the stationary distribution of a Markov chain: A production model, Queueing Syst., 62 (2009), 311-344.doi: 10.1007/s11134-009-9140-y.
[2]	V. Anantharam, P. Heidelberger and P. Tsoucas, Analysis of rare events in continuous time Markov chains via time reversal and fluid approximation, Research Report, RC 16280, Computer Science Division, IBM T. J. Watson Center, Yorktown Heights, New York.
[3]	F. Baccelli and P. Bremaud, "Elements of Queueing Theory," Springer Verlag, 2003.
[4]	F. Baccelli and D. McDonald, Rare events for stationary processes, Stochastic Processes and their Applications, 89 (1997), 141-173.doi: 10.1016/S0304-4149(00)00018-1.
[5]	A. A. Borovkov and A. A. Mogul'skii, Limit theorems in the boundary hitting problem for a multidimensional random walk, Siberian Mathematical Journal, 4 (2001), 245-270.doi: 10.1023/A:1004832928857.
[6]	R. Foley and D. McDonald, Join the shortest queue: stability and exact asymptotics, Annals of Applied Probability, 11 (2001), 569-607.
[7]	R. D. Foley and D. R. McDonald, Large deviations of amodified jackson network: Stability and rough asymptotics, Ann. Appl. Probab., 15 (2004), 519-541.doi: 10.1214/105051604000000666.
[8]	R. D. Foley and D. R. McDonald, Bridges and networks: Exact asymptotics, Annals of Applied Probability, 15 (2005), 542-–586.doi: 10.1214/105051604000000675.
[9]	R. D. Foley and D. R. McDonald, Constructing a harmonic function for an irreducible non-negative matrix with convergence parameter $R > 1$, Accepted subject to revisions London Mathematical Society.
[10]	I. Ignatiouk-Robert and C. Loree, Martin boundary of a killed random walk on a quadrant, Ann. Probab, 38 (2010), 1106-1142.doi: 10.1214/09-AOP506.
[11]	T. G. Kurtz, Strong approximation theorems for density dependent Markov chains, Stoch. Proc. Appl., 6 (1978), 223-240.doi: 10.1016/0304-4149(78)90020-0.
[12]	K. Majewski and K. Ramanan, How large queue lengths build up in a Jackson network, preprint. 2008.
[13]	S. P. Meyn and R. L. Tweedie, "Markov Chains and Stochastic Stability," Springer-Verlag, London. 1993.
[14]	M. Miyazawa and Y. Q. Zhao, The stationary tail asymptotics in the GI/G/1-type queue with countably many background states, Advances in Applied Probability, 36 (2004), 1231-1251.doi: 10.1239/aap/1103662965.
[15]	V. Nicola and T. Zaburnenko, Efficient importance sampling heuristics for the simulation of population overflow in jackson networks, ACM Transactions on Modeling and Computer Simulation, 17 (2007).