INTERNET DRAFT  IP Fast Reroute Using Notvia Addresses        Mar 2005

Network Working Group                                         S. Bryant
Internet Draft                                                 M. Shand
Expiration Date: Sep 2005                                 Cisco Systems

                                                               Mar 2005

                IP Fast Reroute Using Notvia Addresses

Status of this Memo

   By submitting this Internet-Draft, we certify that any applicable
   patent or other IPR claims of which we are aware have been
   disclosed, or will be disclosed, and any of which we become aware
   will be disclosed, in accordance with RFC 3668.

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

   The list of current Internet-Drafts can be accessed at

   The list of Internet-Draft Shadow Directories can be accessed at

   This draft describes a mechanism that provides fast reroute in an
   IP network through encapsulation to "notvia" addresses. A single
   level of encapsulation is used. The mechanism protects unicast,
   multicast and LDP traffic against link, router and shared risk
   group failure, regardless of network topology and metrics.

Conventions used in this document

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   this document are to be interpreted as described in RFC 2119

Bryant, Shand              Expires Sep 2005                   [Page 1]

INTERNET DRAFT  IP Fast Reroute Using Notvia Addresses        Mar 2005

Table of Contents
1. Introduction........................................................3

2. Overview of Notvia Repairs..........................................3

3. Repair Computation..................................................4

4. How a repairing node repairs........................................5
 4.1 Node Failure.....................................................5
 4.2 Link Failure.....................................................5
 4.3 Multi-homed Prefix...............................................6
 4.4 Shared Risk Groups...............................................7
 4.5 Multicast........................................................7
 4.6 Fast Reroute in an MPLS LDP Network..............................7
5. Local Area Networks.................................................8

6. Loop Free Alternatives.............................................10

7. Equal Cost Multi-Path..............................................10

8. Encapsulation......................................................10

9. Routing Extensions.................................................11

10. Incremental Deployment............................................11

11. IANA considerations...............................................11

12. Security Considerations...........................................11

Bryant, Shand              Expires Sep 2005                   [Page 2]

INTERNET DRAFT  IP Fast Reroute Using Notvia Addresses        Mar 2005

1.    Introduction

   When a link or a router fails, only the neighbors of the failure
   are initially aware that the failure has occurred. In a network
   operating IP fast reroute (IPFRR), the routers that are the
   neighbors of the failure repair the failure. These repairing
   routers have to steer packets to their destinations despite the
   fact that most other routers in the network are unaware of the
   nature and location of the failure.

   A common limitation in most IPFRR mechanisms is an inability to
   steer the repaired packet round an identified failure. The extent
   to which this limitation affects the repair coverage is topology
   dependent. The mechanism proposed here is to encapsulate the packet
   to an address that explicitly identifies the network component that
   the repair must avoid. This produces a repair mechanism, which,
   provided the network in not partitioned by the failure, will always
   achieve a repair.

2.    Overview of Notvia Repairs

   The purpose of a repair is to deliver packets to their destination
   without traversing a known failure in the network, i.e. to deliver
   the packet not via the failure. In its simplest form, this repair
   mechanism works by assigning an additional address to each
   interface in the network. This additional address is called the
   notvia address. The semantics of a notvia address are that a packet
   addressed to a notvia address must be delivered to the router with
   that address, not via the neighboring router on the interface to
   which that address is assigned.

   To repair a failure, the repairing router encapsulates the packet
   to the notvia address of the router interface on the far side of
   the failure. The routers on the repair path then know to which
   router they must deliver the packet, and which network component
   they must avoid. The network fragment shown in Figure 1 illustrates

              |Ap                Bp is the address to use to get
              |                  a packet to B notvia P
    Sp      Pa|Pb
            Ps|Pc      Bp

      Figure 1: Notvia Addresses

Bryant, Shand              Expires Sep 2005                   [Page 3]

INTERNET DRAFT  IP Fast Reroute Using Notvia Addresses        Mar 2005

   Assume that S has a packet for some destination D that it would
   normally send via P and B, and that S suspects that P has failed. S
   encapsulates the packet to Bp. The path from S to Bp is the
   shortest path from S to B not going via P. If the network contains
   a path from S to B that does not transit router P, then the packet
   will be successfully delivered to B. When the packet addressed to
   Bp arrives at B, B removes the encapsulation and forwards the
   repaired packet towards its final destination.

   Note that a packet may back track after the encapsulation is
   removed. However, because the decapsulating router is always closer
   to the packet destination than the encapsulating router, the packet
   will not loop.

3.    Repair Computation

   The notvia repair mechanism requires that all routers on the path
   from S to B (Figure 1) have a route to Bp. They can calculate this
   by failing node P, running an SPF, and finding the shortest route
   to B.

   A router has no simple way of knowing whether it is on the shortest
   path for any particular repair. It is therefore necessary for every
   router to calculate the path it would use in the event of any
   possible router failure. Each router therefore fails every router
   in the network, one at a time, and calculates it own best route to
   each of the neighbors of that router. In other words, again with
   reference to Figure 1, some router X will consider each router in
   turn to be P, fail P, and then calculate its own route to each of
   the notvia P addresses advertised by the neighbors of P. i.e. X
   calculates its route to Sp, Ap, Bp, and Cp, in each case, not via

   To calculate the repair paths a router has to calculate n-1 SPFs
   where n is the number of routers in the network. This is expensive
   to compute. However the problem is amenable to a solution in which
   each router (X) proceeds as follows. X first calculates the base
   topology with all routers functional and determines its normal path
   to all notvia addresses. X then fails some router P and performs an
   incremental SPF. This incremental calculation is terminated when
   all of the notvia P addresses are attached to the SPT. X then
   reverts to the base topology and repeats the process failing each
   router P in turn.

   This algorithm is significantly less expensive than a set of full
   SPFs. Thus, although a router has to calculate the repair paths for
   n-1 failures, the computational effort is much less than n-1 SPFs.

   Experiments on a selection of real world network topologies with
   between 40 and 400 nodes suggest that the worst case computational
   complexity using the above optimizations is equivalent to
   performing between 5 and 13 full SPFs.

Bryant, Shand              Expires Sep 2005                   [Page 4]

INTERNET DRAFT  IP Fast Reroute Using Notvia Addresses        Mar 2005

4.    How a repairing node repairs

   This section explains the operation of each type of repair
   necessary in the network.

4.1    Node Failure

   When router P fails (Figure 1) S encapsulates any packet that it
   would send to B via P to Bp, and then sends the encapsulated packet
   on the shortest path to Bp. S follows the same procedure for
   routers A, and C in Figure 1. The packet is decapsulated at the
   repair target (A, B or C) and then forwarded normally to its

   Notice that with this technique only one level of encapsulation is
   needed, and that it is possible to repair ANY failure regardless of
   link metrics and any asymmetry that may be present in the network.
   The only exception to this is where the failure was a single point
   of failure that partitioned the network, in which case ANY repair
   is clearly impossible.

4.2    Link Failure

   The normal mode of operation of the network would be to assume
   router failure. However, where some destinations are only reachable
   through the failed router, it is desirable that an attempt be made
   to repair to those destinations by assuming that only a link
   failure has occurred.

   To perform a link repair, S encapsulates to Ps (i.e. it instructs
   the network to deliver the packet to P notvia S). All of the
   neighbors of S will have calculated a path to Ps in case S itself
   had failed. S could therefore give the packet to any of its
   neighbors (except, of course, P). However, S should preferably send
   the encapsulated packet on the shortest available path to P. This
   path is calculated by running an SPF with the link SP failed. Note
   that this may again be an incremental calculation which can
   terminate when address Ps has been reattached.

   It is necessary to consider the behavior of IPFRR solutions when a
   link repair is attempted in the presence of node failure. The
   notvia IPFRR solution prevents the formation of loops forming as a
   result of mutual repair, by never providing a repair path for a
   notvia address. Referring to Figure 1, if A was the neighbor of P
   that was on the link repair path from S to P, and P itself had
   failed, the repaired packet from S would arrive at A encapsulated
   to Ps. A would have detected that the AP link had failed and would
   normally attempt to repair the packet. However, no repair path is
   provided for any notvia address, and so A would be forced to drop
   the packet, thus preventing the formation of loop.

Bryant, Shand              Expires Sep 2005                   [Page 5]

INTERNET DRAFT  IP Fast Reroute Using Notvia Addresses        Mar 2005

4.3    Multi-homed Prefix

   A multi-homed Prefix (MHP) is reachable via more than one router in
   the network. When IPFRR router S (Figure 2) discovers that P has
   failed, it needs to send MHP packets addressed to X, which are
   normally reachable through P, to an alternate router, which is
   still able to reach X.

   X                          X                          X
   |                          |                          |
   |                          |                          |
   |                Sp        |Pb                        |
                            Ps|Pc      Bp

                Figure 2: Multi-home Prefixes

   S should choose the closest router that can reach X during the
   failure as the alternate router. S determines which router to use
   as the alternate while running the SPF with P failed. This is
   accomplished by continuing to run the incremental SPF with P failed
   until all of P's notvia addresses and MHPs (X) are attached.

   Assume that the alternate router is Z, which S can reach without
   using the failed router P. S cannot just send the packet towards Z,
   because the other routers in the network will not be aware of the
   failure of P, and may loop the packet back to S. S therefore
   encapsulates the packet to Z (using a normal address for Z). Z
   removes the encapsulation and forwards the packet to X.

   Now assume that the alternate router is Y, which S reaches via P
   and B. To reach Y, S must first repair the packet to B using the
   normal notvia repair mechanism. To do this S encapsulates the
   packet for X to Bp. B removes the encapsulation and discovers that
   the packet is intended for MHP X. B then follows the algorithm
   above and B encapsulates the packet to Y (using a normal address
   for Y). Y removes the encapsulation and forwards the packet to X.

   It may be that the cost of reaching X using local delivery from the
   alternate router is greater than the cost of reaching X via P.
   Under those circumstances the alternate router would normally
   forward to X via P, which would cause the IPFRR repair to loop. To
   prevent the repair from looping the alternate router must locally
   deliver a packet received via a repair encapsulation.

   Notice that using the notvia approach, only one level of
   encapsulation was needed to repair MHPs to the alternate router.

Bryant, Shand              Expires Sep 2005                   [Page 6]

INTERNET DRAFT  IP Fast Reroute Using Notvia Addresses        Mar 2005

4.4    Shared Risk Groups

   When the network contains a shared risk group (SRG), it must be
   assumed that all members of the SRG fail simultaneously. When
   undertaking SRG repair the scope of the notvia address therefore
   changes from notvia a particular router to notvia the whole SRG.
   All routers calculate a route to each of the notvia addresses of
   the interfaces that connect the SRG to the rest of the network.
   This calculation is made by simultaneously failing all members of
   the SRG in the incremental SPF.

   When a router that is adjacent to an SRG member makes a repair, it
   encapsulates the packet to the notvia address of the router that
   has the lowest cost from the SRG to the destination (i.e. the
   egress point of the SRG prior to the failure).

                           Asrg          Fsrg
              |      |         |
              |Csrg  |Dsrg     |
              C      D         E
              |      |         |
              |      |         |
              H      J         K

            Figure 3: Shared Risk Group

   Thus in Figure 3, S would encapsulate to Csrg to reach H, to Dsrg
   to reach J, to Asrg to reach K and to Fsrg to reach G.

4.5    Multicast

   Multicast traffic is repaired in a similar way to unicast, however
   the multicast forwarder is able to use the notvia address to which
   the multicast packet was addressed as an indication of the expected
   receive interface and hence to correctly run the required RPF

   A more complete description of multicast operation will be provided
   in the next version of this draft.

4.6    Fast Reroute in an MPLS LDP Network.

   Notvia addresses are IP addresses and LDP will distribute labels
   for them in the usual way. The notvia repair mechanism may
   therefore be used to provide fast re-route in an MPLS network by
   first pushing the label which the repair endpoint uses to forward
   the packet, and then pushing the label corresponding to the notvia
   address needed to effect the repair. Referring once again to Figure
   1, if S has a packet destined for D that it must reach via P and B,
   S first pushes B's label for D. S then pushes the label that its
   next hop to Bp needs to reach Bp.

Bryant, Shand              Expires Sep 2005                   [Page 7]

INTERNET DRAFT  IP Fast Reroute Using Notvia Addresses        Mar 2005

   Note that in an MPLS LDP network it is necessary for S to have the
   repair endpoint's label for the destination. When S is effecting a
   link repair it already has this. In the case of a node repair, S
   either needs to set up a directed LDP session with each of its
   neighbor's neighbors, or it needs to use the next-next hop label
   distribution mechanism proposed in [NNHL]. Where an extended SRG is
   being repaired, S must determine which routers its traffic would
   traverse on egress form the SRG, and then establish directed LDP
   sessions with each of those routers.

5.    Local Area Networks

   LANs are a special type of SRG and are solved using the SRG
   mechanisms outlined above. With all SRGs there is a trade-off
   between the sophistication of the fault detection and the size of
   the SRG.


            Figure 4 Local Area Networks

   Consider the LAN shown in Figure 4. For connectivity purposes, we
   consider that the LAN is represented by the pseudonode (N). To
   provide IPFRR protection, S must run a connectivity check to each
   of its protected LAN adjacencies P, P', and P'', using, for example
   BFD [BFD].

   When S discovers that it has lost connectivity to P, it is unsure
   whether the failure is:

     . its own interface to the LAN,

     . the LAN itself,

     . the LAN interface of P

     . or the node P.

   With no further diagnostics S must repair traffic sent through P
   and B, to B notvia P,N (i.e. not via P and not via N), on the

Bryant, Shand              Expires Sep 2005                   [Page 8]

INTERNET DRAFT  IP Fast Reroute Using Notvia Addresses        Mar 2005

   conservative assumption that both the entire LAN and P have failed.
   Destinations for which P is a single point of failure must as usual
   be sent to P using an address which avoids the interface by which P
   is reached from S, i.e. to P notvia N. Similarly for routers P' and

   Notice that each router that is connected to a LAN must, as usual,
   advertise one notvia address for each neighbor. In addition, each
   router on the LAN must advertise an extra address not via the
   pseudonode (N).

   Notice also that each neighbor of a router connected to a LAN must
   advertise two notvia addresses, the usual one not via the neighbor
   and an additional one, not via either the neighbor or the
   pseudonode. The required set of LAN address assignments is shown in
   figure 5 below. Each router on the LAN, and each of its neighbors,
   is advertising exactly one address more than it would otherwise
   have advertised if this degree of connectivity had been achieved
   through the use of point to point links.

                                P's P'p  P'c  Cp'n
                        |       P'p''Pn       Cp'
       Asn   Sa Pp Pp'  |
      A--------S--------+       Ps  Pp' Pb   Bpn
       As       P''Pn   +--------------P--------B
                        |       Pp''Pn        Bp
                        |       Ps  Pp    Pd Dp''n
                                Pp' Pn       Dp''

            Figure 5 Local Area Networks

   To explicitly diagnose the failed network component S correlates
   the connectivity reports from P and one or more of the other
   routers on the LAN, in this case, P' and P''. If it lost
   connectivity to P alone, it could deduce that the LAN was still
   functioning and that the fault lay with either P, or the interface
   connecting P to the LAN. It would then repair to B not via P (and P
   notvia N for destinations for which P is a signal point of failure)
   in the usual way. If S lost connectivity to more than one router on
   the LAN, it could conclude that the fault lay only with the LAN,
   and could repair to P, P' and P'' notvia N, again in the usual way.

   Now we need to consider what happens if S fails. Router A needs to
   be able to repair to every router on the LAN notvia S which it does
   in the usual way using the set of notvia S addresses.

   An alternative approach that provides less post-failure
   connectivity, but uses less addresses is to consider the LAN and

Bryant, Shand              Expires Sep 2005                   [Page 9]

INTERNET DRAFT  IP Fast Reroute Using Notvia Addresses        Mar 2005

   all of its connected routers as a single SRG. Thus the address P
   not via the LAN (Pl) would require P to be reached notvia any
   router connected to the LAN. This is shown in Figure 6.

                                    P'l       Cl
                        |                P'c
       As       Sl      |
      A--------S--------+            Pl       Bl
             Sa         +--------------P--------B
                        |               Pb
                        |          P''l       Dl

            Figure 6 Local Area Networks - LAN SRG

   In this case when S detected that P had failed it would send
   traffic reached via P and B to B notvia the LAN or any router
   attached to the LAN (i.e. to Bl). Any destination only reachable
   through P would be addressed to P notvia the LAN or any router
   attached to the LAN (except of course P).

6.    Loop Free Alternatives

   The use of loop free alternates (LFA) as a repair mechanism has
   been studied [LFA]. Where an LFA exists, S may use this in place of
   the notvia repair mechanism for unicast packets (including MHP
   alternate routers). Multicast traffic requires the use of a repair
   encapsulation so that the router at the repair endpoint can make
   the necessary RPF check.

7.    Equal Cost Multi-Path

   A router can use an equal cost multi-path (ECMP) repair in place of
   a notvia repair for unicast packets.

   A router computing a notvia repair path MAY subject the repair to

8.    Encapsulation

   Any IETF specified IP in IP encapsulation may be used to carry a
   notvia repair. IP in IP [IPIP], GRE [RFC1701] and L2TPv3 [L2TPv3],
   all have the necessary and sufficient properties. The requirement
   is that both the encapsulating router and the router to which the
   encapsulated packet is addressed have a common ability to process
   the chose encapsulation type.

Bryant, Shand              Expires Sep 2005                  [Page 10]

INTERNET DRAFT  IP Fast Reroute Using Notvia Addresses        Mar 2005

9.    Routing Extensions

   IPFRR requires IGP extensions. Each IPFRR router that is directly
   connected to a protected network component must advertise a notvia
   address for that component. This must be advertised in such a way
   that the association between the protected component (router or
   SRG) and the notvia address can be determined by the other routers
   in the network.

   It is necessary that notvia capable routers advertise in the IGP
   that they will calculate notvia routes.

   It is necessary for routers to advertise the type of encapsulation
   that they support (LDP, GRE [RFC1701], L2TPv3 etc). However the
   deployment of mixed IP encapsulation types within a network is

10.     Incremental Deployment

   Incremental deployment is supported by excluding routers that are
   not calculating notvia routes from the base topology. In that way
   repairs may be steered around island of routers that are not IPFRR

   Routers that are protecting a network component need to have the
   capability to encapsulate and decapsulate packets. However, routers
   that are on the repair path only need to be capable of calculating
   notvia paths and including the notvia addresses in their FIB i.e.
   these routers do not need any changes to their forwarding

11.     IANA considerations

   There are no IANA considerations that arise from this draft.

12.     Security Considerations

   The repair endpoints present vulnerability in that they might be
   used as a method of disguising the delivery of a packet to a point
   in the network. The primary method of protection should be through
   the use of a private address space for the notvia addresses. These
   addresses MUST NOT be advertised outside the area, and SHOULD be
   filtered at the network entry points. In addition a mechanism might
   be developed that allowed the use of the mild security available
   through the use of a key [RFC1701] [L2TPv3]. With the deployment of
   such mechanisms, the repair endpoints would not increase the
   security risk beyond that of existing IP tunnel mechanisms.

   An attacker may attempt to overload a router by addressing an
   excessive traffic load to the decapsulation endpoint. Typically
   routers take a 50% performance penalty in decapsulating a packet.
   The attacker could not be certain that the router would be
   impacted, and the extremely high volume of traffic needed, would
   easily be detected as an anomaly.

Bryant, Shand              Expires Sep 2005                  [Page 11]

INTERNET DRAFT  IP Fast Reroute Using Notvia Addresses        Mar 2005

   If an attacker were able to influence the availability of a link,
   they could cause the network to invoke the notvia repair mechanism.
   A network protected by notvia IPFRR is less vulnerable to such an
   attack than a network that undertook a full convergence in response
   to a link up/down event.

Intellectual Property Statement

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed
   to pertain to the implementation or use of the technology described
   in this document or the extent to which any license under such
   rights might or might not be available; nor does it represent that
   it has made any independent effort to identify any such rights.
   Information on the procedures with respect to rights in RFC
   documents can be found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use
   of such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at

 Full copyright statement

   Copyright (C) The Internet Society (2004). This document is subject
   to the rights, licenses and restrictions contained in BCP 78, and
   except as set forth therein, the authors retain all their rights.

   This document and the information contained herein are provided on

Normative References

   There are no normative references.

Informative References

   Internet-drafts are works in progress available from

Bryant, Shand              Expires Sep 2005                  [Page 12]

INTERNET DRAFT  IP Fast Reroute Using Notvia Addresses        Mar 2005

   [BFD]         Katz, D., Ward, D., "Bidirectional Forwarding
                 Detection", < draft-katz-ward-bfd-02.txt>, May
                 2004, (work in progress).

   RFC1701       RFC 1701, Generic Routing Encapsulation (GRE).
                 S. Hanks, T. Li, D. Farinacci, P. Traina.
                 October 1994.

   [IPFRR]       Shand, M., "IP Fast-reroute Framework", <draft-
                 ietf-rtgwg-ipfrr-framework-01.txt>, June 2004,
                 (work in progress).

   [l2TPV3]      J. Lau, Ed., et al., "Layer Two Tunneling
                 Protocol - Version 3 (L2TPv3)" <draft-ietf-
                 l2tpext-l2tp-base-15.txt>,  December 2004,
                 (work in progress)

   [LFA]         A. Atlas, Ed, "Basic Specification for IP Fast-
                 Reroute: Loop-free Alternates", <draft-ietf-
                 rtgwg-ipfrr-spec-base-02.txt>, January 2005,
                 (work in progress).

   [LDP]         Andersson, L., Doolan, P., Feldman, N.,
                 Fredette, A. and B. Thomas, "LDP
                 Specification", RFC 3036,
                 January 2001.

   [NNHL]        Shen, N., et al "Discovering LDP Next-Nexthop
                 Labels", <draft-shen-mpls-ldp-nnhop-label-
                 01.txt>, July 2004, (work in progress)

   [MPLS-TE]     Ping Pan, et al, "Fast Reroute Extensions to
                 RSVP-TE for LSP Tunnels",
                 (work in progress).

   [TUNNEL]      Bryant, S., Shand, M., "IP Fast Reroute using
                 tunnels", <draft-bryant-ipfrr-tunnels-00.txt>,
                 May 2004 (work in progress).

Authors' Addresses

   Stewart Bryant
   Cisco Systems,
   250, Longwater,
   Green Park,
   Reading, RG2 6GB,
   United Kingdom.             Email:

   Mike Shand
   Cisco Systems,

Bryant, Shand              Expires Sep 2005                  [Page 13]

INTERNET DRAFT  IP Fast Reroute Using Notvia Addresses        Mar 2005

   250, Longwater,
   Green Park,
   Reading, RG2 6GB,
   United Kingdom.             Email:

Bryant, Shand              Expires Sep 2005                  [Page 14]