Internet Draft Alia Atlas, Ed (Avici Systems)
Expires: November 2004
Loop-Free Alternates for IP/LDP Local Protection
draft-atlas-ip-local-protect-loopfree-00.txt
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
By submitting this Internet-Draft, I certify that any applicable
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
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.
Abstract
This document defines an architecture and selection process for
providing local protection for IP unicast and/or LDP traffic in the
event of a single link or node failure until the router has
converged. When computing the primary next-hop for a prefix, a
router S also determines an alternate next-hop which can be used if
the primary next-hop fails. The alternate next-hop is said to be a
loop-free alternate, which goes to a neighbor whose shortest path to
the prefix does not go back through the router S.
Atlas et al. [Page 1]
Internet Draft November 2004
Contents
1 Introduction ................................................. 2
2 Terminology .................................................. 4
3 Finding an Alternate ......................................... 5
3.1 Loop-Free Alternates ....................................... 6
3.2 Selection of an Alternate .................................. 7
3.2.1 Failure Scenarios ........................................ 7
3.2.2 Broadcast and NBMA Interfaces ............................ 9
3.2.3 Interactions wtih ISIS Overload, RFC 3137
and Costed Out Links ..................................... 9
3.2.4 Characterization of Neighbors ............................ 10
3.2.5 Selection Procedure ...................................... 10
4 Using an Alternate ........................................... 11
5 Requirements on LDP Mode ..................................... 11
6 Routing Aspects .............................................. 12
6.1 Multiple-Region Routing .................................... 12
6.1.1 Inheriting Alternate Next-Hops with One Primary Neighbor . 14
6.1.2 OSPF Inter-Area Routes ................................... 15
6.1.3 OSPF Inter-Area Routes ................................... 15
6.1.4 ISIS Multi-Level Routing ................................. 15
6.2 OSPF Virtual Links ......................................... 15
6.3 BGP Next-Hop Synchronization ............................... 16
6.4 Multicast Considerations ................................... 16
7 Security Considerations ...................................... 16
8 Full Copyright Statement ..................................... 17
9 References ................................................... 17
10 Authors 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
Applications for interactive multimedia services such as VoIP and
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
time is generally on the order of seconds; the application traffic
may be sensitive to losses greater than 10s of milliseconds.
As discussed in [FRAMEWORK], minimizing traffic loss requires a
mechanism for the router adjacent to a failure rapidly invoke a
repair path, which is minimally affected by any subsequent re-
convergence. This document describes such a mechanism which allows a
Atlas et al. [Page 2]
Internet Draft November 2004
router whose local link 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.
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
affected prefixes, and only then install those new primary next-hops
into the forwarding plane. Until the new primary next-hops are
installed, traffic directed towards the affected prefixes is
discarded. This process can take seconds.
/__
\ +-----+
/------| S |--\
/ +-----+ \
/ 5 8 \
/ \
+-----+ +-----+
| P | | N_1 |
+-----+ +-----+
\ /
\ \ 4 3 / /
\| \ / |/
-+ \ +-----+ / +-
\---| D |---/
+-----+
Figure 1: Basic Topology
The goal of IP/LDP Local Protection is to reduce that traffic
convergence time to 10s of milliseconds by using a pre-computed
alternate interface, in the event that the currently selected primary
interface fails, so that the alternate can be rapidly used when the
failure is detected.
To clarify the behavior of IP/LDP Local Protection, consider the
simple topology in Figure 1. When router S computes its shortest
path to router D, router S determines to use the interface to router
P as its primary next-hop. Without IP/LDP Local Protection, that
interface is the only next-hop that router S computes to reach D.
With IP/LDP Local Protection, S also looks for an alternate next-hop
interface to use. In this example, S would determine that it could
send traffic destined to D by using the interface to router N_1 and
therefore S would install the interface to N_1 as its alternate
next-hop. At some later time, the link between router S and router P
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
traffic destined for D towards P via the failed link, and instead
Atlas et al. [Page 3]
Internet Draft November 2004
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
installed. As with the primary next-hop, an alternate next-hop is
computed for each destination. The process of computing an alternate
next-hop does not alter the primary next-hop computed via a standard
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
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
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
next-hop is topology dependent.
2. Terminology
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.
Atlas et al. [Page 4]
Internet Draft November 2004
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 | \ -+ +- __/ \
Atlas et al. [Page 5]
Internet Draft November 2004
+-----+ \____ / \
\ \ / \
\ +-----+ \
\ _| 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
Atlas et al. [Page 6]
Internet Draft November 2004
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: Criteria for a Loop-Free Alternate
To check this equation, we can consider the other conditions where
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
The selection of the alternate to use depends upon the failure
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 simplest case is to locate an alternate which protects against a
link failure.
A loop-free link-protecting alternate may cause traffic looping in
the event of a node failure. This issue is illustrated in Figure 3.
If Link(S->P) fails, then the link-protecting alternate via N will
work correctly. However, if router P 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
Atlas et al. [Page 7]
Internet Draft November 2004
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 |
+-+---+ 5 +-----+
| |
| 5 5 | |
| | | \|/
\|/ | |
| +-----+ |
+----| P |---+
+--+--+
|
|
| 10
|
+--+--+
| 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)
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
against other correlated failures. In the general case, these are
Atlas et al. [Page 8]
Internet Draft November 2004
handled by shared risk link groups (SRLGs) where any links in the
network can belong to the 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
only during the selection of an acceptable alternate. This sub-
category is to express correlated failures of links which are
connected to the same router. For example, if there are multiple
logical sub-interfaces on the same physical interface, such as VLANs
on an Ethernet interface, if multiple interfaces use the same
physical port because of channelization, or if multiple interfaces
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
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
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-
protection; i.e. picking a loop-free node-protecting alternate.
3.2.2 Broadcast and NBMA Interfaces
The computation for node-protection and link-protection is a bit more
complicated for broadcast interfaces. In an SPF computation, a
broadcast interface 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 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
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
desirable not to have the router used on an alternate path.
For computing an alternate, a router MUST not consider diverting from
the SPF tree along a link whose reverse cost is LSInfinity (for OSPF)
or whose router has the overload bit set (for ISIS).
Atlas et al. [Page 9]
Internet Draft November 2004
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
using N_i as an alternate.
Similarly in the case of ISIS, if N_i has the overload bit set, then
S cannot consider using N_i as an alternate.
This preserves the desired behavior of diverting traffic away from a
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
maintenance, of not permitting traffic across that link unless there
is no other path.
If a link or router which is costed out was the only possible
alternate to protect traffic from a particular router S to a
particular destination, then there will be no alternate provided for
protection.
3.2.4 Characterization of Neighbors
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
Once the neighbors have been categorized, a selection can be made.
The selection should maximize the failure cases which can be
protected against.
Atlas et al. [Page 10]
Internet Draft November 2004
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 just because S does not support ECMP.
If S has a single primary neighbor, then S SHOULD select a loop-free
node-protecting alternate, if one is available. If none is
available, then S MAY select a loop-free link-protecting alternate.
If S has multiple primary neighbors, then S should select an
alternate to protect against the failure of each of the primary
next-hops. The loop-free alternate selected should be either one of
the other primary next-hops or should provide node-protection.
4. Using an Alternate
If an alternate is available, it is used to redirect traffic when the
primary next-hop has failed.
When a local interface failure is detected, traffic that was destined
to go out the failed interface must be redirected to the appropriate
alternate next-hops. The alternate next-hop is pre-computed to be
the most appropriate as mentioned in the selection criteria in the
event of the failure scenario being protected against (i.e. link or
node failure).
IP/LDP Local Protection does not require any mechanisms for the
detection of the failure. The same mechanisms that enable RSVP-TE
Fast-Reroute can work here. Because the alternate next-hop is pre-
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
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
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 out-segments can be installed in the forwarding plane
before the failure occurs.
This means that a Label Switched Router (LSR) running LDP must
distribute its labels for the FECs it can provide to all its
neighbors, regardless of whether or not they are upstream.
Additionally, LDP must be acting in liberal label retention mode so
that the labels which correspond to interfaces that aren't currently
Atlas et al. [Page 11]
Internet Draft November 2004
the primary next-hop are stored. Similarly, LDP should be in
downstream unsolicited mode, so that the labels for the FEC are
distributed other than along the SPT.
If these requirements are met, then LDP can use the loop-free
alternates without requiring any targeted sessions or signaling
extensions for this purpose.
6. Routing Aspects
An SPF-like computation is run for each topology, which corresponds
to a particular OSPF area or ISIS level. The IGP needs to determine
the inheritance of loop-free alternates, as determined for singly
advertised routes, to multiply advertised routes, for protocols such
as BGP and LDP and for inter-area or inter-level routes. These
alternates are provided to LDP and BGP for forwarding purposes only;
the alternates are not redistributed in any fashion into other
protocols.
The alternate next-hop inheritance is described in the context of
inter-area routes, but applies equally well to BGP routes and to
routes which are advertised by multiple routers in the IGP area.
6.1 Multiple-Region Routing
Routes in different regions inherit their primary next-hops from the
border routers (area border routers (ABRs) or level boundary routers)
which offer the shortest path to the destination(s) announcing the
route. Similarly, routes must inherit their alternate next-hop and
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
that case, both the primary and the alternate next-hops can be
inherited from that border router. Figure 4 illustrates this case
where D is reached via ABR1; the primary next-hop for ABR1 is P and
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.
Atlas et al. [Page 12]
Internet Draft November 2004
.............
...... ......
... ...
.. ..
.. 10 +-----+ 5 +-----+ 5 ..
. +------| A1 +---------| R1 |-----+ .
.. | +-----+ +-----+ | .
. | +-----+ 10
. | +--------------| ABR1|---------+
. | | 5 +-----+ |
. +-----+ 5 +---+-+ . |
. | S |-----------| P |------------+ . +-----+
. +-----+ +-----+ 10 | . | D |
. | | . +-----+
. | | . |
.. | +-----+ +-----+ 20 |
. +-----| A2 |------------------| ABR2|------------+
. 10 +-----+ 5 +-----+
... ...
... ...
...... ......
.............
Figure 4: Inter-Region Destination via One Border Router
..........
...... ......
... ...
.. ..
.. 10 +-----+ 5 +-----+ ..
. +------| A1 +---------| R1 |-----+
.. | +-----+ +-----+ |.
. | +-----+ +-----+ 10
. | +-----------| P1 |------------| ABR1|---------+
. | | 5 +-----+ 5 +-----+ |
. +-----+ . |
. | S |---+ 5 +-----+ 10 . +-----+
. +-----+ +-------| P2 |------------+ . | D |
. | +-----+ | . +-----+
. | | . |
.. | +-----+ +-----+ 20 |
. +-----| A2 |------------------| ABR2|------------+
. 10 +-----+ 5 +-----+
... ...
... ...
...... ......
..........
Atlas et al. [Page 13]
Internet Draft November 2004
Figure 5: Inter-Region Destination via
Multiple Border Routers and Multiple Primary Neighbors
In the third case, the shortest path to an inter-region route
may be learned from multiple border routers but with a single
primary neighbor. This is shown in Figure 6, where D can be
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.
It is necessary to select one of the alternates to be inherited.
.............
...... ......
... ...
.. ..
.. 5 +-----+ 15 +-----+ 20 ..
. +------| A1 +---------| R1 |-----+ .
.. | +-----+ +-----+ | .
. | +-----+ 10
. | +--------------| ABR1|---------+
. | | 15 +-----+ |
. +-----+ 5 +---+-+ . |
. | S |-----------| P |------------+ . +-----+
. +-----+ +-----+ 5 | . | D |
. | | . +-----+
. | | . |
.. | +-----+ +-----+ 20 |
. +-----| A2 |------------------| ABR2|------------+
. 10 +-----+ 15 +-----+
... ...
... ...
...... ......
.............
Figure 6: Inter-Region Destination via
Multiple Border Routers but One Primary Neighbor
6.1.1 Inheriting Alternate Next-Hops with One Primary Neighbor
The main question when deciding whether an alternate can be inherited
is whether or not that alternate will continue to provide the
necessary protection. I.e., will the alternate continue to be usable
as an alternate and provide the same link or node protection with
respect to the destination that was provided with respect to the
border router. The relationships shown in Figure 6 will be used for
illustrative purposes, although the topology connecting them may be
more general than that shown. The proofs and explanations are
provided in Appendix A, but the answer is that the alternate will be
usable as an alternate and provide at least the same link or node
Atlas et al. [Page 14]
Internet Draft November 2004
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
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
summary LSAs into the backbone area and inject summary LSAs of the
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
to as a summary route.
The alternate next-hop inheritance for summary routes is as described
in Section 6.1.1
6.1.3 OSPF External Routing
Rules of inheritance of alternate next-hops for external routes is
the same as for inter-area destinations. The additional complication
comes from forwarding addresses, where an ASBR uses a forwarding
address to indicate to all routers in the Autonomous System to use
the specified address instead of going through the ASBR. When a
forwarding address has been indicated, all routers in the topology
calculate the shortest path to the link specified in the external
LSA. In this case, the alternate next-hop of the forwarding link
should be used, in conjunction with the primary next-hop of the
forwarding link, instead of those associated with the ASBR.
6.1.4 ISIS Multi-Level Routing
ISIS maintains separate databases for each level with which it is
dealing. Nodes in one level do not have any information about state
of nodes and edges of the other level. ISIS level boundary points ,
also known as ISIS level boundary routers, are attached to both
levels. ISIS level boundary routers summarize the destinations in
each, level. ISIS inter-level route computation is very similar to
OSPF inter area routing. Rules for alternate next-hop inheritance is
the same as described in Section 6.1.1
6.2 OSPF Virtual Links
OSPF virtual links are used to connect two disjoint backbone areas
using a transit area. A virtual link is configured at the border
routers of the disjoint area. There are two scenarios, depending
Atlas et al. [Page 15]
Internet Draft November 2004
upon the position of the root, router S.
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
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. This means that the data path may diverge from the
virtual neighbor's control path. An ABR's primary and alternate
next-hops are calculated by RAPID on the transit area.
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
for inter-area destinations must be followed for OSPF virtual links
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
side of the disjoint area will inherit the virtual link's endpoint,
the transit ABR. The same OSPF inter-area rules described in Section
6.1.1 must be followed here as well.
A virtual link cannot be used as an alternate next-hop.
6.3 BGP Next-Hop Synchronization
Typically BGP prefixes are advertised with AS exit routers router-id,
and AS exit routers are reached by means of IGP routes. BGP resolves
its advertised next-hop to the immediate next-hop by potential
recursive lookups in the routing database. IP/LDP Local Protection
computes the alternate next-hops to the all the IGP destinations,
which includes alternate next-hops to the AS exit router's router-id.
BGP simply inherits the alternate next-hop from IGP. The BGP
decision process is unaltered; BGP continue to use the IGP optimal
distance to find the nearest exit router. MBGP routes do not need to
copy the alternate next hops.
6.4 Multicast Considerations
IP/LDP Local Protection does not apply to multicast traffic. The
alternate next-hops SHOULD not used for multi-cast RPF checks.
7. 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.
Atlas et al. [Page 16]
Internet Draft November 2004
8. 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
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS 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.
9. References
[FRAMEWORK] M. Shand, "IP Fast Reroute Framework", draft-ietf-rtgwg-
ipfrr-framework-01.txt, June 2004
[LDP] L. Anderson, P. Doolan, N. Feldman, A. Fredette, B. Thomas,
"LDP Specification", RFC 3036, January 2001
[RSVP-TE] D. Awduche, L. Berger, D. Gan, T. Li, V Srinivasan, G.
Swallow, "RSVP-TE: Extensions to RSVP for LSP Tunnels", RFC 3209,
December 2001
[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
Tunnels", work-in-progress draft-ietf-mpls-rsvp-lsp-fastreroute-
06.txt, June 2004
[RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and
McPherson, D., "OSPF Stub Router Advertisement", RFC 3137, June 2001
Atlas et al. [Page 17]
Internet Draft November 2004
[RFC3277] D. McPherson, "Intermediate System to Intermediate System
(IS-IS) Transient Blackhole Avoidance", RFC 3277, April 2002
[ISIS] R. Callon, "Use of OSI IS-IS for Routing in TCP/IP and Dual
Environments", RFC 1195, December 1990
[RFC2966] T. Li, T. Przygienda, H. Smit, "Domain-wide Prefix
Distribution with Two-Level IS-IS", RFC 2966, October 2000
[OSPF] J. Moy, "OSPF Version 2", RFC 2328, April 1998
[RFC2370] R. Coltun, "The OSPF Opaque LSA Option", RFC 2370, July
1998
10. Authors Information
Raveendra Torvi
Avici Systems
101 Billerica Avenue
N. Billerica, MA 01862
USA
email: rtorvi@avici.com
phone: +1 978 964 2026
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
WilTel Communications
3180 Rider Trail South
Bridgeton, MO 63045
USA
email: brent.imhoff@wcg.com
phone: +1 314 595 6853
Don Fedyk
Atlas et al. [Page 18]
Internet Draft November 2004
Nortel Networks
600 Technology Park
Billerica, MA 01821
email: dwfedyk@nortelnetworks.com
phone: +1 978 288 3041
11. Editor's Information
Alia Atlas
Avici Systems
101 Billerica Avenue
N. Billerica, MA 01862
USA
email: aatlas@avici.com
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|-----------------------+
+-----+
Atlas et al. [Page 19]
Internet Draft November 2004
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) +
Atlas et al. [Page 20]
Internet Draft November 2004
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).
Atlas et al. [Page 21]
Internet Draft November 2004
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(S, 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.
Atlas et al. [Page 22]