Reliability Evaluation for an Information Network With Node Failure Under Cost Constraint

The quality of service is an important index to measure the performance of an information system. This paper constructs a stochastic-flow network to model the information system. In this network, each node and arc having a designated capacity will have different lower levels due to various partial and complete failures. The studied problem is to evaluate the possibility that a given amount of multicommodity can be sent through an information network under the cost constraint. Such a possibility, which is named the mission reliability, is an appropriate performance index to measure the quality level. The terminology "flow" represents the quantity of data transmitted via such a network, and "demand" represents the required data from clients. Based on the properties of minimal paths, a simple algorithm is first proposed to generate all lower boundary points for the demand; then, the mission reliability can be calculated in terms of such points. The lower boundary point for the demand is a minimal vector, which represents the capacity of each component (arc or node), such that the demand can be fulfilled. Extending the stochastic-flow network to the node failure case, another algorithm is proposed to calculate the mission reliability

I. Introduction

Each arc of a binary-state network has good/bad states. The network reliability, which is the probability that source communicates with sink , can be computed in terms of minimal paths (MPs) or minimal cuts (MCs) [9]. An MP is an ordered sequence of arcs from to that has no cycle. Note that an MP is different from the so-called minimum path. The latter one is a path with minimum cost whenever the arc contains the cost attribute. An MC is a cut whose proper subsets are no longer cuts. The network reliability can be treated as a performance index to measure the quality level for a real-life system with supply–demand character. Aggarwal et al. [3] extended the reliability problem to the node failure case. They proposed the concept that the failure of a node implies the failure of arcs incident from it. Using this concept, the original network with node failure can be modified to be a conventional network with perfect nodes.