draft-ietf-rtgwg-ipfrr-spec-base-09.txt   draft-ietf-rtgwg-ipfrr-spec-base-10.txt 
Routing Area Working Group A. Atlas, Ed. Routing Area Working Group A. Atlas, Ed.
Internet-Draft Google, Inc. Internet-Draft BT
Intended status: Standards Track A. Zinin, Ed. Intended status: Standards Track A. Zinin, Ed.
Expires: March 21, 2008 Alcatel Expires: May 19, 2008 Alcatel
Sept 18, 2007 Nov 16, 2007
Basic Specification for IP Fast-Reroute: Loop-free Alternates Basic Specification for IP Fast-Reroute: Loop-free Alternates
draft-ietf-rtgwg-ipfrr-spec-base-09 draft-ietf-rtgwg-ipfrr-spec-base-10
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79. aware will be disclosed, in accordance with Section 6 of BCP 79.
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
skipping to change at page 1, line 35 skipping to change at page 1, line 35
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 as "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/ietf/1id-abstracts.txt.
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.
This Internet-Draft will expire on March 21, 2008. This Internet-Draft will expire on May 19, 2008.
Copyright Notice Copyright Notice
Copyright (C) The IETF Trust (2007). Copyright (C) The IETF Trust (2007).
Abstract Abstract
This document describes the use of loop-free alternates to provide This document describes the use of loop-free alternates to provide
local protection for unicast traffic in pure IP and MPLS/LDP networks local protection for unicast traffic in pure IP and MPLS/LDP networks
in the event of a single failure, whether link, node or shared risk in the event of a single failure, whether link, node or shared risk
link group (SRLG). The goal of this technology is to reduce the link group (SRLG). The goal of this technology is to reduce the
micro-looping and packet loss that happens while routers converge packet loss that happens while routers converge after a topology
after a topology change due to a failure. Rapid failure repair is change due to a failure. Rapid failure repair is achieved through
achieved through use of precalculated backup next-hops that are loop- use of precalculated backup next-hops that are loop-free and safe to
free and safe to use until the distributed network convergence use until the distributed network convergence process completes.
process completes. This simple approach does not require any support from other routers.
The extent to which this goal can be met by this specification is
dependent on the topology of the network.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Failure Scenarios . . . . . . . . . . . . . . . . . . . . 5 1.1. Failure Scenarios . . . . . . . . . . . . . . . . . . . . 5
2. Applicability of Described Mechanisms . . . . . . . . . . . . 8 2. Applicability of Described Mechanisms . . . . . . . . . . . . 8
3. Alternate Next-Hop Calculation . . . . . . . . . . . . . . . . 9 3. Alternate Next-Hop Calculation . . . . . . . . . . . . . . . . 9
3.1. Basic Loop-free Condition . . . . . . . . . . . . . . . . 10 3.1. Basic Loop-free Condition . . . . . . . . . . . . . . . . 10
3.2. Node-Protecting Alternate Next-Hops . . . . . . . . . . . 10 3.2. Node-Protecting Alternate Next-Hops . . . . . . . . . . . 10
3.3. Broadcast and NBMA Links . . . . . . . . . . . . . . . . . 11 3.3. Broadcast and NBMA Links . . . . . . . . . . . . . . . . . 11
3.4. ECMP and Alternates . . . . . . . . . . . . . . . . . . . 12 3.4. ECMP and Alternates . . . . . . . . . . . . . . . . . . . 12
3.5. Interactions with ISIS Overload, RFC 3137 and Costed 3.5. Interactions with ISIS Overload, RFC 3137 and Costed
Out Links . . . . . . . . . . . . . . . . . . . . . . . . 13 Out Links . . . . . . . . . . . . . . . . . . . . . . . . 13
3.5.1. Interactions with ISIS Link Attributes . . . . . . . . 14 3.5.1. Interactions with ISIS Link Attributes . . . . . . . . 14
3.6. Selection Procedure . . . . . . . . . . . . . . . . . . . 14 3.6. Selection Procedure . . . . . . . . . . . . . . . . . . . 14
3.7. A Simplification: Per-Next-Hop LFAs . . . . . . . . . . . 18 3.7. LFA types and Trade-offs . . . . . . . . . . . . . . . . . 18
4. Using an Alternate . . . . . . . . . . . . . . . . . . . . . . 19 3.8. A Simplification: Per-Next-Hop LFAs . . . . . . . . . . . 19
4.1. Terminating Use of Alternate . . . . . . . . . . . . . . . 19 4. Using an Alternate . . . . . . . . . . . . . . . . . . . . . . 20
5. Requirements on LDP Mode . . . . . . . . . . . . . . . . . . . 21 4.1. Terminating Use of Alternate . . . . . . . . . . . . . . . 20
6. Routing Aspects . . . . . . . . . . . . . . . . . . . . . . . 21 5. Requirements on LDP Mode . . . . . . . . . . . . . . . . . . . 22
6.1. Multi-Homed Prefixes . . . . . . . . . . . . . . . . . . . 21 6. Routing Aspects . . . . . . . . . . . . . . . . . . . . . . . 22
6.2. ISIS . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 6.1. Multi-Homed Prefixes . . . . . . . . . . . . . . . . . . . 22
6.3. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 6.2. ISIS . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6.3.1. OSPF External Routing . . . . . . . . . . . . . . . . 23 6.3. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.3.2. OSPF Multi-Topology . . . . . . . . . . . . . . . . . 23 6.3.1. OSPF External Routing . . . . . . . . . . . . . . . . 24
6.4. BGP Next-Hop Synchronization . . . . . . . . . . . . . . . 24 6.3.2. OSPF Multi-Topology . . . . . . . . . . . . . . . . . 25
6.5. Multicast Considerations . . . . . . . . . . . . . . . . . 24 6.4. BGP Next-Hop Synchronization . . . . . . . . . . . . . . . 25
7. Security Considerations . . . . . . . . . . . . . . . . . . . 24 6.5. Multicast Considerations . . . . . . . . . . . . . . . . . 25
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 7. Security Considerations . . . . . . . . . . . . . . . . . . . 25
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 25 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 25 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 26
10.1. Normative References . . . . . . . . . . . . . . . . . . . 25 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 26
10.2. Informative References . . . . . . . . . . . . . . . . . . 25 10.1. Normative References . . . . . . . . . . . . . . . . . . . 26
10.2. Informative References . . . . . . . . . . . . . . . . . . 26
Appendix A. OSPF Example Where LFA Based on Local Area Appendix A. OSPF Example Where LFA Based on Local Area
Topology is Insufficient . . . . . . . . . . . . . . 26 Topology is Insufficient . . . . . . . . . . . . . . 27
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 27 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 28
Intellectual Property and Copyright Statements . . . . . . . . . . 30 Intellectual Property and Copyright Statements . . . . . . . . . . 31
1. Introduction 1. Introduction
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119. [RFC2119] document are to be interpreted as described in RFC 2119. [RFC2119]
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
skipping to change at page 4, line 29 skipping to change at page 4, line 29
+-----+ +-----+
Figure 1: Basic Topology Figure 1: Basic Topology
The goal of IP Fast-Reroute is to reduce failure reaction time to 10s The goal of IP Fast-Reroute is to reduce failure reaction time to 10s
of milliseconds by using a pre-computed alternate next-hop, in the of milliseconds by using a pre-computed alternate next-hop, in the
event that the currently selected primary next-hop fails, so that the event that the currently selected primary next-hop fails, so that the
alternate can be rapidly used when the failure is detected. A alternate can be rapidly used when the failure is detected. A
network with this feature experiences less traffic loss and less network with this feature experiences less traffic loss and less
micro-looping of packets than a network without IPFRR. There are micro-looping of packets than a network without IPFRR. There are
cases where micro-looping is still a possibility since IPFRR coverage cases where traffic loss is still a possibility since IPFRR coverage
varies but in the worst possible situation a network with IPFRR is varies but in the worst possible situation a network with IPFRR is
equivalent with respect to traffic convergence to a network without equivalent with respect to traffic convergence to a network without
IPFRR. IPFRR.
To clarify the behavior of IP Fast-Reroute, consider the simple To clarify the behavior of IP Fast-Reroute, consider the simple
topology in Figure 1. When router S computes its shortest path to topology in Figure 1. When router S computes its shortest path to
router D, router S determines to use the link to router E as its router D, router S determines to use the link to router E as its
primary next-hop. Without IP Fast-Reroute, that link is the only primary next-hop. Without IP Fast-Reroute, that link is the only
next-hop that router S computes to reach D. With IP Fast-Reroute, S next-hop that router S computes to reach D. With IP Fast-Reroute, S
also looks for an alternate next-hop to use. In this example, S also looks for an alternate next-hop to use. In this example, S
skipping to change at page 5, line 36 skipping to change at page 5, line 36
a more restrictive condition that is applicable to more complex a more restrictive condition that is applicable to more complex
failure scenarios: failure scenarios:
Distance_opt(N, D) < Distance_opt(S, D) Distance_opt(N, D) < Distance_opt(S, D)
Inequality 2: Downstream Path Criterion Inequality 2: Downstream Path Criterion
1.1. Failure Scenarios 1.1. Failure Scenarios
The alternate next-hop can protect against a single link failure, a The alternate next-hop can protect against a single link failure, a
single node failure, one or more shared risk link group failures, or single node failure, failure of one or more links within a shared
a combination of these. Whenever a failure occurs that is more risk link group failures, or a combination of these. Whenever a
extensive than what the alternate was intended to protect, there is failure occurs that is more extensive than what the alternate was
the possibility of temporarily looping traffic (note again, that such intended to protect, there is the possibility of temporarily looping
a loop would only last until the next complete SPF calculation). The traffic (note again, that such a loop would only last until the next
example where a node fails when the alternate provided only link complete SPF calculation). The example where a node fails when the
protection is illustrated below. If unexpected simultaneous failures alternate provided only link protection is illustrated below. If
occur, then micro-looping may occur since the alternates are not pre- unexpected simultaneous failures occur, then micro-looping may occur
computed to avoid the set of failed links. since the alternates are not pre-computed to avoid the set of failed
links.
If only link protection is provided and the node fails, it is If only link protection is provided and the node fails, it is
possible for traffic using the alternates to experience micro- possible for traffic using the alternates to experience micro-
looping. This issue is illustrated in Figure 2. If Link(S->E) looping. This issue is illustrated in Figure 2. If Link(S->E)
fails, then the link-protecting alternate via N will work correctly. 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 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 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 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 thus causing a forwarding loop. Such a scenario can arise because
the key assumption, that all other routers in the network are the key assumption, that all other routers in the network are
forwarding based upon the shortest path, is violated because of a forwarding based upon the shortest path, is violated because of a
second simultaneous correlated failure - another link connected to second simultaneous correlated failure - another link connected to
the same primary neighbor. If there are not other protection the same primary neighbor. If there are not other protection
mechanisms a node failure is still a concern when only using link mechanisms to handle node failure, a node failure is still a concern
protection. when only using link protecting LFAs.
<@@@ <@@@
@@@> @@@>
+-----+ +-----+ +-----+ +-----+
| S |-------| N | | S |-------| N |
+-+---+ 5 +-----+ +-+---+ 5 +-----+
| | | |
| 5 4 | | | 5 4 | |
| | | \|/ | | | \|/
\|/ | | \|/ | |
skipping to change at page 6, line 37 skipping to change at page 6, line 38
| 10 | 10
| |
+--+--+ +--+--+
| D | | D |
+-----+ +-----+
Figure 2: Link-Protecting Alternates Causing Loop on Node Failure Figure 2: Link-Protecting Alternates Causing Loop on Node Failure
Micro-looping of traffic via the alternates caused when a more Micro-looping of traffic via the alternates caused when a more
extensive failure than planned for occurs can be prevented via extensive failure than planned for occurs can be prevented via
selection of only downstream paths as alternates. In Figure 2, S selection of only downstream paths as alternates. A micro-loop due
would be able to use N as an alternate, but N could not use S; to the use of alternates can be avoided by using downstream paths
therefore N would have no alternate and would discard the traffic, because each succeeding router in the path to the destination must be
thus avoiding the micro-loop. A micro-loop due to the use of closer to the destination than its predecessor (according to the
alternates can be avoided by using downstream paths because each topology prior to the failures). Although use of downstream paths
succeeding router in the path to the destination must be closer to ensures that the micro-looping via alternates does not occur, such a
the destination than its predecessor (according to the topology prior restriction can severely limit the coverage of alternates. In
to the failures). Although use of downstream paths ensures that the Figure 2, S would be able to use N as a downstream alternate, but N
micro-looping via alternates does not occur, such a restriction can could not use S; therefore N would have no alternate and would
severely limit the coverage of alternates. discard the traffic, thus avoiding the micro-loop.
As shown above, the use of either a node protecting LFA or a As shown above, the use of either a node protecting LFA (described in
downstream path provides protection against micro-looping in the Section 3.2) or a downstream path provides protection against micro-
event of node failure. There are topologies where there may be looping in the event of node failure. There are topologies where
either a node portecting LFA, a downstream path, both or neither. A there may be either a node portecting LFA, a downstream path, both or
node may select either a node protecting LFA or a downstream path neither. A node may select either a node protecting LFA or a
without risk of causing micro-loops in the event of node failure. downstream path without risk of causing micro-loops in the event of
While a link-and-node-protecting LFA guarantees protection against neighbor node failure. While a link-and-node-protecting LFA
either link or node failure, a downstream path provides protection guarantees protection against either link or node failure, a
only against a link failure and may or may not provide protection downstream path provides protection only against a link failure and
against a node failure depending on the protection available at the may or may not provide protection against a node failure depending on
downstream node, but it cannot cause a micro-loop. For example in the protection available at the downstream node, but it cannot cause
Figure 2, if S uses N as a downstream path, although no looping can a micro-loop. For example in Figure 2, if S uses N as a downstream
occur, the traffic will not be protected in the event of the failure path, although no looping can occur, the traffic will not be
of node E because N has no viable repair path, and it will simply protected in the event of the failure of node E because N has no
discard the packet. However, if N had a link and node protecting LFA viable repair path, and it will simply discard the packet. However,
or downstream path via some other path (not shown), then the repair if N had a link and node protecting LFA or downstream path via some
may succeed. other path (not shown), then the repair may succeed.
Since the functionality of link and node protecting LFAs is greater Since the functionality of link and node protecting LFAs is greater
than that of downstream paths, a router SHOULD select a link and node than that of link protecting downstream paths, a router SHOULD select
protecting LFA over a downstream path. If there are any destinations a link and node protecting LFA over a link protecting downstream
for which a link and node protecting LFA is not available, then by path. If there are any destinations for which a link and node
definition the path to all of those destinations from any neighbor of protecting LFA is not available, then by definition the path to all
the computing router (S) must be through the node (E) being protected of those destinations from any neighbor of the computing router (S)
(otherwise there would be a node protecting LFA for that must be through the node (E) being protected (otherwise there would
destination). Consequently, if there exists a downstream path to the be a node protecting LFA for that destination). Consequently, if
protected node as destination, then that downstream path may be used there exists a downstream path to the protected node as destination,
for all those destinations for which a link and node protecting LFA then that downstream path may be used for all those destinations for
is not available; the existence of a downstream path can be which a link and node protecting LFA is not available; the existence
determined by a single check of the condition Distance_opt(N, E) < of a downstream path can be determined by a single check of the
Distance_opt(S, E). condition Distance_opt(N, E) < Distance_opt(S, E).
It may be desirable to find an alternate that can protect against It may be desirable to find an alternate that can protect against
other correlated failures (of which node failure is a specific other correlated failures (of which node failure is a specific
instance). In the general case, these are handled by shared risk instance). In the general case, these are handled by shared risk
link groups (SRLGs) where any links in the network can belong to the link groups (SRLGs) where any links in the network can belong to the
SRLG. General SRLGs may add unacceptably to the computational SRLG. General SRLGs may add unacceptably to the computational
complexity of finding a loop-free alternate. 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-
skipping to change at page 11, line 42 skipping to change at page 11, line 42
| | 8 | | 8
| 5 | | 5 |
+-----+ 5 +-----+ +-----+ 5 +-----+
| E |----| D | | E |----| D |
+-----+ +-----+ +-----+ +-----+
Figure 3: Loop-Free Alternate that is Link-Protecting Figure 3: Loop-Free Alternate that is Link-Protecting
In Figure 3, N offers a loop-free alternate which is 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 If the primary next-hop uses a broadcast link, then an alternate
SHOULD be loop-free with respect to that link's pseudo-node to SHOULD be loop-free with respect to that link's pseudo-node (PN) to
provide link protection. This requirement is described in provide link protection. This requirement is described in
Inequality 4 below. Inequality 4 below.
D_opt(N, D) < D_opt(N, pseudo) + D_opt(pseudo, D) D_opt(N, D) < D_opt(N, PN) + D_opt(PN, D)
Inequality 4: Loop-Free Link-Protecting Criterion for Broadcast Links Inequality 4: Loop-Free Link-Protecting Criterion for Broadcast Links
Because the shortest path from the pseudo-node goes through E, if a Because the shortest path from the pseudo-node goes through E, if a
loop-free alternate from a neighbor N is node-protecting, the loop-free alternate from a neighbor N is node-protecting, the
alternate will also be link-protecting unless the router S can only alternate will also be link-protecting unless the router S can only
reach the alternate neighbor N via the same pseudo-node. Because S reach the alternate neighbor N via the same pseudo-node. Because S
can direct the traffic away from the shortest path to use the can direct the traffic away from the shortest path to use the
alternate N, traffic might pass through the same broadcast link as it alternate N, traffic might pass through the same broadcast link as it
would when S sent the traffic to the primary E. Thus, an LFA from N would when S sent the traffic to the primary E. Thus, an LFA from N
skipping to change at page 16, line 17 skipping to change at page 16, line 17
The following procedure describes how to select an alternate next- The following procedure describes how to select an alternate next-
hop. The procedure is described to determine alternate next-hops to hop. The procedure is described to determine alternate next-hops to
use to reach each router in the topology. Prefixes that are use to reach each router in the topology. Prefixes that are
advertised by a single router can use the alternate next-hop computed advertised by a single router can use the alternate next-hop computed
for the router to which they are attached. The same procedure can be for the router to which they are attached. The same procedure can be
used to reach a prefix that is advertised by more than one router used to reach a prefix that is advertised by more than one router
when the logical topological transformation described in Section 6.1 when the logical topological transformation described in Section 6.1
is used. is used.
S is the computing router and has candidate next-hops H_1 through S is the computing router. S has neighbors N_1 to N_j. A candidate
H_k. N_i and N_j are used to refer to neighbors of S. For a next-hop next-hop is indicated by (outgoing link, neighbor) and the outgoing
to be a candidate, the next-hop must be associated with a bi- link must be bidirectionally connected, as is determined by the IGP.
directional link, as is determined by the IGP. For a particular The candidate next-hops of S are enumerated as H_1 through H_k.
destination router D, let S have already computed D_opt(S, D), and Recall that S may have multiple next hops over different interfaces
for each neighbor N_i, D_opt(N_i, D), D_opt(N_i, S), and D_opt(N_i, to a neighbor. H_i.link refers to the outgoing link of that next-hop
N_j), the distance from N_i to each other neighbor N_j, and the set and H_i.neighbor refers to the neighbor of that nexthop.
of SRLGs traversed by the path D_opt(N_i, D). S should follow the
below procedure for every primary next-hop selected to reach D. This For a particular destination router D, let S have already computed
set of primary next-hops is represented P_1 to P_p. This procedure D_opt(S, D), and for each neighbor N_i, D_opt(N_i, D), D_opt(N_i, S),
finds the alternate next-hop(s) for P_i. and D_opt(N_i, N_j), the distance from N_i to each other neighbor
N_j, and the set of SRLGs traversed by the path D_opt(N_i, D). S
should follow the below procedure for every primary next-hop selected
to reach D. This set of primary next-hops is represented P_1 to P_p.
This procedure finds the alternate next-hop(s) for P_i.
First, initialize the alternate information for P_i as follows: First, initialize the alternate information for P_i as follows:
P_i.alt_next_hops = {} P_i.alt_next_hops = {}
P_i.alt_type = NONE P_i.alt_type = NONE
P_i.alt_link-protect = FALSE P_i.alt_link-protect = FALSE
P_i.alt_node-protect = FALSE P_i.alt_node-protect = FALSE
P_i.alt_srlg-protect = {} P_i.alt_srlg-protect = {}
For each candidate next-hop H_h, For each candidate next-hop H_h,
skipping to change at page 17, line 26 skipping to change at page 17, line 32
5. cand_type = LOOP-FREE. 5. cand_type = LOOP-FREE.
6. If H_h is a primary next-hop, set cand_type to PRIMARY. 6. If H_h is a primary next-hop, set cand_type to PRIMARY.
7. If H_h.link is not P_i.link, set cand_link-protect to TRUE. 7. If H_h.link is not P_i.link, set cand_link-protect to TRUE.
8. If D_opt(H_h.neighbor, D) < D_opt(H_h.neighbor, P_i.neighbor) + 8. If D_opt(H_h.neighbor, D) < D_opt(H_h.neighbor, P_i.neighbor) +
D_opt(P_i.neighbor, D), set cand_node-protect to TRUE. D_opt(P_i.neighbor, D), set cand_node-protect to TRUE.
9. If the router considers SRLGs, then set the cand_srlg-protect to 9. If the router considers SRLGs, then set the cand_srlg-protect to
the set of SRLGs traversed on the path from S via P_i to the set of SRLGs traversed on the path from S via P_i.link to
P_i.neighbor. Remove the set of SRLGs to which H_h belongs from P_i.neighbor. Remove the set of SRLGs to which H_h belongs from
cand_srlg-protect. Remove from cand_srlg-protect the set of cand_srlg-protect. Remove from cand_srlg-protect the set of
SRLGs traversed on the path from H_h.neighbor to D. Now SRLGs traversed on the path from H_h.neighbor to D. Now
cand_srlg-protect holds the set of SRLGs to which P_i belongs cand_srlg-protect holds the set of SRLGs to which P_i belongs
and that are not traversed on the path from S via H_h to D. and that are not traversed on the path from S via H_h to D.
10. If cand_type is PRIMARY, the router prefers other primary next- 10. If cand_type is PRIMARY, the router prefers other primary next-
hops for use as the alternate, and the P_i.alt_type is not hops for use as the alternate, and the P_i.alt_type is not
PRIMARY, goto Step 19. PRIMARY, goto Step 20.
11. If cand_node-protect is TRUE and P_i.alt_node-protect is FALSE, 11. If cand_type is not PRIMARY, P_i.alt_type is PRIMARY and the
goto Paragraph 19. router prefers other primary next-hops for use as the alternate,
then continue to the next candidate next-hop
12. If cand_link-protect is TRUE and P_i.alt_link-protect is FALSE, 12. If cand_node-protect is TRUE and P_i.alt_node-protect is FALSE,
goto Step 19. goto Paragraph 20.
13. If cand_srlg-protect has a better set of SRLGs than 13. If cand_link-protect is TRUE and P_i.alt_link-protect is FALSE,
P_i.alt_srlg-protect, goto Step 19. goto Step 20.
14. If cand_srlg-protect is different from P_i.alt_srlg-protect, 14. If cand_srlg-protect has a better set of SRLGs than
P_i.alt_srlg-protect, goto Step 20.
15. If cand_srlg-protect is different from P_i.alt_srlg-protect,
then select between H_h and P_i.alt_next_hops based upon then select between H_h and P_i.alt_next_hops based upon
distance, IP addresses, or any router-local tie-breaker. If H_h distance, IP addresses, or any router-local tie-breaker. If H_h
is preferred, then goto Step 19. Otherwise, skip H_h and is preferred, then goto Step 20. If P_i.alt_next_hops is
continue to the next candidate next-hop. preferred, skip H_h and continue to the next candidate next-hop.
15. If D_opt(H_h.neighbor, D) < D_opt(P_i.neighbor, D) and 16. If D_opt(H_h.neighbor, D) < D_opt(P_i.neighbor, D) and
D_opt(P_i.alt_next_hops, D) >= D_opt(P_i.neighbor, D), then H_h D_opt(P_i.alt_next_hops, D) >= D_opt(P_i.neighbor, D), then H_h
is a downstream alternate and P_i.alt_next_hops is simply an is a downstream alternate and P_i.alt_next_hops is simply an
LFA. Prefer H_h and goto Step 19. LFA. Prefer H_h and goto Step 20.
16. Based upon the alternate types, the alternate distances, IP 17. Based upon the alternate types, the alternate distances, IP
addresses, or other tie-breakers, decide if H_h is preferred to addresses, or other tie-breakers, decide if H_h is preferred to
P_i.alt_next_hops. If so, goto Step 19. P_i.alt_next_hops. If so, goto Step 20.
17. Decide if P_i.alt_next_hops is preferred to H_h. If so, then 18. Decide if P_i.alt_next_hops is preferred to H_h. If so, then
skip H_h and continue to the next candidate next-hop. skip H_h and continue to the next candidate next-hop.
18. Add H_h into P_i.alt_next_hops. Set P_i.alt_type to the better 19. Add H_h into P_i.alt_next_hops. Set P_i.alt_type to the better
type of H_h.alt_type and P_i.alt_type. Continue to the next type of H_h.alt_type and P_i.alt_type. Continue to the next
candidate next-hop. candidate next-hop.
19. Replace the P_i alternate next-hop set with H_h as follows: 20. Replace the P_i alternate next-hop set with H_h as follows:
P_i.alt_next_hops = {H_h} P_i.alt_next_hops = {H_h}
P_i.alt_type = cand_type P_i.alt_type = cand_type
P_i.alt_link-protect = cand_link-protect P_i.alt_link-protect = cand_link-protect
P_i.alt_node-protect = cand_node-protect P_i.alt_node-protect = cand_node-protect
P_i.alt_srlg-protect = cand_srlg-protect P_i.alt_srlg-protect = cand_srlg-protect
Continue to the next candidate next-hop. Continue to the next candidate next-hop.
3.7. A Simplification: Per-Next-Hop LFAs 3.7. LFA types and Trade-offs
LFAs can provide different amounts of protection and the decision
about which type to prefer is dependent upon network topology and
other techniques in use in the network. This section describes the
different protection levels and the trade-offs associated with each.
1. Primary Next-hop: When there are equal-cost primary next-hops,
using one as an alternate is guaranteed to not cause micro-loops
involving S. Traffic flows across the paths that the network will
converge to, but congestion may be experienced on the primary
paths since traffic is sent across fewer. All primary next-hops
are downstream paths.
2. Downstream Paths: A downstream path, unlike an LFA, is guaranteed
not to cause a micro-loop involving S regardless of the actual
failure detected. However, the expected coverage of such
alternates in a network is expected to be poor. All downstream
paths are LFAs.
3. LFA: An LFA can have good coverage of a network, depending on
topology. However, it is possible to get micro-loops involving S
if a more severe failure occurs than is protected against.
The different types of protection are abbreviated as LP (link-
protecting), NP (node-protecting) and SP (SRLG-protecting).
a. LP, NP, and SP: If such an alternate exists, it gives protection
against all failures.
b. LP and NP only: Many networks may handle SRLG failures via
another method or may focus on node and link failures as being
more common.
c. LP only: A network may handle node failures via a high
availability technique and be concerned primarily about
protecting the more common link failure case.
d. NP only: These only exist on interfaces that aren't point-to-
point. If link protection is handled in a different layer, then
an NP alternate may be acceptable.
3.8. A Simplification: Per-Next-Hop LFAs
It is possible to simplify the computation and use of LFAs when It is possible to simplify the computation and use of LFAs when
solely link protection is desired by considering and computing only solely link protection is desired by considering and computing only
one link-protecting LFA for each next-hop connected to the router. one link-protecting LFA for each next-hop connected to the router.
All prefixes that use that next-hop as a primary will use the LFA All prefixes that use that next-hop as a primary will use the LFA
computed for that next-hop as its LFA. computed for that next-hop as its LFA.
Even a prefix with multiple primary next-hops will have each primary Even a prefix with multiple primary next-hops will have each primary
next-hop protected individually by the primary next-hop's associated next-hop protected individually by the primary next-hop's associated
LFA. That associated LFA might or might not be another of the LFA. That associated LFA might or might not be another of the
skipping to change at page 19, line 39 skipping to change at page 20, line 41
specifically out of scope for this specification. specifically out of scope for this specification.
4.1. Terminating Use of Alternate 4.1. Terminating Use of Alternate
A router MUST limit the amount of time an alternate next-hop is used 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 after the primary next-hop has become unavailable. This ensures that
the router will start using the new primary next-hops. It ensures the router will start using the new primary next-hops. It ensures
that all possible transient conditions are removed and the network that all possible transient conditions are removed and the network
converges according to the deployed routing protocol. converges according to the deployed routing protocol.
There are techniques available to handle the micro-forwarding loops
that can occur in a networking during convergence.
A router that implements [I-D.ietf-rtgwg-microloop-analysis] SHOULD A router that implements [I-D.ietf-rtgwg-microloop-analysis] SHOULD
follow the rules given there for terminating the use of an alternate. follow the rules given there for terminating the use of an alternate.
A router that implements [I-D.francois-ordered-fib] SHOULD follow the A router that implements [I-D.francois-ordered-fib] SHOULD follow the
rules given there for terminating the use of an alternate. rules given there for terminating the use of an alternate.
It is desirable to avoid micro-forwarding loops involving S. An It is desirable to avoid micro-forwarding loops involving S. An
example illustrating the problem is given in Figure 5. If the link example illustrating the problem is given in Figure 5. If the link
from S to E fails, S will use N1 as an alternate and S will compute 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 N2 as the new primary next-hop to reach D. If S starts using N2 as
skipping to change at page 25, line 39 skipping to change at page 26, line 43
draft-francois-ordered-fib-02 (work in progress), draft-francois-ordered-fib-02 (work in progress),
October 2006. October 2006.
[I-D.ietf-isis-link-attr] [I-D.ietf-isis-link-attr]
Vasseur, J. and S. Previdi, "Definition of an IS-IS Link Vasseur, J. and S. Previdi, "Definition of an IS-IS Link
Attribute sub-TLV", draft-ietf-isis-link-attr-03 (work in Attribute sub-TLV", draft-ietf-isis-link-attr-03 (work in
progress), February 2007. progress), February 2007.
[I-D.ietf-isis-wg-multi-topology] [I-D.ietf-isis-wg-multi-topology]
Przygienda, T., "M-ISIS: Multi Topology (MT) Routing in Przygienda, T., "M-ISIS: Multi Topology (MT) Routing in
IS-IS", draft-ietf-isis-wg-multi-topology-11 (work in IS-IS", draft-ietf-isis-wg-multi-topology-12 (work in
progress), October 2005. progress), November 2007.
[I-D.ietf-ospf-mt-ospfv3] [I-D.ietf-ospf-mt-ospfv3]
Mirtorabi, S. and A. Roy, "Multi-topology routing in Mirtorabi, S. and A. Roy, "Multi-topology routing in
OSPFv3 (MT-OSPFv3)", draft-ietf-ospf-mt-ospfv3-03 (work in OSPFv3 (MT-OSPFv3)", draft-ietf-ospf-mt-ospfv3-03 (work in
progress), July 2007. progress), July 2007.
[I-D.ietf-ospf-ospfv3-update] [I-D.ietf-ospf-ospfv3-update]
Ferguson, D., "OSPF for IPv6", Ferguson, D., "OSPF for IPv6",
draft-ietf-ospf-ospfv3-update-17 (work in progress), draft-ietf-ospf-ospfv3-update-17 (work in progress),
August 2007. August 2007.
skipping to change at page 28, line 8 skipping to change at page 29, line 8
is less than 35, the cost of the path in area 1. Therefore, A uses is less than 35, the cost of the path in area 1. Therefore, A uses
the path from area 2 and directs traffic to F. The path from F in the path from area 2 and directs traffic to F. The path from F in
area 2 goes to B. B is also an ABR and learns the ASBR from both area 2 goes to B. B is also an ABR and learns the ASBR from both
areas 1 and area 2; B's path via area 1 is shorter (cost 20) than B's areas 1 and area 2; B's path via area 1 is shorter (cost 20) than B's
path via area 2 (cost 25). Therefore, B uses the path from area 1 path via area 2 (cost 25). Therefore, B uses the path from area 1
that connects to S. that connects to S.
Authors' Addresses Authors' Addresses
Alia K. Atlas (editor) Alia K. Atlas (editor)
Google, Inc. BT
One Broadway, 7th Floor
Cambridge, MA 02142
USA
Email: akatlas@google.com Email: alia.atlas@bt.com
Alex Zinin (editor) Alex Zinin (editor)
Alcatel Alcatel
701 E Middlefield Rd. 701 E Middlefield Rd.
Mountain View, CA 94043 Mountain View, CA 94043
USA USA
Email: alex.zinin@alcatel.com Email: alex.zinin@alcatel.com
Raveendra Torvi Raveendra Torvi
 End of changes. 35 change blocks. 
121 lines changed or deleted 175 lines changed or added

This html diff was produced by rfcdiff 1.34. The latest version is available from http://tools.ietf.org/tools/rfcdiff/