Using minimal cuts to evaluate the system reliability of a stochastic-flow network with failures at nodes and arcs

This paper deals with a stochastic-flow network in which each node and arc has a designated capacity, which will have different lower levels due to various partial and complete failures. We try to evaluate the system reliability that the maximum flow of the network is not less than a demand (d+1). A simple algorithm in terms of minimal cuts is first proposed to generate all upper boundary points for d, and then the system reliability can be calculated in terms of such points. The upper boundary point for d is a maximal vector, which represents the capacity of each component (arc or node), such that the maximum flow of the network is d. A computer example is shown to illustrate the solution procedure.     

Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery

This paper introduces an evolutionary optimization approach that can be readily applied to solve stochastic network interdiction problems (SNIP). The network interdiction problem solved considers the minimization of the cost associated with an interdiction strategy such that the maximum flow that can be transmitted between a source node and a sink node for a fixed network design is greater than or equal to a given reliability requirement. Furthermore, the model assumes that the nominal capacity of each network link and the cost associated with their interdiction can change from link to link and that such interdiction has a probability of being successful. This version of the SNIP is for the first time modeled as a capacitated network reliability problem allowing for the implementation of computation and solution techniques previously unavailable. The solution process is based on an evolutionary algorithm that implements: (1) Monte-Carlo simulation, to generate potential network interdiction strategies, (2) capacitated network reliability techniques to analyze strategies’ source-sink flow reliability and, (3) an evolutionary optimization technique to define, in probabilistic terms, how likely a link is to appear in the final interdiction strategy. Examples for different sizes of networks are used throughout the paper to illustrate the approach.     

A model for the seismic reliability assessment of electric power transmission systems

A comprehensive model to evaluate the seismic reliability of electric power transmission systems is presented. The model provides information on the probability of structural failure of critical equipment at the major substations, from which the corresponding probabilities of power disruption to a given service area are determined. With the proposed methodology earthquake ground motions are defined as stochastic processes, and seismic capacities of electrical equipment are determined on the basis of available test data and simple modeling, from which fragility functions of critical equipment and specific substations are developed. Probabilities of power disruption resulting from network disconnectivity and abnormal power flow are assessed through Monte Carlo simulation. As a case study, the proposed model is applied to the electric power network in San Francisco and vicinity under the 1989 Loma Prieta earthquake, and the probabilities of power interruption are contrasted with the actual power failures observed during that earthquake.     

Maximal network reliability for a stochastic power transmission network

Many studies regarded a power transmission network as a binary-state network and constructed it with several arcs and vertices to evaluate network reliability. In practice, the power transmission network should be stochastic because each arc (transmission line) combined with several physical lines is multistate. Network reliability is the probability that the network can transmit d units of electric power from a power plant (source) to a high voltage substation at a specific area (sink). This study focuses on searching for the optimal transmission line assignment to the power transmission network such that network reliability is maximized. A genetic algorithm based method integrating the minimal paths and the Recursive Sum of Disjoint Products is developed to solve this assignment problem. A real power transmission network is adopted to demonstrate the computational efficiency of the proposed method while comparing with the random solution generation approach.     

Use of Stochastic Networks in Reliability Analysis

The application of stochastic networks to reliability analysis is discussed. The article illustrates how the conventional “reliability block diagram” can be replaced by a stochastic network. Once the stochastic network is developed the analyst is able to determine the mean and variance of the reliability of complex systems with relative ease by using the computer program presented. The program is coded in FORTRAN IV and will evaluate the reliability of any mixture of series and parallel subsystems. An example problem is presented in order to illustrate the technique and the use of the program.     

System reliability of a manufacturing network with reworking action and different failure rates

From the perspective of network analysis, the manufacturing system can be constructed as a stochastic-flow network, since the capacity of each machine is stochastic (i.e. multistate) owing to the failure, partial failure, and maintenance. Considering reworking action and different failure rates of machines, the input flow (raw materials/work in process) processed by each machine might be defective, and therefore the output flow (work in process/products) would be less than the input amount. To evaluate the capability of the manufacturing system, we measure the probability that the manufacturing network can satisfy demand. Such a probability is defined as the system reliability. A decomposition method is first proposed to divide the manufacturing network into one general processing path and one reworking path. Subsequently, two algorithms are utilised for different network models to generate the lower boundary vector of machine capacity to guarantee that the manufacturing network is able to produce sufficient products fulfilling the demand. The system reliability of the manufacturing network can be derived in terms of such a capacity vector afterwards.     

Confidence bounds for the reliability of binary capacitated two-terminal networks

Binary capacitated two-terminal reliability at demand level d (2TR_d) is defined as the probability that network capacity, generated by binary capacitated components, between specified source and sink nodes is greater than or equal to a demand of d units. For the components that comprise these networks, reliability estimates are usually obtained from some source of testing. For these estimates and depending on the type of testing, there is an associated uncertainty that can significantly affect the overall estimation of 2TR_d. That is, an accurate estimate of 2TR_d is highly dependent on the uncertainty associated to the reliability of the network components. Current methods for the estimation of network reliability and associated uncertainty are restricted to the case where the network follows a series-parallel architecture and the components are binary and non-capacitated. For different capacitated network designs, an estimate on 2TR_d can only be approximated for specific scenarios. This paper presents a bounding approach for 2TR_d by explaining how component reliability and associated uncertainty impact estimates at the network level. The proposed method is based on a structured approach that generates a α-level confidence interval (CI) for binary capacitated two-terminal network reliability. Simulation results on different test networks show that the proposed methods can be used to develop very accurate bounds of two-terminal network reliability.     

Lifecycle operational reliability assessment of water distribution networks based on the probability density evolution method

In this study, a lifecycle operational reliability assessment framework for water distribution networks (WDNs) is proposed on the basis of the probability density evolution method (PDEM). The occurrence models of daily accidents are fitted using the maintenance data provided by a local water administration sector. For a given accident, two types of accidents (e.g., leaks and bursts) are distinguished in different occurrence probabilities and simulated in various ways. The pipe deterioration process in the lifecycle is reflected by incorporating the time-dependent pipe roughness model. Considering various randomness in the model, PDEM, a newly proposed and developed method for a stochastic system, is used to evaluate the lifecycle operational reliability of WDNs. The framework is demonstrated using an actual WDN, and the nodal reliabilities in the lifecycle are obtained. Comparisons of the operational reliabilities of all nodes calculated via the PDEM and Monte Carlo simulations prove that PDEM is an accurate and highly efficient method.     

Analytical models of blocking probability for multi-granularity cross-connect-based optical networks

Multi-granularity optical cross-connect (MG-OXC)-based optical network is a promising optical network architecture as it is capable of flexible switching at different granularity levels. In MG-OXC-based optical networks, wavelength conversion (WC) capability and the number of usable add/drop ports of the nodes are two key factors affecting its performance. Two analytical models of blocking probability for MG-OXC-based optical networks both without WC capability and with sparse WC capability are proposed, exploiting Erlang?s loss formula and birth?death process. Based on the models and simulation, the impact of WC capability and the number of add/drop ports on the blocking probability are investigated. Three kinds of granularities (i.e. fibre, waveband and wavelength) are considered in MG-OXC nodes to reduce the complexity and size of switch fabric. Both the analytical and simulation results are given on two network topologies under dynamic traffic patterns. Simulation results show that the proposed models are accurate and effective for the analysis of blocking probability in MG-OXC-based optical networks.     

Fast approximate methods for the reliability analysis of computer networks

The complexity of computer communication networks has taken a dramatic upswing, following significant developments in electronic technology such as medium and large scale integrated circuits and microprocessors. Although components of a computer communication network are broadly classified into software, hardware and communications, the most important problem is that of ensuring the reliable flow of information from source to destination. An important parameter in the analysis of these networks is to find the probability of obtaining a situation in which each node in the network communicates with all other remaining communication centres (nodes). This probability, termed as overall reliability, can be determined using the concept of spanning trees. As the exact reliability evaluation becomes unmanageable even for a reasonable sized system, we present an approximate technique using clustering methods. It has been shown that when component reliability ⩾ 0.9, the suggested technique gives results quite close to those obtained by exact methods with an enormous saving in computation time and memory usage. For still quicker reliability analysis while designing the topological configuration of real-time computer systems, an empirical form of the reliability index is proposed which serves as a fairly good indicator of overall reliability and can be easily incorporated in a design procedure, such as local search, to design maximally reliable computer communication network.     

A simple algorithm to generate all (d,B)-MCs of a multicommodity stochastic-flow network

Both minimal paths and minimal cuts are important media to evaluate the performance indexes, the system reliability or unreliability, for a single-commodity stochastic-flow network. This paper concentrates on a multicommodity stochastic-flow network in which each arc has both the capacity and cost attributes. Different from the single-commodity case, the system capacity is a pattern for multicommodity case. Since the traditional performance indexes are not suitable for multicommodity case, we propose a new performance index, the probability that the system capacity is less than or equal to a given pattern under the budget constraint. A simple algorithm based on minimal cuts is presented to generate all (d,B)-MCs that are the maximal capacity vectors meeting the demand d and budget B. The proposed performance index can be evaluated in terms of (d,B)-MCs.     

First-passage failure of quasi linear systems subject to multi-time-delayed feedback control and wide-band random excitation

A procedure for studying the first-passage failure of quasi-linear systems subject to multi-time-delayed feedback control and wide-band random excitation is proposed. The stochastic averaging method for quasi-integrable Hamiltonian systems is first introduced. The backward Kolmogorov equation governing the conditional reliability function and a set of generalized Pontryagin equations governing the conditional moments of first-passage time are then established. The conditional reliability function, the conditional probability density and moments of first-passage time are obtained by solving the backward Kolmogorov equation and generalized Pontryagin equations with suitable initial and boundary conditions. An example is given to illustrate the proposed procedure and the results from digital simulation are obtained to verify the effectiveness of the proposed procedure. The effects of time delay in feedback control forces on the conditional reliability function, conditional probability density and moments of first-passage time are analyzed.     

Evaluate the performance of a stochastic-flow network with cost attribute in terms of minimal cuts

This paper proposes a performance index to measure the quality level of a stochastic-flow network in which each node has a designated capacity, which will have different lower levels due to various partial and complete failures. The performance index is the probability that the maximum flow of the network equals the demand d without exceeding the budget b. A simple algorithm in terms of minimal cuts is first proposed to generate all upper boundary points for (d, b), and then the probability that the maximum flow is less than or equal to d can be calculated in terms of such points. The upper boundary point for (d, b) is a maximal vector representing the capacity of each arc such that the maximum flow of the network under the budget b is d. The performance index can be calculated by repeating the proposed algorithm to obtain all upper boundary point for (d−1, b). A benchmark example is shown to illustrate the solution procedure.     

System reliability for joint minimal paths under time constraint

The quickest path in a transmission problem for a multistate flow network is considered in this article. In this problem, a given amount of data is transmitted to the destination through multiple minimal paths (MPs) simultaneously, and the probability of complete transmission within a time constraint is of interest. In particular, the MPs are joint such that a constriction occurs. An algorithm is developed by applying Monte Carlo simulation to find the system reliability. Furthermore, the proposed algorithm can be used to manage situations with either joint or disjoint MPs. Although the system reliability obtained from this algorithm is an approximate value, the experiments and inference statistics indicate that the expected value is very close to the actual system reliability.     

随机结构动力可靠度分析的概率密度演化方法

基于随机结构动力反应分析的概率密度演化方法，提出了一类新的随机结构动力可靠度分析方法。在随机结构动力反应概率密度演化方程的基础上，对于首次超越问题，根据所给的首次超越破坏准则施加相应的吸收壁边界条件，求解具有吸收壁边界条件的概率密度演化方程并在安全域内积分．给出结构的动力可靠度。结合精细时程积分方法和具有TVD性质的差分格式，讨论了计算结构动力可靠度的数值方法。以八层框架结构为例进行了动力可靠度分析并与随机模拟分析结果进行了比较。     

System Travel Time Reliability: A Measure of the Quality of Service of Networks

In this study, the travel time reliability of network systems is measured by travel time limitation as well as two‐terminal reliability. In the network, each arc is a binary random variable weighted by travel time as well as by operational probability. The performance index or QoS of a network system indicates the probability that the source node can successfully travel to the destination node, while satisfying the travel time limitation. Unlike existing literature that evaluated travel time reliability via a single optimization path, the proposed index focuses on the performance of the entire network system. This study presents an efficient decomposition method in computing QoS based on the Dijkstra shortest path method. We employ a small network to demonstrate the algorithm step by step. In addition, computational experiments conducted on a prototype network show that the proposed algorithm is superior to existing methods. Copyright © 2015 John Wiley & Sons, Ltd.     

Towards Fully Secure 5G Ultra-Low Latency Communications: ACost-Security Functions Analysis

Future components to enhance the basic, native security of 5G networks are either complex mechanisms whose impact in the requiring 5G communications are not considered, or lightweight solutions adapted to ultra-reliable low-latency communications (URLLC) but whose security properties remain under discussion. Although different 5G network slices may have different requirements, in general, both visions seem to fall short at provisioning secure URLLC in the future. In this work we address this challenge, by introducing cost-security functions as a method to evaluate the performance and adequacy of most developed and employed non-native enhanced security mechanisms in 5G networks. We categorize those new security components into different groups according to their purpose and deployment scope. We propose to analyze them in the context of existing 5G architectures using two different approaches. First, using model checking techniques, we will evaluate the probability of an attacker to be successful against each security solution. Second, using analytical models, we will analyze the impact of these security mechanisms in terms of delay, throughput consumption, and reliability. Finally, we will combine both approaches using stochastic cost-security functions and the PRISM model checker to create a global picture. Our results are first evidence of how a 5G network that covers and strengthened all security areas through enhanced, dedicated non-native mechanisms could only guarantee secure URLLC with a probability of ∼55%.     

Proxy-Based Hierarchical Distributed Mobility Management for Tactical Networks

An important requirement in a military domain is a highly reliable mobility management method, especially when components of the networks are moving in tactical network environments. To increase reliability, the mobility management technology of the tactical network should be able to reflect the characteristics of the tactical network, such as a limited environment, failure, and hierarchical unit structure. In this paper, we propose a proxy-based hierarchical distributed mobility management scheme, which is highly focused on tactical networks. Considering the characteristics of tactical networks, the proposed scheme is composed of the following: 1) a proxy-based method, 2) a distributed mobility management method that synchronizes a mobility database between entities, and 3) a method of managing mobility by dividing the tactical network into upper and lower layers. Mathematical analysis and modeling and simulation results demonstrate that the method outperforms the existing state-of-the-art method in overcoming entity failure, handover cost, and delay in tactical environments.     

Dynamic response and reliability analysis of structures with uncertain parameters

An original approach for dynamic response and reliability analysis of stochastic structures is proposed. The probability density evolution equation is established which implies that incremental rate of the probability density function is related to the structural response velocity. Therefore, the response analysis of stochastic structures becomes an initial‐value partial differential equation problem. For the dynamic reliability problem, the solution can be derived through solving the probability density evolution equation with an initial value condition and an absorbing boundary condition corresponding to specified failure criterion. The numerical algorithm for the proposed method is suggested by combining the precise time integration method and the finite difference method with TVD scheme. To verify and validate the proposed method, a SDOF system and an 8‐storey frame with random parameters are investigated in detail. In the SDOF system, the response obtained by the proposed method is compared with the counterparts by the exact solution. The responses and the reliabilities of a frame with random stiffness, subject to deterministic excitation or random excitation, are evaluated by the proposed method as well. The mean, the standard deviation and the reliabilities are compared, respectively, with the Monte Carlo simulation. The numerical examples verify that the proposed method is of high accuracy and efficiency. Moreover, it is found that the probability transition of structural responses is like water flowing in a river with many whirlpools, showing complexity of probability transition process of the stochastic dynamic responses. Copyright © 2004 John Wiley & Sons, Ltd.     

An efficient method for reliability evaluation of multistate networks given all minimal path vectors

The multistate networks under consideration consist of a source node, a sink node, and some independent failure-prone components in between the nodes. The components can work at different levels of capacity. For such a network, we are interested in evaluating the probability that the flow from the source node to the sink node is equal to or greater than a demanded flow of d units. A general method for reliability evaluation of such multistate networks is using minimal path (cut) vectors. A minimal path vector to system state d is called a d-MP. Approaches for generating all d-MPs have been reported. Given that all d-MPs have been found, the issue becomes how to evaluate the probability of the union of the events that the component state vector is greater than or equal to at least one of the d-MPs. There is a need for a more efficient method of determining the probability of this union of events. In this paper, we report an efficient recursive algorithm for this union probability evaluation based on the Sum of Disjoint Products (SDP) principle, and name it the Recursive Sum of Disjoint Products (RSDP) algorithm. The basic idea is that, based on the SDP principle and a specially defined “maximum” operator, “⊕”, the probability of a union with L vectors can be calculated via calculating the probabilities of several unions with L-1 vectors or less. The correctness of RSDP is illustrated. The efficiency of this algorithm is investigated by comparing it with an existing algorithm that is generally accepted to be efficient. It is found that RSDP is more efficient than the existing algorithm when the number of components of a system is not too small. RSDP provides us with an efficient, systematic and simple approach for evaluating multistate network reliability given all d-MPs.