System reliability for quickest path problems under time threshold and budget

AbstractMany studies on hardware framework and routing policy are devoted to reducing the transmission time for a computer network. The quickest path problem thus arises to find a path which sends a given amount of data from the source to the sink such that the transmission time is minimized. More specifically, the capacity of each arc in the network is assumed to be deterministic. However, in many real-life networks such as computer systems, telecommunication systems, etc., the capacity of each arc is stochastic due to failure, maintenance, etc. Such a network is named stochastic-flow network. Hence, the minimum transmission time is not a fixed number. We extend the quickest path problem to evaluating the probability that d units of data can be sent from the source to the sink under both time threshold T and budget B. Such a probability is named system reliability. A simple algorithm is proposed to generate all lower boundary points for (d,T,B) and the system reliability can then be computed in terms of such points