The stochastic quickest path problem via minimal paths

Abstract

The quickest path problem, a version of the shortest path problem, is to find a single quickest path that sends a given amount of data from the source to the sink with minimum transmission time. More specifically, the capacity of each arc in a 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 a stochastic-flow network. Therefore, the minimum transmission time is not a fixed number. The transmission time can be reduced if the data are transmitted through several minimal paths simultaneously. Focusing on a stochastic flow network with multistate arcs, this article studies the stochastic quickest path problem. We evaluate the probability that d units of data can be sent through two minimal paths (MPs) simultaneously under time constraint T. Such a probability is named the system reliability. A simple algorithm is proposed to generate all (d, T)-MPs and the system reliability can then be computed in terms of (d, T)-MPs by applying inclusion–exclusion.

最快路徑問題 (quickest path problem) 乃是求出一條能夠從起點至終點傳送特定數量資料 ， 且傳輸時間為最小的路徑。 模型中假設網路中每個傳輸邊 (arc) 的容量為確定數值。 然而 ， 由於故障、 維修等因素 ， 許多實際的流量網路如電腦系統、 電信系統等 ， 其傳輸邊的容量應視為隨機性 (stochastic)。 此種流量網路稱之為隨機型流量網路 (stochastic-flow network) ， 而最小的傳輸時間亦不為一確定數值。 然而 ， 若資料的傳輸是同時透過多條最短路徑 ， 則傳輸時間會因此而縮短。 本研究著重於在隨機型網路的多狀態空間下 ， 隨機型最快路徑問題的分析。 研究中分析於時間 T 限制下 ， 該網路能夠同時透過兩條最快路徑成功傳送特定資料數量 d 的機率 ， 此機率定義為系統可靠度。 本研究提供一套演算法產生所有能夠滿足 (d,T)-MPs 限制下的最短路徑 ， 並透過交集互斥法 (inclusion-exclusion) 計算可靠度。

(*聯絡人: [email protected])

Keywords:

• stochastic quickest path problem
• minimal paths
• time constraint
• (d, T)-MP
• inclusion–exclusion

Keywords:

• 關鍵詞： 隨機最快路徑問題 ， 最短路徑 ， 時間限制 ， (d, T)-MP ， 交集互斥法

Notes

(*聯絡人: [email protected])