Network Reliability And Resilience (springerbriefs In Electrical And Computer Engineering)

This book is devoted to the probabilistic description of the behavior of a network in the process of random removal of its components (links, nodes) appearing as a result of technical failures, natural disasters or intentional attacks. It is focused on a practical approach to network reliability and resilience evaluation, based on applications of Monte Carlo methodology to numerical approximation of network combinatorial invariants, including so-called multidimensional destruction spectra. This allows to develop a probabilistic follow-up analysis of the network in the process of its gradual destruction, to identify most important network components and to develop efficient heuristic algorithms for network optimal design. Our methodology works with satisfactory accuracy and efficiency for most applications of reliability theory to real life problems in networks." Network Reliability and Resilience 2 Preface 4 References 6 Contents 7 Notation and Abbreviations 9 1 Theory 1 1.1 Graphs, Networks, Terminals, Structure Function 2 1.2 Network Reliability 6 1.2.1 Binary Networks with Independent Binary Components 6 1.2.2 Network Components with Independent Lifetimes 8 1.2.3 Concluding Remarks: Network Resilience 10 1.3 D-Spectra 11 1.3.1 Introduction 11 1.3.2 D-Spectrum of a Single-Step Network 12 1.3.3 Formula for Network DOWN Probability 17 1.3.4 Networks with Many States 20 1.3.5 D-Spectrum and Signature 21 1.3.6 Renewal Process of Component Failures 23 1.4 Series, Parallel and Recurrent Systems 24 1.4.1 Spectra of Parallel, Series and Recurrent Networks 24 1.4.2 Generalized Series and Parallel Multistate Systems 28 1.5 Networks with Colored Links 29 1.6 Network Component Importance 31 1.6.1 Birnbaum Measure of Component Importance 31 1.6.2 BIM-Spectrum 32 1.6.3 BIMs for Network with Several States 34 1.6.4 Joint Reliability Importance 36 1.7 Reliability Gradient 37 1.7.1 Border States. Evolution Process 37 1.7.2 Gradient Formula 39 1.8 Basic Monte Carlo Algorithms 41 1.8.1 Testing the Network Terminal Connectivity 41 1.8.2 Estimating the D-Spectra and Component Importance 42 1.8.3 Estimating the Gradient Vector 43 1.8.4 Accuracy of Monte Carlo Reliability Estimation 43 1.9 D-Spectra for Multi-Step Systems 46 References 49 2 Applications 1 2.1 Network Under Attack: Symmetric Versus Scale-Free Network 1 2.2 Network Reliability Design 5 2.2.1 Introductory Remarks 5 2.2.2 The Dodecahedron Network 6 2.2.3 Gradient-Based Network Reorganization 7 2.3 Optimal Predisaster Design of Transportation Network 12 2.3.1 Formulation of the Problem. The Network 12 2.3.2 Scenario A 13 2.3.3 Scenario B 14 2.3.4 Scenario C 14 2.4 Network Disintegration 17 2.4.1 Introduction 17 2.4.2 Discrete Densities of the Transition Times 17 2.4.3 The Cumulative D-Spectra and State Probabilities 18 2.4.4 Network State Probabilities as Function of q 19 2.4.5 Network Resilience 21 References 21 Index 1 Cover 1 Network Reliability and Resilience 3 Preface 5 References 7 Contents 8 Notation and Abbreviations 10 1 Theory 12 1.1 Graphs, Networks, Terminals, Structure Function 13 1.2 Network Reliability 17 1.2.1 Binary Networks with Independent Binary Components 17 1.2.2 Network Components with Independent Lifetimes 19 1.2.3 Concluding Remarks: Network Resilience 21 1.3 D-Spectra 22 1.3.1 Introduction 22 1.3.2 D-Spectrum of a Single-Step Network 23 1.3.3 Formula for Network DOWN Probability 28 1.3.4 Networks with Many States 31 1.3.5 D-Spectrum and Signature 32 1.3.6 Renewal Process of Component Failures 34 1.4 Series, Parallel and Recurrent Systems 35 1.4.1 Spectra of Parallel, Series and Recurrent Networks 35 1.4.2 Generalized Series and Parallel Multistate Systems 39 1.5 Networks with Colored Links 40 1.6 Network Component Importance 42 1.6.1 Birnbaum Measure of Component Importance 42 1.6.2 BIM-Spectrum 43 1.6.3 BIMs for Network with Several States 45 1.6.4 Joint Reliability Importance 47 1.7 Reliability Gradient 48 1.7.1 Border States. Evolution Process 48 1.7.2 Gradient Formula 50 1.8 Basic Monte Carlo Algorithms 52 1.8.1 Testing the Network Terminal Connectivity 52 1.8.2 Estimating the D-Spectra and Component Importance 53 1.8.3 Estimating the Gradient Vector 54 1.8.4 Accuracy of Monte Carlo Reliability Estimation 54 1.9 D-Spectra for Multi-Step Systems 57 References 60 2 Applications 62 2.1 Network Under Attack: Symmetric Versus Scale-Free Network 62 2.2 Network Reliability Design 66 2.2.1 Introductory Remarks 66 2.2.2 The Dodecahedron Network 67 2.2.3 Gradient-Based Network Reorganization 68 2.3 Optimal Predisaster Design of Transportation Network 73 2.3.1 Formulation of the Problem. The Network 73 2.3.2 Scenario A 74 2.3.3 Scenario B 75 2.3.4 Scenario C 75 2.4 Network Disintegration 78 2.4.1 Introduction 78 2.4.2 Discrete Densities of the Transition Times 78 2.4.3 The Cumulative D-Spectra and State Probabilities 79 2.4.4 Network State Probabilities as Function of q 80 References 82 2.4.5 Network Resilience 82 Index 84 1.1 Graphs, Networks, Terminals, Structure Function......Page 2 Preface......Page 4 2.2.2 The Dodecahedron Network......Page 6 References......Page 7 Notation and Abbreviations......Page 9 Cover......Page 1 Contents......Page 8 Notation and Abbreviations......Page 10 1.3.1 Introduction......Page 11 1 Theory......Page 12 1.2.1 Binary Networks with Independent Binary Components......Page 17 1.3.4 Networks with Many States......Page 20 1.2.3 Concluding Remarks: Network Resilience......Page 21 1.3.2 D-Spectrum of a Single-Step Network......Page 23 1.4.1 Spectra of Parallel, Series and Recurrent Networks......Page 24 1.3.3 Formula for Network DOWN Probability......Page 28 1.5 Networks with Colored Links......Page 29 1.3.4 Networks with Many States......Page 31 1.3.5 D-Spectrum and Signature......Page 32 1.3.6 Renewal Process of Component Failures......Page 34 1.6.4 Joint Reliability Importance......Page 36 1.7.1 Border States. Evolution Process......Page 37 1.4.2 Generalized Series and Parallel Multistate Systems......Page 39 1.8.1 Testing the Network Terminal Connectivity......Page 41 1.6.1 Birnbaum Measure of Component Importance......Page 42 1.6.2 BIM-Spectrum......Page 43 1.9 D-Spectra for Multi-Step Systems......Page 46 References......Page 49 Preface......Page 5 1.1 Graphs, Networks, Terminals, Structure Function......Page 13 2.3.4 Scenario C......Page 14 2.4.3 The Cumulative D-Spectra and State Probabilities......Page 18 1.2.2 Network Components with Independent Lifetimes......Page 19 Network Reliability and Resilience......Page 3 1.3.1 Introduction......Page 22 1.4.1 Spectra of Parallel, Series and Recurrent Networks......Page 35 1.5 Networks with Colored Links......Page 40 1.6.3 BIMs for Network with Several States......Page 45 1.6.4 Joint Reliability Importance......Page 47 1.7.1 Border States. Evolution Process......Page 48 1.7.2 Gradient Formula......Page 50 1.8.1 Testing the Network Terminal Connectivity......Page 52 1.8.2 Estimating the D-Spectra and Component Importance......Page 53 1.8.4 Accuracy of Monte Carlo Reliability Estimation......Page 54 1.9 D-Spectra for Multi-Step Systems......Page 57 References......Page 60 2.1 Network Under Attack: Symmetric Versus Scale-Free Network......Page 62 2.2.1 Introductory Remarks......Page 66 2.2.2 The Dodecahedron Network......Page 67 2.2.3 Gradient-Based Network Reorganization......Page 68 2.3.1 Formulation of the Problem. The Network......Page 73 2.3.2 Scenario A......Page 74 2.3.4 Scenario C......Page 75 2.4.2 Discrete Densities of the Transition Times......Page 78 2.4.3 The Cumulative D-Spectra and State Probabilities......Page 79 2.4.4 Network State Probabilities as Function of q......Page 80 2.4.5 Network Resilience......Page 82 Index......Page 84 This book is devoted to the probabilistic description of a network in the process of its destruction, i.e. removal of its components (links, nodes) appearing as a result of technical failures, natural disasters or intentional attacks . It is focused on a practical approach to network reliability, based on application of Monte Carlo methodology to numerical evaluation of network most important structural parameters. This allows to obtain a probabilistic description of the network in the process of its destruction, to identify most important network components and to develop efficient heuristic algorithms for network optimal design. The methodology works with satisfactory accuracy and efficiency for small -to-medium size networks