A Minimum Cost Active and Backup Path Algorithm with SRLG Constraints

As more and more mission critical service are now transported over high-speed networks, it becomes an important issue to make use of the relativity of multiple link/node failures and improve transport performance for high-speed networks. In this paper, we propose a novel algorithm called low cost an S disjoint paths algorithm (LCSD for short) to establish a SRLG disjoint active path and backup path pair for network protection. Based on the TF algorithm, LCSD algorithm introduces the number of links which relate to the SRLG as a new constraint. Through link weight adjustment before the second time SPF calculate, the backup path can avoid the risk sharing with active path. Theoretical analysis and experiment results have shown that LCSD algorithm resolved the trap problem and path pair total cost non-optimal problem under SRLG disjoint constraint. Compared with RF and TF algorithms, LCSD algorithm is significantly superiority in the successful ratio to find feasible solution and can guarantee minimum total cost of active and backup path.