IP Fast Reroute Using Tunnel-AT
draft-xu-ipfrr-tunnelat-00

Status of this Memo

This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The person(s) controlling the copyright in some of this material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as “work in progress.”

The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt.

The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html.

This Internet-Draft will expire on January 6, 2010.

Copyright Notice

Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document.

Abstract

This draft decribes Tunnel-AT mechanism that improves the Tunnel IP fast re-route mechanism. Tunnel-AT provides 100% node protection coverage in a symmetric biconnected network at a computational cost of less than one full SPT calculation.

Table of Contents

1.  Introduction
2.  Terminology
3.  Tunnel Repair Paths
    3.1.  Repair Paths
    3.2.  Tunnel Mechanism
4.  Tunnel-AT Algorithm
    4.1.  Complexity
5.  IANA Considerations
6.  Security Considerations
7.  References
§  Authors' Addresses

1.  Introduction

When a link or node failure occurs in an IP network, there is a period of disruption to the delivery of traffic until the network re-converges on a new topology. IP fast reroute (IPFRR) mechanisms are methods used in pure IP networks to provide protection from such disruptions. This is done by having failure-adjacent nodes compute backup routes in advance that allow them to repair failures immediately upon detection of failures. Traffic can be delivered to their correct destinations even before the network has re-converged on a new topology.

Thus far, there are three different IPFRR mechanisms that are documented in RFCs or RFC drafts: LFA in RFC 5286 (Atlas, A., Zinin, A., Torvi, R., Choudhury, G., Martin, C., Imhoff, B., and D. Fedyk, “Basic Specification for IP Fast-Reroute: Loop-free Alternates,” September 2008.) [1], Tunnel in [I-D.ietf-bryant-ipfrr-tunnels], and NotVia in [I-D.ietf-rtgwg-ipfrr-notvia-addresses]. However, LFA only provides 50~80% single-node failure protection coverage; routers running NotVia must maintain extra NotVia addresses, which causes high address management burden. In addition, NotVia also can cause packets to be forwarded through unnecessary loops. The original Tunnel can not provide 100% protection coverage for single node failures and the original draft does not describes an efficient method to calculate tunnel endpoints.

This draft presents Tunnel-AT to improve Tunnel. Tunnel-AT requires less than one full SPT computation, provides 100% single node protection, and does not require routers to maintain extra addresses. In addition, the length of the backup paths computed under Tunnel-AT are always exactly or very close to the length of the shortest working path to the destination.

2.  Terminology

This section defines the terms and symbols used in this draft.

Directed Forwarding:

The ability of the repairing router (S) to specify the next hop (Q) on exit from a tunnel end-point (P).

T:

The original shortest path tree of S.

T':

The new shortest path tree of S after removing a supposed failed neighbor (F) and associated edges from original topology.

Affected node:

A node in the subtree of T rooted at F.

Attaching Tree:

A maximal common subtree of T and T' formed by affected nodes.

Incoming node:

An incoming node of an affected node D is 1) D itself if D's parent under T' is not an affected node, 2) the same as the incoming node of its parent.

3.  Tunnel Repair Paths

3.1.  Repair Paths

When a failure occurs in an IP network, there is no way for the failure-adjacent routers to tell whether the failure was caused by a node failures or simply a link failure. To cope with the worst case, routers will first try to use the backup paths precalculated for a node failure. If no such routes are available, they will try to use the backup paths for a link failure.

The backup paths are used until the completion of the routing transition. Only routers adjacent to the failed component are aware of the nature of the failure. Once all the routers compute new shortest path based on the new topology, the backup paths will not be used anymore since packets are no longer forwarded through the failed components. At this time, the computation of new backup paths for the new topology are scheduled.

3.2.  Tunnel Mechanism

The idea behind Tunnel is very simple: router S chooses a router P that can forward packets to destination D bypassing the supposed failed router F. If P is the neighbor of S, then S can force the packet directly there. Otherwise, S should create a tunnel using P as the endpoint.

Let M denote the set of nodes in S's shortest path tree that are not in the branch rooted at F, and let Q denote the set of nodes in D's shortest path tree that are not in the branch rooted at F. The set of candidate tunnel end nodes for D are members of both M and Q (denoted as MQ). Tunnel fails if MQ is empty. For example, in Figure 1, the default link cost is 1, and link N-H and link H-I have a high cost (20). For destination H, and supposed failed neighbor F, the set M is {S, N}, while the set Q is {H}. Since MQ is empty, S can't find a tunnel end point to route packets to H.

                                   --------[I]
                              +---/         |
                 [S]---------[F]            | 20
                  +           +----------\  |
                  |                       \ |
                  +----[N]-----------------[H]
                                20

          Figure 1: A case shows when Tunnel and Tunnel-DF fail.
          The default link cost is 1. And the cost of link N-H
          and link H-I is 20, much higher than the others.

A mechanism called Directed Forwarding (DF) is introduced to remedy this problem (We use Tunnel-DF to denote Tunnel with directed forwarding). If MQ is empty, S searches a node T1 in M which has a neighbor T2 in Q. S uses T1 as the tunnel end point and makes an extra mark on the packet so that T1 would forward the packet to T2 directly. Using Figure 1 as an example, S chooses N as T1 and H as T2. S first routes a packet with destination H to N, and then N directly forwards it to H.

However, even with directed forwarding, Tunnel can't provide 100% node protection. Also using Figure 1 as an example, this time node I is the destination. M is {S, N} and Q is {I}. MQ is empty and no node in Q is a neighbor of a node in M.

Tunnel-AT can handle this problem. Under Tunnel-AT, S would forward packets with destination I to N and tell N to directly forward it to H. Since H also notices the failure of F and also performs Tunnel-AT, it would forward packets to I directly instead of using the original next hop F. So, packets have been protected more than once. We call the subsequent protections re-protections. Using re-protection, Tunnel-AT achieves 100% protection coverage - a significant improvement over Tunnel.

4.  Tunnel-AT Algorithm

Under the link weight routing protocol, repairing node S has already computed an original shortest path tree T based on the current topology. Next, for each neighbor N, S deletes N and associated links from the original topology and computes repair paths for every affected destination.

Tunnel-AT algorithm is based on the property that given a repairing node S and a supposed failed neighbor F, to deliver a packet to an affected node D, it is sufficient to reroute it to D's incoming node (This property is deduced from from the concept of Attaching Tree, thus comes the name Tunnel-AT). From the original tree T, the iSPF (Narvaez, Siu, and Tzeng, “New dynamic SPT algorithm based on a ball-and-string model,” 2001.) [2] algorithm can be used to compute the new shortest path tree T'. During the process of constructing T' from T, the incoming node of each affected node can be determined according to its definition given at Section 2 (Terminology).

To reroute a packet with destination D to the incoming node I, the parent of I, denoted as P, can be used as the tunnel endpoint. It is also needed to determine whether directed forwarding is necessary. The original distance from S to P and from S to D, i.e. dist(S, P) and dist(S, D), can be obtained from the original tree T; the new distance from P to D, dist'(P, D), can be obtained from tree T'. If the network is symmetric, dist(P, S) equals to dist(S, P). However, the condition

          dist'(P, D) < dist(P, S) + dist(S, D)

But this condition only guarantees P does not forward the packet back to S. Figure 2 shows a very simple counter-example. Here, D's incoming node is D itself and

          dist'(P, D) = 7 < 8 = dist(P, S) + dist(S, D) .

But P will send the packet to N if directed forwarding is not used because P->N->F->D is a shorter path and P is not aware of the failure. The packet will still reach D via the protection by N for the second time, but it takes a longer path that it has to.

                       +---[D]----+ 3
                       |          |
                       |      1   |
                     7 |   +-----[F]
                       |  [N]     |
                       |  /       |
                       | / 2      | 2
                       |/         |
                      [P]--------[S]
                           3

          Figure 2: An example: If S does not tell P to
          directly forwarding a packet with destination
          D to D, the packet will take the long path
          S->P->N->P->D.

To avoid P routing packets back to F, another more rigorous condition can be used:

          dist'(P, D) < dist(P, S) - dist(S, F) .

It can be proved that this condition ensures the shortest path from P to D does not traverse F.

4.1.  Complexity

Based on the original shortest path tree T calculated by the normal link state routing protocol, every node has to perform k times incremental shortest path tree (iSPT) (k is the number of neighbors) to construct backup routes for all destinations. The core of these algorithms are queue operations. The full SPT algorithm (Dijkstra's algorithm) invokes three types of queue operations: ADD, EXTRACT-MIN, and DECREASE-KEY. The iSPT algorithm invokes one extra type of operation -- REMOVE. If the queue is implemented as a binary heap, in a network of V nodes and E edges, the complexity of full SPT is O(ElgV). Let V_i denote the number of affected nodes if neighbor i fails, let E_i denote the number of edges attached to one of these nodes, the number of operations in the iSPT for this neighbor i can be expressed as follows:

• Maximum number of EXTRACT-MIN: the iteration number l in iSPT.
• Maximum number of ADD: V_i.
• Maximum number of REMOVE: V_i - l.
• Maximum number of DECREASE-KEY: E_i.

The main component is DECREASE-KEY. For a node, the Tunnel-AT algorithm complexity is

           O(E_1 lg V_1) + ... + O(E_k lg V_k)
                = O (E_1 lg V) + ... + O(E_k lg V)
                = O (ElgV)

the same as one full SPT.

5.  IANA Considerations

There are no IANA considerations that arise from this architectural description of IPFRR. However there will be changes to the IGPs to support IPFRR in which there will be IANA considerations.

6.  Security Considerations

Changes to the IGPs to support IPFRR do not introduce any additional security risks.

7. References

Authors' Addresses