System performance of a two-commodity stochastic-flow network with cost attributes in terms of minimal cuts

摘要

In the single-commodity case, the system capacity of a stochastic-flow network is the maximum flow from the source to the sink. We concentrate on a two-commodity stochastic-flow network (each arc has several possible capacities and may fail) in which each arc has both capacity and cost attributes. Two types of commodities are transmitted through the same network simultaneously and compete for the capacities. The system capacity is defined as a pattern, and a performance index, the probability that the upper bound of the system capacity equals a given pattern under the budget constraint, is proposed to evaluate the system performance. Such a performance index can be computed in terms of the maximal capacity vectors which satisfy both the demand and budget constraints. A simple approach based on minimal cuts is proposed to generate all such maximal capacity vectors.