American Institute of Mathematical Sciences

Advanced
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

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 & 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.  Google Scholar

[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. Google Scholar

[3]

F. Baccelli and P. Bremaud, "Elements of Queueing Theory," Springer Verlag, 2003.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

R. Foley and D. McDonald, Join the shortest queue: stability and exact asymptotics, Annals of Applied Probability, 11 (2001), 569-607.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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., ().   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

K. Majewski and K. Ramanan, How large queue lengths build up in a Jackson network, preprint. 2008. Google Scholar

[13]

S. P. Meyn and R. L. Tweedie, "Markov Chains and Stochastic Stability," Springer-Verlag, London. 1993.  Google Scholar

[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.  Google Scholar

[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). Google Scholar

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.  Google Scholar

[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. Google Scholar

[3]

F. Baccelli and P. Bremaud, "Elements of Queueing Theory," Springer Verlag, 2003.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

R. Foley and D. McDonald, Join the shortest queue: stability and exact asymptotics, Annals of Applied Probability, 11 (2001), 569-607.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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., ().   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

K. Majewski and K. Ramanan, How large queue lengths build up in a Jackson network, preprint. 2008. Google Scholar

[13]

S. P. Meyn and R. L. Tweedie, "Markov Chains and Stochastic Stability," Springer-Verlag, London. 1993.  Google Scholar

[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.  Google Scholar

[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). Google Scholar

[1]

Tatsuaki Kimura, Hiroyuki Masuyama, Yutaka Takahashi. Light-tailed asymptotics of GI/G/1-type Markov chains. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2093-2146. doi: 10.3934/jimo.2017033
[2]

Idriss Mazari. Trait selection and rare mutations: The case of large diffusivities. Discrete & Continuous Dynamical Systems - B, 2019, 24 (12) : 6693-6724. doi: 10.3934/dcdsb.2019163
[3]

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 & Management Optimization, 2010, 6 (3) : 603-619. doi: 10.3934/jimo.2010.6.603
[4]

Miguel Abadi, Sandro Vaienti. Large deviations for short recurrence. Discrete & Continuous Dynamical Systems, 2008, 21 (3) : 729-747. doi: 10.3934/dcds.2008.21.729
[5]

Jerry L. Bona, Laihan Luo. Large-time asymptotics of the generalized Benjamin-Ono-Burgers equation. Discrete & Continuous Dynamical Systems - S, 2011, 4 (1) : 15-50. doi: 10.3934/dcdss.2011.4.15
[6]

Jean Dolbeault, Giuseppe Toscani. Fast diffusion equations: Matching large time asymptotics by relative entropy methods. Kinetic & Related Models, 2011, 4 (3) : 701-716. doi: 10.3934/krm.2011.4.701
[7]

Sandra Cerrai, Mark Freidlin, Michael Salins. On the Smoluchowski-Kramers approximation for SPDEs and its interplay with large deviations and long time behavior. Discrete & Continuous Dynamical Systems, 2017, 37 (1) : 33-76. doi: 10.3934/dcds.2017003
[8]

Dongmei Zheng, Ercai Chen, Jiahong Yang. On large deviations for amenable group actions. Discrete & Continuous Dynamical Systems, 2016, 36 (12) : 7191-7206. doi: 10.3934/dcds.2016113
[9]

Salah-Eldin A. Mohammed, Tusheng Zhang. Large deviations for stochastic systems with memory. Discrete & Continuous Dynamical Systems - B, 2006, 6 (4) : 881-893. doi: 10.3934/dcdsb.2006.6.881
[10]

Kenrick Bingham, Yaroslav Kurylev, Matti Lassas, Samuli Siltanen. Iterative time-reversal control for inverse problems. Inverse Problems & Imaging, 2008, 2 (1) : 63-81. doi: 10.3934/ipi.2008.2.63
[11]

Rodrigo I. Brevis, Jaime H. Ortega, David Pardo. A source time reversal method for seismicity induced by mining. Inverse Problems & Imaging, 2017, 11 (1) : 25-45. doi: 10.3934/ipi.2017002
[12]

Yongqiang Suo, Chenggui Yuan. Large deviations for neutral stochastic functional differential equations. Communications on Pure & Applied Analysis, 2020, 19 (4) : 2369-2384. doi: 10.3934/cpaa.2020103
[13]

Thomas Bogenschütz, Achim Doebler. Large deviations in expanding random dynamical systems. Discrete & Continuous Dynamical Systems, 1999, 5 (4) : 805-812. doi: 10.3934/dcds.1999.5.805
[14]

Mathias Staudigl, Srinivas Arigapudi, William H. Sandholm. Large deviations and Stochastic stability in Population Games. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021021
[15]

Felix X.-F. Ye, Yue Wang, Hong Qian. Stochastic dynamics: Markov chains and random transformations. Discrete & Continuous Dynamical Systems - B, 2016, 21 (7) : 2337-2361. doi: 10.3934/dcdsb.2016050
[16]

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
[17]

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 & Continuous Dynamical Systems - B, 2018, 23 (6) : 2153-2176. doi: 10.3934/dcdsb.2018229
[18]

Josef DiblÍk, Rigoberto Medina. Exact asymptotics of positive solutions to Dickman equation. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 101-121. doi: 10.3934/dcdsb.2018007
[19]

Zvi Drezner, Carlton Scott. Approximate and exact formulas for the $(Q,r)$ inventory model. Journal of Industrial & Management Optimization, 2015, 11 (1) : 135-144. doi: 10.3934/jimo.2015.11.135
[20]

Albert Fannjiang, Knut Solna. Time reversal of parabolic waves and two-frequency Wigner distribution. Discrete & Continuous Dynamical Systems - B, 2006, 6 (4) : 783-802. doi: 10.3934/dcdsb.2006.6.783

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (76)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy