Many different networking scenarios today require the calculation of a backup path in addition to calculating a normal path thorugh the network. Furthermore, both paths are required to satisfy some quality (i.e., bandwidth) constraints. The traditional methods for calculating the backup paths often do not account for sharing of bandwidth between different backup paths, and consequently utilize the network resources poorly.
In this work, we first present a centralized algorithm to exactly consider the bandwidth sharing on each link across various backup paths, and hence minimize the bandwidth resources used for protection. We take into account disjoint normal paths that can share their backup bandwidths and also consider the fact that normal bandwidth need no longer be reserved along all the links if a link on the path fails, thereby achieving the optimal protection bandwidth reuse.
Finally, we also present a distributed algorithm for the same problem, which results in a solution that is less optimal, but still far more efficient than the naive method.