Cascading Failures in Dynamic Networks

Abstract

Denne masteroppgaven ser på hvordan feil sprer seg gjennom et nettverk. En enkel modell for feil- og reparasjonsdynamikk blir implementert for å simulere feilspredning. I modellen blir nettverkskomponenter forstyrret og kan ødelegges av å ha ødelagte naboer. Sannsynligheten for at en ødelagt komponent blir reparert er avhengig av systemets totale reparasjonskapasitet.

Differensialligningen for modellen har blitt analysert ved bruk av "mean-field approximation" og grafisk analyse av Eran Reches. Resultatene fra analysen indikerer noen kritiske parameterverdier som kan avgjøre om systemet vil bryte sammen eller ikke. Simuleringer blir kjørt for å undersøke om disse parameterverdiene gir samme utfall i de stokastiske simuleringene.

Resultater fra de stokastiske simuleringene viser at analysen kan forutse forekomst av "gode" og "dårlige" utfall i systemet. Ved å dele tidssteg i mindre deler dt går også simuleringsresultatene mot de verdiene for disse utfallene som ble forutsett av analysen.

Resultatene fra simuleringene på ulike typer nettverk viser at "scale-free networks" er mer sårbare enn "random networks", og at "grids" er mer robust mot kaskadefeil. Dette stemmer overens med tidligere studier.

This master thesis looks at how failure spreads across a network. A simple model for failure and repair dynamics is implemented to simulate cascading failure. In it network components are disturbed and can fail if they have failing neighbours. Failed nodes are repaired with probability depending on the total repair capacity for the system.

The differential equation for the model has been analyzed using mean-field approximation and graphical analysis by Eran Reches. The analysis suggests some critical parameter values that determine whether the system crashes or not. Simulations are run to investigate if these parameter values have the same end-state in the stochastic simulations.

Results from the stochastic simulations show that the analysis can predict the presence of "good" and "bad" steady states in the system. Dividing time steps into smaller dt also makes the simulations approach the predicted value for both these steady states and threshold that divides them.

The results of simulations on different types of networks show that scale-free networks are more vulnerable than random networks, and that regular grids are more robust to cascading failure. These results are in keeping with previous studies.