Integrating path computation and precomputation for quality-of-service provisioning

QoS provisioning involves reserving resources along a suitable path through the network for the entire lifetime of a connection. To assess the suitability of the possible paths, their QoS metrics which indicate the available resources, should be computed. The QoS metrics can be computed on-demand after the arrival of a QoS connection request or precomputed. On-demand path computation is superior to path precomputation in that suitable paths may be determined using most up to date network state. However, the delay incurred in determining a suitable path on demand may be unacceptable. Path precomputation overcomes the drawback of long delay of on-demand path computation. In addition, path precomputation may be preferred over on-demand path computation for scalability issues, when the number of expected QoS connection requests is very large. Typically, path precomputation needs to be performed frequently, for different routing problems, and from each source node to every possible destination node, which causes excessive consumption of resources. The overheads associated with typical on-demand and path precomputation techniques become unacceptable when routing inter-domain connections, and hence these techniques have been used almost exclusively in the context of intra-domain connections. The present paper describes an effective QoS provisioning technique which integrates path computation and precomputation intelligently in order to exploit the advantages offered by both these approaches. A novel reverse path precomputation technique which reduces the overheads associated with the precomputation process is also described. The presented QoS provisioning technique is suitable for provisioning both intra-domain and inter-domain connections.