07-03-2011, 10:03 AM
Presented by:
Amund Kvalbein
[attachment=9646]
Fast recovery in IP networks using Multiple Routing Configurations
Motivation
• Increasing use of the Internet for applications with stringent performance requirements
– Telephony, videoconferencing, online games
– ISPs must adhere to tough SLAs
• The recovery mechanisms in the Internet are not designed for these requirements
– Many (most) failures are short lived
– Failures are advertised too widely!
– This gives slow reaction and fosters instability
Our approach
• Failure reaction should be local
– To avoid instability and overhead
– Challenge: avoid loops
– Failure reaction should be proactive
– To reduce recovery times and packet loss
– Challenge: minimize overhead
Outline
• Multiple Routing Configurations
– The basic idea
– Generating backup configurations
– Forwarding
• Evaluation
• Load balancing improvement
• Implementation issues
• Wrap up
• Multiple Routing Configurations
• Guaranteed protection against single link, node or SRLG failures
• Same mechanism for both page link and node failures
– Generally difficult to distinguish at neighbor
• A configuration is the graph and the weight function
– Different weight setting in each configuration
• The general observation
• An unused page link can fail without consequences
• So can a single-connected node
• Several links and/or nodes can be protected in one logical topology
– All nodes are still reachable
• Build topologies so that all elements are protected
– Few such topologies are needed to protect all elements!
Isolated links and nodes
• An isolated page link has infinite weight
• A restricted page link has a high weight wr
– wr is chosen so that the page link is used only as a ”last resort”
• A node is isolated when all attached links are either isolated or restricted
Building backup configurations
• Forwarding
• How many configurations are needed?
• How long are the backup paths?
What about load distribution?
• Why bother to avoid overload?
- it’s only for short while…
Motivation for fast rerouting
– Do not loose packets
– Increase stability
• FRR should not make it worse for unaffected traffic
Routing performance during FRR
• Given TM estimate: What decides the load distribution?
– Link weights in C0
– Structure of backup configurations
– Link weights in backup configurations
• Three step approach
– Optimize page link weights in C0
– Build backup configurations
– Optimize page link weights in backup configurations
Building backup configurations
• Optimize C0 independently
• Identify the ”heaviest” nodes (most traffic)
• Build configs with good connectivity for heavy nodes
Optimizing page link weights
• Heavy optimization task
– Dependencies between configurations
• Local weight search heuristic
– Based on well known Fortz/Thorup method
• Optimize only for most severe page link failures
• Take advantage of configuration structure
– A page link failure only activates one or two backup configurations
Evaluation – Max page link load
• Real and synthetic network topologies
• Gravity model traffic demands
Evaluation – Number of configurations
• Implementation issues
• Representing backup configurations
– IETF: Multi-Topology routing
• Can calculate independent shortest path trees in each topology
• Need ability to switch configuration in-flight
• Marking packets
– Same problem as in MT-routing
– Reuse of ToS/DSCP bits has been proposed
Summary
• MRC guarantees protection against any single page link or node failure
• Modest state overhead
• Small path length stretch for recovered traffic
• Flexibility in how recovered traffic is routed
• Realistic to implement
Related work
• Failure Insensitive Routing (FIR)
– Relies on interface-specific routing tables to infer page link failures
• Not-via addresses
– Calculates one ”configuration” for each protected element
MRC extensions
• Multi-failure protection
– SRLG, uncorrelated failures
– Can guarantee protection against two independent failures (at a cost)
• Improved configuration construction
– Eliminate isolated links
– Use deflection in forwarding procedure
• Use in TE context
– Spread demands on several topologies
• Lab implementation
– Using Quagga routing software
Amund Kvalbein
[attachment=9646]
Fast recovery in IP networks using Multiple Routing Configurations
Motivation
• Increasing use of the Internet for applications with stringent performance requirements
– Telephony, videoconferencing, online games
– ISPs must adhere to tough SLAs
• The recovery mechanisms in the Internet are not designed for these requirements
– Many (most) failures are short lived
– Failures are advertised too widely!
– This gives slow reaction and fosters instability
Our approach
• Failure reaction should be local
– To avoid instability and overhead
– Challenge: avoid loops
– Failure reaction should be proactive
– To reduce recovery times and packet loss
– Challenge: minimize overhead
Outline
• Multiple Routing Configurations
– The basic idea
– Generating backup configurations
– Forwarding
• Evaluation
• Load balancing improvement
• Implementation issues
• Wrap up
• Multiple Routing Configurations
• Guaranteed protection against single link, node or SRLG failures
• Same mechanism for both page link and node failures
– Generally difficult to distinguish at neighbor
• A configuration is the graph and the weight function
– Different weight setting in each configuration
• The general observation
• An unused page link can fail without consequences
• So can a single-connected node
• Several links and/or nodes can be protected in one logical topology
– All nodes are still reachable
• Build topologies so that all elements are protected
– Few such topologies are needed to protect all elements!
Isolated links and nodes
• An isolated page link has infinite weight
• A restricted page link has a high weight wr
– wr is chosen so that the page link is used only as a ”last resort”
• A node is isolated when all attached links are either isolated or restricted
Building backup configurations
• Forwarding
• How many configurations are needed?
• How long are the backup paths?
What about load distribution?
• Why bother to avoid overload?
- it’s only for short while…
Motivation for fast rerouting
– Do not loose packets
– Increase stability
• FRR should not make it worse for unaffected traffic
Routing performance during FRR
• Given TM estimate: What decides the load distribution?
– Link weights in C0
– Structure of backup configurations
– Link weights in backup configurations
• Three step approach
– Optimize page link weights in C0
– Build backup configurations
– Optimize page link weights in backup configurations
Building backup configurations
• Optimize C0 independently
• Identify the ”heaviest” nodes (most traffic)
• Build configs with good connectivity for heavy nodes
Optimizing page link weights
• Heavy optimization task
– Dependencies between configurations
• Local weight search heuristic
– Based on well known Fortz/Thorup method
• Optimize only for most severe page link failures
• Take advantage of configuration structure
– A page link failure only activates one or two backup configurations
Evaluation – Max page link load
• Real and synthetic network topologies
• Gravity model traffic demands
Evaluation – Number of configurations
• Implementation issues
• Representing backup configurations
– IETF: Multi-Topology routing
• Can calculate independent shortest path trees in each topology
• Need ability to switch configuration in-flight
• Marking packets
– Same problem as in MT-routing
– Reuse of ToS/DSCP bits has been proposed
Summary
• MRC guarantees protection against any single page link or node failure
• Modest state overhead
• Small path length stretch for recovered traffic
• Flexibility in how recovered traffic is routed
• Realistic to implement
Related work
• Failure Insensitive Routing (FIR)
– Relies on interface-specific routing tables to infer page link failures
• Not-via addresses
– Calculates one ”configuration” for each protected element
MRC extensions
• Multi-failure protection
– SRLG, uncorrelated failures
– Can guarantee protection against two independent failures (at a cost)
• Improved configuration construction
– Eliminate isolated links
– Use deflection in forwarding procedure
• Use in TE context
– Spread demands on several topologies
• Lab implementation
– Using Quagga routing software