System reliability for quickest path problems under time threshold and budget

Yi-Kuei Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Many 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.

Original languageEnglish
Pages (from-to)2326-2332
Number of pages7
JournalComputers and Mathematics with Applications
Issue number8
StatePublished - 1 Oct 2010


  • Budget
  • Lower boundary points
  • Quickest path
  • Stochastic-flow network
  • System reliability
  • Time threshold

Fingerprint Dive into the research topics of 'System reliability for quickest path problems under time threshold and budget'. Together they form a unique fingerprint.

Cite this