Sequential capacity determination of subnetworks in network performance analysis

摘要

In the process of performance evaluation for a stochastic network whose links are subject to failure, subnetworks are repeatedly generated to reflect various states of the network, and the capacity of each subnetwork is to be determined upon generation. The capacity of a network is the maximum amount of flow which can be transmitted through the network. Although there are existing algorithms for network capacity computation, it would create a great number of repetitions to compute the capacity of each subnetwork anew upon generation in the process. This is true because subnetworks are generated by combining certain links to the current one, and hence each current subnetwork is embedded in those new subnetworks. Recently, a number of methods have been proposed in the context of searching a method which efficiently computes the capacity of subnetworks by utilizing the given information of minimal paths, and preferably without many repetitions in sequential computations. But, most of the methods still have drawbacks of either failing to give correct results in certain situations, or computing the capacity of each subnetwork anew whenever the subnetwork is generated. In this paper, we propose a method based on the concepts of signed minimal path, and unilateral link, as defined in the text. Our method not only computes the capacity of each subnetwork correctly, but also eliminates the repetitive steps in sequential computations, and thereby efficiently reduces the number of subnetworks to consider for capacity computation as well. Numerical examples are presented to illustrate the method. The drawbacks of other methods are also discussed with counter examples.