In the last few years, various quality of service (QoS) routing algorithms have been proposed. There is an assumption in most of these proposals that the information being used to determine the paths is accurate. Ideally, this is not the case. There is a certain time interval before the routing information database gets updated. Within this time interval, the routing algorithm uses information that might have changed since the update took place. A few routing approaches consider this inaccuracy factor in their operations. The routing algorithm presented in this paper is one of the efforts in this direction.

The proposed approach, called RandomRoute, is a randomized, on-demand QoS routing algorithm for use on networks with inaccurate network state information. The metrics considered are safety (the probability that the bandwidth required will be satisfied) and delay. The randomized approach is preferred over the deterministic approach, since it leads to load balancing, prevention of performance degradation, and improvement of overall network performance. Route computation is done on demand, since this strategy uses the most recent state information and reduces storage usage. There is no QoS routing table maintained. RandomRoute assumes that all hops have the same delay.

The two metrics are precomputed and used in the route computation. This practice also helps eliminate links that do not satisfy the metrics requirements; the probability that a link will be selected for the path is dependent on both bandwidth and delay. The path is computed by selecting the intermediate links from the source to the destination, using the probability computed for each possible option. The efficiency of the approach also depends on the number of times a satisfactory path is searched; there is a tradeoff between successful determination of the path and computation time. The overall time complexity of the algorithm is O(2(n log n + m) + m * (loopbound + 2)) where n is the number of nodes, m is the number of links, and loopbound is the number of times for searching a satisfactory path.

The performance of RandomRoute is better than three other similar algorithms: shortest path, safest-shortest, and shortest-safest. This is irrespective of the triggering policy used for the update of state information. Actual performance depends on the triggering policy, since the accuracy of the state information depends on it.