Fast Reroute Mechanisms

Network reliability is an important measure for deployability of sensitive applications. When a link, node or SRLG failure occurs in a routed network, there is inevitably a period of disruption to the delivery of traffic until the network reconverges on the new topology.

Fast reaction is essential for the failed element. There are two approaches for the fast reaction:

Fast convergence and Fast reroute. When a local failure occur four steps are necessary for the convergence.

1. Failure detection

2. Failure propagation

3. New information process

4. Update new route into RIB/FIB

For fast convergence, these steps may need to be tuned. Although the RIB/FIB update is hardware dependent, all other steps can be configured by the network operator. One thing always needs to be kept in mind; Fast convergence and fast reroute can affect network stability.

Unlike fast convergence, for the fast reroute, routes are precomputed and preprogrammed into the router RIB/FIB.  Additional, an alternate is found, if possible, and pre-installed into the RIB/FIB.  As soon as the local failure is detected, the PLR (Point of Local Repair) switches the routes to use the alternate path.   This preserves the traffic while the normal convergence process of failure propagation and SPF recomputation occurs.

In this post I will show the fast reroute mechanisms since there are already great resources for the fast convergence out there.

There are many drafts and RFCs in the IETF for the fast reroute mechanisms. In this post you will see the following mechanism for fast reroute, pros and cons of each one of them and applications of these mechanisms.

  • Loop Free Alternates  (RFC5286, deployable today)
  • Remote Loop Free Alternates  (draft in RTGWG, implemented by some vendors)
  • MRT-FRR (draft in RTGWG, proto-types in progress)
  • MPLS RSVP-TE FRR  (RFC 4090, deployable today)
  • U-turns Alternates  (historical interest)
  • Not-via Address  (RFC6981,  academic interest)

We will use the figure-1 to demonstrate the mechanisms.

FRR

FIGURE-1

 Assume all the link cost is the same and link-state protocol is used, in figure-1 if R1-R2 link fails, to reach the destination networks which are behind R2; R1 needs to find a way to send a packet. When R1-R2 link fails, for the IP and MPLS networks, if R1 sends a packet to R3, since all the link cost is the same, R3’s next-hop for the R2 is R1. This is called micro-loop. Until R3 learns of the failure and computes its new primary next-hop R5, packets are looped in between R1 and R3. This is can cause a congestion on the link.

Loop free alternate mechanism looks for the alternate path for the R1 to send a packet to R2 when R1-R2 link fails. In order mechanism to work, R1 runs additional SPFs from its neighbor point of view. It is obvious that R1 cannot use R3 as its alternate next-hop. All other 5 mechanism can solve this issue with the different ways.  This is the drawback of LFA – there may not be either node or link protection because it is very topology dependent.   Some small topologies (RFC6571) can work very well.

If somehow R3 knew that packet is coming from its primary next-hop and it should send the packet to its alternate next-hop then packet could reach to R2 through R1-R3-R5-R6-R4-R2. This is called U-turn alternate since packet is sent back to R3 from R1 without causing a micro-loop.

Mechanism to work, R3 either explicitly marked or implicitly learns that packet is coming from its primary next hop. Also R3 needs to have loop-free node-protecting alternate path.

Loop-free alternate traffic is sent to a neighbor who will not send it back. U-turn alternate traffic is sent to a neighbor who will send it to a neighbor’s alternate instead of back.

MRT-FRR works by computing two maximally redundant trees to each destination; the two trees MRT-Red and MRT-Blue take as diverse paths to the destination as is possible.  If the primary next-hop might be the same as on MRT-Red, then MRT-Blue is selected and vice-versa.

To indicate that the packet is traveling on the MRT-Red or MRT-Blue tree, two additional MPLS labels are allocated and signaled via LDP for the destination router’s loopback .  LDP and IP packets are labeled appropriately to indicate both the destination router and the MRT-Red or MRT-Blue path.

MRT-FRR is guaranteed to always find a link and node protecting alternate – unless the network topology is partitioned by the failure.

The other three mechanisms rely on tunnels. Before going further explanation, it is important to understand some general concepts.

First, there is Remote LFA.  The basic concept is to find a node that the PLR can reach without going through the failure point and where that node can also reach the destination (or a proxy for the destination) without going through the failure point.   Then the PLR can tunnel traffic to this node and it will reach the destination without going across the failure point.

To find this node, there are two steps.  First, the PLR determines all nodes that it can reach without going through the primary next-hop.  This set of nodes is called the extended P-space.  Either the PLR’s shortest path to these nodes avoids the primary next-hop or the PLR has a neighbor whose shortest path to these nodes avoids the primary next-hop.

  • For example, the set of routers which can be reached from R1 without traversing R1-R2  is called the extended P-space of R1 with respect to the link R1-R2.  Second, the set of routers from which the node R2 can be reached, by normal  forwarding, without traversing the link R1-R2 is termed the Q-space of  R2 with respect to the link R1-R2.

Any nodes that are both in extended P space and Q space are candidate PQ nodes that can be the end of the repair tunnel.  In the above example, R6 is a PQ node.  R3 and R5 are not in Q space because when either decapsulate a packet destined to R2, the packet would be sent back to R1 and thus cause a loop.  R4 is not in extended P space because neither R1 nor R3 can reach R4 without potentially going via R1-R2.

While any tunnel technology, such as IP in IP, GRE or L2TPv3 could be used, current implementations depend upon using MPLS tunnels signaled via LDP (and targeted LDP sessions to protect LDP traffic).

 

When R6 is chosen as the tunnel end point, once packet decapsulate, packet is sent towards the R2 without looping back. Different implementations may implement different policy to select among PQ nodes.

Remote LFA works based on this principle. Currently only MPLS tunnels are supported.  R6 is chosen in this topology for MPLS tunnel endpoint.

For an IP packet, R1 stores an alternate next-hop to R3 with the MPLS label that R3 provided to reach R6.

If the packet has an LDP-distributed label, R1 must learn the MPLS label that R6 uses for the FEC for R2; this can be done via a targeted LDP session.

Then, the label on the packet is swapped to one that R6 understands to mean R2 and finally the label that R3 understands to mean R6 is used pushed on the packet.  R6 as a penultimate router does PHP and R4 receives a labeled packet for R2.

This describes basically how Remote LFA can be used to provide link protection.   Like LFA, Remote LFA is not guaranteed to find link-protecting alternates in a topology but it does significantly improve the coverage compared to LFA.  Additional computation can be done so that Remote LFA finds node-protecting alternates when available.

The second tunneling mechanism :MPLS RSVP-TE-Fast Reroute can provide guaranteed protection for the links, nodes and SRLG failures.   When used for local repair, an LSP can be created to protect against a particular link or node failing; each LSP requires a CSPF at the PLR.

  • For example, R1 could have an LSP to protect against link R1-R2 failing; that LSP would be routed R1-R3-R5-R6-R4-R2.  This LSP can be used as an alternate.   Just as with any tunneling mechanism, targeted LDP sessions are needed to learn the labels protect the LDP traffic.

 

Since failure is local, as soon as it detects, alternate path can be started to use.   Assume there is a LSP between R1 to R4, if constraints are met since MPLS TE LSP use by default shortest IGP path, R1-R2-R4 LSP is established. If R1-R2 link will be protected, then backup tunnel is configured through the nodes R1-R3-R5-R6-R4-R2.

To reach the same destination behind R4, traffic flow is R1-R3-R5-R6-R4-R2-R4. There is obvious hair pinning. This is well known and common problem in the MPLS TE-FRR networks.  It appears unnecessarily with fast-reroute when the repair end-point is pinned to the next-hop (for link protection) or next-next-hop (for node protection).

 

Lastly, the third tunneling mechanism is Not-Via (In the site there is an article of Russ.), which can also guarantee protection for link, node, and SRLG failures.  To accomplish this, each router is given additional IP addresses with extra semantics.

  • For instance, R2 would have an address that means “R2 but not via R1-R2”.  To find the next-hop for “R2 but not via R1-R2”, each router would remove R1-R2 from the network graph and then compute an SPF.   The computation can be optimized with ISPF, but many ISPFs can be needed (per failure-point).

The alternate from R1 to R2 would thus involve tunneling the packet by adding a header that had a destination address of “R2 but not via R1-R2”.

The path from R1 to “R2 but not via R1-R2” is R1-R3-R5-R6-R4-R2.  Because of the special semantics of the Not-Via address, R3 knows that it shouldn’t use R1-R2 link to reach R2 and it sends the packets to R5.

 

 

Orhan Ergun
Orhan Ergun, CCIE, CCDE, is a network architect mostly focused on service providers, data centers, virtualization and security. He has more than 10 years in IT, and has worked on many network design and deployment projects. Orhan works as a freelance network instructor, for training you can add ' Orhan Ergun ' on skype. In addition, Orhan is a: Blogger at Network Computing. Blogger and podcaster at Packet Pushers. Manager of Google CCDE Group. On Twitter @OrhanErgunCCDE
  • riw777

    Didn’t see this ’til I’d already posted the MRT explanation just a few minutes ago… Good summary, Orhan!

  • http://networkerzone.blogspot.com/ ORHAN ERGUN

    Glad you liked it. As I pointed out in this post , with your last MRT explanation in additon to the existing FRR post , almost everything has been covered for fast reroute. I am lucky to learn FRR by talking with you and also from your books :) . I can’t also wait for your last effort which is The Art of Network Architecture.

7ads6x98y