Network Working Group A. Atlas, Ed. Internet-Draft Avici Systems, Inc. Expires: April 24, 2005 October 24, 2004 U-turn Alternates for IP/LDP Fast-Reroute draft-atlas-ip-local-protect-uturn-01 Status of this Memo This document is an Internet-Draft and is subject to all provisions of section 3 of RFC 3667. By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she 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/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 April 24, 2005. Copyright Notice Copyright (C) The Internet Society (2004). Abstract This document defines and describes the use of u-turn alternates to provide local protection for IP unicast and/or LDP traffic in the event of a single link or node failure. When a topology change occurs, a router S pre-computes for each prefix an alternate next-hop that can be used if the primary next-hop fails. An acceptable alternate can be either a loop-free alternate or a U-turn alternate. A U-turn alternate uses a neighbor, whose primary next-hop to the prefix is router S itself and which has itself a loop-free Atlas Expires April 24, 2005 [Page 1] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 node-protecting alternate, which thus does not go through router S to reach the destination prefix. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 2. U-turn Alternates . . . . . . . . . . . . . . . . . . . . . . 5 2.1 ECMP U-turn Neighbors . . . . . . . . . . . . . . . . . . 7 2.2 U-turn Neighbor's Alternate . . . . . . . . . . . . . . . 8 2.3 Identifying U-turn Traffic . . . . . . . . . . . . . . . . 9 2.3.1 Implicit U-turn Packet Identification . . . . . . . . 9 2.3.1.1 Broadcast and NBMA Interfaces . . . . . . . . . . 9 2.3.2 Explicitly Marked U-turn Packet Identification . . . . 10 3. Example Algorithm for finding U-turn Alternates . . . . . . . 12 3.1 SRLG Protection . . . . . . . . . . . . . . . . . . . . . 15 4. Alternate Next-Hop Calculation . . . . . . . . . . . . . . . . 15 4.1 IP/LDP Fast-Reroute Alternate Capability . . . . . . . . . 15 4.2 U-turn Recipient Capabilities . . . . . . . . . . . . . . 16 4.3 Link-Protecting U-turn Alternate . . . . . . . . . . . . . 17 4.4 U-turn Node-Protecting Alternate . . . . . . . . . . . . . 17 4.5 Selection Procedure . . . . . . . . . . . . . . . . . . . 17 4.5.1 Selection Procedure with One Primary Neighbor . . . . 18 4.5.1.1 Selection Between Multiple Loop-Free Node-Protecting Alternate . . . . . . . . . . . . 18 4.5.2 Alternate Selection with Multiple Primary Neighbors . 19 5. Using an Alternate . . . . . . . . . . . . . . . . . . . . . . 19 5.1 Alternate Use On Failure . . . . . . . . . . . . . . . . . 20 5.2 U-turn Packets Forwarding . . . . . . . . . . . . . . . . 22 6. LDP Interactions and Routing Aspects . . . . . . . . . . . . . 22 6.1 LDP Interactions . . . . . . . . . . . . . . . . . . . . . 22 6.2 Inter-Region Routes . . . . . . . . . . . . . . . . . . . 22 7. U-turn Alternates Interactions with Tunnels . . . . . . . . . 23 8. Security Considerations . . . . . . . . . . . . . . . . . . . 24 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 24 10. Intellectual Property Considerations . . . . . . . . . . . . 24 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 24 Editor's Address . . . . . . . . . . . . . . . . . . . . . . . 25 Contributing Authors' Addresses . . . . . . . . . . . . . . . 25 Intellectual Property and Copyright Statements . . . . . . . . 27 Atlas Expires April 24, 2005 [Page 2] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 1. Introduction This document extends IP Fast-Reroute, as defined in [IPFRR] and [FRAMEWORK], which allows a router whose local interface or next-hop has failed to forward traffic to a pre-computed alternate until the router installs the new primary next-hops based upon the changed network topology. The existence of suitable loop-free alternate next-hops is topology dependent. This document defines a second type of alternate next-hop, known as a u-turn alternate, and provides the common behavior and selection method necessary to allow u-turn alternates to function. The topology in Figure 1 is an example where there is no loop-free alternate from S to D, but there is a u-turn alternate. @@@> <--- +-----+ +----------| N_1 | | 5 +-----+ | | +---+-+ | | S | @ |10 +-----+ @ | | V | | |5 | V | | | | +-----+ | | E | +-----+ +-----+ | R_1 | | +-----+ | |5 | | | 10 | | V | | | +-----+ | V | D |---------+ +-----+ Figure 1: Topology with U-turn Alternate In Figure 1, there is no loop-free alternate for S to use to reach D. This is because the costs are such that N_1 uses S as its primary neighbor; therefore if S were to send the traffic to N_1, it would loop back to S. If both S and N_1 support the mechanisms defined in this document, then S could use N_1 as a u-turn alternate. Traffic Atlas Expires April 24, 2005 [Page 3] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 destined to D which was sent by S to N_1 would be forwarded by N_1 to R_1, N_1's loop-free node-protecting alternate. In examining realistic networks, it was seen that loop-free alternates did not provide adequate coverage for the traffic between all the source-destination pairs. As with loop-free alternates, the existence of suitable u-turn alternates is topology dependent; it is seen to substantially extend the coverage on realistic topology above that seen with just loop-free alternates. This document describes the case where a loop-free node-protecting alternate must be available at a neighbor's neighbor. It is possible to extend the length of the U-turn to provide better coverage at the cost of additional local computational complexity. 1.1 Terminology This document uses the terminology defined in [FRAMEWORK] and the additional terms defined below. Distance_opt(A, B) or D_opt(A,B): The distance of a shortest path from A to B. Distance_!S(A, B) or D_!S(A,B): The distance of a shortest path from A to B that does not traverse S. Reverse Distance of a node X: --- This is the Distance_opt(X, S). U-Turn Alternate: This is an alternate next-hop of S that goes to a neighbor N_i, whose primary next-hop is S, and whose alternate neighbor does not go back trough the router S, which may therefore use the link to N_i as an alternate. Link(A->B): A link connecting router A to router B. ---> An arrow indicating the primary next-hop towards D. @@@> An arrow indicating the alternate next-hop towards D. U-Turn Neighbor: A neighbor N_i is a U-Turn neighbor of router S with respect to a given destination D if and only if S is a primary neighbor of N_i to reach the destination D for all optimal paths which go through S to reach D. ECMP U-Turn Neighbor: A neighbor N_i which is a U-Turn neighbor and which has at least one equal cost path to reach D that does not go through S as well as the path(s) which do go through S to reach D. Atlas Expires April 24, 2005 [Page 4] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 Looping Neighbor: A neighbor N_i is a looping neighbor of router S with respect to a given destination D if and only if S is not the primary next-hop of N_i on at least one optimal path from S to D that also goes through S. 2. U-turn Alternates As with primary next-hops, an alternate next-hop is discussed in relation to a particular destination router D. As described in [IPFRR], a neighbor can provide a loop-free alternate if Equation 1 is true. D_opt(N_i, D) < D_opt(N_i, S) + D_opt(S, D) Equation 1: Criteria for a Loop-Free Alternate When there are no loop-free alternates, this means that all of S's remaining non-primary neighbors will send traffic for D back to S, either directly or indirectly. It is probable that one of S's non-primary neighbors will have a loop-free node-protecting alternate that could be utilized if the neighbor N_i is able to identify a packet as a U-turn packet. N_i can indicate its ability to correctly identify incoming U-turn packets on each layer-3 interface; such an interface is U-turn Recipient capable[ISIS-LOCAL-PROTECT][OSPF-LOCAL-PROTECT]. U-turn packets are identified implicitly or explicitly as described in Section 2.3. N_i MUST only send U-turn packets to N_i's loop-free node-protecting alternate if the packet is received from a primary neighbor for that destination. This motivates the definitions below of a Looping Neighbor and a U-turn Neighbor. These examples are illustrated in Figure 2. Looping Neighbor: A neighbor N_i is a looping neighbor of router S with respect to a given destination D if any of N_i's shortest paths to D goes through S but S is not the primary next-hop of N_i for all those paths through S. U-Turn Neighbor: A neighbor N_i is a U-Turn Neighbor of router S with respect to a given destination D if and only if S is a primary next-hop of N_i to reach the destination D for all optimal paths that go through S to reach D. Atlas Expires April 24, 2005 [Page 5] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 +-----+ --> | N_4 |------ <--- +-----+ +-----+ | |-----| R_3 | | 15 | | 5 +-----+ |50 | | | +-----+ ---> | +-----+ | 70 | N_2 |------ | | N_3 | | +-----+ | | +-----+ | | 15 | | | 30 | | 10 | +-----+ <--- | | @ | ----| S |--------| | @ | <@@@ +-----+ | V | | | | | 10 | | | +-----+ | V | | R_2 | +-----+ | +-----+ | E | | | | +-----+ | | | 40 | | | V | 10 | | | | +-----+ | V | -----| R_1 |-----| | +-----+ | | ---> +-----+ | |------------------| D |--------- 10 +-----+ E is primary next-hop of S N_2 and N_3 are U-Turn Neighbors of S N_4 is a Looping Neighbor of S Figure 2: Terminology of Looping Neighbors and Example U-Turn Alternate Mathematically, for a neighbor N_i to be a U-Turn neighbor, it is necessary that Equation 1 be false. If D_opt(N_i,D) = D_opt(N_i,S) + D_opt(S,D), then there may be multiple optimal paths, at least one of which goes through S and one does not. If the shortest distance path from N_i to D that doesn't traverse S (D_!S(N_i, D)) is equal to D_opt(N_i, S) + D_opt(S, D, then there are multiple optimal paths where at least one traverses S and one does not. Such a neighbor may be an ECMP U-Turn neighbor or may be a looping neighbor. Additionally, all optimal paths to reach D that go via S must be via a direct link between N_i and S. If a neighbor N_i does not satisfy Equation 1 and all optimal paths to reach D that go via S are via a direct link between N_i and S, then it is a U-turn neighbor. Atlas Expires April 24, 2005 [Page 6] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 2.1 ECMP U-turn Neighbors The above definition for U-Turn Neighbor allows a neighbor, which has equal cost paths (an ECMP set) where at least one of those paths goes directly to S and others may or may not, to be a U-Turn Neighbor. Consider the topology shown in Figure 3. In this figure, N_1 has three equal-cost paths to reach D which are N_1 - S - E - D, N_1 - R_1 - D, and N_1 - R_2 - D. Because the only path that goes through S goes directly through S, N_1 is a U-Turn neighbor of S. A neighbor is an ECMP neighbor if an optimal path from N_i to D traverses S and there are multiple optimal paths from N_i to D. +-----+------------- ---------| N_1 | | 5 | | +-----+--------- | +-----+ | | 10 | 15 | |----| R_3 | V | | | | +-----+ +-----+ | | 10 | | 15 | | S | V | | | | | +-----+ | V | | | | +-----+ | | V 10 | | ---| R_1 | | | | | | +-----+ | | | V | | +-----+ | | | | 20 | R_2 | | +-----+ V | +-----+ +-----+ | E | | | | X | +-----+ | 15 | | +-----+ | | |---------| | | | | 10 | | V | | | +-----+ <--- | V |--------| D |---------------------| 15 +-----+ Figure 3: ECMP U-Turn Neighbor S does not know whether a neighbor N_i supports ECMP or how that neighbor selects among the equal cost paths. Recall that a node will only direct U-turn packets to the alternate if those packets are received from that node's primary neighbors. Consider the topology in Figure 4, where N_2 has three equal cost primary neighbors which are S, N_1 and R_1. If N_2 were to select only N_1 as its primary neighbor, then N_2 would break U-Turns only on traffic received from N_1 and not on traffic received from S. Therefore, S cannot consider N_2 as an ECMP U-Turn neighbor because S cannot rely upon N_2 to break U-turns for traffic destined to D which Atlas Expires April 24, 2005 [Page 7] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 is received from S. <--- 10 +-----+ ---> --------------------| N_2 |----- | +-----+ | | 5 | | | | +-----+ | | | | | N_1 |----| V | 5 +-----+ +-----+ +-----+ | S | <-- | 5 | R_1 | +-----+---------- +-----+ 5 | | | 15 +-----+ | | | | | E |----| V | | +-----+ V | 5 | ---> +-----+ | |------------------| D |------------- +-----+ Figure 4: ECMP Neighbor Which is Not an ECMP U-Turn Neighbor If N_2 has multiple paths to reach D that traverse S and not all such paths have S as the next-hop, then S cannot use N_2 as a U-Turn neighbor. 2.2 U-turn Neighbor's Alternate For router S to use a U-turn neighbor N_i for a U-turn alternate, N_i requires a loop-free node-protecting alternate[IPFRR]. If R_i_j provides a loop-free node-protecting alternate for N_i and S is N_i's primary neighbor, then the path from R_i_j to D will not traverse S. The requirement for an R_i_j to provide a suitable alternate is: D_opt(R_i_j, D) < D_opt(R_i_j, S) + D_opt(S, D) Equation 2: Loop-Free Neighbor's Neighbor Because N_i is a U-turn neighbor, N_i's shortest path to D traverse S, Equation 2 means that the shortest paths from R_i_j to D also do not traverse N_i. Each router independently computes the alternate that it will select for a given destination D. For the U-turn alternate to provide node protection, the router N_i must consistently select a suitable alternate, if available, such that N_i's primary neighbor S can determine what R_i_j is providing that alternate. This constraint is Atlas Expires April 24, 2005 [Page 8] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 not required to determine if the U-turn alternate provides link-protection. 2.3 Identifying U-turn Traffic There are two methods for identifying a packet as a U-turn packet. The methods are implicit U-turn packet identification and marking-based U-turn packet identification. These methods are described in Section 2.3.1 and Section 2.3.2. A router supporting this specification MUST support one of these two methods for identifying U-turn packets. A 2.3.1 Implicit U-turn Packet Identification The first method requires no modification to the packets sent into the U-turn alternate. In this method, when, on a U-turn Recipient Capable interface or sub-interface, a packet for a destination D is received from the primary neighbor to which the router would forward the packet, then the router locally identifies the packet as a U-turn packet and forwards on the loop-free alternate. In essence, this breaks the single hop micro-loop. 2.3.1.1 Broadcast and NBMA Interfaces NBMA and broadcast interfaces can be treated identically for IP/LDP Fast-Reroute; both involve the case of possibly receiving traffic from multiple neighbors. With broadcast interfaces (i.e. Gigabit Ethernet), there can be multiple neighbors connected to the same interface. If all the neighbors are not in the same IGP area, then explicit U-turn packet identification MUST be used. If implicit U-turn packet identification were used, traffic could be incorrectly sent to the alternate. It is extremely desirable to have at most one forwarding table per interface or sub-interface. If all the neighbors are in the same IGP area, it still MUST be considered whether all traffic received on an interface can be treated identically, regardless of the neighbor sourcing the traffic on that interface; otherwise explicit packet identification SHOULD be used. The cost for any node on the broadcast interface to reach S or its primary neighbor E will be identical. Because all link costs are positive, no neighbor on the broadcast interface will ever send traffic to S along that interface in order to reach E. Therefore, S can assume that any traffic received on the broadcast interface which goes to a destination via a primary next-hop neighbor that is also on the broadcast interface is in fact sent by that primary next-hop neighbor and should be redirected to break the U-Turn. Atlas Expires April 24, 2005 [Page 9] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 Thus, if router S has a primary next-hop neighbor for a given prefix on the broadcast interface, S should redirect all traffic received destined to that prefix on the broadcast interface to S's alternate next-hop. +-----------+-----------+------------+----------+ | | | | | | | /E\ | /E\ | /E\ | /E\ | 2 3| | 3| | 4| | 5| | | | | | | +-----+ +-----+ +-----+ +-----+ +-----+ | E | | S | | N_1 | | N_2 | | N_3 | +-----+ +-----+ +-----+ +-----+ +-----+ | | | | 10 @ | 10 | | @ | V | V | | +-----+ | | N_4 | | +-----+ +-----+ 10 | | D |----------| +-----+ <--- Figure 5: Topology With Broadcast Link If it were acceptable to have one forwarding table per neighbor on the interface, then the restriction that all neighbors on a broadcast link be in the same IGP region could be removed. 2.3.2 Explicitly Marked U-turn Packet Identification The second method requires that U-turn packets be explicitly marked as such by the router that is directing the packet into the U-turn alternate. This method is motivated by the following benefits: a. For certain existing hardware platforms, it may be difficult to implicitly detect packets as coming from a primary neighbor and forward those packets differently. An explicit marking permits straightforward U-turn handling. b. For broadcast and NBMA links, if packets in the U-turn alternate are not explicitly marked, it is necessary that all neighbors on the link be part of the same IGP region (see Section 2.3.1.1). This could limit realistic deployment scenarios where hosts may exist on the same broadcast link as routers. When U-turn packets are explicitly marked, the router can treat some packets received Atlas Expires April 24, 2005 [Page 10] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 on the interface as U-turn packets and some as normal packets. This permits routers and hosts on a link to send normal traffic while the primary neighbor can send explicitly marked U-turn packets. c. If a router were to request penultimate-hop popping (PHP) for an LSP egressing on interface that the router had also advertised as U-turn Recipient capable, then it would be possible for traffic exiting that LSP to be mis-identified using the topology-based identification. If U-turn packets are explicitly marked, then this confusion would not occur and the router could both request PHP for LSPs egressing an interface and supported marked U-turn packet identification. Explicitly marking U-turn traffic has the following disadvantages, which could be viewed as advantages for the implicit U-turn traffic: a. A marking method must be selected. This marking will need to be below Layer 3; there are certainly no available bits for this purpose in the IPv4 header. b. In some cases implicit U-turn marking will mitigate loops that form by detecting the loop and forwarding to a loop-free node-protecting alternate. This capability is lost when packets are explicitly marked. There are a number of different ways in which U-turn packets could be explicitly marked. For example, this could be done at Layer 2 by using different PPP types, Ethernet types, etc. The simplest mechanism that can apply regardless of the Layer 2 technology is to use a well-known MPLS label (referred to as a U-turn Label). By requiring that routers supporting this specification use the same well-known MPLS label, there is no need to communicate the label. There are already different PPP types, Ethernet types, etc. for MPLS. If a router does not support any other MPLS mechanism, then a packet received with the U-turn label can be clearly identified from the layer-2 information indicating that the packet is MPLS. The MPLS label on the packet SHOULD be checked to verify that the label is the U-turn label. Unlike the common use of MPLS labels, the U-turn label does not indicate specifically where the packet should be switched. The U-turn label indicates that the packet should be tentatively identified as a U-turn packet. The label is always popped on the receiving node. If the explicitly marked packet was received from a primary neighbor, Atlas Expires April 24, 2005 [Page 11] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 then the packet is a U-turn packet; the U-turn label MUST be popped and the decision on where to forward the packet is based on the packet's identification as a U-turn packet and the packet's destination IP address or the new top MPLS label (after the U-turn label has been popped). If the explicitly marked packet was not received from a primary neighbor, then the packet is not a U-turn packet, the U-turn label must be popped, and the packet MUST be forwarded as a normal packet based upon its destination IP address or the top MPLS label (after the U-turn label has been popped). This scenario could occur if a failure happened during another topology change where the sending router will be or was the receiving router's primary neighbor. The QoS characteristics associated with a packet with a U-turn label SHOULD be based on the IP packet or the MPLS packet after the U-turn label has been removed. 3. Example Algorithm for finding U-turn Alternates This section describes an algorithm that allows the identification of U-turn alternates with at most one additional SPF computation per neighbor that could be used as a U-turn alternate. These are required in addition to those required to locate loop-free alternates. The computational complexity of locating alternates is extremely important. There are several factors which potentially influence this. N: Number of neighbors of S A: Number of neighbors that could be used as alternates U: Number of neighbors that could be used as U-turn alternates Clearly, any path computation mechanisms will depend upon the cost of SPF calculations, which depend upon the number of links and nodes and pseudo-nodes in the network and the parameter above. However, different approaches can lead to very different numbers of SPF calculations, ranging from a number of computations proportional to N (or A and U) up to a number proportional to the number of nodes in the network, the number of local links, and the number of neighbors' neighbors. Clearly, the latter is undesirable. A single SPF is done to find the primary next-hops; this yields D_opt(S, D) for all D. The additional computation required for loop-free alternates is at worst a reverse SPF rooted at S plus an Atlas Expires April 24, 2005 [Page 12] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 SPF rooted at each neighbor N_i that can be used as an alternate. This gives a worst-case of an additional (1+A) SPF computations to find loop-free alternates. The information obtained is D_opt(D, S) and D_opt(N_i, D) for all N_i and D. It is important to understand the minimum computation required for U-turn alternates beyond that needed for loop-free alternates. The minimum information that must be determined is whether a particular neighbor N_i has a loop-free node-protecting alternate. This can be determined for a neighbor N_i by running a single u-turn SPF. To explain the rationale behind the mechanisms in a u-turn SPF, consider the following. An SPF algorithm is performing a minimization across the potential paths. A regular SPF is started by exploring each link connected to the root N_i and using the metric associated with that link as the cost. Therefore, at each destination D, it determines D_opt(N_i, D). If instead each link from the root N_i is explored with a cost of 0, then, if there are J neighbors of N_i, the distance associated with the path at each destination D would be min_forall j in J (D_!N_i(R_i_j, D)) where D_!N_i indicates the shortest path from the particular R_i_j to D that does not traverse N_i. Now, if one considers the loop-free test from Equation 2 and groups all the R_i_j terms onto one side, one obtains the following equation: D_opt(R_i_j, D) - D_opt(R_i_j, S) < D_opt(S, D). If an SPF could be modified to minimize the left-hand side of the above equation for all R_i_j neighboring N_i, then the resulting value could be compared to D_opt(S,D) to determine if N_i had a loop-free node-protecting alternate. Mathematically, if there are 1 to J different neighbors of N_i, the desired result at each destination D would be: min_forall j in J (D_opt(R_i,j, D) - D_opt(R_i_j, S)). It is sufficient to determine at each destination D: min_forall j in J (D_!N_i(R_i,j, D) - D_opt(R_i_j, S)). Equation 3: Path Minimization for U-turn Alternate Check To visualize this, consider the following 2 different cases where N_i's primary neighbor is S. Atlas Expires April 24, 2005 [Page 13] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 A shortest path from R_i_j to D is via N_i and thus S. Therefore, D_!N_i(R_i_j, D) >= D_opt(R_i_j, D). A shortest path from R_i_j to D is not via N_i. Therefore, D_!N_i(R_i_j, D) = D_opt(R_i_j, D). Now that the rationale behind a u-turn SPF is clearer, here is the description of a u-turn SPF. If this procedure is followed, then the stored path distance at each destination D will be Equation 3. A u-turn SPF is a regular SPF where the initial exploration of links from the root N_i uses different costs depending upon the node at the other end of the link. Links from N_i to a node R_i_j are explored with a cost of -D_opt(R_i_j, S). If a link goes from N_i to a pseudo-node, then the pseudo-node's links are also explored as part of this step. The pseudo-node itself is not given a non-infinite path distance in this step. In this step, each link from a pseudo-node neighboring N_i to a node R_i_j is explored with a cost of -D_opt(R_i_j, S). At the end of this step, each R_i_j will be on the candidate-list. From this point, the normal mechanics of the Dijkstra algorithm apply; when a node is removed from the candidate-list, its links will be explored with the cost that of the link metric. From the above description of a u-turn SPF and the rationale behind it, it can be seen that at most one u-turn SPF is needed per neighbor that could be used as a U-turn alternate. The computational complexity of a u-turn SPF is roughly the same as a regular SPF. The additional computational complexity is U u-turn SPF computations, where U is the number of neighbors that could be considered as U-turn alternates. The above gives the ability to determine if a neighbor N_i has a loop-free node-protecting alternate and can therefore provide a U-turn alternate. It does not provide a method to determine if that U-turn alternate is node-protecting. Because D_opt(R_i_j, E) is not known as a result of the previous SPFs, a simple distance comparison is not possible without additional SPFs. To obtain D_opt(R_i_j, E) would require R SPF computations and replace the U u-turn SPF computations. In a network the number of neigbhors is generally much less then the number of neighbors' neighbors. Therefore, another method of determining node protection for U-turn alternates is desirable. During the u-turn SPF, it is possible to track those neighbors of S that were visited along the stored path. If this is done and N_i always selects the R_i_j corresponding to that path as an alternate, then S can determine whether that stored path traverses E, S's Atlas Expires April 24, 2005 [Page 14] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 primary next-hop. This allows S to determine node-protection at the cost of a bit of additional book-keeping. This discussion of an algorithm to compute U-turn alternates is intended to provide explanatory background for the selection procedure defined in Section 4.5.1.1. 3.1 SRLG Protection It may be desirable to obtain an alternate that provides SRLG protection. If SRLGs are being considered, then this would need to be signaled to neighboring routers; an extension to the router capability would provide the mechanism. It can be determined if a U-turn alternate provides SRLG-protection by tracking the SRLGs traversed. This may miss a possible U-turn alternate; to locate all possible U-turn alternates and determine SRLG protection may need an SPF computation per neighbors' neighbor. Intelligent pruning of the R_i_j considered based upon first link SRLGs may improve the completeness of the algorithm while not requiring an SPF computation per neighbors' neighbor. 4. Alternate Next-Hop Calculation A router S must select an appropriate alternate next-hop. A common selection method is required to support U-turn Alternates. At a minimum, a router must select a loop-free node-protecting alternate. This will ensure that a U-turn alternate via that router will be link-protecting. To provide node protection, it is necessary for router S to know the properties of the R_i_j that will be selected by N_i. The same set of failure scenarios that can be protected against with a loop-free alternate is of interest with a u-turn alternate. Similarly, there is the same interaction with maximum costed links and broadcast interfaces as described in [IPFRR]. In addition, if all links from a neighbor N_i to a neighbor's neighbor R_i_j have a reverse cost of LSInfinity, then router S cannot consider that N_i could provide a U-turn alternate via R_i_j. The rationales for these restrictions are the same as given in [IPFRR]. 4.1 IP/LDP Fast-Reroute Alternate Capability There are a number of different reasons why an operator may not wish for a particular interface to be used as an alternate. For instance, the interface may go to an edge router or the interface may not have sufficient bandwidth to contain the traffic which would be put on it in the event of failure. Atlas Expires April 24, 2005 [Page 15] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 In order to indicate interfaces as eligible alternates, a router must signal this link capability. The neighbor routers must not consider that links, which are not eligible alternates, might be capable of providing a loop-free node-protecting alternate. Therefore, this eligible alternate capability is flooed as part of the link capabilities information. Links that are not capable of being alternates are not explored in the first step of the u-turn SPF. Because a router's neighbors may desire to use that router to provide a U-turn alternate, a router must flood to its neighbors which interfaces are not capable of providing alternates. This information allows a router's neighbors to accurately determine whether or not the router has a loop-free node-protecting alternate. The extensions to signal this IP/LDP fast-reroute alternate capability are described in [OSPF-LOCAL-PROTECT] and [ISIS-LOCAL-PROTECT]. 4.2 U-turn Recipient Capabilities A router S can only use a neighbor as a U-turn alternate next-hop if that neighbor has advertised its ability to identify U-turn alternates on a link to S. The implicit U-turn recipient capability or the explicit marked U-turn recipient capability must be signaled by a neighbor for a link in order for S to determine that it is allowed to use that neighbor as a potential U-turn alternate. By default, S MUST assume that a neighbor cannot provide a U-Turn alternate unless that neighbor indicates the implicit or the explicit marked U-Turn recipient capability on the link to be used by S to reach that neighbor. These U-Turn recipient capabilities need only be flooded to a node's neighbors. The U-turn alternate next-hop MUST use a link which has been advertised as implicit or explicit marked U-turn Recipient capable by the intended neighbor. If router S is only capable of sending unmarked U-turn packets, then router S MUST not use links which are not advertised as implicit U-turn Recipient capable to reach a U-turn alternate next-hop. Similarly, if router S is only capable of sending marked U-turn packets, then router S MUST not use links which are not advertised as explicit marked U-turn Recipient capable to reach a U-turn alternate next-hop. If a link is advertised only as explicit marked U-turn Recipient capable and it is selected to reach the U-turn alternate next-hop, then router S MUST apply the marking, as described in the explicit marked U-turn packet identification method, to each packet sent into the U-turn alternate. If the link is advertised only as implicit U-turn Recipient capable and it is selected to reach the U-turn Atlas Expires April 24, 2005 [Page 16] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 alternate next-hop, then router S MUST not apply any additional marking. If the link is advertised as both implicit U-turn Recipient capable and explicit marked U-turn Recipient capable, then router S may make a local decision as to whether to apply the additional marking. The extensions to signal the U-turn recipient capability and the Marked U-turn recipient capability are described in [OSPF-LOCAL-PROTECT] and [ISIS-LOCAL-PROTECT]. 4.3 Link-Protecting U-turn Alternate For a neighbor N_i to be useable by a router S as a U-turn alternate next-hop to reach a destination D, the following topology-based conditions MUST be true. 1. S is a U-turn neighbor. In other words, S is always the primary next-hop on all shortest paths from N_i to D that traverse S. 2. D_opt(N_i, D) >= D_opt(N_i, S) + D_opt(S, D) 3. For at least one of N_i's neighbors, R_i_j: D_opt(R_i_j, D) < D_opt(R_i_j, S) + D_opt(S, D) The path used from the neighbor's neighbor R_i_j to the destination is along the SPT. If the link from S to N_i is a broadcast link, it cannot be used by R_i_j's shortest path because the shortest path from the pseudo-node representing the broadcast link is via S. This is clear from the fact that N_i's shortest path via the broadcast link is immediately via S. Therefore, if N_i can offer a U-turn alternate, it is also link-protecting. The non-topology based conditions are dependent upon the signaled link capabilities as described earlier. 4.4 U-turn Node-Protecting Alternate For a U-turn alternate next-hop to protect against node failure, S must be able to determine the set of R_i_j that might be used to provide the loop-free node-protecting alternate to N_i. All optimal paths from each of those R_i_j to the destination D MUST avoid S's primary neighbor E. 4.5 Selection Procedure A router supporting this specification SHOULD select a loop-free alternate next-hop or a U-turn alternate next-hop for each primary next-hop used for a given prefix. A router MAY decide to not use an Atlas Expires April 24, 2005 [Page 17] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 available loop-free or U-turn alternate next-hop. The selection should maximize the failure cases that can be protected against. As specified in [IPFRR], the selection procedure depends on whether S has a single primary neighbor or multiple primary neighbors. A node S is defined to have a single primary neighbor only if there are no equal cost paths that go through any other neighbor; i.e., a node S cannot be considered to have a single primary neighbor simply because S does not support ECMP. The following sections outline the decision criteria for various network configurations. 4.5.1 Selection Procedure with One Primary Neighbor A router S can only be used as a U-turn alternate next-hop by its primary neighbor E if S selects a loop-free node-protecting alternate next-hop. Therefore a router MUST select a loop-free node-protecting alternate if one is available. Otherwise, a router MAY select a U-turn node-protecting alternate, a loop-free link-protecting alternate or a U-turn link-protecting alternate, if any such is available. 4.5.1.1 Selection Between Multiple Loop-Free Node-Protecting Alternate The specific selection policy described in this section is motivated by the ability to reduce the computational complexity associated with identifying U-turn alternates. This mechanism is explained in Section 3. D_opt(R_i_j, D) - D_opt(R_i_j, S) Equation 4: Shortest Reverse-Path-Discounted Distance from R_i_j to D A consequence of this mechanism is that the only path traced during the u-turn SPF is that of the shortest reverse-path-discounted path. A second consequence is that the optimal distance between a neighbor's neighbor and S's primary neighbor E ( D_opt(R_i_j, E) ) is not always known. By constraining the loop-free node-protecting alternate selection as specified below, it is sufficient to know only the path of the shortest reverse-path-discounted path via any of N_i's neighbors. The selection by a router among loop-free node-protecting alternates MUST be as follows. Each loop-free node-protecting alternate next-hop is a specific R_i_k Atlas Expires April 24, 2005 [Page 18] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 where there are K members. The selected R_i_m must be provide the shortest reverse-path-discounted path among all the R_i_j. D_opt(R_i_m, D) - D_opt(R_i_m, S) = min_forall k in K (D_opt(R_i_k, D) - D_opt(R_i_k, S) If there are multiple such R_i_m and one provides the destination, then that one SHOULD be selected. Otherwise, if there are multiple such R_i_m, the router SHOULD make a consistent selection. A consequence of this selection algorithm is that, all else being equal, a more expensive link from an R_i_j will be preferred. This should be considered when determining appropriate metrics for IP traffic-engineering. 4.5.2 Alternate Selection with Multiple Primary Neighbors The selection among multiple equal cost paths is a router-local decision. Therefore, a router N_i cannot know which of the potential primary neighbors that S will choose to use. As described in Section 2.1, N_i can only select S for its U-Turn alternate if any potential primary neighbor which S might select, except for N_i itself, will not go via N_i to reach the destination D. Because the router has multiple potential primary neighbors, the router MUST select one or more alternates for forwarding U-Turns packets from among the router's potential primary neighbors. If the router does not have a potential primary neighbor that is node-protecting for a particular primary next-hop, this is an indication that that primary neighbor will not use S as a U-turn alternate. A router MAY use different alternate(s) for forwarding U-turn packets and for forwarding traffic when a primary next-hop fails. The alternate(s) used when a primary next-hop fails are a router-local decision. 5. Using an Alternate If an alternate is available, it may be used in two circumstances. The first is when a local failure is detected; the behavior on a local failure is that specified in [IPFRR]. The second is when U-turn packets are received and the alternate is loop-free and node-protecting. Atlas Expires April 24, 2005 [Page 19] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 5.1 Alternate Use On Failure If an alternate next-hop is available, the router SHOULD redirect traffic to the alternate next-hop when the primary interface has failed. If the alternate next-hop provides node protection, the router SHOULD redirect traffic to the alternate next-hop when the primary next-hop has failed and the detection of that failure has occurred within an appropriately short period. The mechanisms available for failure detection are discussed in [FRAMEWORK] and are outside the scope of this specification. The alternate next-hop MUST be used only for traffic types which are routed according to the shortest path. Multicast traffic is specifically out of scope for this specification. The details in [IPFRR] on terminating the use of the alternate apply equally to U-turn alternates. Although extremely unlikely in examined topologies, it is theoretically possible that the convergence on the part of the U-turn neighbor N_i could cause a short micro-loop as in the following topology. In this example, N provides a U-turn alternate to S via the loop-free node-protecting alternate A. After the link from S to E fails, N's alternate continues to function. When N converges, the new primary next-hop is B; if B has not already converged, then a micro-loop between N and B could form. Atlas Expires April 24, 2005 [Page 20] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 1 +---+ 1 -------| B |------ | +---+ | | | +---+ 1 +---+ 10 +---+ | | S |----| N |----| A | | +---+ +---+ +---+ | 1 | 5 | | +---+ +---+ +---+ | E | | C | | F | +---+ +---+ +---+ | 5 | | 1 | +---+ | 4 |---------------| D |----| +---+ Figure 6: Micro-loop Affecting U-turn Alternate To avoid such an unlikely circumstance, a router SHOULD delay installation of the new primary and alternate next-hops for a destination if the failed link is connected to a primary neighbor and there is a loop-free node-protecting alternate to protect that primary neighbor and that alternate was not a shortest path to D (before the failure). This installation delay SHOULD terminate a. if the new primary next-hop was loop-free prior to the topology change, or b. if a configured hold-down, which represents a worst-case bound on the length of the network convergence transition, has expired, or c. if notification of an unrelated topological change in the network is received. This delay is required only due to the possibility that the U-turn alternate next-hop may have a new primary neighbor that was not loop-free prior to the failure. The loop-free node-protecting alternate of N_i which goes via R_i,j will not be affected by the failure, because it was independent of the affected elements. If N_i's new primary neighbor remains S, then the traffic will continue to be directed towards the appropriate R_i,j. If N_i converges to a path that does not include S to reach D, then traffic received from S for D will be sent along the new path and a micro-forwarding loop is theoretically possible. Atlas Expires April 24, 2005 [Page 21] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 5.2 U-turn Packets Forwarding If a packet is received from a primary neighbor and is successfully identified as a U-turn packet (see Section 2.3), then a router which supports this specification MUST send the packet to the loop-free node-protecting alternate, selected according to the rules in this specification. If, on a U-turn Recipient capable interface, a packet is received from a non-primary neighbor (who during a topology change may still believe that it is a primary neighbor) and the packet is marked to indicate that it is a U-turn packet, then a router which supports this specification MUST send the packet to a primary next-hop. 6. LDP Interactions and Routing Aspects 6.1 LDP Interactions U-turn alternates do not impose any additional sessions or signaling on LDP. LDP can use the u-turn alternates to protect LDP traffic if the requirements specified in [IPFRR] are met. 6.2 Inter-Region Routes As described in [IPFRR], the additional complexity for inheriting alternate next-hops is for inter-region routes in the case of ECMP through different area border routers and with a single primary neighbor. This scenario is illustrated in Figure 7. It can be proven that a U-turn alternate can be inherited to inter-region routes and provide at least the same link or node protection that was provided with respect to the border router. The alternate next-hop inheritance procedure SHOULD select a loop-free node-protecting alternate, if one is available. The use of this for alternate next-hop inheritance applies to OSPF, ISIS and BGP as described in [IPFRR]. Atlas Expires April 24, 2005 [Page 22] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 ............... +--+--+ 15 ......+----------------| ABRt|----------------+ ... | 15 +-----+ | .. | ... | .. 5 +-----+ 15 +--+--+ .. | . +------| A2 +---------| R1 |-----+ . | .. | +-----+ +-----+ 20 | . | . | +-----+ 10 | . | +--------------| ABR2|---------+ | . | | 15 +-----+ | | . +-----+ 5 +---+-+ . | | . | S |-----------| P |------------+ . +-----+ . +-----+ +-----+ 5 | . | D | . | | . +-----+ . | | . | .. | +-----+ +-----+ 20 | . +-----| A1 |------------------| ABR1|------------+ . 10 +-----+ 15 +-----+ ... ... ... ... ...... ..... .............. Figure 7: Inter-Region Destination via Multiple Border Routers with One Primary Neighbor 7. U-turn Alternates Interactions with Tunnels IP Fast-Reroute treats IGP tunnels the same as any other link. If router S is not the endpoint of the tunnel, then the alternate path is computed as normal. If router S is the ingress into the tunnel, then all destinations, which have the tunnel as a primary next-hop, may be protected either via a protection scheme associated with the tunnel or via IP FRR. One issue with MPLS RSVP-TE tunnels is that an LSP may be created where the router uses penultimate-hop popping (PHP). If the topology-base U-turn packet identification method is used, then traffic received via that tunnel is undistinguishable from traffic received over the interface. If some packets received via the LSP are destined back to the penultimate hop, then the egress router would consider that those were U-turn packets and redirect that traffic to its alternate, if available. To avoid such a scenario, a router can simply not request PHP for those LSPs which are entering via an interface upon which the router has advertised that it can break U-Turns. Alternately, a router could use the marking-based U-turn packet identification method. If that is not supported and Atlas Expires April 24, 2005 [Page 23] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 the router must do PHP, then the router can stop advertising the link as U-turn recipient capable. 8. Security Considerations This document does not introduce any new security issues. The mechanisms described in this document depend upon the network topology distributed via an IGP, such as OSPF or ISIS. It is dependent upon the security associated with those protocols. 9. Acknowledgements The authors would like to thank Joel Halpern for his helpful review and comments, particularly as pertains to Section 3. 10. Intellectual Property Considerations Avici Systems has intellectual property rights claimed in regard to the specification contained in this document. 11 References [FRAMEWORK] Shand, M., "IP Fast Reroute Framework", draft-ietf-rtgwg-ipfrr-framework-02.txt (work in progress), October 2004. [IPFRR] Atlas, A., "Basic Specification for IP Fast-Reroute: Loop-free Alternates", draft-ietf-rtgwg-ipfrr-spec-base-01.txt (work in progress), October 2004. [ISIS-LOCAL-PROTECT] Atlas, A., Torvi, R. and C. Martin, "ISIS Extensions for Signaling Local Protection Capabilities", draft-martin-isis-local-protect-cap-01.txt (work in progress), October 2004. [OSPF-LOCAL-PROTECT] Atlas, A., Torvi, R., Choudhury, G., Martin, C., Imhoff, B. and D. Fedyk, "OSPFv2 Extensions for Link Capabilities and IP/LDP Local Protection", draft-atlas-ospf-local-protect-cap-01.txt (work in progress), October 2004. [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and dual environments", RFC 1195, December 1990. Atlas Expires April 24, 2005 [Page 24] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [RFC2370] Coltun, R., "The OSPF Opaque LSA Option", RFC 2370, July 1998. [RFC2966] Li, T., Przygienda, T. and H. Smit, "Domain-wide Prefix Distribution with Two-Level IS-IS", RFC 2966, October 2000. [RFC3036] Andersson, L., Doolan, P., Feldman, N., Fredette, A. and B. Thomas, "LDP Specification", RFC 3036, January 2001. [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A. and D. McPherson, "OSPF Stub Router Advertisement", RFC 3137, June 2001. [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V. and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP Tunnels", RFC 3209, December 2001. [RFC3277] McPherson, D., "Intermediate System to Intermediate System (IS-IS) Transient Blackhole Avoidance", RFC 3277, April 2002. Editor's Address Alia K. Atlas (editor) Avici Systems, Inc. 101 Billerica Avenue N. Billerica, MA 01862 USA Phone: +1 978 964 2070 EMail: aatlas@avici.com Contributing Authors' Addresses Raveendra Torvi Avici Systems 101 Billerica Avenue N. Billerica, MA 01862 USA Phone: +1 978 964 2026 EMail: rtorvi@avici.com Atlas Expires April 24, 2005 [Page 25] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 Gagan Choudhury AT&T Room D5-3C21 200 Laurel Avenue Middletown, NJ 07748 USA EMail: gchoudhury@att.com Phone: +1 732 420-3721 Christian Martin Verizon 1880 Campus Commons Drive Reston, VA 20191 EMail: cmartin@verizon.com Brent Imhoff LightCore 14567 North Outer Forty Rd. Chesterfield, MO 63017 USA EMail: brent@lightcore.net Phone: +1 314 880 1851 Don Fedyk Nortel Networks 600 Technology Park Billerica, MA 01821 EMail: dwfedyk@nortelnetworks.com Phone: +1 978 288 3041 Atlas Expires April 24, 2005 [Page 26] Internet-Draft draft-atlas-ip-local-protect-uturn-01 October 2004 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. Disclaimer of Validity 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. 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. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Atlas Expires April 24, 2005 [Page 27]