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]

Angelica Pachon, Federico Polito, Costantino Ricciuti. On discrete-time semi-Markov processes. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1499-1529. doi: 10.3934/dcdsb.2020170
[2]

Serena Dipierro, Benedetta Pellacci, Enrico Valdinoci, Gianmaria Verzini. Time-fractional equations with reaction terms: Fundamental solutions and asymptotics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 257-275. doi: 10.3934/dcds.2020137
[3]

Emre Esentürk, Juan Velazquez. Large time behavior of exchange-driven growth. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 747-775. doi: 10.3934/dcds.2020299
[4]

Junyong Eom, Kazuhiro Ishige. Large time behavior of ODE type solutions to nonlinear diffusion equations. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3395-3409. doi: 10.3934/dcds.2019229
[5]

Xiaoping Zhai, Yongsheng Li. Global large solutions and optimal time-decay estimates to the Korteweg system. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1387-1413. doi: 10.3934/dcds.2020322
[6]

Qiwei Wu, Liping Luan. Large-time behavior of solutions to unipolar Euler-Poisson equations with time-dependent damping. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021003
[7]

Olivier Ley, Erwin Topp, Miguel Yangari. Some results for the large time behavior of Hamilton-Jacobi equations with Caputo time derivative. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021007
[8]

Jérôme Lohéac, Chaouki N. E. Boultifat, Philippe Chevrel, Mohamed Yagoubi. Exact noise cancellation for 1d-acoustic propagation systems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020055
[9]

Guo-Niu Han, Huan Xiong. Skew doubled shifted plane partitions: Calculus and asymptotics. Electronic Research Archive, 2021, 29 (1) : 1841-1857. doi: 10.3934/era.2020094
[10]

Zsolt Saffer, Miklós Telek, Gábor Horváth. Analysis of Markov-modulated fluid polling systems with gated discipline. Journal of Industrial & Management Optimization, 2021, 17 (2) : 575-599. doi: 10.3934/jimo.2019124
[11]

Neil S. Trudinger, Xu-Jia Wang. Quasilinear elliptic equations with signed measure. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 477-494. doi: 10.3934/dcds.2009.23.477
[12]

Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of a Sobolev type impulsive functional evolution system in Banach spaces. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020049
[13]

Jian Zhang, Tony T. Lee, Tong Ye, Liang Huang. An approximate mean queue length formula for queueing systems with varying service rate. Journal of Industrial & Management Optimization, 2021, 17 (1) : 185-204. doi: 10.3934/jimo.2019106
[14]

Joel Kübler, Tobias Weth. Spectral asymptotics of radial solutions and nonradial bifurcation for the Hénon equation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3629-3656. doi: 10.3934/dcds.2020032
[15]

Ugo Bessi. Another point of view on Kusuoka's measure. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020404
[16]

Fabio Camilli, Giulia Cavagnari, Raul De Maio, Benedetto Piccoli. Superposition principle and schemes for measure differential equations. Kinetic & Related Models, 2021, 14 (1) : 89-113. doi: 10.3934/krm.2020050
[17]

Xin Zhao, Tao Feng, Liang Wang, Zhipeng Qiu. Threshold dynamics and sensitivity analysis of a stochastic semi-Markov switched SIRS epidemic model with nonlinear incidence and vaccination. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021010
[18]

Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103
[19]

Isabeau Birindelli, Françoise Demengel, Fabiana Leoni. Boundary asymptotics of the ergodic functions associated with fully nonlinear operators through a Liouville type theorem. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020395
[20]

Harrison Bray. Ergodicity of Bowen–Margulis measure for the Benoist 3-manifolds. Journal of Modern Dynamics, 2020, 16: 305-329. doi: 10.3934/jmd.2020011

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences