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. 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/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Abstract 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", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119]. 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 this. A |Ap Bp is the address to use to get | a packet to B notvia P Sp Pa|Pb S----------P----------B Ps|Pc Bp | Cp| C 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 P. 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 destination. 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 | Z...............S----------P----------B...............Y Ps|Pc Bp | Cp| C 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 S----------P------P'--------A----P''------F--------G | | | |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 check. 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. +--------------P'-------C | | | A--------S--------+ (N) +--------------P--------B | | | +--------------P''------D 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 P''. 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'-------C | 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 +--------------P''------D 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 | P'c | As Sl | A--------S--------+ Pl Bl Sa +--------------P--------B | Pb | | P''l Dl +--------------P''------D P''d 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 ECMP. 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 deprecated. 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 capable. 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 mechanism. 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 at http://www.ietf.org/ipr. 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 ietf-ipr@ietf.org. 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 an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 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", , June 2004, (work in progress). [l2TPV3] J. Lau, Ed., et al., "Layer Two Tunneling Protocol - Version 3 (L2TPv3)" , December 2004, (work in progress) [LFA] A. Atlas, Ed, "Basic Specification for IP Fast- Reroute: Loop-free Alternates", , 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", , 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", , May 2004 (work in progress). Authors' Addresses Stewart Bryant Cisco Systems, 250, Longwater, Green Park, Reading, RG2 6GB, United Kingdom. Email: stbryant@cisco.com 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: mshand@cisco.com Bryant, Shand Expires Sep 2005 [Page 14]