A method to evaluate the routing policy with two minimal paths within time threshold

摘要

Two attributes, the capacity and the lead time, are involved in the quickest path problem which finds a path with the minimum transmission time. The capacity of each edge is assumed to be deterministic in this problem. However, in many real-life networks such as computer, telecommunication, logistics networks, etc., each edge should be multistate due to failure, maintenance, etc. Such a network is named a multistate network. Hence, the minimum transmission time through a multistate network is not fixed. We evaluate the system reliability that a specified amount of data can be sent through a pair of minimal paths simultaneously within the time threshold. A solution procedure is first proposed to calculate it. In order to boost the system reliability, the network administrator decides the routing policy in advance to indicate the first and the second priority pairs of minimal paths. The second one will be responsible for the transmission duty if the first one fails. According to the routing policy, the system reliability can be subsequently computed. The case to transmit data through more than two minimal paths can be extended easily.