Dynamic routing of bandwidth guaranteed tunnels with restoration

This paper presents new algorithms for dynamic routing of restorable bandwidth-guaranteed paths. A straightforward 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 routed. We give an integer programming formulation for this problem which is new. Complete path routing knowledge is a reasonable assumption for a centralized routing algorithm. However, it requires maintenance of non-aggregated or per-path information which is not often desirable particularly when distributed routing is preferred. We show that a partial information scenario which uses only aggregated and not per-path information provides sufficient information for a suitably developed algorithm to be able to perform almost as well as the complete information scenario. In this partial information scenario the routing algorithm only knows what fraction of each link´s bandwidth, is currently used by active paths, and is currently used by backup paths. Obtaining this information is feasible using proposed traffic engineering extensions to routing protocols. We formulate the dynamic restorable bandwidth routing problem in this partial information scenario and develop efficient routing algorithms. We compare there routing performance of this algorithm to a bound obtained using complete information. Our partial information-based algorithm performs very well and its performance in terms of the number of rejected requests is very close to the full information bound