A new cascading failure model with delay time in congested complex networks

Abstract

Cascading failures often occur in congested complex networks. Cascading failures can be expressed as a three-phase process: generation, diffusion, and dissipation of congestion. Different from the betweenness centrality, a congestion function is proposed to represent the extent of congestion on a given node. Inspired by the restart process of a node, we introduce the concept of “delay time,” during which the overloaded node cannot receive or forward any traffic, so an intergradation between permanent removal and nonremoval is built and the flexibility of the presented model is demonstrated. Considering the connectivity of a network before and after cascading failures is not cracked because the overloaded node are not removed from network permanently in our model, a new evaluation function of network efficiency is also proposed to measure the damage caused by cascading failures. Finally, we investigate the effects of network structure and size, delay time, processing ability, and traffic generation speed on congestion propagation. Cascading processes composed of three phases and some factors affecting cascade propagation are uncovered as well.

Keywords

Complex networks / cascading failures / congestion effects / propagation model

References

[1] Albert R., Albert I., Nakarado G.L.. Structural vulnerability of the North American power grid. Physical Review E, 2004, 69(2): 025103.

[2] Ash J., Newth D.. Optimizing complex networks for resilience against cascading failure. Physica A, 2007, 380: 673-683.

[3] Barabási A.-L., Albert R.. Emergence of scaling in random networks. Science, 1999, 286(5439): 509-511.

[4] Bollobás B.. Random Graphs, 1985, London: Academic Press.

[5] Brandes U.. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 2001, 25: 163-177.

[6] Carreras B.A., Lynch V.E., Dobson I., Newman D.E.. Complex dynamics of blackouts in power transmission systems. Chaos, 2004, 14(3): 643-652.

[7] Cholvi V.. Dissemination of information in complex networks with congestion. Physica A, 2006, 366: 571-577.

[8] Chowdjury, B.H. & Baravc, S. (2006). Creating cascading failure scenarios in interconnected power systems. In: IEEE Power Engineering Society General Meeting, Montreal, Canada, July 18–22, 2006

[9] David B.C., Carl S.Y.. Infection dynamics on the Internet. Computers & Security, 2005, 24(4): 280-286.

[10] Dueñas-Osorio L., Vemuru S.M.. Cascading failures in complex infrastructure systems. Structural Safety, 2009, 31(2): 157-167.

[11] Gallos L.K., Cohen R., Argyrakis P., Bunde A., Havlin S.. Stability and topology of scale-free networks under attack and defense strategies. Physical Review Letters, 2005, 94: 188701.

[12] Galstyan A., Cohen P.. Cascading dynamics in modular networks. Physical Review E, 2007, 75: 036109.

[13] Jacobson V.. Congestion avoidance and control. SIGCOMM Computer Communication Review, 1988, 18(4): 314-329.

[14] Kim D.-H., Motter A.E.. Resource allocation pattern in infrastructure networks. Journal of Physics A: Mathematical and Theoretical, 2008, 41: 224019.

[15] Latora V., Marchiori M.. Efficient behavior of small-world networks. Physical Review Letters, 2001, 87(19): 198701.

[16] Motter A.E.. Cascade control and defense in complex networks. Physical Review Letters, 2004, 93(9): 098701.

[17] Motter A.E., Lai Y.-C.. Cascade-based attacks on complex networks. Physical Review E, 2002, 66(6): 065102.

[18] Ohira T., Sawatari R.. Phase transition in computer network traffic model. Physical Review E, 1998, 58(1): 193-195.

[19] Petersen I.. Fatal Defect: Chasing Killer Computer Bugs, 1996, New York: Vintage

[20] Sharma S., Srivastava L.. Prediction of transmission line overloading using intelligent technique. Applied Soft Computing, 2008, 8(1): 626-633.

[21] Shen B., Gao Z.Y.. Dynamical properties of transportation on complex networks. Physica A, 2008, 387(5–6): 1352-1360.

[22] Siganos G., Faloutsos M., Faloutsos P., Faloutsos C.. Power-laws and the AS-level internet topology. IEEE/ACM Transactions on Networking, 2003, 11(4): 514-524.

[23] Wang W.X., Chen G.R.. Universal robustness characteristic of weighted networks against cascading failure. Physical Review E, 2008, 77: 026101.

[24] Watts D.J.. A simple model of global cascades on random networks. Proceedings of the National Academy of Sciences, USA, 2002, 99(9): 5766-5771.

[25] Wu J.J., Gao Z.Y., Sun H.J.. Effects of the cascading failures on scale-free traffic networks. Physica A, 2007, 378(2): 505-511.

[26] Wu J.J., Sun H.J., Gao Z.Y.. Cascading failures on weighted urban traffic equilibrium network. Physica A, 2007, 386(1): 407-413.

[27] Zhao L., Park K., Lai Y.-C.. Attack vulnerability of scale-free networks due to cascading breakdown. Physical Review E, 2004, 70(3): 035101.

[28] Zheng J.F., Gao Z.Y., Zhao X.M.. Modeling cascading failures in congested complex networks. Physica A, 2007, 385(2): 700-706.