TY - JOUR

T1 - Reliability of a flow network subject to budget constraints

AU - Lin, Yi-Kuei

PY - 2007/3/1

Y1 - 2007/3/1

N2 - The system capacity of a deterministic flow network is the maximum flow from the source to the destination. In a single-commodity stochastic-flow network (branches all have several possible capacities, and may fail), the system reliability, the probability that the maximum flow is larger than or equal to a given demand, is an important performance index to measure the quality level of a network. In a two-commodity stochastic-flow network, different types of commodities are transmitted through the same network simultaneously, and compete for the capacities. We concentrate on the reliability problem for such a network subject to the budget constraint. This paper defines firstly the system capacity as a pattern. We propose a performance index, the probability that the system capacity is less than or equal to a given pattern subject to the budget constraint, to evaluate the system performance. A simple algorithm based on minimal cuts is proposed to generate all maximal vectors meeting the demand and budget constraints. The performance index can then be computed in terms of all such maximal vectors.

AB - The system capacity of a deterministic flow network is the maximum flow from the source to the destination. In a single-commodity stochastic-flow network (branches all have several possible capacities, and may fail), the system reliability, the probability that the maximum flow is larger than or equal to a given demand, is an important performance index to measure the quality level of a network. In a two-commodity stochastic-flow network, different types of commodities are transmitted through the same network simultaneously, and compete for the capacities. We concentrate on the reliability problem for such a network subject to the budget constraint. This paper defines firstly the system capacity as a pattern. We propose a performance index, the probability that the system capacity is less than or equal to a given pattern subject to the budget constraint, to evaluate the system performance. A simple algorithm based on minimal cuts is proposed to generate all maximal vectors meeting the demand and budget constraints. The performance index can then be computed in terms of all such maximal vectors.

KW - Budget

KW - Capacity vectors

KW - Minimal cuts

KW - Performance index

KW - Reliability

KW - Two-commodity

UR - http://www.scopus.com/inward/record.url?scp=34047181508&partnerID=8YFLogxK

U2 - 10.1109/TR.2006.884594

DO - 10.1109/TR.2006.884594

M3 - Article

AN - SCOPUS:34047181508

VL - 56

SP - 10

EP - 16

JO - IEEE Transactions on Reliability

JF - IEEE Transactions on Reliability

SN - 0018-9529

IS - 1

ER -