21-07-2012, 03:45 PM
Multiple Routing Configurations for Fast IP Network Recovery
[attachment=28376]
Evaluation Setup
The synthetic topologies are obtained from the BRITE topology generation tool [17] using the Waxman [18] and the Generalized Linear Preference (GLP) [19] models. The number of nodes is varied between 16 and 512 to demonstrate the scalability. To explore the effect of network density, the average node degree is 4 or 6 for Waxman topologies and 3.6 for GLP topologies. For all synthetic topologies, the links are given unit weight. The real topologies are taken from the Rocketfuel topology database [20]. For each topology, we measure the minimum number of backup configurations needed by our algorithm to isolate every node and link in the network. Recall from Section III-B that our algorithm for creating backup configurations only takes the network topology as input, and is not influenced by the link weights. Hence, the number of configurations needed is valid irrespective of the link weight settings used. For the Rocketfuel opologies, we also measure the number of configurations needed if we exclude the nodes that can be covered by Loop-Free Alternates (LFA) [21]. LFA is a cheaper fast reroute technique that exploits the fact that for many destinations, there exists an alternate next-hop that will not lead to a forwarding loop.
Conclusion
We have presented Multiple Routing Configurations as an approach
to achieve fast recovery in IP networks. MRC is based on
providing the routers with additional routing configurations, allowing
them to forward packets along routes that avoid a failed
component. MRC guarantees recovery from any single node or
link failure in an arbitrary bi-connected network. By calculating
backup configurations in advance, and operating based on locally
available information only, MRC can act promptly after
failure discovery
[attachment=28376]
Evaluation Setup
The synthetic topologies are obtained from the BRITE topology generation tool [17] using the Waxman [18] and the Generalized Linear Preference (GLP) [19] models. The number of nodes is varied between 16 and 512 to demonstrate the scalability. To explore the effect of network density, the average node degree is 4 or 6 for Waxman topologies and 3.6 for GLP topologies. For all synthetic topologies, the links are given unit weight. The real topologies are taken from the Rocketfuel topology database [20]. For each topology, we measure the minimum number of backup configurations needed by our algorithm to isolate every node and link in the network. Recall from Section III-B that our algorithm for creating backup configurations only takes the network topology as input, and is not influenced by the link weights. Hence, the number of configurations needed is valid irrespective of the link weight settings used. For the Rocketfuel opologies, we also measure the number of configurations needed if we exclude the nodes that can be covered by Loop-Free Alternates (LFA) [21]. LFA is a cheaper fast reroute technique that exploits the fact that for many destinations, there exists an alternate next-hop that will not lead to a forwarding loop.
Conclusion
We have presented Multiple Routing Configurations as an approach
to achieve fast recovery in IP networks. MRC is based on
providing the routers with additional routing configurations, allowing
them to forward packets along routes that avoid a failed
component. MRC guarantees recovery from any single node or
link failure in an arbitrary bi-connected network. By calculating
backup configurations in advance, and operating based on locally
available information only, MRC can act promptly after
failure discovery