Adaptive shared protection rearrangement

We propose two algorithms for dynamic routing of guaranteed bandwidth pipes with shared protection that provide low blocking through thrifty resource usage. We assume that a single working path can be protected by one or multiple protection paths, which are partially or fully disjoint from the working path. This allows better capacity re-use (i.e., better capacity sharing among protection paths). Furthermore, the resources of a working path affected by a failure can be re-used by the protection paths. The main feature of the proposed protection rearrangement framework is that since the protection paths do not carry any traffic until a failure they can be adaptively rerouted (rearranged) as the traffic and network conditions change. This steady reoptimisation of protection paths leads to lower usage of resources and therefore higher throughput and lower blocking. The other novelty we propose in this paper is a modelling trick referred to as LD: link doubling that allows distinguishing the sharable part of the link capacity from the free capacity in case when multiple protection paths are being rerouted simultaneously. LD allows finding optimal routing of shared protection paths for the case of any single link failure! The obtained results can be used for routing with protection in SDH/SONET, ngSDH/SONET, ATM, MPLS, WR-DWDM (including ASTN/GMPLS) and other networks.