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.