Spare capacity allocation using shared backup path protection for dual link failures

摘要

This paper extends the spare capacity allocation (SCA) problem from single failures to dual link failures on mesh-like IP or WDM networks. The SCA problem pre-plans traffic flows with mutually disjoint one working and two backup paths using the shared backup path protection (SBPP) scheme. The spare provision matrix (SPM) method aggregates per-flow based information and computes the shared spare capacity for dual link failures. When compared to previous two-flow based methods, it has better scalability and flexibility. The SCA problem is formulated as a non-linear integer programming model and partitioned into two sequential linear sub-models: one finds all primary backup paths, and the other finds all secondary backup paths. We extend the terminologies in the 1+1 and 1:1 link protection for the backup path protection: using ":" to indicate backup paths with shared spare capacity; and using "+" to indicate backup paths with dedicated capacity. Numerical results from five networks show that the network redundancy of the 1+1+1 dedicated path protection is in the range of 313-400%. It drops to 96-180% in the 1:1:1 shared backup path protection without loss of dual-link resiliency, but with the trade-off of the highest complexity on spare capacity shared by all backup paths. The 1+1:1 hybrid path protection provides intermediate redundancy at 187-310% with the moderate complexity. It has dedicated primary backup paths and shared secondary backup paths. We also compare passive sharing with active sharing. They perform spare capacity sharing either after or during the backup path routing, i.e., the active sharing approach performs share spare capacity within the backup path routing, while the passive sharing does so only after all backup paths are found. The active sharing approaches always achieve lower redundancy values than the passive sharing. The reduction percentages are about 12% for 1+1:1 and 25% for 1:1:1 respectively. The extension of the Successive Survivable Routing (SSR) heuristic algorithm to the dual failure case is given and the numerical results show that SSR maintains a 4-11% gap from optimal on small or medium networks, and scales up well on large networks.