Internet DRAFT - draft-xu-ipfrr-tunnelat

draft-xu-ipfrr-tunnelat






Network Working Group                                              M. Xu
Internet-Draft                                                    L. Pan
Expires: September 8, 2010                           Tsinghua University
                                                                 S. Yang
                                         Beijing University of Posts and
                                                      Telecommunications
                                                                   Q. Li
                                                     Tsinghua University
                                                           March 7, 2010


                    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.



M. Xu, et al.           Expires September 8, 2010               [Page 1]

Internet-Draft       IP Fast Reroute Using Tunnel-AT          March 2010


   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.






























M. Xu, et al.           Expires September 8, 2010               [Page 2]

Internet-Draft       IP Fast Reroute Using Tunnel-AT          March 2010


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  4
   3.  Tunnel-AT Overview . . . . . . . . . . . . . . . . . . . . . .  5
   4.  Tunnel-AT Routing Algorithm  . . . . . . . . . . . . . . . . .  7
     4.1.  Rerouting to the Incoming Node . . . . . . . . . . . . . .  7
     4.2.  Complexity . . . . . . . . . . . . . . . . . . . . . . . .  9
   5.  Forwarding Plane Mechanism . . . . . . . . . . . . . . . . . . 10
   6.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 12
   7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 13
   8.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 14
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 15






































M. Xu, et al.           Expires September 8, 2010               [Page 3]

Internet-Draft       IP Fast Reroute Using Tunnel-AT          March 2010


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 [1], Tunnels [3]
   in [I-D.ietf-bryant-ipfrr-tunnels], and NotVia [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.





















M. Xu, et al.           Expires September 8, 2010               [Page 4]

Internet-Draft       IP Fast Reroute Using Tunnel-AT          March 2010


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.



































M. Xu, et al.           Expires September 8, 2010               [Page 5]

Internet-Draft       IP Fast Reroute Using Tunnel-AT          March 2010


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
   [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) [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



M. Xu, et al.           Expires September 8, 2010               [Page 6]

Internet-Draft       IP Fast Reroute Using Tunnel-AT          March 2010


   subsequent protections re-protections.  Using re-protection,
   Tunnel-AT achieves 100% protection coverage.

















































M. Xu, et al.           Expires September 8, 2010               [Page 7]

Internet-Draft       IP Fast Reroute Using Tunnel-AT          March 2010


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



M. Xu, et al.           Expires September 8, 2010               [Page 8]

Internet-Draft       IP Fast Reroute Using Tunnel-AT          March 2010


   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.





M. Xu, et al.           Expires September 8, 2010               [Page 9]

Internet-Draft       IP Fast Reroute Using Tunnel-AT          March 2010


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:

   o  Maximum number of EXTRACT-MIN: the iteration number l in iSPT.

   o  Maximum number of ADD: V_i.

   o  Maximum number of REMOVE: V_i - l.

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



















M. Xu, et al.           Expires September 8, 2010              [Page 10]

Internet-Draft       IP Fast Reroute Using Tunnel-AT          March 2010


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.



M. Xu, et al.           Expires September 8, 2010              [Page 11]

Internet-Draft       IP Fast Reroute Using Tunnel-AT          March 2010


   2.  If the nested header is a df header, it forwards the packet by
       the corresponding interface.

















































M. Xu, et al.           Expires September 8, 2010              [Page 12]

Internet-Draft       IP Fast Reroute Using Tunnel-AT          March 2010


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.














































M. Xu, et al.           Expires September 8, 2010              [Page 13]

Internet-Draft       IP Fast Reroute Using Tunnel-AT          March 2010


7.   Security Considerations

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















































M. Xu, et al.           Expires September 8, 2010              [Page 14]

Internet-Draft       IP Fast Reroute Using Tunnel-AT          March 2010


8.  References

   [1]  Atlas, A., Zinin, A., Torvi, R., Choudhury, G., Martin, C.,
        Imhoff, B., and D. Fedyk, "Basic Specification for IP Fast-
        Reroute: Loop-free Alternates", RFC 5286, September 2008.

   [2]  Narvaez, Siu, and Tzeng, "New dynamic SPT algorithm based on a
        ball-and-string model", IEEE/ACM Trans. Netw., 2001.

   [3]  Bryant, S., Filsfils, C., Previdi, S., and M. Shand, "IP Fast
        Reroute using tunnels", Internet
        draft draft-bryant-ipfrr-tunnels-03, 2008.

   [4]  Shand, M., Bryant, S., and S. Previdi, "IP Fast Reroute Using
        Not-via Addresses", Internet
        draft draft-ietf-rtgwg-ipfrr-notvia-addresses-04, 2009.



































M. Xu, et al.           Expires September 8, 2010              [Page 15]

Internet-Draft       IP Fast Reroute Using Tunnel-AT          March 2010


Authors' Addresses

   Mingwei Xu
   Tsinghua University
   Department of Computer Science
   Beijing  100084
   China

   Email: xmw@csnet1.cs.tsinghua.edu.cn


   Lingtao Pan
   Tsinghua University
   Department of Computer Science
   Beijing  100084
   China

   Email: freeplant@gmail.com


   Sijie Yang
   Beijing University of Posts and Telecommunications
   Department of Computer Science
   Beijing  100876
   China

   Email: iyangsj@gmail.com


   Qing Li
   Tsinghua University
   Department of Computer Science
   Beijing  100084
   China

   Email: liqing@csnet1.cs.tsinghua.edu.cn















M. Xu, et al.           Expires September 8, 2010              [Page 16]