draft-ietf-rtgwg-ipfrr-spec-base-00.txt   draft-ietf-rtgwg-ipfrr-spec-base-01.txt 
Internet Draft Alia Atlas, Ed (Avici Systems) Internet Draft Alia Atlas, Ed (Avici Systems)
Expires: March 2005 Expires: March 2005
Loop-Free Alternates for IP/LDP Local Protection Basic Specification for IP Fast-Reroute: Loop-free Alternates
draft-ietf-rtgwg-ipfrr-spec-base-00.txt draft-ietf-rtgwg-ipfrr-spec-base-01.txt
Status of this Memo Status of this Memo
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026. all provisions of Section 10 of RFC2026.
By submitting this Internet-Draft, I certify that any applicable By submitting this Internet-Draft, I certify that any applicable
patent or other IPR claims of which I am aware have been disclosed, patent or other IPR claims of which I am aware have been disclosed,
or will be disclosed, and any of which I become aware will be or will be disclosed, and any of which I become aware will be
disclosed, in accordance with RFC 3668. disclosed, in accordance with RFC 3668.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet- other groups may also distribute working documents as Internet-
Drafts. Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as ``work in progress.'' material or to cite them other than a "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt http://www.ietf.org/1id-abstracts.html
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html"
Abstract Abstract
This document defines an architecture and selection process for This document describes the use of loop-free alternates to provide
providing local protection for IP unicast and/or LDP traffic in the local protection for IP unicast and/or LDP traffic in the event of a
event of a single link or node failure until the router has single link or node failure. When a topology change occurs, a router
converged. When computing the primary next-hop for a prefix, a S determines for each prefix an alternate next-hop which can be used
router S also determines an alternate next-hop which can be used if if the primary next-hop fails. An acceptable alternate next-hop must
the primary next-hop fails. The alternate next-hop is said to be a be a loop-free alternate, which goes to a neighbor whose shortest
loop-free alternate, which goes to a neighbor whose shortest path to path to the prefix does not go back through the router S.
the prefix does not go back through the router S.
Contents Contents
1 Introduction ................................................. 2 1 Introduction ................................................. 2
2 Terminology .................................................. 4 1.1 Failure Scenarios ......................................... 4
3 Finding an Alternate ......................................... 5 2 Alternate Next-Hop Calcuation ................................ 6
3.1 Loop-Free Alternates ....................................... 6 2.1 Basic Loop-Free Condition ................................ 6
3.2 Selection of an Alternate .................................. 7 2.2 Node-Protecting Alternate Next-Hops ..................... 6
3.2.1 Failure Scenarios ........................................ 7 2.3 Broadcast and NBMA Links ................................. 6
3.2.2 Broadcast and NBMA Interfaces ............................ 9 2.4 Interactions wtih ISIS Overload, RFC 3137
3.2.3 Interactions wtih ISIS Overload, RFC 3137 and Costed Out Links ..................................... 7
and Costed Out Links ..................................... 9 2.5 Selection Procedure ...................................... 8
3.2.4 Characterization of Neighbors ............................ 10 3 Using an Alternate ........................................... 9
3.2.5 Selection Procedure ...................................... 10 3.1 Terminating Use of Alternate ............................. 9
4 Using an Alternate ........................................... 11 4 Requirements on LDP Mode ..................................... 11
5 Requirements on LDP Mode ..................................... 11 5 Routing Aspects .............................................. 11
6 Routing Aspects .............................................. 12 5.1 Multiple-Region Routing .................................... 12
6.1 Multiple-Region Routing .................................... 12 5.1.1 Inheriting Alternate Next-Hops with One Primary Neighbor . 14
6.1.1 Inheriting Alternate Next-Hops with One Primary Neighbor . 14 5.1.2 OSPF Inter-Area Routes ................................... 14
6.1.2 OSPF Inter-Area Routes ................................... 15 5.1.3 OSPF Inter-Area Routes ................................... 15
6.1.3 OSPF Inter-Area Routes ................................... 15 5.1.4 ISIS Multi-Level Routing ................................. 15
6.1.4 ISIS Multi-Level Routing ................................. 15 5.2 OSPF Virtual Links ......................................... 15
6.2 OSPF Virtual Links ......................................... 15 5.3 BGP Next-Hop Synchronization ............................... 16
6.3 BGP Next-Hop Synchronization ............................... 16 5.4 Multicast Considerations ................................... 16
6.4 Multicast Considerations ................................... 16 6 Security Considerations ...................................... 16
7 Security Considerations ...................................... 16 7 Full Copyright Statement ..................................... 16
8 Full Copyright Statement ..................................... 17 8 References ................................................... 17
9 References ................................................... 17 9 Authors Information .......................................... 17
10 Authors Information .......................................... 18 10 Editor's Information ......................................... 18
11 Editor's Information ......................................... 19
Appendix A Loop-Free Alternate Proofs .......................... 19
Appendix A.1 Loop-Free Node-Protecting Alternate Proofs ........ 21
1. Introduction 1. Introduction
Applications for interactive multimedia services such as VoIP and Applications for interactive multimedia services such as VoIP and
pseudo-wires can be very sensitive to traffic loss, such as occurs pseudo-wires can be very sensitive to traffic loss, such as occurs
when a link or router in the network fails. A router's convergence when a link or router in the network fails. A router's convergence
time is generally on the order of seconds; the application traffic time is generally on the order of seconds; the application traffic
may be sensitive to losses greater than 10s of milliseconds. may be sensitive to losses greater than 10s of milliseconds.
As discussed in [FRAMEWORK], minimizing traffic loss requires a As discussed in [FRAMEWORK], minimizing traffic loss requires a
mechanism for the router adjacent to a failure rapidly invoke a mechanism for the router adjacent to a failure rapidly invoke a
repair path, which is minimally affected by any subsequent re- repair path, which is minimally affected by any subsequent re-
convergence. This document describes such a mechanism which allows a convergence. This specification describes such a mechanism which
router whose local link has failed to forward traffic to a pre- allows a router whose local link has failed to forward traffic to a
computed alternate until the router installs the new primary next- pre-computed alternate until the router installs the new primary
hops based upon the changed network topology. next-hops based upon the changed network topology. The terminology
used in this specification is given in [FRAMEWORK].
When a local link fails, a router currently must signal the event to When a local link fails, a router currently must signal the event to
its neighbors via the IGP, recompute new primary next-hops for all its neighbors via the IGP, recompute new primary next-hops for all
affected prefixes, and only then install those new primary next-hops affected prefixes, and only then install those new primary next-hops
into the forwarding plane. Until the new primary next-hops are into the forwarding plane. Until the new primary next-hops are
installed, traffic directed towards the affected prefixes is installed, traffic directed towards the affected prefixes is
discarded. This process can take seconds. discarded. This process can take seconds.
/__ <--
\ +-----+ +-----+
/------| S |--\ /------| S |--\
/ +-----+ \ / +-----+ \
/ 5 8 \ / 5 8 \
/ \ / \
+-----+ +-----+ +-----+ +-----+
| P | | N_1 | | E | | N_1 |
+-----+ +-----+ +-----+ +-----+
\ / \ /
\ \ 4 3 / / \ \ 4 3 / /
\| \ / |/ \| \ / |/
-+ \ +-----+ / +- -+ \ +-----+ / +-
\---| D |---/ \---| D |---/
+-----+ +-----+
Figure 1: Basic Topology Figure 1: Basic Topology
The goal of IP/LDP Local Protection is to reduce that traffic The goal of IP Fast-Reroute is to reduce that traffic convergence
convergence time to 10s of milliseconds by using a pre-computed time to 10s of milliseconds by using a pre-computed alternate next-
alternate interface, in the event that the currently selected primary hop, in the event that the currently selected primary next-hop fails,
interface fails, so that the alternate can be rapidly used when the so that the alternate can be rapidly used when the failure is
failure is detected. detected.
To clarify the behavior of IP/LDP Local Protection, consider the To clarify the behavior of IP Fast-Reroute, consider the simple
simple topology in Figure 1. When router S computes its shortest topology in Figure 1. When router S computes its shortest path to
path to router D, router S determines to use the interface to router router D, router S determines to use the link to router E as its
P as its primary next-hop. Without IP/LDP Local Protection, that primary next-hop. Without IP Fast-Reroute, that link is the only
interface is the only next-hop that router S computes to reach D. next-hop that router S computes to reach D. With IP Fast-Reroute, S
With IP/LDP Local Protection, S also looks for an alternate next-hop also looks for an alternate next-hop to use. In this example, S
interface to use. In this example, S would determine that it could would determine that it could send traffic destined to D by using the
send traffic destined to D by using the interface to router N_1 and link to router N_1 and therefore S would install the link to N_1 as
therefore S would install the interface to N_1 as its alternate its alternate next-hop. At some later time, the link between router
next-hop. At some later time, the link between router S and router P S and router E could fail. When that link fails, S and E will be the
could fail. When that link fails, S (and most likely P) will be the
first to detect it. On detecting the failure, S will stop sending first to detect it. On detecting the failure, S will stop sending
traffic destined for D towards P via the failed link, and instead traffic destined for D towards E via the failed link, and instead
send the traffic to S's pre-computed alternate next-hop, which is the send the traffic to S's pre-computed alternate next-hop, which is the
interface to N_1, until a new SPF is run and its results are link to N_1, until a new SPF is run and its results are installed.
installed. As with the primary next-hop, an alternate next-hop is As with the primary next-hop, an alternate next-hop is computed for
computed for each destination. The process of computing an alternate each destination. The process of computing an alternate next-hop
next-hop does not alter the primary next-hop computed via a standard does not alter the primary next-hop computed via a standard SPF.
SPF. The alternate next-hop can protect against a single link or
node failure.
If in the example of Figure 1, the link cost from N_1 to D increased If in the example of Figure 1, the link cost from N_1 to D increased
to 30 from 3, then N_1 would not be a loop-free alternate, because to 30 from 3, then N_1 would not be a loop-free alternate, because
the cost of the path from N_1 to D via S would be 17 while the cost the cost of the path from N_1 to D via S would be 17 while the cost
from N_1 directly to D would be 30. In real networks, we may often from N_1 directly to D would be 30. In real networks, we may often
face this situation. The existence of a suitable loop-free alternate face this situation. The existence of a suitable loop-free alternate
next-hop is topology dependent. next-hop is topology dependent.
2. Terminology A neighbor N can provide a loop-free alternate if and only if
SPT --- Shortest Path Tree
D --- The destination router under discussion.
S --- The source router under discussion. It is the viewpoint from
which IP/LDP Local Protection is described.
P --- The router which is the primary next-hop neighbor to get from S
to D. Where there is an ECMP set for the shortest path from S
to D, these will be referred to as P_1, P_2, etc.
N_i --- The ith neighbor of S
R_i_j --- The jth neighbor of N_i, the ith neighbor of S.
Distance_!S(N_i, D) --- The distance of the shortest path from N_i to
D which does not go through router S.
Distance_opt(A, B) --- The distance of the shortest path from A to B.
Reverse Distance of a node X --- This is the Distance_opt(X, S).
Loop-Free Alternate --- This is a next-hop that is not a primary
next-hop whose shortest path to the destination from the
alternate neighbor does not go back through the router S.
This is also known as a downstream path or a feasible
alternate.
Downstream Path --- This is a loop-free alternate.
Link(A->B) --- A link connecting router A to router B.
____\ This is an arrow indicating the primary next-hop towards D.
/
@@@@\ This is an arrow indicating the alternate next-hop towards D
/
Primary Neighbor --- One or more of the primary next-hops for S to
reach the destination D goes directly to this neighbor.
Loop-Free Neighbor --- A Neighbor N_i which is not the primary
neighbor and whose shortest path to D does not go through S.
Loop-Free Node-Protecting Alternate --- This is a path via a Loop-
Free Neighbor N_i which does not go through the particular
primary neighbor of S which is being protected to reach the
destination D.
Loop-Free Link-Protecting Alternate --- This is a path via a Loop-
Free Neighbor N_i which does go through the particular primary
neighbor of S which is being protected to reach the destination
D.
Upstream Forwarding Loop --- This is a forwarding loop which involves
a set of routers, none of which are directly connected to the
link which has caused the topology change that triggered a new
SPF in any of the routers.
3. Finding an Alternate
As with primary next-hops, an alternate next-hop is discussed in
relation to a particular destination router D. For this discussion,
the following terminology, as described earlier and illustrated in
Figure 2, will be used.
In IP routing, a router S can join the shortest path tree (SPT) at
exactly one point -- itself. A loop-free alternate next-hop allows
traffic from S to D to deviate from the SPT and then rejoin it. For
instance, if S were to send traffic destined for D to N_1 instead of
P, thereby deviating from the SPT, then when N_1 received it, N_1
would send that traffic along its shortest path to D.
+-----+
\ / _| R_2 |
+-----+__ \| |/ / +-----+
| N_3 | \ -+ +- __/ \
+-----+ \____ / \
\ \ / \
\ +-----+ \
\ _| N_2 | \
| __/ +-----+ \
\ / \ |
\ / / \_ |
+-----+ |/ \ |
| S | +- \ +-----+ |
+-----+ \_| R_1 | |
/ / \ +-----+ |
|/ / \ / |
+- / \ / |
/ +-----+ / / |
+-----+/ | N_1 | / |/ |
| P | +-----+ / +- |
+-----+ \ / /
\ \ \__ / /
\ \ \| \ / /
\| \ -+ +-----+ /
-+ \_________________| D |---------/
+-----+
Figure 2: Topology for Terminology
3.1. Loop-Free Alternates
With loop-free alternates, the goal is to expand the set of points at
which S can cause its traffic to join the SPT. To illustrate this
let's first consider S's neighbors. Router S has the ability to send
traffic to any one of its neighbors N_i; this is the easiest possible
deviation from the SPT that S can cause to happen. Thus, all of
router S's neighbors are candidate alternates at which S could cause
traffic to rejoin the SPT. However, it is not useful for router S to
use a next-hop which results in traffic rejoining the SPT upstream of
S, such that the traffic will transit S again. This would cause a
loop. Avoiding a loop is thus the first constraint imposed on the
alternate next-hop. In Figure 2, S's neighbors N_2 and N_3 are not
loop-free alternate neighbors.
A next-hop which goes to a neighbor that does not have a loop back to
S and is not the primary next-hop may be selected as an alternate
next-hop. In Figure 2, that is the case for S's neighbor N_1. N_1
is referred to as a loop-free alternate with respect to traffic
flowing from S to D because there is no loop caused by forwarding
traffic for D to N_1.
An algorithm run on router S must be able to determine which Distance_opt(N, D) < Distance_opt(N, S) + Distance_opt(S, D)
neighbors provide loop-free alternates. By running an SPF
computation from S's perspective, router S can determine the distance
from a neighbor N_i to the destination D for the optimal path that
does not go through S. This is referred to as Distance_!S(N_i, D).
If a neighbor N_i is a loop-free alternate, then it must be cheaper
(a lower metric) to get to the destination D without returning to S.
This gives the following requirement, where Distance_opt(A, B) gives
the distance of the optimal path from A to B.
Distance_!S(N_i, D) < Distance_opt(N_i, S) + Distance_opt(S, D) Equation 1: Loop-Free Criterion
Equation 1: Criteria for a Loop-Free Alternate A sub-set of loop-free alternate are downstream paths which must meet
the more restrictive condition of
To check this equation, we can consider the other conditions where Distance_opt(N, D) < Distance_opt(S, D)
this is not true. Recall that a router will take the shortest path
to a destination that it can see. Thus, if Distance_!S(N_i, D) >
Distance_opt(N_i, S) + Distance_opt(S, D), then router N_i will,
based on its own shortest path computations, determine to send
traffic destined for D to S. Similarly, if Distance_!S(N_i, D) =
Distance_opt(N_i, S) + Distance_opt(S, D), then router N_i has equal
cost paths to the destination D where one or more of those paths go
through S. In such a case where a router N_i has an ECMP set to
reach the destination and one or more paths go through S, then the
router N_i cannot provide a loop-free alternate because some traffic
destined to D may be sent back to S by N_i.
3.2. Selection of an Alternate Equation 2: Downstream Path Criterion
The selection of the alternate to use depends upon the failure 1.1 Failure Scenarios
scenario for which the protection is intended. As with other
protection mechanisms, the alternate selected will protect against
only a single failure. It is possible to protect against a node
failure, which appears as correlated link failures, by explicitly
selecting a loop-free alternate which does not use that node.
3.2.1 Failure Scenarios The alternate next-hop can protect against a single link failure, a
single node failure, or both.
The simplest case is to locate an alternate which protects against a If only link protection is provided and the node fails, it is
link failure. possible for traffic using the alternates to loop. This issue is
illustrated in Figure 2. If Link(S->E) fails, then the link-
protecting alternate via N will work correctly. However, if router E
fails, then both S and N will detect a failure and switch to their
alternates. In this example, that would cause S to redirect the
traffic to N and N to redirect the traffic to S and thus causing a
forwarding loop. Such a scenario can arise because the key
assumption, that all other routers in the network are forwarding
based upon the shortest path, is violated because of a second
simultaneous correlated failure - another link connected to the same
primary neighbor.
A loop-free link-protecting alternate may cause traffic looping in Such a scenario may be a concern if node failure is not otherwise
the event of a node failure. This issue is illustrated in Figure 3. protected against. Selection of only downstream paths as alternates
If Link(S->P) fails, then the link-protecting alternate via N will will ensure this does not occur, but such a restriction can severely
work correctly. However, if router P fails, then both S and N will limit the coverage of alternates.
detect a failure and switch to their alternates. In this example,
that would cause S to redirect the traffic to N and N to redirect the
traffic to S and thus causing a forwarding loop. Such a scenario can
arise because the key assumption, that all other routers in the
network are forwarding based upon the shortest path, is violated
because of a second simultaneous correlated failure - another link
connected to the same primary neighbor.
/ <@@@
\ @@@ @@@>
@@@ \ +-----+ +-----+
+-----+ / +-----+
| S |-------| N | | S |-------| N |
+-+---+ 5 +-----+ +-+---+ 5 +-----+
| | | |
| 5 5 | | | 5 5 | |
| | | \|/ | | | \|/
\|/ | | \|/ | |
| +-----+ | | +-----+ |
+----| P |---+ +----| E |---+
+--+--+ +--+--+
| |
| |
| 10 | 10
| |
+--+--+ +--+--+
| D | | D |
+-----+ +-----+
Figure 3: Link-Protecting Alternates Causing Loop on Node Failure
Such a scenario may be a concern if node failure is not otherwise
protected against.
One way to solve such an issue is to add a constraint that the loop-
free alternate is loop-free with respect to P and the destination.
This gives a loop-free node-protecting alternate. An alternate will
be node-protecting if it doesn't go through the same primary neighbor
as the primary next-hop. This is the case if Equation 2 is true,
where N is the neighbor providing a loop-free alternate.
Distance_opt(N, D) < Distance_opt(N, P) + Distance_opt(P, D) Figure 2: Link-Protecting Alternates Causing Loop on Node Failure
However unlike Equation 1, where if the equation did not hold, the neighbor
wasn't loop-free, if Equation 2 does not hold, the neighbor may still
provide a loop-free alternate that is not node-protecting. In the
case of ECMP, the neighbor may even provide a node-protecting loop-
free alternate, but S cannot determine this.
It may also be desirable to find an alternate which can protect It may be desirable to find an alternate which can protect against
against other correlated failures. In the general case, these are other correlated failures (of which node failure is a specific
handled by shared risk link groups (SRLGs) where any links in the instance). In the general case, these are handled by shared risk
network can belong to the SRLG. General SRLGs may add unacceptably link groups (SRLGs) where any links in the network can belong to the
to the computational complexity of finding a loop-free alternate. SRLG. General SRLGs may add unacceptably to the computational
complexity of finding a loop-free alternate.
However, a sub-category of SRLGs is of interest and can be applied However, a sub-category of SRLGs is of interest and can be applied
only during the selection of an acceptable alternate. This sub- only during the selection of an acceptable alternate. This sub-
category is to express correlated failures of links which are category is to express correlated failures of links which are
connected to the same router. For example, if there are multiple connected to the same router. For example, if there are multiple
logical sub-interfaces on the same physical interface, such as VLANs logical sub-interfaces on the same physical interface, such as VLANs
on an Ethernet interface, if multiple interfaces use the same on an Ethernet interface, if multiple interfaces use the same
physical port because of channelization, or if multiple interfaces physical port because of channelization, or if multiple interfaces
share a correlated failure because they are on the same line-card. share a correlated failure because they are on the same line-card.
This sub-category of SRLGs will be referred to as local-SRLGs. A This sub-category of SRLGs will be referred to as local-SRLGs. A
local-SRLG has all of its member links with one end connected to the local-SRLG has all of its member links with one end connected to the
same router. Thus, router S could select a loop-free alternate which same router. Thus, router S could select a loop-free alternate which
does not use a link in the same local-SRLG as the primary next-hop. does not use a link in the same local-SRLG as the primary next-hop.
The local-SRLGs belonging to P can be protected against via node- The local-SRLGs belonging to E can be protected against via node-
protection; i.e. picking a loop-free node-protecting alternate. protection; i.e. picking a loop-free node-protecting alternate.
3.2.2 Broadcast and NBMA Interfaces 2. Alternate Next-Hop Calculation
The computation for node-protection and link-protection is a bit more To support IP Fast-Reroute, a router must be able to determine if a
complicated for broadcast interfaces. In an SPF computation, a next-hop will provide a loop-free alternate before the router
broadcast interface is represented as a pseudo-node with links of 0 installs that next-hop as an alternate. That next-hop must go to a
cost exiting the pseudo-node. For an alternate to be considered loop-free neighbor.
link-protecting, it must avoid the pseudo-node. Thus, a potential
alternate which doesn't avoid the next node on the primary path
cannot be used as an alternate if the next node on the path is a
pseudo-node because the potential alternate would use the link that
may fail. Additionally, an alternate which would normally be termed
node-protecting because it avoided the next node on the primary path
may be only link-protecting. If the alternate avoids the pseudo-node
but goes through the next node on the path (i.e. the real neighbor of
S), then the alternate is link-protecting; if the alternate avoids
not only the pseudo-node but the following node on the primary path,
then the alternate is node-protecting.
3.2.3 Interactions with ISIS Overload, RFC 3137 and Costed Out Links To do this computation, a router could run an SPF from the
perspective of each of its neighbors as well as from its own
perspective. This provides the router with all the information
necessary to test the equations given is this specification.
2.1 Basic Loop-free Condition
Alternate next hops used by implementations following this
specification MUST conform to at least the loop-freeness condition
stated above in Equation 1. Further conditions may be applied when
determining link-protecting and/or node-protecting alternate next-
hops as described in Sections 2.2 and 2.3.
2.2 Node-Protecting Alternate Next-Hops
For an alternate next-hop to protect against node failure, the
alternate next-hop MUST be loop-free with respect to the primary
neighbor E and the destination.
An alternate will be node-protecting if it doesn't go through the
same primary neighbor as the primary next-hop. This is the case if
Equation 3 is true, where N is the neighbor providing a loop-free
alternate.
Distance_opt(N, D) < Distance_opt(N, E) + Distance_opt(E, D)
Equation 3: Criteria for a Node-Protecting Loop-Free Alternate
If Distance_opt(N,D) = Distance_opt(N, E) + Distance_opt(E, D), it is
possible that the neighbor may have equal-cost paths and one of those
could provide a loop-free node-protecting alternate. However, the
decision as to which of equal-cost paths a router will use is a
router-local decision. Therefore, a router MUST assume that an
alternate next-hop does not offer node protection if Equation 3 is
not met.
2.3 Broadcast and NBMA Links
The computation for link-protection is a bit more complicated for
broadcast links. In an SPF computation, a broadcast links is
represented as a pseudo-node with links of 0 cost exiting the
pseudo-node. For an alternate to be considered link-protecting, it
must be loop-free with regard to the pseudo-node. Consider the
example in Figure 3.
+-----+ 15
| S |-------
+-----+ |
| 5 |
/----\ 5 +-----+
| PN |----| N |
\----/ +-----+
| |
| 5 | 2
| |
+-----+ 5 +-----+
| E |----| D |
+-----+ +-----+
Figure 3: Loop-Free Alternate that isn't Link-Protecting
In Figure 3, N offers a loop-free alternate which is link-protecting.
If the primary next-hop uses a broadcast link, then an alternate must
be loop-free with respect to that link's pseudo-node to provide link
protection. This requirement is described in Equation 4 below.
Distance_opt(N, D) < Distance_opt(N, pseudo) + Distance_opt(pseudo, D)
Equation 4: Loop-Free Link-Protecting Criterion for Broadcast Links
Because the shortest path from the pseudo-node goes through E, if a
loop-free alternate from a neighbor N is node-protecting, the
alternate will also be link-protecting unless the router S can only
reach the neighbor N via the same pseudo-node. This can occur
because S will direct traffic away from the shortest path to use an
alternate.
2.4 Interactions with ISIS Overload, RFC 3137 and Costed Out Links
As described in RFC 3137, there are cases where it is desirable not As described in RFC 3137, there are cases where it is desirable not
to have a router used as a transit node. For those cases, it is also to have a router used as a transit node. For those cases, it is also
desirable not to have the router used on an alternate path. desirable not to have the router used on an alternate path.
For computing an alternate, a router MUST not consider diverting from For computing an alternate, a router MUST not consider diverting from
the SPF tree along a link whose reverse cost is LSInfinity (for OSPF) the SPF tree along a link whose reverse cost is LSInfinity (for OSPF)
or whose router has the overload bit set (for ISIS). or whose router has the overload bit set (for ISIS).
In the case of OSPF, if all links from router S to a neighbor N_i In the case of OSPF, if all links from router S to a neighbor N_i
have a reverse cost of LSInfinity, then router S cannot consider have a reverse cost of LSInfinity, then router S MUST NOT consider
using N_i as an alternate. using N_i as an alternate.
Similarly in the case of ISIS, if N_i has the overload bit set, then Similarly in the case of ISIS, if N_i has the overload bit set, then
S cannot consider using N_i as an alternate. S MUST NOT consider using N_i as an alternate.
This preserves the desired behavior of diverting traffic away from a This preserves the desired behavior of diverting traffic away from a
router which is following RFC 3137 and it also preserves the desired router which is following RFC 3137 and it also preserves the desired
behavior when an operator sets the cost of a link to LSInfinity for behavior when an operator sets the cost of a link to LSInfinity for
maintenance, of not permitting traffic across that link unless there maintenance which is not permitting traffic across that link unless
is no other path. there is no other path.
If a link or router which is costed out was the only possible If a link or router which is costed out was the only possible
alternate to protect traffic from a particular router S to a alternate to protect traffic from a particular router S to a
particular destination, then there will be no alternate provided for particular destination, then there will be no alternate provided for
protection. protection.
3.2.4 Characterization of Neighbors 2.5 Selection Procedure
Each neighbor N_i can be categorized as to the type of path it can
provide to a particular destination D. Once the primary paths paths
have been determined and removed from consideration, each neighbor
can be characterized as providing a path in one of the following
categories for a particular destination D. It is possible for a
neighbor to provide both the primary path and a loop-free link-
protecting alternate. The path through the neighbor N_i is either a:
Loop-Free Node-Protecting Alternate - not a primary path and the
path avoids both S, one of S's primary neighbors on the path to
D and the interface connecting S to that primary neighbor.
Loop-Free Link-Protecting Alternate - not a primary path and the
path avoids S and an interface connecting S to one of S's
primary neighbors, but goes through that primary neighbor on the
path to D. Note that some neighbors of this type may have ECMP
paths to reach the destination, where some of those paths are
independent of the primary neighbor.
Unavailable - because the path goes through S to reach D,
because the interface to reach the neighbor is costed out, etc.
3.2.5 Selection Procedure A router supporting this specification SHOULD select a loop-free
alternate next-hop for each primary next-hop used for a given prefix.
A router MAY decide to not use an available loop-free alternate
next-hop. A reason for such a decision might be that the loop-free
alternate next-hop does not provide protection for the failure
scenario of interest.
Once the neighbors have been categorized, a selection can be made.
The selection should maximize the failure cases which can be The selection should maximize the failure cases which can be
protected against. protected against.
The selection procedure depends on whether S has a single primary The selection procedure depends on whether S has a single primary
neighbor or multiple primary neighbors. A node S is defined to have 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 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 go through any other neighbor; i.e., a node S cannot be considered to
have a single primary neighbor just because S does not support ECMP. have a single primary neighbor simply because S does not support
ECMP.
If S has a single primary neighbor, then S SHOULD select a loop-free If S has a single primary neighbor, then S SHOULD select a loop-free
node-protecting alternate, if one is available. If none is node-protecting alternate next-hop, if one is available. If S has a
available, then S MAY select a loop-free link-protecting alternate. choice between a loop-free link-protecting node-protecting alternate
and a loop-free node-protecting alternate which is not link-
protecting, S SHOULD select a loop-free node-protecting alternate
which is also link-protecting. This can occur as explained in
Section 2.3. If no loop-free node-protecting alternate is available,
then S MAY select a loop-free link-protecting alternate.
If S has multiple primary neighbors, then S should select an If S has multiple primary neighbors, then S SHOULD select as a loop-
alternate to protect against the failure of each of the primary free alternate either one of the other primary next-hops or a loop-
next-hops. The loop-free alternate selected should be either one of free node-protecting alternate. S MAY select a loop-free link-
the other primary next-hops or should provide node-protection. protecting alternate.
4. Using an Alternate Each next-hop can be categorized as to the type of alternate it can
provide to a particular destination D from router S for a particular
primary next-hop which goes to a neighbor E. A next-hop may provide
one of the following types of paths:
If an alternate is available, it is used to redirect traffic when the Primary Path - This is the primary next-hop.
primary next-hop has failed.
Loop-Free Node-Protecting Alternate - This next-hop satisfies
Equations 1 and 3. The path avoids S, S's primary neighbor E,
and the link from S to E.
Loop-Free Link-Protecting Alternate - This next-hop satisfies
Equation 1 but not Equation 3. If the primary next-hop uses a
broadcast link, then this next-hop satisfies Equation 4.
Unavailable - This may be because the path goes through S to
reach D, because the link is costed out, etc.
3. Using an Alternate
If an alternate next-hop is available, the router SHOULD redirect
traffic to the alternate next-hop when the primary next-hop has
failed.
When a local interface failure is detected, traffic that was destined When a local interface failure is detected, traffic that was destined
to go out the failed interface must be redirected to the appropriate to go out the failed interface must be redirected to the appropriate
alternate next-hops. The alternate next-hop is pre-computed to be alternate next-hops. Other failure detection mechanisms which detect
the most appropriate as mentioned in the selection criteria in the the loss of a link or a node may also be used to trigger redirection
event of the failure scenario being protected against (i.e. link or of traffic to the appropriate alternate next-hops. The mechanisms
node failure). available for failure detection are discussed in [FRAMEWORK] and are
outside the scope of this specification.
IP/LDP Local Protection does not require any mechanisms for the The alternate next-hop MUST be used only for traffic types which are
detection of the failure. The same mechanisms that enable RSVP-TE routed according to the shortest path. Multicast traffic is
Fast-Reroute can work here. Because the alternate next-hop is pre- specifically out of scope for this specification.
computed, it should be extremely fast to switch traffic to use it,
exactly as is the case with RSVP-TE Fast-Reroute.
5. Requirements on LDP Mode 3.1 Terminating Use of Alternate
A router MUST limit the amount of time an alternate next-hop is used
after the primary next-hop has become unavailable. This ensures that
the router will start using the new primary next-hops. It ensures
that all possible transient conditions are remvoed and the network
converges according to the deployed routing protocol.
It is desirable to avoid micro-forwarding loops involving S. An
example illustrating the problem is given in Figure 4. If the link
from S to E fails, S will use N1 as an alternate and S will compute
N2 as the new primary next-hop to reach D. If S starts using N2 as
soon as S can compute and install its new primary, it is probable
that N2 will not have yet installed its new primary next-hop. This
would cause traffic to loop and be dropped until N2 has installed the
new topology. This can be avoided by S delaying its installation and
leaving traffic on the alternate next-hop.
+-----+
| N2 |-------- |
+-----+ 1 | \|/
| |
| +-----+ @@> +-----+
| | S |---------| N1 |
10 | +-----+ 10 +-----+
| | |
| 1 | | |
| | \|/ 10 |
| +-----+ | |
| | E | | \|/
| +-----+ |
| | |
| 1 | | |
| | \|/ |
| +-----+ |
|----| D |--------------
+-----+
Figure 4: Example where Continued Use of Alternate is Desirable
This is an example of a case where the new primary is not a loop-free
alternate before the failure and therefore may have been forwarding
traffic through S. This will occur when the path via a previously
upstream node is shorter than the the path via a loop-free alternate
neighbor. In these cases, it is useful to give sufficient time to
ensure that the new primary neighbor and other nodes on the new
primary path have switched to the new route.
If the newly selected primary was loop-free before the failure, then
it is safe to switch to that new primary immediately; the new
primary wasn't dependent on the failure and therefore its path will
not have changed.
Given that there is an alternate providing appropriate protection and
while the assumption of a single failure holds, it is safe to delay
the installation of the new primaries; this will not create
forwarding loops because the alternate's path to the destination is
known to not go via S or the failed element and will therefore not be
affected by the failure.
An implementation SHOULD continue to use the alternate next-hops for
packet forwarding even after the new routing information is available
based on the new network topology. The use of the alternate next-
hops for packet forwarding 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.
4. Requirements on LDP Mode
Since LDP traffic will follow the path specified by the IGP, it is Since LDP traffic will follow the path specified by the IGP, it is
also possible for the LDP traffic to follow the loop-free alternates also possible for the LDP traffic to follow the loop-free alternates
indicated by the IGP. To do so, it is necessary for LDP to have the indicated by the IGP. To do so, it is necessary for LDP to have the
appropriate labels available for the alternate so that the appropriate labels available for the alternate so that the
appropriate out-segments can be installed in the forwarding plane appropriate out-segments can be installed in the forwarding plane
before the failure occurs. before the failure occurs.
This means that a Label Switched Router (LSR) running LDP must This means that a Label Switched Router (LSR) running LDP must
distribute its labels for the FECs it can provide to all its distribute its labels for the FECs it can provide to all its
neighbors, regardless of whether or not they are upstream. neighbors, regardless of whether or not they are upstream.
Additionally, LDP must be acting in liberal label retention mode so Additionally, LDP must be acting in liberal label retention mode so
that the labels which correspond to interfaces that aren't currently that the labels which correspond to neighbors that aren't currently
the primary next-hop are stored. Similarly, LDP should be in the primary neighbor are stored. Similarly, LDP should be in
downstream unsolicited mode, so that the labels for the FEC are downstream unsolicited mode, so that the labels for the FEC are
distributed other than along the SPT. distributed other than along the SPT.
If these requirements are met, then LDP can use the loop-free If these requirements are met, then LDP can use the loop-free
alternates without requiring any targeted sessions or signaling alternates without requiring any targeted sessions or signaling
extensions for this purpose. extensions for this purpose.
6. Routing Aspects 5. Routing Aspects
An SPF-like computation is run for each topology, which corresponds An SPF-like computation is run for each topology, which corresponds
to a particular OSPF area or ISIS level. The IGP needs to determine to a particular OSPF area or ISIS level. The IGP needs to determine
the inheritance of loop-free alternates, as determined for singly the inheritance of loop-free alternates, as determined for singly
advertised routes, to multiply advertised routes, for protocols such advertised routes, to multiply advertised routes, for protocols such
as BGP and LDP and for inter-area or inter-level routes. These as BGP and LDP and for inter-area or inter-level routes. These
alternates are provided to LDP and BGP for forwarding purposes only; alternates are provided to LDP and BGP for forwarding purposes only;
the alternates are not redistributed in any fashion into other the alternates are not redistributed in any fashion into other
protocols. protocols.
The alternate next-hop inheritance is described in the context of The alternate next-hop inheritance is described in the context of
inter-area routes, but applies equally well to BGP routes and to inter-area routes, but applies equally well to BGP routes and to
routes which are advertised by multiple routers in the IGP area. routes which are advertised by multiple routers in the IGP area.
6.1 Multiple-Region Routing 5.1 Multiple-Region Routing
Routes in different regions inherit their primary next-hops from the Routes in different regions inherit their primary next-hops from the
border routers (area border routers (ABRs) or level boundary routers) border routers (area border routers (ABRs) or level boundary routers)
which offer the shortest path to the destination(s) announcing the which offer the shortest path to the destination(s) announcing the
route. Similarly, routes must inherit their alternate next-hop and route. Similarly, routes must inherit their alternate next-hop and
will do so from the same border routers. The shortest path to an will do so from the same border routers. The shortest path to an
inter-region route may be learned from a single border router. In inter-region route may be learned from a single border router. In
that case, both the primary and the alternate next-hops can be that case, both the primary and the alternate next-hops can be
inherited from that border router. Figure 4 illustrates this case inherited from that border router. Figure 5 illustrates this case
where D is reached via ABR1; the primary next-hop for ABR1 is P and where D is reached via ABR1; the primary next-hop for ABR1 is E and
the loop-free node-protecting alternate is A1. the loop-free node-protecting alternate is A1.
The shortest path to an inter-region route may be learned from
multiple border routers with at least 2 different primary neighbors,
as is illustrated in Figure 5. D is reached via ABR1 and ABR2 with
equal cost from S. The primary neighbor to reach ABR1 is P1 and the
alternate is A1. The primary neighbor to reach ABR2 is P2 and the
alternate is A2. In this case, there are equal-cost primary next-
hops to reach D and they can protect each other. In this example,
the primary next-hops would be to P1 and P2; if the link to P2
failed, then P1 could be used as an alternate and vice-versa. Thus
the alternates can be obtained from the primary next-hops.
............. .............
...... ...... ...... ......
... ... ... ...
.. .. .. ..
.. 10 +-----+ 5 +-----+ 5 .. .. 10 +-----+ 5 +-----+ 5 ..
. +------| A1 +---------| R1 |-----+ . . +------| A1 +---------| R1 |-----+ .
.. | +-----+ +-----+ | . .. | +-----+ +-----+ | .
. | +-----+ 10 . | +-----+ 10
. | +--------------| ABR1|---------+ . | +--------------| ABR1|---------+
. | | 5 +-----+ | . | | 5 +-----+ |
. +-----+ 5 +---+-+ . | . +-----+ 5 +---+-+ . |
. | S |-----------| P |------------+ . +-----+ . | S |-----------| E |------------+ . +-----+
. +-----+ +-----+ 10 | . | D | . +-----+ +-----+ 10 | . | D |
. | | . +-----+ . | | . +-----+
. | | . | . | | . |
.. | +-----+ +-----+ 20 | .. | +-----+ +-----+ 20 |
. +-----| A2 |------------------| ABR2|------------+ . +-----| A2 |------------------| ABR2|------------+
. 10 +-----+ 5 +-----+ . 10 +-----+ 5 +-----+
... ... ... ...
... ... ... ...
...... ...... .........................
.............
Figure 4: Inter-Region Destination via One Border Router Figure 5: Inter-Region Destination via One Border Router
The shortest path to an inter-region route may be learned from
multiple border routers with at least 2 different primary neighbors,
as is illustrated in Figure 6. D is reached via ABR1 and ABR2 with
equal cost from S. The primary neighbor to reach ABR1 is E1 and the
alternate is A1. The primary neighbor to reach ABR2 is E2 and the
alternate is A2. In this case, there are equal-cost primary next-
hops to reach D and they can protect each other. In this example,
the primary next-hops would be to E1 and E2; if the link to E2
failed, then E1 could be used as an alternate and vice-versa. Thus
the alternates can be obtained from the primary next-hops.
.......... ..........
...... ...... ...... ......
... ... ... ...
.. .. .. ..
.. 10 +-----+ 5 +-----+ .. .. 10 +-----+ 5 +-----+ ..
. +------| A1 +---------| R1 |-----+ . +------| A1 +---------| R1 |-----+
.. | +-----+ +-----+ |. .. | +-----+ +-----+ |.
. | +-----+ +-----+ 10 . | +-----+ +-----+ 10
. | +-----------| P1 |------------| ABR1|---------+ . | +-----------| E1 |------------| ABR1|---------+
. | | 5 +-----+ 5 +-----+ | . | | 5 +-----+ 5 +-----+ |
. +-----+ . | . +-----+ . |
. | S |---+ 5 +-----+ 10 . +-----+ . | S |---+ 5 +-----+ 10 . +-----+
. +-----+ +-------| P2 |------------+ . | D | . +-----+ +-------| E2 |------------+ . | D |
. | +-----+ | . +-----+ . | +-----+ | . +-----+
. | | . | . | | . |
.. | +-----+ +-----+ 20 | .. | +-----+ +-----+ 20 |
. +-----| A2 |------------------| ABR2|------------+ . +-----| A2 |------------------| ABR2|------------+
. 10 +-----+ 5 +-----+ . 10 +-----+ 5 +-----+
... ... ... ...
... ... ... ...
...... ...... ...... ......
.......... ..........
Figure 5: Inter-Region Destination via Figure 6: Inter-Region Destination via
Multiple Border Routers and Multiple Primary Neighbors Multiple Border Routers and Multiple Primary Neighbors
In the third case, the shortest path to an inter-region route In the third case, the shortest path to an inter-region route
may be learned from multiple border routers but with a single may be learned from multiple border routers but with a single
primary neighbor. This is shown in Figure 6, where D can be primary neighbor. This is shown in Figure 7, where D can be
equally reached from S via ABR1 and ABR2. The alternate next- equally reached from S via ABR1 and ABR2. The alternate next-
hop to reach ABR1 is A1 while the alternate to reach ABR2 is A2. hop to reach ABR1 is A1 while the alternate to reach ABR2 is A2.
It is necessary to select one of the alternates to be inherited. It is necessary to select one of the alternates to be inherited.
............. .............
...... ...... ...... ......
... ... ... ...
.. .. .. ..
.. 5 +-----+ 15 +-----+ 20 .. .. 5 +-----+ 15 +-----+ 20 ..
. +------| A1 +---------| R1 |-----+ . . +------| A1 +---------| R1 |-----+ .
.. | +-----+ +-----+ | . .. | +-----+ +-----+ | .
. | +-----+ 10 . | +-----+ 10
. | +--------------| ABR1|---------+ . | +--------------| ABR1|---------+
. | | 15 +-----+ | . | | 15 +-----+ |
. +-----+ 5 +---+-+ . | . +-----+ 5 +---+-+ . |
. | S |-----------| P |------------+ . +-----+ . | S |-----------| E |------------+ . +-----+
. +-----+ +-----+ 5 | . | D | . +-----+ +-----+ 5 | . | D |
. | | . +-----+ . | | . +-----+
. | | . | . | | . |
.. | +-----+ +-----+ 20 | .. | +-----+ +-----+ 20 |
. +-----| A2 |------------------| ABR2|------------+ . +-----| A2 |------------------| ABR2|------------+
. 10 +-----+ 15 +-----+ . 10 +-----+ 15 +-----+
... ... ... ...
... ... ... ...
...... ...... ...... ......
............. .............
Figure 6: Inter-Region Destination via Figure 7: Inter-Region Destination via
Multiple Border Routers but One Primary Neighbor Multiple Border Routers but One Primary Neighbor
6.1.1 Inheriting Alternate Next-Hops with One Primary Neighbor 5.1.1 Inheriting Alternate Next-Hops with One Primary Neighbor
The main question when deciding whether an alternate can be inherited The main question when deciding whether an alternate can be inherited
is whether or not that alternate will continue to provide the is whether or not that alternate will continue to provide the
necessary protection. I.e., will the alternate continue to be usable necessary protection. I.e., will the alternate continue to be usable
as an alternate and provide the same link or node protection with as an alternate and provide the same link or node protection with
respect to the destination that was provided with respect to the respect to the destination that was provided with respect to the
border router. The relationships shown in Figure 6 will be used for border router. It can be proved that the alternate will be usable as
illustrative purposes, although the topology connecting them may be an alternate and provide at least the same link or node protection
more general than that shown. The proofs and explanations are that was provided with respect to the border router. The alternate
provided in Appendix A, but the answer is that the alternate will be next-hop inheritance procedure SHOULD select a loop-free node-
usable as an alternate and provide at least the same link or node protecting alternate, if one is available.
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.
6.1.2 OSPF Inter-Area Routes 5.1.2 OSPF Inter-Area Routes
In OSPF, each area's links are summarized into a summary LSA, which In OSPF, each area's links are summarized into a summary LSA, which
is announced into an area by an Area Border Router. ABRs announce is announced into an area by an Area Border Router. ABRs announce
summary LSAs into the backbone area and inject summary LSAs of the summary LSAs into the backbone area and inject summary LSAs of the
backbone area into other non-backbone areas. A route can be learned backbone area into other non-backbone areas. A route can be learned
via summary LSA from one or more ABRs; such a route will be referred via summary LSA from one or more ABRs; such a route will be referred
to as a summary route. to as a summary route.
The alternate next-hop inheritance for summary routes is as described The alternate next-hop inheritance for summary routes is as described
in Section 6.1.1 in Section 5.1.1
6.1.3 OSPF External Routing 5.1.3 OSPF External Routing
Rules of inheritance of alternate next-hops for external routes is Rules of inheritance of alternate next-hops for external routes is
the same as for inter-area destinations. The additional complication the same as for inter-area destinations. The additional complication
comes from forwarding addresses, where an ASBR uses a forwarding comes from forwarding addresses, where an ASBR uses a forwarding
address to indicate to all routers in the Autonomous System to use address to indicate to all routers in the Autonomous System to use
the specified address instead of going through the ASBR. When a the specified address instead of going through the ASBR. When a
forwarding address has been indicated, all routers in the topology forwarding address has been indicated, all routers in the topology
calculate the shortest path to the link specified in the external calculate the shortest path to the link specified in the external
LSA. In this case, the alternate next-hop of the forwarding link LSA. In this case, the alternate next-hop of the forwarding link
should be used, in conjunction with the primary next-hop of the should be used, in conjunction with the primary next-hop of the
forwarding link, instead of those associated with the ASBR. forwarding link, instead of those associated with the ASBR.
6.1.4 ISIS Multi-Level Routing 5.1.4 ISIS Multi-Level Routing
ISIS maintains separate databases for each level with which it is ISIS maintains separate databases for each level with which it is
dealing. Nodes in one level do not have any information about state dealing. Nodes in one level do not have any information about state
of nodes and edges of the other level. ISIS level boundary points , of nodes and edges of the other level. ISIS level boundary points ,
also known as ISIS level boundary routers, are attached to both also known as ISIS level boundary routers, are attached to both
levels. ISIS level boundary routers summarize the destinations in levels. ISIS level boundary routers summarize the destinations in
each, level. ISIS inter-level route computation is very similar to each, level. ISIS inter-level route computation is very similar to
OSPF inter area routing. Rules for alternate next-hop inheritance is OSPF inter area routing. Rules for alternate next-hop inheritance is
the same as described in Section 6.1.1 the same as described in Section 5.1.1
6.2 OSPF Virtual Links 5.2 OSPF Virtual Links
OSPF virtual links are used to connect two disjoint backbone areas OSPF virtual links are used to connect two disjoint backbone areas
using a transit area. A virtual link is configured at the border using a transit area. A virtual link is configured at the border
routers of the disjoint area. There are two scenarios, depending routers of the disjoint area. There are two scenarios, depending
upon the position of the root, router S. upon the position of the root, router S.
If router S is itself an ABR or one of the endpoints of the disjoint If router S is itself an ABR or one of the endpoints of the disjoint
area, then router S must resolve its paths to the destination on the area, then router S must resolve its paths to the destination on the
other side of the disjoint area by using the summary links in the other side of the disjoint area by using the summary links in the
transit area and using the closest ABR summarizing them into the transit area and using the closest ABR summarizing them into the
transit area. This means that the data path may diverge from the transit area. This means that the data path may diverge from the
virtual neighbor's control path. An ABR's primary and alternate virtual neighbor's control path. An ABR's primary and alternate
next-hops are calculated by RAPID on the transit area. next-hops are calculated by S on the transit area.
The primary next-hops to use are determined based upon the closest The primary next-hops to use are determined based upon the closest
set of equidistant ABRs; the same rules described in Section 6.1.1 set of equidistant ABRs; the same rules described in Section 5.1.1
for inter-area destinations must be followed for OSPF virtual links for inter-area destinations must be followed for OSPF virtual links
to determine the alternate next-hop. The same ECMP cases apply. to determine the alternate next-hop. The same ECMP cases apply.
If router S is not an ABR, then all the destinations on the other If router S is not an ABR, then all the destinations on the other
side of the disjoint area will inherit the virtual link's endpoint, side of the disjoint area will inherit the virtual link's endpoint,
the transit ABR. The same OSPF inter-area rules described in Section the transit ABR. The same OSPF inter-area rules described in Section
6.1.1 must be followed here as well. 5.1.1 must be followed here as well.
A virtual link cannot be used as an alternate next-hop. A virtual link cannot be used as an alternate next-hop.
6.3 BGP Next-Hop Synchronization 5.3 BGP Next-Hop Synchronization
Typically BGP prefixes are advertised with AS exit routers router-id, Typically BGP prefixes are advertised with AS exit routers router-id,
and AS exit routers are reached by means of IGP routes. BGP resolves and AS exit routers are reached by means of IGP routes. BGP resolves
its advertised next-hop to the immediate next-hop by potential its advertised next-hop to the immediate next-hop by potential
recursive lookups in the routing database. IP/LDP Local Protection recursive lookups in the routing database. IP Fast-Reroute computes
computes the alternate next-hops to the all the IGP destinations, the alternate next-hops to the all the IGP destinations, which
which includes alternate next-hops to the AS exit router's router-id. includes alternate next-hops to the AS exit router's router-id. BGP
BGP simply inherits the alternate next-hop from IGP. The BGP simply inherits the alternate next-hop from IGP. The BGP decision
decision process is unaltered; BGP continue to use the IGP optimal process is unaltered; BGP continue to use the IGP optimal distance to
distance to find the nearest exit router. MBGP routes do not need to find the nearest exit router. MBGP routes do not need to copy the
copy the alternate next hops. alternate next hops.
6.4 Multicast Considerations 5.4 Multicast Considerations
IP/LDP Local Protection does not apply to multicast traffic. The Multicast traffic is out of scope for this specification of IP Fast-
alternate next-hops SHOULD not used for multi-cast RPF checks. Reroute. The alternate next-hops SHOULD not used for multi-cast RPF
checks.
7. Security Considerations 6. Security Considerations
This document does not introduce any new security issues. The This document does not introduce any new security issues. The
mechanisms described in this document depend upon the network mechanisms described in this document depend upon the network
topology distributed via an IGP, such as OSPF or ISIS. It is topology distributed via an IGP, such as OSPF or ISIS. It is
dependent upon the security associated with those protocols. dependent upon the security associated with those protocols.
8. Full Copyright Statement 7. Full Copyright Statement
Copyright (C) The Internet Society (2004). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be Copyright (C) The Internet Society (2004). This document is subject
revoked by the Internet Society or its successors or assigns. 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 is provided on an This document and the information contained herein are provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
9. References 8. References
[FRAMEWORK] M. Shand, "IP Fast Reroute Framework", draft-ietf-rtgwg- [FRAMEWORK] M. Shand, "IP Fast Reroute Framework", draft-ietf-rtgwg-
ipfrr-framework-01.txt, June 2004 ipfrr-framework-01.txt, June 2004
[LDP] L. Anderson, P. Doolan, N. Feldman, A. Fredette, B. Thomas, [LDP] L. Anderson, P. Doolan, N. Feldman, A. Fredette, B. Thomas,
"LDP Specification", RFC 3036, January 2001 "LDP Specification", RFC 3036, January 2001
[RSVP-TE] D. Awduche, L. Berger, D. Gan, T. Li, V Srinivasan, G. [RSVP-TE] D. Awduche, L. Berger, D. Gan, T. Li, V Srinivasan, G.
Swallow, "RSVP-TE: Extensions to RSVP for LSP Tunnels", RFC 3209, Swallow, "RSVP-TE: Extensions to RSVP for LSP Tunnels", RFC 3209,
December 2001 December 2001
[RSVP-TE FRR] P. Pan, D. Gan, G. Swallow, JP Vasseur, D. Cooper, A. [RSVP-TE FRR] P. Pan, D. Gan, G. Swallow, JP Vasseur, D. Cooper, A.
Atlas, and M. Jork, "Fast Reroute Extensions to RSVP-TE for LSP Atlas, and M. Jork, "Fast Reroute Extensions to RSVP-TE for LSP
Tunnels", work-in-progress draft-ietf-mpls-rsvp-lsp-fastreroute- Tunnels", work-in-progress draft-ietf-mpls-rsvp-lsp-fastreroute-
06.txt, June 2004 07.txt, June 2004
[RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and
McPherson, D., "OSPF Stub Router Advertisement", RFC 3137, June 2001 McPherson, D., "OSPF Stub Router Advertisement", RFC 3137, June 2001
[RFC3277] D. McPherson, "Intermediate System to Intermediate System [RFC3277] D. McPherson, "Intermediate System to Intermediate System
(IS-IS) Transient Blackhole Avoidance", RFC 3277, April 2002 (IS-IS) Transient Blackhole Avoidance", RFC 3277, April 2002
[ISIS] R. Callon, "Use of OSI IS-IS for Routing in TCP/IP and Dual [ISIS] R. Callon, "Use of OSI IS-IS for Routing in TCP/IP and Dual
Environments", RFC 1195, December 1990 Environments", RFC 1195, December 1990
[RFC2966] T. Li, T. Przygienda, H. Smit, "Domain-wide Prefix [RFC2966] T. Li, T. Przygienda, H. Smit, "Domain-wide Prefix
Distribution with Two-Level IS-IS", RFC 2966, October 2000 Distribution with Two-Level IS-IS", RFC 2966, October 2000
[OSPF] J. Moy, "OSPF Version 2", RFC 2328, April 1998 [OSPF] J. Moy, "OSPF Version 2", RFC 2328, April 1998
skipping to change at page 18, line 18 skipping to change at page 17, line 43
Environments", RFC 1195, December 1990 Environments", RFC 1195, December 1990
[RFC2966] T. Li, T. Przygienda, H. Smit, "Domain-wide Prefix [RFC2966] T. Li, T. Przygienda, H. Smit, "Domain-wide Prefix
Distribution with Two-Level IS-IS", RFC 2966, October 2000 Distribution with Two-Level IS-IS", RFC 2966, October 2000
[OSPF] J. Moy, "OSPF Version 2", RFC 2328, April 1998 [OSPF] J. Moy, "OSPF Version 2", RFC 2328, April 1998
[RFC2370] R. Coltun, "The OSPF Opaque LSA Option", RFC 2370, July [RFC2370] R. Coltun, "The OSPF Opaque LSA Option", RFC 2370, July
1998 1998
10. Authors Information 9. Authors Information
Raveendra Torvi Raveendra Torvi
Avici Systems Avici Systems
101 Billerica Avenue 101 Billerica Avenue
N. Billerica, MA 01862 N. Billerica, MA 01862
USA USA
email: rtorvi@avici.com email: rtorvi@avici.com
phone: +1 978 964 2026 phone: +1 978 964 2026
Gagan Choudhury Gagan Choudhury
skipping to change at page 19, line 10 skipping to change at page 18, line 36
email: brent.imhoff@wcg.com email: brent.imhoff@wcg.com
phone: +1 314 595 6853 phone: +1 314 595 6853
Don Fedyk Don Fedyk
Nortel Networks Nortel Networks
600 Technology Park 600 Technology Park
Billerica, MA 01821 Billerica, MA 01821
email: dwfedyk@nortelnetworks.com email: dwfedyk@nortelnetworks.com
phone: +1 978 288 3041 phone: +1 978 288 3041
11. Editor's Information 10. Editor's Information
Alia Atlas Alia Atlas
Avici Systems Avici Systems
101 Billerica Avenue 101 Billerica Avenue
N. Billerica, MA 01862 N. Billerica, MA 01862
USA USA
email: aatlas@avici.com email: aatlas@avici.com
phone: +1 978 964 2070 phone: +1 978 964 2070
Appendix A: Loop-Free Alternate Proofs
Consider where A2 is a loop-free alternate with respect to S and ABR2. Will A2
be a loop-free alternate with respect to S and D? Let there be three ABRs which
must be considered. Each ABR can represent a group of ABRs with the same
characteristics.
.............
...... ......
... ...
.. ..
.. 5 +-----+ 15 +-----+ 20 ..
. +------| A1 +---------| R1 |-----+ .
.. | +-----+ +-----+ | .
. | +-----+ 10
. | +--------------| ABR1|---------+
. | | 15 +-----+ |
. +-----+ 5 +---+-+ . |
. | S |-----------| P |------------+ . +-----+
. +-----+ +-----+ 5 | . | D |
. | | . +-----+
. | | . | |
.. | +-----+ +-----+ 20 | |
. +-----| A2 |------------------| ABR2|------------+ |
. 10 +-----+ 15 +-----+ |
... | ... |
... +---------------+ ... |
...... 10 +--+--+. 20 |
...........| ABRt|-----------------------+
+-----+
Figure 7: Inter-Region Destination via
Multiple Border Routers but One Primary Neighbor
ABR1 is from the set of ABRs where D_opt(A2, ABR1) = D_opt(A2,
S) + D_opt(S, ABR1). In other words, A2 is not loop-free with
regards to S and ABR1. Additionally, D_opt(S, D) = D_opt(S,
ABR1) + D_opt(ABR1, D) so ABR1 is on a shortest path from S to
D.
ABR2 is from the set of ABRs where D_opt(A2, ABR2) < D_opt(A2,
S) + D_opt(S, ABR2). In other words, A2 is loop-free with
regards to S and ABR2. Additionally, D_opt(S, D) = D_opt(S,
ABR2) + D_opt(ABR2, D) so ABR2 is on a shortest path from S to
D.
ABRt is from a set of ABRs where D_opt(S, D) < D_opt(S, ABRt) +
D_opt(ABRt, D). In other words, ABRt is not on a shortest path
from S to D.
First, we will prove that D_opt(A2, D) < D_opt(A2, ABR1) +
D_opt(ABR1, D). In other words, the shortest path from A2 to D
does not go through ABR1.
The shortest path from A2 to D via ABR1 also goes via S. A
shortest path from S to D goes via ABR1.
Step i: D_opt(A2, ABR1) + D_opt(ABR1, D) =
D_opt(A2, S) + D_opt(S, ABR1) + D_opt(ABR1, D)
The shortest path from A2 to D via ABR2 does not go through S.
ABR2 is on a shortest path from S to D.
Step ii: D_opt(A2, ABR2) + D_opt(ABR2, D) <
D_opt(A2, S) + D_opt(S, ABR2) + D_opt(ABR2, D)
From previous and given that ABR1 and ABR2 provide equal-cost
paths from S to D:
Step iii: D_opt(A2, ABR2) + D_opt(ABR2, D) <
D_opt(A2, S) + D_opt(S, ABR1) + D_opt(ABR1, D)
From previous and Step i:
Step iv: D_opt(A2, ABR2) + D_opt(ABR2, D) <
D_opt(A2, ABR1) + D_opt(ABR1, D)
Step v: D_opt(A2, D) <= D_opt(A2, ABR2) + D_opt(ABR2, D) <
D_opt(A2, ABR1) + D_opt(ABR1, D)
Thus, the optimal path from A2 to D cannot go through ABR1.
Next, we will prove that if D_opt(A2, D) = D_opt(A2, ABRt) +
D_opt(ABRt, D), then A2 is still loop-free with respect to S and D.
In other words, even if A2's shortest path to D goes through an ABRt
which isn't on a shortest path from S to D, the path from A2 to D is
still loop-free with respect to S and D. This is proved via
contradiction.
Assume that D_opt(A2, D) goes through ABRt.
Step i: D_opt(A2, ABRt) + D_opt(ABRt, D) <=
D_opt(A2, ABR2) + D_opt(ABR2, D)
Because A2 is loop-free with respect to S and ABR2
Step ii: D_opt(A2, ABR2) + D_opt(ABR2, D) <
D_opt(A2, S) + D_opt(S, ABR2) + D_opt(ABR2, D)
Because ABR2 is on a shortest path from S to D and ABRt is not
Step iii: D_opt(S, ABR2) + D_opt(ABR2,D) <
D_opt(S, ABRt) + D_opt(ABRt, D)
From previous by adding Dopt(A2, S) to both sides
Step iv: D_opt(A2, S) + D_opt(S, ABR2) + D_opt(ABR2,D) <
D_opt(A2, S) + D_opt(S, ABRt) + D_opt(ABRt, D)
From Steps i and ii:
Step v: D_opt(A2, ABRt) + D_opt(ABRt, D) <
D_opt(A2, S) + D_opt(S, ABR2) + D_opt(ABR2, D)
From Steps iv and v:
Step vi: D_opt(A2, ABRt) + D_opt(ABRt, D) <
D_opt(A2, S) + D_opt(S, ABRt) + D_opt(ABRt, D)
Therefore, if D_opt(A2, D) is via ABRt, it does not go through
S.
These two proofs show that if A2 is loop-free with respect to S and
ABR2, then A2 is loop-free with respect to S and D.
Appendix A.1 Loop-Free Node-Protecting Alternate Proofs
It must also be shown that if A2 is loop-free and node-protecting
with respect to S and ABR2, then A2 will still be node-protecting
with respect to S and D. In other words, that A2 will be loop-free
with respect to P and D.
This is shown where D_opt(S, D) = D_opt(S, P) + D_opt(P, D), so that
D_opt(P, ABR1) + D_opt(ABR1, D) = D_opt(P, ABR2) + D_opt(ABR2, D).
First, it has already been proven that an ABR offering equal-cost
from S to D which is also loop-free with respect to S and D will be
selected by A2 over an ABR offering equal-cost from S to D which is
not loop-free with respect to S and D. Since the alternate
inheritance is of interest only where all the ABRs offering equal-
cost paths to D have the same primary next-hop P, if A2 is loop-free
and node-protecting for one ABR offering equal-cost paths to D, then
A2 is node-protecting for all those ABRs.
Next, given that A2's optimal path to ABR2 does not go through P, is
to prove that if A2's optimal path to D goes via some ABRt, that that
path does not go through P. This can be shown using variable
replacement of the second proof given as follows:
Assume that D_opt(A2, D) goes through ABRt.
Step i: D_opt(A2, ABRt) + D_opt(ABRt, D) <=
D_opt(A2, ABR2) + D_opt(ABR2, D)
Step ii: D_opt(A2, ABR2) + D_opt(ABR2, D) <
D_opt(A2, P) + D_opt(P, ABR2) + D_opt(ABR2, D)
Step iii: D_opt(P, ABR2) + D_opt(ABR2,D) <
D_opt(P, ABRt) + D_opt(ABRt, D)
From previous by adding Dopt(A2, P) to both sides
Step iv: D_opt(A2, P) + D_opt(P, ABR2) + D_opt(ABR2,D) <
D_opt(A2, P) + D_opt(P, ABRt) + D_opt(ABRt, D)
From Steps i and ii:
Step v: D_opt(A2, ABRt) + D_opt(ABRt, D) <
D_opt(A2, P) + D_opt(P, ABR2) + D_opt(ABR2, D)
From Steps iv and v:
Step vi: D_opt(A2, ABRt) + D_opt(ABRt, D) <
D_opt(A2, P) + D_opt(P, ABRt) + D_opt(ABRt, D)
Therefore, if Dopt(A2, D) is via ABRt, it does not go through P.
This proves that if A2 provides a loop-free node-protecting alternate
for S to reach ABR2, then A2 will also provide a loop-free node-
protecting alternate for S to reach D.
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/