Spare routing reliability for a stochastic flow network through two minimal paths under budget constraint

Yi-Kuei Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

28 Scopus citations


Reducing the transmission time is an imperative issue for many real-life systems such as computers, telecommunication networks, and transportation systems. For a deterministic flow network, the well-known quickest path problem is to find a path with minimum time for sending a specified amount of data through a single minimal path. A stochastic-flow network (SFN) composed by multistate arcs is more suitable to describe some real systems. The minimum transmission time through a SFN is thus not fixed. Allowing the data to be sent through two disjoint minimal paths simultaneously will shorten the transmission time. Hence, this paper is concerned with evaluating the reliability defined as when a SFN can transmit a given amount of data through a specified pair of minimal paths simultaneously under both time and budget constraints. In terms of subsets-union methods, a solution procedure is first proposed to calculate the reliability. Furthermore, a spare routing for boosting the reliability is established in advance to indicate the first pair, and the spare pairs of minimal paths. The corresponding reliability can be subsequently computed. An easy criterion is finally proposed to derive an ideal spare routing with higher reliability.

Original languageEnglish
Article number5411944
Pages (from-to)2-10
Number of pages9
JournalIEEE Transactions on Reliability
Issue number1
StatePublished - 23 Feb 2010


  • Quickest path
  • Spare routing
  • Stochastic-flow network

Fingerprint Dive into the research topics of 'Spare routing reliability for a stochastic flow network through two minimal paths under budget constraint'. Together they form a unique fingerprint.

Cite this