System Reliability of a Limited-Flow Network in Multicommodity Case

摘要

Network analysis is an important approach to model real-world systems. System reliability, and system unreliability are two related performance indices useful to measure the quality level of a supply-demand system. For a binary-state network without flow, the system unreliability is the probability that the system can not connect the source and the sink. Extending to a limited-flow network in the single-commodity case, the arc capacity is stochastic, and the system capacity (i.e. the maximum flow) is not a fixed number. The system unreliability for (d+1), the probability that the upper bound of the system capacity equals d, can be computed in terms of upper boundary points. An upper boundary point is the maximal system state such that the system fulfills the demand. This paper concentrates on a multicommodity limited-flow network (MLFN) in which multicommodity are transmitted through unreliable nodes and arcs. Nevertheless, the system capacity is not suitable to be treated as the maximal sum of the commodity because each commodity consumes the capacity differently. We define the system capacity as a demand vector if the system fulfills at most such a demand vector. The main problem of this paper is to measure the quality level of a MLFN. We propose a new performance index, the probability that the upper bound of the system capacity equals the demand vector subject to the budget constraint, to evaluate the quality level of a MLFN. A branch-and-bound algorithm based on minimal cuts is presented to generate all upper boundary points in order to compute the performance index. The computational complexity of the proposed algorithm is analyzed