A two-step approach to restorable dynamic QoS routing

Abstract

Aiming at minimizing the combined bandwidth cost of a pair of disjoint active and backup paths, a popular approach to designing Restorable Dynamic QoS Routing schemes is based on Integer Linear Programming (ILP) formulation. Owing to the very different natures of active and backup paths, we found this approach problematic. In this paper, we propose a simple alternative approach, called two-step routing. In the first step, active path is found using the widest-shortest path (WSP) routing. In the second step, the corresponding backup path is determined using one of the three variants of shortest-widest path (SWP) routing, Basic-SWP, Approximate-SWP and Composite-SWP. Combining both steps, three novel restorable routing algorithms, SBW, SAW and SCW, are obtained. Comparing with the existing best-known algorithms, we show that our two-step routing approach yields noticeably lower call blocking probability, shorter active path length, and adjustable backup path length (depending on the SWP variant adopted). Besides, our two-step routing approach gives a much shorter running time than the ILP approach, which makes it more attractive for dynamic routing.