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

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.

Status of this Memo

This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79.

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 September 8, 2010.

Copyright Notice

Copyright (c) 2010 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 (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the BSD License.

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.

Table of Contents

1.  Introduction
2.  Terminology
3.  Tunnel-AT Overview
4.  Tunnel-AT Routing Algorithm
    4.1.  Rerouting to the Incoming Node
    4.2.  Complexity
5.  Forwarding Plane Mechanism
6.  IANA Considerations
7.  Security Considerations
8.  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 IETF 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], Tunnels (Bryant, S., Filsfils, C., Previdi, S., and M. Shand, “IP Fast Reroute using tunnels,” 2008.) [3] in [I-D.ietf-bryant-ipfrr-tunnels], and NotVia (Bryant, S., Filsfils, C., Previdi, S., and M. Shand, “IP Fast Reroute using tunnels,” 2008.) [3] 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 tracebacks. 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.

Incremental SPT:

Algorithms to build new shortest path tree based on the original shortest path tree upon topological change.

3.  Tunnel-AT Overview

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.

The forwarding plane mechanism of Tunnel-AT is similar to Tunnels (Bryant, S., Filsfils, C., Previdi, S., and M. Shand, “IP Fast Reroute using tunnels,” 2008.) [3]. It uses tunnel and directed forwarding to implement repair paths, too. But in the routing plane, Tunnel-AT is totally different from Tunnels. The routing algorithm is based on the incremental SPF ((iSPF) (Narvaez, Siu, and Tzeng, “New dynamic SPT algorithm based on a ball-and-string model,” 2001.) [2]) algorithm in and the concept of Attaching Tree (thus comes the name Tunnel-AT).

A simple example is given in Figure 1 to demonstrate Tunnel-AT. In Figure 1, the default link cost is 1, and link P-H and link H-I have a high cost (20). For destination H, and supposed failed neighbor F, S can reroute packets to H by first using the S-P tunnel to reroute packets to P. S also makes extra marks on the packets so that P would directed forwarding these packets to H.

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

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

To reroute packets to node I, S would forward packets with destination I to P and tell P 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.

4.  Tunnel-AT Routing 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. The remaining part of this section describes how S computes repair paths for a specific supposed failed neighbor F.

Tunnel-AT is based on the incremental SPF algorithm. Intuitively, the process of the iSPF algorithm can be viewed as attaching subtrees of the original shortest path tree back one by one and finally forming a new shortest path tree. We name the subtrees Attaching Trees. An attaching tree may be attached to a node of another attaching tree. In this way, they form a super attaching tree. The root of the super attaching tree attached to a node that is not affected by the changing of tolopogy. We call the root the traffic incoming node, or simply the incoming node. Given a node S and a supposed failed neighbor F, to deliver a packet to an affected destination D, it is sufficient to reroute it to D's incoming node. From the original shortest path tree, the iSPF algorithm can be used to compute the new shortest path tree after removing F from the topology, and the incoming node of each affected node can be determined during the process.

4.1.  Rerouting to the Incoming Node

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 to ensure P forwarding the packet to I. 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). At a first glance, the following condition seems works:

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

However 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(F, D) <= dist(S, P) - dist(S, F) .

It can be proved that this condition ensures that P forwords packets with destination D to nieghbor I, so no mark for directed forwording is needed. To see how this equation works, let's assume the above condition holds but P routing packet back to F, so

          dist(P, D) >= dist(P, N) + dist(N, F) + dist(F, D)

since the shortest path from S to P does not traverse F, we have

          dist(S, P) < dist(S, F) + dist(F, N) + dist(N, P)

Combining the two inequalities yields:

          dist(P, D) - dist(F, D) > dist(S, P) - dist(S, F)

Since dist'(P, D) >= dist(P, D), we have

          dist'(P, D) - dist(F, D) > dist(S, P) - dist(S, F)

A contridiction.

4.2.  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.  Forwarding Plane Mechanism

Tunnel-AT routes are pre-computed in anticipation of later failures by the routing algorithm described above. When a router detects an adjacent failure, it uses these routes to reroute packets until the completion of the routing transition.

A Tunnel-AT route contains two extra fields, Tunnel IP address(Tunnel adrresss) and directed forwarding IP address (DF address). The Tunnel address is the IP address of the tunnel end point router. The DF address is the next hop IP address when the tunnel end point router needs to perform directed forwarding. If tunnel or directed forwarding is not needed, the corresponding field is not set.

Here we describe a way to implement tunnel and directed forwarding. It is not required that an implementation follow exactly the method given in the following section.

When a router receives a packet, it will perform general IP forwarding. If a tunnel-at route is chosen for a packet:

1. If DF address is set, a new IP header (DF header) is prepend to the packet. The DST field of the prepended IP header is set to the DF address.
2. If Tunnel address is set, another new IP header (tunnel header) is prepended, while its DST field is set to tunnel IP address.
3. The TOS fields of these prepended headers are set to 2 and the PROTOCOL fields are also set to a special value IP_TUNAT. We also increase the value of TOS field of the original packet by 1.
4. In the case of IP fragmentation, the above operations are performed on all fragments.

TOS field is used to avoid routing loops, which may occur in the scenarios of multi-link failures. When a route receives a packet with TOS field being value 2 and find it need another protection, it simply drop the packet. So if a packet is being protected, it will not be protected again. If a packet has been protected twice, the TOS field of the original packet will be 2, it will not be protected for another time.

If the packet is delivered locally to the router:

1. If the packet has a tunnel header, i.e. the field of PROTOCOL equals IP_TUNAT, and the router is the destination of the tunnel, it drops the tunnel header and check the next header.
2. If the nested header is a df header, it forwards the packet by the corresponding interface.

6.  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.

7.  Security Considerations

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

8. References

Authors' Addresses