Abstract

Aiming at minimizing the combined bandwidth cost of a pair of disjoint active and backup paths, a popular approach to designing restorable dynamic quality of service (QoS) routing schemes is based on the 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 an alternative approach, called two-step restorable QoS routing. In the first step, an 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 or composite SWP. Combining the two steps, three novel two-step routing algorithms, denoted by SBW, SAW, and SCW, are obtained. Comparing with the best known algorithms, we show that our two-step routing approach yields noticeably lower call blocking probability, shorter active-path length, and additional flexibility of adjusting 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 suitable for dynamic routing.

© 2005 IEEE

PDF Article

References

You do not have subscription access to this journal. Citation lists with outbound citation links are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access OSA Member Subscription

Cited By

You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access OSA Member Subscription