Minimum Backup Configuration-Creation Method for IP Fast Reroute

IP fast reroute techniques have been proposed for achieving fast failure recovery in just a few milliseconds. The basic idea of IP fast reroute is to reduce recovery time after failure by precomputing backup routes. A multiple routing configurations (MRC) algorithm has been proposed for obtaining IP fast reroute. MRC prepares backup configurations, which are used for finding a detour route after failure. On the other hand, requiring too many backup configurations consumes more network resources. It is necessary to recover more traffic flows with fewer backup configurations to ensure scalability. We propose a new backup configuration-creation algorithm for maximizing traffic flows which are fast recovered as much as possible under a limited number of backup configurations. The basic idea is to construct a spanning tree excluding failure links with higher link-loads in each backup configuration. We show that our algorithm has more robust on actual large IP networks.