A method to evaluate routing policy through p minimal paths for stochastic case

Abstract: In this paper, a stochastic-flow network is presented to model a computer network in which each arc has various possible capacities and may fail. In order to shorten the transmission time, the transmission protocol allowing the data to be sent through multiple minimal paths simultaneously is utilized for the computer network. However, the minimum transmission time to send a given amount of data is not fixed due to the property of stochastic capacity. Accordingly, the first addressed issue is to evaluate the probability that the network is able to send the data within a time constraint by adopting the transmission protocol. Such a probability is named as transmission reliability that is regarded as a performance indicator to measure the QoS for a computer network. Without knowing all minimal paths in advance, an efficient solution procedure is proposed to calculate transmission reliability. The experimental results of 35 random networks show that the proposed algorithm can be executed efficiently. Moreover, in order to increase transmission reliability, the network administrator decides the routing policy to designate the first and the second priority p minimal paths. The second addressed issue is to evaluate transmission reliability associated with the routing policy. A sort criterion is subsequently presented to find an ideal routing policy. [Copyright &y& Elsevier]