Effective algorithms for finding optimum pairs of link-disjoint paths in α + 1 path protection

摘要

Path protection ensures continuity of network services against link failure by assigning a link-disjoint secondary path to protect the primary path. Existing path protection schemes are classified into dedicated- and shared-path protections. However, these schemes either require high redundancy or substantial response time to resolve link failure. The end-to-end partial bandwidth protection scheme, denoted as α + 1 protection, offers an alternative where only critical real-time information of the primary path is duplicated over the secondary path. The parameter α is defined as the ratio of the protection bandwidth (of secondary path) to the full bandwidth (of primary path). The challenge of α + 1 protection is to identify a pair of primary-secondary paths with lowest total cost comprising the optimal solution. This paper derives the properties inherent in the optimal solution and subsequently presents two optimum paths-finding algorithms. The performance of the proposed algorithms over existing approaches is then compared through simulation.