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

[13]

S. P. Meyn and R. L. Tweedie, "Markov Chains and Stochastic Stability,", Springer-Verlag, (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.  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.  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, (1628).   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.  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.  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.   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.  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).  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.  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.  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., (2008).   Google Scholar

[13]

S. P. Meyn and R. L. Tweedie, "Markov Chains and Stochastic Stability,", Springer-Verlag, (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.  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]

Shihu Li, Wei Liu, Yingchao Xie. Large deviations for stochastic 3D Leray-$ \alpha $ model with fractional dissipation. Communications on Pure & Applied Analysis, 2019, 18 (5) : 2491-2509. doi: 10.3934/cpaa.2019113
[2]

Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258
[3]

Linlin Li, Bedreddine Ainseba. Large-time behavior of matured population in an age-structured model. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2561-2580. doi: 10.3934/dcdsb.2020195
[4]

Charlene Kalle, Niels Langeveld, Marta Maggioni, Sara Munday. Matching for a family of infinite measure continued fraction transformations. Discrete & Continuous Dynamical Systems - A, 2020, 40 (11) : 6309-6330. doi: 10.3934/dcds.2020281
[5]

Pavel I. Naumkin, Isahi Sánchez-Suárez. Asymptotics for the higher-order derivative nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021028
[6]

V. Vijayakumar, R. Udhayakumar, K. Kavitha. On the approximate controllability of neutral integro-differential inclusions of Sobolev-type with infinite delay. Evolution Equations & Control Theory, 2021, 10 (2) : 271-296. doi: 10.3934/eect.2020066
[7]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018
[8]

Jianping Gao, Shangjiang Guo, Wenxian Shen. Persistence and time periodic positive solutions of doubly nonlocal Fisher-KPP equations in time periodic and space heterogeneous media. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2645-2676. doi: 10.3934/dcdsb.2020199
[9]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[10]

Cécile Carrère, Grégoire Nadin. Influence of mutations in phenotypically-structured populations in time periodic environment. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3609-3630. doi: 10.3934/dcdsb.2020075
[11]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183
[12]

Guillermo Reyes, Juan-Luis Vázquez. Long time behavior for the inhomogeneous PME in a medium with slowly decaying density. Communications on Pure & Applied Analysis, 2009, 8 (2) : 493-508. doi: 10.3934/cpaa.2009.8.493
[13]

Wei-Jian Bo, Guo Lin, Shigui Ruan. Traveling wave solutions for time periodic reaction-diffusion systems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (9) : 4329-4351. doi: 10.3934/dcds.2018189
[14]

Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044
[15]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069
[16]

Zengyun Wang, Jinde Cao, Zuowei Cai, Lihong Huang. Finite-time stability of impulsive differential inclusion: Applications to discontinuous impulsive neural networks. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2677-2692. doi: 10.3934/dcdsb.2020200
[17]

Elena K. Kostousova. External polyhedral estimates of reachable sets of discrete-time systems with integral bounds on additive terms. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021015
[18]

Marita Holtmannspötter, Arnd Rösch, Boris Vexler. A priori error estimates for the space-time finite element discretization of an optimal control problem governed by a coupled linear PDE-ODE system. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021014

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences