Network resource reallocation strategy based on an improved capacity-load model

• Autorzy: Zhou J. , Huang N. , Sun X. , Xing L. , Zhang S.

Identyfikatory

DOI

10.17531/ein.2015.4.2

Warianty tytułu

PL

Strategia realokacji zasobów sieciowych oparta o udoskonalony model przepustowości-obciążenia

• Języki publikacji: EN

Abstrakty

EN

Network resource reallocation is a common way to help restore performance of network systems subject to cascading failures. Majority of current network resource allocation strategies either give little regard to or make impractical assumptions about the relationship between capacity and load of network nodes, despite this relationship is closely related to the propagation of network failures. In this work we present and verify an improved nonlinear network capacity-load model based on the actual relation between network capacity and load. According to the verified model and realistic dynamic characteristics of network loads, we propose a new network resource reallocation strategy for networks under attacks from the perspective of maintenance. The strategy aims to effectively reallocate new capacity to network nodes after cascading failures occur. Both theoretical analysis and empirical studies are performed on three typical types of complex networks. Results show that the proposed network resource reallocation strategy is more efficient in mitigating devastating impact of cascading failures on network performance, in comparison to other three existing network resource reallocation strategies.

PL

Realokacja zasobów sieci jest powszechnym sposobem, stosowanym w celu przywrócenia działania systemów sieciowych objętych awariami kaskadowymi. Większość współczesnych strategii alokacji zasobów sieciowych kładzie mały nacisk lub czyni niepraktyczne założenia dotyczące zależności między przepustowością i obciążeniem węzłów sieci, choć zależność ta jest ściśle związana z rozchodzeniem się awarii sieci. W niniejszej pracy przedstawiono i zweryfikowano udoskonalony nieliniowy model przepustowości-obciążenia sieci na podstawie rzeczywistej relacji między przepustowością sieci i jej obciążeniem. Na podstawie zweryfikowanych modelu i realistycznych cech dynamicznych obciążeń sieciowych, proponujemy nową strategię realokacji zasobów dla sieci poddawanych atakom z perspektywy utrzymania ruchu. Celem strategii jest skuteczna realokacja nowej przepustowości węzłom sieci po wystąpieniu kaskadowych awarii. Przeprowadzono zarówno teoretyczne analizy, jak i badania empiryczne na trzech typowych rodzajach sieci złożonych. Wyniki pokazują, że proponowana strategia realokacji zasobów sieci jest bardziej skuteczna w zwalczaniu niszczącego wpływu kaskadowych awarii na przepustowość sieci w porównaniu do pozostałych trzech wykorzystywanych strategii realokacji zasobów sieciowych.

Słowa kluczowe

EN

network reliability; maintenance; resource reallocation; cascading failures; capacity-load relationship

PL

niezawodność sieci; utrzymanie ruchu; realokacja zasobów; awaria kaskadowa; zależność przepustowość; obciążenie

• Wydawca: Polskie Naukowo-Techniczne Towarzystwo Eksploatacyjne
• Czasopismo: Eksploatacja i Niezawodność
• Rocznik: 2015
• Tom: Vol. 17, no. 4
• Strony: 487--495
• Opis fizyczny: Bibliogr. 40 poz., rys., tab.

Twórcy

autor

Zhou J.

• School of Reliability and Systems Engineering, Beihang University No.37, Xueyuan Road, Haidian District, Beijing, 100191, China Science & Technology on Reliability & Environmental Engineering Laboratory No.37, Xueyuan Road, Haidian District, Beijing, 100191, China

autor

Huang N.

• School of Reliability and Systems Engineering, Beihang University No.37, Xueyuan Road, Haidian District, Beijing, 100191, China Science & Technology on Reliability & Environmental Engineering Laboratory No.37, Xueyuan Road, Haidian District, Beijing, 100191, China

autor

Sun X.

• School of Reliability and Systems Engineering, Beihang University No.37, Xueyuan Road, Haidian District, Beijing, 100191, China Science & Technology on Reliability & Environmental Engineering Laboratory No.37, Xueyuan Road, Haidian District, Beijing, 100191, China

autor

Xing L.

• Department of Electrical & Computer Engineering, University of Massachusetts Dartmouth, 285 Old Westport Road, MA 02747-2300, Dartmouth, USA

autor

Zhang S.

• School of Reliability and Systems Engineering, Beihang University No.37, Xueyuan Road, Haidian District, Beijing, 100191, China Science & Technology on Reliability & Environmental Engineering Laboratory No.37, Xueyuan Road, Haidian District, Beijing, 100191, China

Bibliografia

• 1. Albert R, Jeong H, Barabási A L. Error and attack tolerance of complex networks. Nature 2000; 406(6794): 378-382, http://dx.doi. org/10.1038/35019019.
• 2. Alipour Z, Monfared M A S, Zio E. Comparing topological and reliability-based vulnerability analysis of Iran power transmission network. Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability 2014; 228(2): 139-151, http://dx.doi.org/10.1177/1748006x13501652.
• 3. Buldyrev S V, Parshani R, Paul G. Catastrophic cascade of failures in interdependent networks. Nature 2010; 464(7291): 1025-1028, http://dx.doi.org/10.1038/nature08932.
• 4. Correa G J, Yusta J M. Grid vulnerability analysis based on scale-free graphs versus power flow models. Electric Power Systems Research 2013; 101: 71-79, http://dx.doi.org/10.1016/j.epsr.2013.04.003.
• 5. Crucitti P, Latora V, Marchiori M. Model for cascading failures in complex networks. Physical Review E 2004; 69(4): 045104, http://dx.doi.org/10.1103/PhysRevE.69.045104.
• 6. Cupac V, Lizier J T, Prokopenko M. Comparing dynamics of cascading failures between network-centric and power flow models. International Journal of Electrical Power & Energy Systems 2013; 49:369-379, http://dx.doi.org/10.1016/j.ijepes.2013.01.017.
• 7. Dorogovtsev S N, Mendes J F. Evolution of networks. Advances in physics 2002; 51(4): 1079-1187, http://dx.doi.org/10.1080/00018730110112519.
• 8. Dou B L, Wang X G, Zhang S Y. Robustness of networks against cascading failures. Physica A: Statistical Mechanics and its Applications 2010; 389(11): 2310-2317, http://dx.doi.org/10.1016/j.physa.2010.02.002.
• 9. Erdös P, Rényi A. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci 1960; 5:17-61.
• 10. Fang Y P, Pedroni N, Zio E. Comparing Network-Centric and Power Flow Models for the Optimal Allocation of Link Capacities in a Cascade-Resilient Power Transmission Network. IEEE Systems Journal, IEEE 2014; PP(99): 1-12.
• 11. Ghamry W K, Elsayed K M. Network design methods for mitigation of intentional attacks in scale-free networks. Telecommunication Systems 2012; 49(3): 313-327, http://dx.doi.org/10.1007/s11235-010-9375-2.
• 12. Glanz J, Perez-Pena R. 90 Seconds That Left Tens of Millions of People in the Dark New York Times. The New York Times 26 August 2003, p.1.
• 13. Goh K I, Kahng B, Kim D. Universal behavior of load distribution in scale-free networks. Physical Review Letters 2001; 87(27): 278701, http://dx.doi.org/10.1103/PhysRevLett.87.278701.
• 14. Holme P, Kim B J. Vertex overload breakdown in evolving networks. Physical Review E 2002; 65(6): 066109, http://dx.doi.org/10.1103/PhysRevE.65.066109.
• 15. Http://www.chinasmartgrid.com.cn/news/20121129/404779.Shtml. (2012, accessed 1 July 2014).
• 16. Huang N, Hou D, Chen Y, Xing L D, Kang R. A network reliability evaluation method based on applications and topological structure. Eksploatacja i Niezawodnosc-Maintenance and Reliability 2011; 3: 77-83.
• 17. Kim D H, Kim B J, Jeong H. Universality class of the fiber bundle model on complex networks. Physical review letters 2005; 94(2): 025501, http://dx.doi.org/10.1103/PhysRevLett.94.025501.
• 18. Kim D H, Motter A E. Resource allocation pattern in infrastructure networks. Journal of Physics A: Mathematical and Theoretical 2008; 41(22): 224019, http://dx.doi.org/10.1088/1751-8113/41/22/224019.
• 19. Latora V, Marchiori M. Efficient behavior of small-world networks. Physical review letters 2001; 87(19): 198701, http://dx.doi.org/10.1103/PhysRevLett.87.198701.
• 20. Lee E, Goh K I, Kahng B, Kim D. Robustness of the avalanche dynamics in data-packet transport on scale-free networks. Physical Review E 2005; 71(5): 056108, http://dx.doi.org/10.1103/PhysRevE.71.056108.
• 21. Lee K, Hui P. High-performance distribution of limited resources via a dynamical reallocation scheme. Physica A: Statistical Mechanics and its Applications 2008; 387(26): 6657-6662, http://dx.doi.org/10.1016/j.physa.2008.08.023.
• 22. Li P, Wang B H, Sun H, Gao P, Zhou T. A limited resource model of fault-tolerant capability against cascading failure of complex network. The European Physical Journal B-Condensed Matter and Complex Systems 2008; 62(1): 101-104, http://dx.doi.org/10.1140/epjb/e2008-00114-1.
• 23. Madar N, Kalisky T, Cohen R, ben-Avraham D, Havlin S. Immunization and epidemic dynamics in complex networks. The European Physical Journal B-Condensed Matter and Complex Systems 2004; 38(2): 269-276, http://dx.doi.org/10.1140/epjb/e2004-00119-8.
• 24. Moreno Y, Pastor-Satorras R,Vespignani A. Critical load and congestion instabilities in scale-free networks. Europhysics Letters 2003; 62(2): 292, http://dx.doi.org/10.1209/epl/i2003-00140-7.
• 25. Pastor-Satorras R, Vespignani A. Epidemics and immunization in scale-free networks. Handbook of graphs and networks: from the genome to the internet 2005; 111-130.
• 26. Reeves J, Ramaswamy A, Locasto M, Bratus S, Smith S. Intrusion detection for resource-constrained embedded control systems in the power grid. International Journal of Critical Infrastructure Protection 2012; 5(2): 74-83, http://dx.doi.org/10.1016/j.ijcip.2012.02.002.
• 27. Sahinoglu Z, Tekinay S. On multimedia networks: self-similar traffic and network performance. Communications Magazine, IEEE 1999; 37(1): 48-52, http://dx.doi.org/10.1109/35.739304.
• 28. Serazzi G, Zanero S. Computer virus propagation models. Performance Tools and Applications to Networked Systems. Springer 2004: 26-50, http://dx.doi.org/10.1007/978-3-540-24663-3_2.
• 29. Shi M C, Pang S P, Zou X Q. An LCOR model for suppressing cascading failure in weighted complex networks. Chinese Physics B 2013; 22(5): 058901, http://dx.doi.org/10.1088/1674-1056/22/5/058901.
• 30. Tao Z, Liu J G, Wang B H. Notes on the algorithm for calculating betweenness. Chinese Physics Letters 2006; 23(8): 2327, http://dx.doi.org/10.1088/0256-307X/23/8/099.
• 31. Wang B, Kim B J. A high-robustness and low-cost model for cascading failures. EPL (Europhysics Letters) 2007; 78(4): 48001, http://dx.doi.org/10.1209/0295-5075/78/48001.
• 32. Wang X, Guan S, Lai C H. Protecting infrastructure networks from cost-based attacks. New Journal of Physics 2009; 11(3): 033006, http://dx.doi.org/10.1088/1367-2630/11/3/033006.
• 33. Watts D J, A simple model of global cascades on random networks. Proceedings of the National Academy of Sciences 2002; 99(9): 5766-5771, http://dx.doi.org/10.1073/pnas.082090499.
• 34. Watts D J, Strogatz S H. Collective dynamics of 'small-world' networks. Nature 1998; 393(6684): 440-442, http://dx.doi.org/10.1038/30918.
• 35. Xia Y, Hill D. Optimal capacity distribution on complex networks. EPL (Europhysics Letters) 2010; 89(5): 58004, http://dx.doi.org/10.1209/0295-5075/89/58004.
• 36. Zhang H, Lan X, Wei D, Mahadevan S, Deng Y. Self-similarity in complex networks: from the view of the hub repulsion. Modern Physics Letters B 2013; 27(28), http://dx.doi.org/10.1142/S0217984913502011.
• 37. Zhang S, Liang M G, Jiang Z Y, Li H J. Queue Resource Reallocation Strategy for Traffic Systems in Scale-Free Network. International Journal of Modern Physics C 2013; 24(03), http://dx.doi.org/10.1142/S0129183113500137.
• 38. Zhou J, Huang N, Sun X L, Wang K L, Yang H Q. A New Model of Network Cascading Failures with Dependent Nodes. Reliability and Maintainability Symposium, 2015: 1-6, http://dx.doi.org/10.1109/rams.2015.7105077.
• 39. Zio E, Sansavini G. Modeling interdependent network systems for identifying cascade-safe operating margins. Reliability, IEEE Transactions on 2011; 60(1): 94-101, http://dx.doi.org/10.1109/TR.2010.2104211.
• 40. Zou C C, Towsley D, Gong W. Email virus propagation modeling and analysis. Report for the Department of Electrical and Computer Engineering. University of Massachusettes, Amherst, USA, 2003.