A scalable and decentralized fast-rerouting scheme with efficient bandwidth sharing

This paper focuses on the protection of virtual circuits (Label Switched Paths, LSPs) in a (G)MPLS (Generalised Multi-Protocol Label Switching) network. The proposed algorithm is designed to protect traffic with strong delay requirements such as EF (Expedited Forwarding) ordered aggregates in a DiffServ domain. Indeed, for this type of application, we need fast restoration in case of failure. The duplication of all the packets in a 1 + 1 end-to-end restoration scheme consumes a large amount of bandwidth. Furthermore, end-to-end recovery with bandwidth sharing schemes are usually considered to be far too slow. Local fast-rerouting is a solution which can compete with restoration times and bandwidth consumption offered by SONET self-healing rings. Our scheme includes a sophisticated resource aggregation mechanism based on the concepts of "backup-backup aggregation" and "backup-primary aggregation". The path selection algorithm is also designed to efficiently reduce the resource usage. Moreover, when considering LSPs at different preemption levels, our algorithm is able to correctly calculate the amount of bandwidth that can be preempted despite the sharing of resource. We show that our approach, though local, can compete with the state-of-the-art end-to-end recovery schemes in terms of resource consumption. The major contribution of our scheme, the "backup-primary aggregation", was then also used in the context of end-to-end recovery and improved its performance substantially. To be able to save a maximum amount of bandwidth in a decentralised implementation, the nodes that compute backup LSPs need to obtain a certain amount of link-state information. We propose a solution where the nodes learn almost all the information they need with RSVP messages. This drastically reduces the information that needs to be flooded in the whole network and is the first scalable decentralised solution capable of sharing a large amount of bandwidth. (c) 2005 Elsevier B.V. All rights reserved.