Toggling dual label: an exact algorithm for finding the optimal pair of link-disjoint paths in path protection

摘要

Most network real-time applications require reliable transmission against incidents such as link failure. Path protection utilizes a link-disjoint secondary path to protect the primary path. Nevertheless, existing path protection schemes have drawbacks in either resource utilization or recovery response from link failure for real-time services. Recently, the protection was proposed to provide partial bandwidth protection for mission critical data only. The protection enables fast recovery from link failure with efficient resource utilization. However, finding the optimal pair of primary-secondary paths for protection remains a challenge. Existing paths-finding algorithms for the protection utilize the -shortest path approach, considerably increasing the algorithm's complexity. This paper presents a novel exact path-finding algorithm, called the Toggling Dual Label algorithm, to efficiently identify the optimum solution in polynomial time without utilizing the -shortest path algorithm. The proposed algorithm is shown to produce the optimum solution while maintaining a low complexity.