Spare Capacity Allocation Using Partially Disjoint Paths for Dual Link Failure Protection

A shared backup path protection (SBPP) scheme can be used to protect dual link failures by pre-planning each traffic flow with mutually disjoint working and two backup paths while minimizing the network overbuild. However, many existing backbone networks are bi-connected without three fully disjoint paths between all node pairs. Hence in practice partially disjoint paths (PDP) have been used for backup paths instead of fully disjoint ones. This paper studies the minimum spare capacity allocation (SCA) problem using PDP within an optimization framework. This is an extension of the spare provision matrix (SPM) method for PDP. The integer linear programming (ILP) model is formulated and an approximation algorithm, Successive Survivable Routing (SSR), is extended and used in the numerical study