Dynamic Routing of Bandwidth Guaranteed Tunnels with Restoration

This paper presents new algorithms for dynamic routing of restorable bandwidth guaranteed tunnels. Dynamic routing implies routing of requests that arrive one-by-one with no a priori knowledge of future arrivals, and so necessitating use of on-line algorithms. Restorability implies that to successfully route a tunnel both an active path and an alternate link (node) disjoint backup path have to be routed at the same time. This joint on-line routing problem arises in many contexts and is becoming particularly important with the trend in backbone transport networks toward dynamic restorable bandwidth provisioning. A straightforward solution solution for the restoration problem is to find two disjoint paths. However, this results in excessive resource usage for backup paths and does not satisfy the implicit service provider requirement of optimizing network resource utilization so as to increase the number of potential future demands that can be route. Given a restoration objective, such as protection against single link failures, backup path bandwidth usage can be reduced by judicious sharing of backup paths amongst certain active paths while still maintaining restorability.