An Efficient Path Precomputation Technique for QoS Routing

To enable QoS routing it is necessary to compute the QoS metrics of the paths through the network. Path precomputation, which consists of computing the QoS metrics of the paths at regular intervals can be used for this purpose. The precomputed paths are then used to select a suitable one to route a requested QoS connection. The primary drawback of path precomputation is that the precomputed paths may not be an accurate depiction of the present network state when they are used for routing, which may lead to inefficient and inaccurate routing decisions. The discrepancy between the precomputed paths and the current network state increases as the time elapsed from the last precomputation process increases. In order to alleviate this issue, path precomputation must be performed frequently and to facilitate frequent precomputation, the communication and the computation overheads associated with path precomputation must be reduced. In this paper we present an efficient path precomputation technique which reduces the overheads associated with path precomputation significantly over the prevalent precomputation techniques. We compare the overheads of the proposed technique with the prevalent techniques via extensive simulations. Since the proposed technique offers a significant reduction in the path precomputation overheads, for given level of overheads, it can be employed more frequently than the prevalent techniques. Intuitively, this suggests that the quality and the efficiency of the routing decisions facilitated by the proposed technique will be better compared to the prevalent techniques for the same level of overheads. Our simulation results confirm this intuition