Scalable Backup Configurations Creation for IP Fast Reroute

Shohei KAMAMURA  Takashi MIYAMURA  Yoshihiko UEMATSU  Kohei SHIOMOTO  

IEICE TRANSACTIONS on Communications   Vol.E94-B    No.1    pp.109-117
Publication Date: 2011/01/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E94.B.109
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Internet
backup configuration,  IP Fast Reroute,  MRC,  robustness,  scalability,  

Full Text: PDF>>
Buy this Article

IP Fast Reroute techniques have been proposed to achieve fast failure recovery, just a few milliseconds. The basic idea of IP Fast Reroute is to reduce recovery time by precomputing backup routes. The multiple routing configurations (MRC) algorithm was proposed to implement IP Fast Reroute. MRC prepares backup configurations, which are used for finding a detour route after a failure. However, this algorithm establishes too many backup configurations to recover from failures. We propose a new backup configuration computation algorithm that creates the fewest possible configurations. The basic idea is to construct a spanning tree that excludes failure links in each backup configuration. We show that the effectiveness of our algorithm is especially high in large-scale power-law networks.