Networks with cascading overloads

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

October 2012, 8(4): 877-894. doi: 10.3934/jimo.2012.8.877

Networks with cascading overloads

Jesse Collingwood ^1, , Robert D. Foley ^2, and David R. McDonald ^1,

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

Received September 2011 Revised July 2012 Published September 2012

Abstract
Related Papers

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: Markov chains., approximate time reversal, change of measure, Rare events, exact asymptotics, large deviations, importance sampling.

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

Citation: Jesse Collingwood, Robert D. Foley, David R. McDonald. Networks with cascading overloads. Journal of Industrial and Management Optimization, 2012, 8 (4) : 877-894. doi: 10.3934/jimo.2012.8.877

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).

show all references

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).

[1]	Tatsuaki Kimura, Hiroyuki Masuyama, Yutaka Takahashi. Light-tailed asymptotics of GI/G/1-type Markov chains. Journal of Industrial and Management Optimization, 2017, 13 (4) : 2093-2146. doi: 10.3934/jimo.2017033
[2]	Koen De Turck, Sabine Wittevrongel. Receiver buffer behavior for the selective repeat protocol over a wireless channel: An exact and large-deviations analysis. Journal of Industrial and Management Optimization, 2010, 6 (3) : 603-619. doi: 10.3934/jimo.2010.6.603
[3]	Idriss Mazari. Trait selection and rare mutations: The case of large diffusivities. Discrete and Continuous Dynamical Systems - B, 2019, 24 (12) : 6693-6724. doi: 10.3934/dcdsb.2019163
[4]	Olivier Pinaud. Time reversal of surface plasmons. Discrete and Continuous Dynamical Systems - B, 2022 doi: 10.3934/dcdsb.2022106
[5]	Miguel Abadi, Sandro Vaienti. Large deviations for short recurrence. Discrete and Continuous Dynamical Systems, 2008, 21 (3) : 729-747. doi: 10.3934/dcds.2008.21.729
[6]	Jerry L. Bona, Laihan Luo. Large-time asymptotics of the generalized Benjamin-Ono-Burgers equation. Discrete and Continuous Dynamical Systems - S, 2011, 4 (1) : 15-50. doi: 10.3934/dcdss.2011.4.15
[7]	Jean Dolbeault, Giuseppe Toscani. Fast diffusion equations: Matching large time asymptotics by relative entropy methods. Kinetic and Related Models, 2011, 4 (3) : 701-716. doi: 10.3934/krm.2011.4.701
[8]	Sandra Cerrai, Mark Freidlin, Michael Salins. On the Smoluchowski-Kramers approximation for SPDEs and its interplay with large deviations and long time behavior. Discrete and Continuous Dynamical Systems, 2017, 37 (1) : 33-76. doi: 10.3934/dcds.2017003
[9]	Dongmei Zheng, Ercai Chen, Jiahong Yang. On large deviations for amenable group actions. Discrete and Continuous Dynamical Systems, 2016, 36 (12) : 7191-7206. doi: 10.3934/dcds.2016113
[10]	Salah-Eldin A. Mohammed, Tusheng Zhang. Large deviations for stochastic systems with memory. Discrete and Continuous Dynamical Systems - B, 2006, 6 (4) : 881-893. doi: 10.3934/dcdsb.2006.6.881
[11]	Felix X.-F. Ye, Yue Wang, Hong Qian. Stochastic dynamics: Markov chains and random transformations. Discrete and Continuous Dynamical Systems - B, 2016, 21 (7) : 2337-2361. doi: 10.3934/dcdsb.2016050
[12]	Yakov Pesin. On the work of Sarig on countable Markov chains and thermodynamic formalism. Journal of Modern Dynamics, 2014, 8 (1) : 1-14. doi: 10.3934/jmd.2014.8.1
[13]	Kenrick Bingham, Yaroslav Kurylev, Matti Lassas, Samuli Siltanen. Iterative time-reversal control for inverse problems. Inverse Problems and Imaging, 2008, 2 (1) : 63-81. doi: 10.3934/ipi.2008.2.63
[14]	Rodrigo I. Brevis, Jaime H. Ortega, David Pardo. A source time reversal method for seismicity induced by mining. Inverse Problems and Imaging, 2017, 11 (1) : 25-45. doi: 10.3934/ipi.2017002
[15]	Yongqiang Suo, Chenggui Yuan. Large deviations for neutral stochastic functional differential equations. Communications on Pure and Applied Analysis, 2020, 19 (4) : 2369-2384. doi: 10.3934/cpaa.2020103
[16]	Thomas Bogenschütz, Achim Doebler. Large deviations in expanding random dynamical systems. Discrete and Continuous Dynamical Systems, 1999, 5 (4) : 805-812. doi: 10.3934/dcds.1999.5.805
[17]	Mathias Staudigl, Srinivas Arigapudi, William H. Sandholm. Large deviations and Stochastic stability in Population Games. Journal of Dynamics and Games, 2021 doi: 10.3934/jdg.2021021
[18]	E. Almaraz, A. Gómez-Corral. On SIR-models with Markov-modulated events: Length of an outbreak, total size of the epidemic and number of secondary infections. Discrete and Continuous Dynamical Systems - B, 2018, 23 (6) : 2153-2176. doi: 10.3934/dcdsb.2018229
[19]	Josef DiblÍk, Rigoberto Medina. Exact asymptotics of positive solutions to Dickman equation. Discrete and Continuous Dynamical Systems - B, 2018, 23 (1) : 101-121. doi: 10.3934/dcdsb.2018007
[20]	Zvi Drezner, Carlton Scott. Approximate and exact formulas for the $(Q,r)$ inventory model. Journal of Industrial and Management Optimization, 2015, 11 (1) : 135-144. doi: 10.3934/jimo.2015.11.135

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Jesse Collingwood Robert D. Foley David R. McDonald
on Google Scholar
Jesse Collingwood Robert D. Foley David R. McDonald

[Back to Top]