draft-ietf-rtgwg-mrt-frr-architecture-06.txt   draft-ietf-rtgwg-mrt-frr-architecture-07.txt 
Routing Area Working Group A. Atlas, Ed. Routing Area Working Group A. Atlas, Ed.
Internet-Draft R. Kebler Internet-Draft R. Kebler
Intended status: Standards Track C. Bowers Intended status: Standards Track C. Bowers
Expires: January 4, 2016 Juniper Networks Expires: April 17, 2016 Juniper Networks
G. Enyedi G. Enyedi
A. Csaszar A. Csaszar
J. Tantsura J. Tantsura
Ericsson Ericsson
R. White R. White
VCE VCE
July 3, 2015 October 15, 2015
An Architecture for IP/LDP Fast-Reroute Using Maximally Redundant Trees An Architecture for IP/LDP Fast-Reroute Using Maximally Redundant Trees
draft-ietf-rtgwg-mrt-frr-architecture-06 draft-ietf-rtgwg-mrt-frr-architecture-07
Abstract Abstract
With increasing deployment of Loop-Free Alternates (LFA) [RFC5286], With increasing deployment of Loop-Free Alternates (LFA) [RFC5286],
it is clear that a complete solution for IP and LDP Fast-Reroute is it is clear that a complete solution for IP and LDP Fast-Reroute is
required. This specification provides that solution. IP/LDP Fast- required. This specification provides that solution. IP/LDP Fast-
Reroute with Maximally Redundant Trees (MRT-FRR) is a technology that Reroute with Maximally Redundant Trees (MRT-FRR) is a technology that
gives link-protection and node-protection with 100% coverage in any gives link-protection and node-protection with 100% coverage in any
network topology that is still connected after the failure. network topology that is still connected after the failure.
skipping to change at page 1, line 47 skipping to change at page 1, line 47
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
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 as "work in progress."
This Internet-Draft will expire on January 4, 2016. This Internet-Draft will expire on April 17, 2016.
Copyright Notice Copyright Notice
Copyright (c) 2015 IETF Trust and the persons identified as the Copyright (c) 2015 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 3, line 29 skipping to change at page 3, line 29
10. Inter-area Forwarding Behavior . . . . . . . . . . . . . . . 23 10. Inter-area Forwarding Behavior . . . . . . . . . . . . . . . 23
10.1. ABR Forwarding Behavior with MRT LDP Label Option 1A . . 23 10.1. ABR Forwarding Behavior with MRT LDP Label Option 1A . . 23
10.1.1. Motivation for Creating the Rainbow-FEC . . . . . . 24 10.1.1. Motivation for Creating the Rainbow-FEC . . . . . . 24
10.2. ABR Forwarding Behavior with IP Tunneling (option 2) . . 24 10.2. ABR Forwarding Behavior with IP Tunneling (option 2) . . 24
10.3. ABR Forwarding Behavior with LDP Label option 1B . . . . 25 10.3. ABR Forwarding Behavior with LDP Label option 1B . . . . 25
11. Prefixes Multiply Attached to the MRT Island . . . . . . . . 26 11. Prefixes Multiply Attached to the MRT Island . . . . . . . . 26
11.1. Protecting Multi-Homed Prefixes using Tunnel Endpoint 11.1. Protecting Multi-Homed Prefixes using Tunnel Endpoint
Selection . . . . . . . . . . . . . . . . . . . . . . . 28 Selection . . . . . . . . . . . . . . . . . . . . . . . 28
11.2. Protecting Multi-Homed Prefixes using Named Proxy-Nodes 29 11.2. Protecting Multi-Homed Prefixes using Named Proxy-Nodes 29
11.2.1. Computing if an Island Neighbor (IN) is loop-free . 31 11.2.1. Computing if an Island Neighbor (IN) is loop-free . 31
11.3. MRT Alternates for Destinations Outside the MRT Island . 32 11.3. MRT Alternates for Destinations Outside the MRT Island . 33
12. Network Convergence and Preparing for the Next Failure . . . 33 12. Network Convergence and Preparing for the Next Failure . . . 34
12.1. Micro-forwarding loop prevention and MRTs . . . . . . . 33 12.1. Micro-forwarding loop prevention and MRTs . . . . . . . 34
12.2. MRT Recalculation . . . . . . . . . . . . . . . . . . . 33 12.2. MRT Recalculation . . . . . . . . . . . . . . . . . . . 34
13. Implementation Status . . . . . . . . . . . . . . . . . . . . 34 13. Implementation Status . . . . . . . . . . . . . . . . . . . . 35
14. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 36 14. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 37
15. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 36 15. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 37
16. Security Considerations . . . . . . . . . . . . . . . . . . . 36 16. Security Considerations . . . . . . . . . . . . . . . . . . . 37
17. References . . . . . . . . . . . . . . . . . . . . . . . . . 36 17. References . . . . . . . . . . . . . . . . . . . . . . . . . 37
17.1. Normative References . . . . . . . . . . . . . . . . . . 36 17.1. Normative References . . . . . . . . . . . . . . . . . . 37
17.2. Informative References . . . . . . . . . . . . . . . . . 37 17.2. Informative References . . . . . . . . . . . . . . . . . 37
Appendix A. General Issues with Area Abstraction . . . . . . . . 39 Appendix A. General Issues with Area Abstraction . . . . . . . . 40
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 40 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 41
1. Introduction 1. Introduction
This document gives a complete solution for IP/LDP fast-reroute This document gives a complete solution for IP/LDP fast-reroute
[RFC5714]. MRT-FRR creates two alternate trees separate from the [RFC5714]. MRT-FRR creates two alternate trees separate from the
primary next-hop forwarding used during stable operation. These two primary next-hop forwarding used during stable operation. These two
trees are maximally diverse from each other, providing link and node trees are maximally diverse from each other, providing link and node
protection for 100% of paths and failures as long as the failure does protection for 100% of paths and failures as long as the failure does
not cut the network into multiple pieces. This document defines the not cut the network into multiple pieces. This document defines the
architecture for IP/LDP fast-reroute with MRT. The associated architecture for IP/LDP fast-reroute with MRT. The associated
skipping to change at page 7, line 24 skipping to change at page 7, line 24
These can be computed in 2-connected graphs. These can be computed in 2-connected graphs.
Maximally Redundant Trees (MRT): A pair of trees where the path Maximally Redundant Trees (MRT): A pair of trees where the path
from any node X to the root R along the first tree and the path from any node X to the root R along the first tree and the path
from the same node X to the root along the second tree share the from the same node X to the root along the second tree share the
minimum number of nodes and the minimum number of links. Each minimum number of nodes and the minimum number of links. Each
such shared node is a cut-vertex. Any shared links are cut-links. such shared node is a cut-vertex. Any shared links are cut-links.
Any RT is an MRT but many MRTs are not RTs. Any RT is an MRT but many MRTs are not RTs.
MRT-Red: MRT-Red is used to describe one of the two MRTs; it is MRT-Red: MRT-Red is used to describe one of the two MRTs; it is
used to described the associated forwarding topology and MT-ID. used to described the associated forwarding topology and MPLS MT-
Specifically, MRT-Red is the decreasing MRT where links in the ID. Specifically, MRT-Red is the decreasing MRT where links in
GADAG are taken in the direction from a higher topologically the GADAG are taken in the direction from a higher topologically
ordered node to a lower one. ordered node to a lower one.
MRT-Blue: MRT-Blue is used to describe one of the two MRTs; it is MRT-Blue: MRT-Blue is used to describe one of the two MRTs; it is
used to described the associated forwarding topology and MT-ID. used to described the associated forwarding topology and MPLS MT-
Specifically, MRT-Blue is the increasing MRT where links in the ID. Specifically, MRT-Blue is the increasing MRT where links in
GADAG are taken in the direction from a lower topologically the GADAG are taken in the direction from a lower topologically
ordered node to a higher one. ordered node to a higher one.
Rainbow MRT: It is useful to have an MT-ID that refers to the Rainbow MRT: It is useful to have an MPLS MT-ID that refers to the
multiple MRT topologies and to the default topology. This is multiple MRT topologies and to the default topology. This is
referred to as the Rainbow MRT MT-ID and is used by LDP to reduce referred to as the Rainbow MRT MPLS MT-ID and is used by LDP to
signaling and permit the same label to always be advertised to all reduce signalling and permit the same label to always be
peers for the same (MT-ID, Prefix). advertised to all peers for the same (MT-ID, Prefix).
MRT Island: The set of routers that support a particular MRT MRT Island: The set of routers that support a particular MRT
profile and the links connecting them that support MRT. profile and the links connecting them that support MRT.
Island Border Router (IBR): A router in the MRT Island that is Island Border Router (IBR): A router in the MRT Island that is
connected to a router not in the MRT Island and both routers are connected to a router not in the MRT Island and both routers are
in a common area or level. in a common area or level.
Island Neighbor (IN): A router that is not in the MRT Island but is Island Neighbor (IN): A router that is not in the MRT Island but is
adjacent to an IBR and in the same area/level as the IBR. adjacent to an IBR and in the same area/level as the IBR.
skipping to change at page 12, line 28 skipping to change at page 12, line 28
B. MRT IPv6 Tunnels B. MRT IPv6 Tunnels
6.1.1. MRT LDP labels 6.1.1. MRT LDP labels
We consider two options for the MRT forwarding mechanisms using MRT We consider two options for the MRT forwarding mechanisms using MRT
LDP labels. LDP labels.
6.1.1.1. Topology-scoped FEC encoded using a single label (Option 1A) 6.1.1.1. Topology-scoped FEC encoded using a single label (Option 1A)
[I-D.ietf-mpls-ldp-multi-topology] provides a mechanism to distribute [RFC7307] provides a mechanism to distribute FEC-Label bindings
FEC-Label bindings scoped to a given topology (represented by MT-ID). scoped to a given MPLS topology (represented by MPLS MT-ID). To use
To use multi-topology LDP to create MRT forwarding topologies, we multi-topology LDP to create MRT forwarding topologies, we associate
associate two MT-IDs with the MRT-Red and MRT-Blue forwarding two MPLS MT-IDs with the MRT-Red and MRT-Blue forwarding topologies,
topologies, in addition to the default shortest path forwarding in addition to the default shortest path forwarding topology with MT-
topology with MT-ID=0. ID=0.
With this forwarding mechanism, a single label is distributed for With this forwarding mechanism, a single label is distributed for
each topology-scoped FEC. For a given FEC in the default topology each topology-scoped FEC. For a given FEC in the default topology
(call it default-FEC-A), two additional topology-scoped FECs would be (call it default-FEC-A), two additional topology-scoped FECs would be
created, corresponding to the Red and Blue MRT forwarding topologies created, corresponding to the Red and Blue MRT forwarding topologies
(call them red-FEC-A and blue-FEC-A). A router supporting this MRT (call them red-FEC-A and blue-FEC-A). A router supporting this MRT
transit forwarding mechanism advertises a different FEC-label binding transit forwarding mechanism advertises a different FEC-label binding
for each of the three topology-scoped FECs. When a packet is for each of the three topology-scoped FECs. When a packet is
received with a label corresponding to red-FEC-A (for example), an received with a label corresponding to red-FEC-A (for example), an
MRT transit router will determine the next-hop for the MRT-Red MRT transit router will determine the next-hop for the MRT-Red
skipping to change at page 13, line 11 skipping to change at page 13, line 11
along the MRT. We will take advantage of this property when along the MRT. We will take advantage of this property when
specifying how to carry LDP traffic on MRT paths using multi-topology specifying how to carry LDP traffic on MRT paths using multi-topology
LDP labels. LDP labels.
This approach is very simple for hardware to support. However, it This approach is very simple for hardware to support. However, it
reduces the label space for other uses, and it increases the memory reduces the label space for other uses, and it increases the memory
needed to store the labels and the communication required by LDP to needed to store the labels and the communication required by LDP to
distribute FEC-label bindings. distribute FEC-label bindings.
This forwarding option uses the LDP signaling extensions described in This forwarding option uses the LDP signaling extensions described in
[I-D.ietf-mpls-ldp-multi-topology]. The MRT-specific LDP extensions [RFC7307]. The MRT-specific LDP extensions required to support this
required to support this option are described in option are described in [I-D.ietf-mpls-ldp-mrt].
[I-D.ietf-mpls-ldp-mrt].
6.1.1.2. Topology and FEC encoded using a two label stack (Option 1B) 6.1.1.2. Topology and FEC encoded using a two label stack (Option 1B)
With this forwarding mechanism, a two label stack is used to encode With this forwarding mechanism, a two label stack is used to encode
the topology and the FEC of the packet. The top label (topology-id the topology and the FEC of the packet. The top label (topology-id
label) identifies the MRT forwarding topology, while the second label label) identifies the MRT forwarding topology, while the second label
(FEC label) identifies the FEC. The top label would be a new FEC (FEC label) identifies the FEC. The top label would be a new FEC
type with two values corresponding to MRT Red and Blue topologies. type with two values corresponding to MRT Red and Blue topologies.
When an MRT transit router receives a packet with a topology-id When an MRT transit router receives a packet with a topology-id
skipping to change at page 22, line 8 skipping to change at page 22, line 8
MRT-Red and MRT-Blue Loopback Addresses have not been defined. MRT-Red and MRT-Blue Loopback Addresses have not been defined.
8.3. Default MRT profile 8.3. Default MRT profile
The following set of options defines the default MRT Profile. The The following set of options defines the default MRT Profile. The
default MRT profile is indicated by the MRT Profile ID value of 0. default MRT profile is indicated by the MRT Profile ID value of 0.
MRT Algorithm: MRT Lowpoint algorithm defined in MRT Algorithm: MRT Lowpoint algorithm defined in
[I-D.ietf-rtgwg-mrt-frr-algorithm]. [I-D.ietf-rtgwg-mrt-frr-algorithm].
MRT-Red MT-ID: TBA-MRT-ARCH-1, final value assigned by IANA MRT-Red MPLS MT-ID: [I-D.ietf-mpls-ldp-mrt] contains the IANA
allocated from the LDP MT-ID space (prototype experiments have request for allocation of this value from the MPLS Multi-Topology
used 3997) Identifiers Registry. Prototype experiments have used a value of
3997.
MRT-Blue MT-ID: TBA-MRT-ARCH-2, final value assigned by IANA MRT-Blue MPLS MT-ID: [I-D.ietf-mpls-ldp-mrt] contains the IANA
allocated from the LDP MT-ID space (prototype experiments have request for allocation of this value from the MPLS Multi-Topology
used 3998) Identifiers Registry. Prototype experiments have used a value of
3998.
GADAG Root Selection Policy: Among the routers in the MRT Island GADAG Root Selection Policy: Among the routers in the MRT Island
and with the highest priority advertised, an implementation MUST and with the highest priority advertised, an implementation MUST
pick the router with the highest Router ID to be the GADAG root. pick the router with the highest Router ID to be the GADAG root.
Forwarding Mechanisms: MRT LDP Labels Forwarding Mechanisms: MRT LDP Labels
Recalculation: Recalculation of MRTs SHOULD occur as described in Recalculation: Recalculation of MRTs SHOULD occur as described in
Section 12.2. This allows the MRT forwarding topologies to Section 12.2. This allows the MRT forwarding topologies to
support IP/LDP fast-reroute traffic. support IP/LDP fast-reroute traffic.
skipping to change at page 22, line 50 skipping to change at page 22, line 52
The FEC-label bindings for the default shortest-path based MT-ID 0 The FEC-label bindings for the default shortest-path based MT-ID 0
MUST still be sent (even though it could be inferred from the Rainbow MUST still be sent (even though it could be inferred from the Rainbow
FEC-label bindings) to ensure continuous operation of normal LDP FEC-label bindings) to ensure continuous operation of normal LDP
forwarding. The Rainbow MRT MT-ID is defined to provide an easy way forwarding. The Rainbow MRT MT-ID is defined to provide an easy way
to handle the special signaling that is needed at ABRs or LBRs. It to handle the special signaling that is needed at ABRs or LBRs. It
avoids the problem of needing to signal different MPLS labels for the avoids the problem of needing to signal different MPLS labels for the
same FEC. Because the Rainbow MRT MT-ID is used only by ABRs/LBRs or same FEC. Because the Rainbow MRT MT-ID is used only by ABRs/LBRs or
an LDP egress router, it is not MRT profile specific. an LDP egress router, it is not MRT profile specific.
[I-D.ietf-mpls-ldp-mrt] contains the IANA request for the Rainbow MRT [I-D.ietf-mpls-ldp-mrt] contains the IANA request for the Rainbow MRT
MT-ID. MPLS MT-ID.
10. Inter-area Forwarding Behavior 10. Inter-area Forwarding Behavior
Unless otherwise specified, in this section we will use the terms Unless otherwise specified, in this section we will use the terms
area and ABR to indicate either an OSPF area and OSPF ABR or ISIS area and ABR to indicate either an OSPF area and OSPF ABR or ISIS
level and ISIS LBR. level and ISIS LBR.
An ABR/LBR has two forwarding roles. First, it forwards traffic An ABR/LBR has two forwarding roles. First, it forwards traffic
within areas. Second, it forwards traffic from one area into within areas. Second, it forwards traffic from one area into
another. These same two roles apply for MRT transit traffic. another. These same two roles apply for MRT transit traffic.
skipping to change at page 27, line 6 skipping to change at page 27, line 6
How a computing router S determines its local MRT Island for each How a computing router S determines its local MRT Island for each
supported MRT profile is already discussed in Section 7. supported MRT profile is already discussed in Section 7.
There are two types of prefixes or FECs that may be multiply attached There are two types of prefixes or FECs that may be multiply attached
to an MRT Island. The first type are multi-homed prefixes that to an MRT Island. The first type are multi-homed prefixes that
usually connect at a domain or protocol boundary. The second type usually connect at a domain or protocol boundary. The second type
represent routers that do not support the profile for the MRT Island. represent routers that do not support the profile for the MRT Island.
The key difference is whether the traffic, once out of the MRT The key difference is whether the traffic, once out of the MRT
Island, remains in the same area/level and might reenter the MRT Island, remains in the same area/level and might re-enter the MRT
Island if a loop-free exit point is not selected. Island if a loop-free exit point is not selected.
FRR using LFA has the useful property that it is able to protect FRR using LFA has the useful property that it is able to protect
multi-homed prefixes against ABR failure. For instance, if a prefix multi-homed prefixes against ABR failure. For instance, if a prefix
from the backbone is available via both ABR A and ABR B, if A fails, from the backbone is available via both ABR A and ABR B, if A fails,
then the traffic should be redirected to B. This can be accomplished then the traffic should be redirected to B. This can be accomplished
with MRT FRR as well. with MRT FRR as well.
If ASBR protection is desired, this has additional complexities if If ASBR protection is desired, this has additional complexities if
the ASBRs are in different areas. Similarly, protecting labeled BGP the ASBRs are in different areas. Similarly, protecting labeled BGP
skipping to change at page 27, line 45 skipping to change at page 27, line 45
prefix. prefix.
The second is to use a proxy-node, that can be named via MPLS label The second is to use a proxy-node, that can be named via MPLS label
or IP address, and pick the appropriate label or IP address to reach or IP address, and pick the appropriate label or IP address to reach
it on either MRT-Blue or MRT-Red as appropriate to avoid the failure it on either MRT-Blue or MRT-Red as appropriate to avoid the failure
point. A proxy-node can represent a destination prefix that can be point. A proxy-node can represent a destination prefix that can be
attached to the MRT Island via at least two routers. It is termed a attached to the MRT Island via at least two routers. It is termed a
named proxy-node if there is a way that traffic can be encapsulated named proxy-node if there is a way that traffic can be encapsulated
to reach specifically that proxy-node; this could be because there is to reach specifically that proxy-node; this could be because there is
an LDP FEC for the associated prefix or because MRT-Red and MRT-Blue an LDP FEC for the associated prefix or because MRT-Red and MRT-Blue
IP addresses are advertised in an as-yet undefined fashion for that IP addresses are advertised (in an as-yet undefined fashion) for that
proxy-node. Traffic to a named proxy-node may take a different path proxy-node. Traffic to a named proxy-node may take a different path
than traffic to the attaching router; traffic is also explicitly than traffic to the attaching router; traffic is also explicitly
forwarded from the attaching router along a predetermined interface forwarded from the attaching router along a predetermined interface
towards the relevant prefixes. towards the relevant prefixes.
For IP traffic, multi-homed prefixes can use tunnel endpoint For IP traffic, multi-homed prefixes can use tunnel endpoint
selection. For IP traffic that is destined to a router outside the selection. For IP traffic that is destined to a router outside the
MRT Island, if that router is the egress for a FEC advertised into MRT Island, if that router is the egress for a FEC advertised into
the MRT Island, then the named proxy-node approach can be used. the MRT Island, then the named proxy-node approach can be used.
skipping to change at page 29, line 38 skipping to change at page 29, line 38
4. If not, then is there a router B that is loop-free to reach p 4. If not, then is there a router B that is loop-free to reach p
while avoiding S and the link from S to F? If so, select B as while avoiding S and the link from S to F? If so, select B as
the endpoint and the MRT alternate for reaching B from S that the endpoint and the MRT alternate for reaching B from S that
avoid the link (S,F). avoid the link (S,F).
The tunnel endpoint selected will receive a packet destined to itself The tunnel endpoint selected will receive a packet destined to itself
and, being the egress, will pop that MPLS label (or have signaled and, being the egress, will pop that MPLS label (or have signaled
Implicit Null) and forward based on what is underneath. This Implicit Null) and forward based on what is underneath. This
suffices for IP traffic since the tunnel endpoint can use the IP suffices for IP traffic since the tunnel endpoint can use the IP
header of the original packet to continue forwarding the packet. header of the original packet to continue forwarding the packet.
However, tunneling will not work for LDP traffic without targeted LDP However, tunnelling of LDP traffic requires targeted LDP sessions for
sesssions for learning the FEC-label binding at the tunnel endpoint. learning the FEC-label binding at the tunnel endpoint.
11.2. Protecting Multi-Homed Prefixes using Named Proxy-Nodes 11.2. Protecting Multi-Homed Prefixes using Named Proxy-Nodes
Instead, the named proxy-node method works with LDP traffic without Instead, the named proxy-node method works with LDP traffic without
the need for targeted LDP sessions. It also has a clear advantage the need for targeted LDP sessions. It also has a clear advantage
over tunnel endpoint selection, in that it is possible to explicitly over tunnel endpoint selection, in that it is possible to explicitly
forward from the MRT Island along an interface to a loop-free island forward from the MRT Island along an interface to a loop-free island
neighbor when that interface may not be a primary next-hop. neighbor when that interface may not be a primary next-hop.
A named proxy-node represents one or more destinations and, for LDP A named proxy-node represents one or more destinations and, for LDP
forwarding, has a FEC associated with it that is signaled into the forwarding, has a FEC associated with it that is signalled into the
MRT Island. Therefore, it is possible to explicitly label packets to MRT Island. Therefore, it is possible to explicitly label packets to
go to (MRT-Red, FEC) or (MRT-Blue, FEC); at the border of the MRT go to (MRT-Red, FEC) or (MRT-Blue, FEC); at the border of the MRT
Island, the label will swap to meaning (MT-ID 0, FEC). It would be Island, the label will swap to meaning (MT-ID 0, FEC). It would be
possible to have named proxy-nodes for IP forwarding, but this would possible to have named proxy-nodes for IP forwarding, but this would
require extensions to signal two IP addresses to be associated with require extensions to signal two IP addresses to be associated with
MRT-Red and MRT-Blue for the proxy-node. A named proxy-node can be MRT-Red and MRT-Blue for the proxy-node. A named proxy-node can be
uniquely represented by the two routers in the MRT Island to which it uniquely represented by the two routers in the MRT Island to which it
is connected. The extensions to signal such IP addresses are not is connected. The extensions to signal such IP addresses are not
defined in [I-D.ietf-ospf-mrt]. The details of what label-bindings defined in [I-D.ietf-ospf-mrt]. The details of what label-bindings
must be originated are described in [I-D.ietf-mpls-ldp-mrt]. must be originated are described in [I-D.ietf-mpls-ldp-mrt].
skipping to change at page 30, line 44 skipping to change at page 30, line 44
each prefix-advertising router is the announced cost to the prefix. each prefix-advertising router is the announced cost to the prefix.
The second set are those routers in the MRT Island that are connected The second set are those routers in the MRT Island that are connected
to routers not in the MRT Island but in the same area/level; such to routers not in the MRT Island but in the same area/level; such
routers will be defined as Island Border Routers (IBRs). The routers routers will be defined as Island Border Routers (IBRs). The routers
connected to the IBRs that are not in the MRT Island and are in the connected to the IBRs that are not in the MRT Island and are in the
same area/level as the MRT island are Island Neighbors(INs). same area/level as the MRT island are Island Neighbors(INs).
Since packets sent to the named proxy-node along MRT-Red or MRT-Blue Since packets sent to the named proxy-node along MRT-Red or MRT-Blue
may come from any router inside the MRT Island, it is necessary that may come from any router inside the MRT Island, it is necessary that
whatever router to which an IBR forwards the packet be loop-free with whatever router to which an IBR forwards the packet be loop-free with
regard to the whole MRT Island for the destination. Thus, an IBR is respect to the whole MRT Island for the destination. Thus, an IBR is
a candidate router only if it possesses at least one IN whose a candidate router only if it possesses at least one IN whose
shortest path to the prefix does not enter the MRT Island. A method shortest path to the prefix does not enter the MRT Island. A method
for identifying loop-free Island Neighbors(LFINs) is discussed below. for identifying loop-free Island Neighbors(LFINs) is discussed below.
The named-proxy-cost assigned to each (IBR, IN) pair is cost(IBR, IN) The named-proxy-cost assigned to each (IBR, IN) pair is cost(IBR, IN)
+ D_opt(IN, prefix). + D_opt(IN, prefix).
From the set of prefix-advertising routers and the set of IBRs with From the set of prefix-advertising routers and the set of IBRs with
at least one LFIN, the two routers with the lowest named-proxy-cost at least one LFIN, the two routers with the lowest named-proxy-cost
are selected. Ties are broken based upon the lowest Router ID. For are selected. Ties are broken based upon the lowest Router ID. For
ease of discussion, the two selected routers will be referred to as ease of discussion, the two selected routers will be referred to as
proxy-node attachment routers. proxy-node attachment routers.
A proxy-node attachment router has a special forwarding role. When a A proxy-node attachment router has a special forwarding role. When a
packet is received destined to (MRT-Red, prefix) or (MRT-Blue, packet is received destined to (MRT-Red, prefix) or (MRT-Blue,
prefix), if the proxy-node attachment router is an IBR, it MUST swap prefix), if the proxy-node attachment router is an IBR, it MUST swap
to the default topology (e.g. swap to the label for (MT-ID 0, prefix) to the shortest path forwarding topology (e.g. swap to the label for
or remove the outer IP encapsulation) and forward the packet to the (MT-ID 0, prefix) or remove the outer IP encapsulation) and forward
IN whose cost was used in the selection. If the proxy-node the packet to the IN whose cost was used in the selection. If the
attachment router is not an IBR, then the packet MUST be removed from proxy-node attachment router is not an IBR, then the packet MUST be
the MRT forwarding topology and sent along the interface(s) that removed from the MRT forwarding topology and sent along the
caused the router to advertise the prefix; this interface might be interface(s) that caused the router to advertise the prefix; this
out of the area/level/AS. interface might be out of the area/level/AS.
11.2.1. Computing if an Island Neighbor (IN) is loop-free 11.2.1. Computing if an Island Neighbor (IN) is loop-free
As discussed, the Island Neighbor needs to be loop-free with regard As discussed above, the Island Neighbor needs to be loop-free with
to the whole MRT Island for the destination. Conceptually, the cost respect to the whole MRT Island for the destination. This can be
of transiting the MRT Island should be regarded as 0. This can be accomplished by running the usual SPF algorithm while keeping track
done by collapsing the MRT Island into a single node, as seen in of which shortest paths have passed through the MRT island. Pseudo-
Figure 4, and then computing SPFs from each Island Neighbor and from code for this is shown in Figure 4. The Island_Marking_SPF() is run
the MRT Island itself. for each IN that needs to be evaluated for the loop-free condition,
with the IN as the spf_root. Whether or not an IN is loop-free with
[G]---[E]---(V)---(U)---(T) respect to the MRT island can then be determined by evaluating
| \ | | | node.PATH_HITS_ISLAND for each destination of interest.
| \ | | |
| \ | | |
[H]---[F]---(R)---(S)----|
(1) Network Graph with Partial Deployment
[E],[F],[G],[H] : No support for MRT
(R),(S),(T),(U),(V): MRT Island - supports MRT
[G]---[E]----| |---(V)---(U)---(T) Island_Marking_SPF(spf_root)
| \ | | | | | Initialize spf_heap to empty
| \ | ( MRT Island ) [ proxy ] | | Initialize nodes' spf_metric to infinity and next_hops to empty
| \ | | | | | and PATH_HITS_ISLAND to false
[H]---[F]----| |---(R)---(S)----| spf_root.spf_metric = 0
insert(spf_heap, spf_root)
while (spf_heap is not empty)
min_node = remove_lowest(spf_heap)
foreach interface intf of min_node
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric
intf.remote_node.spf_metric = path_metric
if min_node is spf_root
intf.remote_node.next_hops = make_list(intf)
else
intf.remote_node.next_hops = min_node.next_hops
if intf.remote_node.IN_MRT_ISLAND
intf.remote_node.PATH_HITS_ISLAND = true
else
intf.remote_node.PATH_HITS_ISLAND =
min_node.PATH_HITS_ISLAND
insert_or_update(spf_heap, intf.remote_node)
else if path_metric == intf.remote_node.spf_metric
if min_node is spf_root
add_to_list(intf.remote_node.next_hops, intf)
else
add_list_to_list(intf.remote_node.next_hops,
min_node.next_hops)
if intf.remote_node.IN_MRT_ISLAND
intf.remote_node.PATH_HITS_ISLAND = true
else
intf.remote_node.PATH_HITS_ISLAND =
min_node.PATH_HITS_ISLAND
(2) Graph for determining (3) Graph for MRT computation Figure 4
loop-free neighbors
Figure 4: Computing alternates to destinations outside the MRT Island It is also possible that a given prefix is originated by a
combination of non-island routers and island routers. The results of
the Island_Marking_SPF computation can be used to determine if the
shortest path from an IN to reach that prefix hits the MRT island.
The shortest path for the IN to reach prefix P is determined by the
total cost to reach prefix P, which is the sum of the cost for the IN
to reach a prefix-advertising node and the cost with which that node
advertises the prefix. The path with the minimum total cost to
prefix P is chosen. If the prefix-advertising node for that minimum
total cost path has PATH_HITS_ISLAND set to True, then the IN is not
loop-free with respect to the MRT Island for reaching prefix P. If
there multiple minimum total cost paths to reach prefix P, then all
of the prefix-advertising routers involved in the minimum total cost
paths MUST have PATH_HITS_ISLAND set to False for the IN to be
considered loop-free to reach P.
The simple way to do this without manipulating the topology is to Note that there are other computations that could be used to
compute the SPFs from each IN and a node in the MRT Island (e.g. the determine if paths from a given IN _might_ pass through the MRT
GADAG root), but use a link metric of 0 for all links between routers Island for a given prefix or destination. For example, a previous
in the MRT Island. The distances computed via SPF this way will be version of this draft specified running the SPF algorithm on modified
refered to as Dist_mrt0. topology which treats the MRT island as a single node (with intra-
island links set to zero cost) in order to provide input to
computations to determine if the path from IN to non-island
destination hits the MRT island in this modified topology. This
computation is enough to guarantee that a path will not hit the MRT
island in the original topology. However, it is possible that a path
which is disqualified for hitting the MRT island in the modified
topology will not actually hit the MRT Island in the original
topology. The algorithm described in Island_Marking_SPF() above does
not modify the original topology, and will only disqualify a path if
the actual path does in fact hit the MRT island.
An IN is loop-free with respect to a destination D if: Dist_mrt0(IN, Since all routers need to come to the same conclusion about which
D) < Dist_mrt0(IN, MRT Island Router) + Dist_mrt0(MRT Island Router, routers qualify as LFINs, this specification requires that all
D). Any router in the MRT Island can be used since the cost of routers computing LFINs MUST use an algorithm whose result is
transiting between MRT Island routers is 0. The GADAG Root is identical to that of the Island_Marking_SPF() in Figure 4.
recommended for consistency.
11.3. MRT Alternates for Destinations Outside the MRT Island 11.3. MRT Alternates for Destinations Outside the MRT Island
A natural concern with new functionality is how to have it be useful A natural concern with new functionality is how to have it be useful
when it is not deployed across an entire IGP area. In the case of when it is not deployed across an entire IGP area. In the case of
MRT FRR, where it provides alternates when appropriate LFAs aren't MRT FRR, where it provides alternates when appropriate LFAs aren't
available, there are also deployment scenarios where it may make available, there are also deployment scenarios where it may make
sense to only enable some routers in an area with MRT FRR. A simple sense to only enable some routers in an area with MRT FRR. A simple
example of such a scenario would be a ring of 6 or more routers that example of such a scenario would be a ring of 6 or more routers that
is connected via two routers to the rest of the area. is connected via two routers to the rest of the area.
skipping to change at page 36, line 18 skipping to change at page 37, line 12
o Contact information: lizhenbin@huawei.com, eric.wu@huawei.com o Contact information: lizhenbin@huawei.com, eric.wu@huawei.com
14. Acknowledgements 14. Acknowledgements
The authors would like to thank Mike Shand for his valuable review The authors would like to thank Mike Shand for his valuable review
and contributions. and contributions.
The authors would like to thank Joel Halpern, Hannes Gredler, Ted The authors would like to thank Joel Halpern, Hannes Gredler, Ted
Qian, Kishore Tiruveedhula, Shraddha Hegde, Santosh Esale, Nitin Qian, Kishore Tiruveedhula, Shraddha Hegde, Santosh Esale, Nitin
Bahadur, Harish Sitaraman, Raveendra Torvi, Anil Kumar SN, and Bruno Bahadur, Harish Sitaraman, Raveendra Torvi, Anil Kumar SN, Bruno
Decraene for their suggestions and review. Decraene, Eric Wu, and Janos Farkas for their suggestions and review.
15. IANA Considerations 15. IANA Considerations
Please create an MRT Profile registry for the MRT Profile TLV. The Please create an MRT Profile registry for the MRT Profile TLV. The
range is 0 to 255. The default MRT Profile has value 0. Values range is 0 to 255. The default MRT Profile has value 0. Values
1-200 are by Standards Action. Values 201-220 are for 1-200 are by Standards Action. Values 201-220 are for
experimentation. Values 221-255 are for vendor private use. experimentation. Values 221-255 are for vendor private use.
Please allocate values from the LDP Multi-Topology (MT) ID Name Space
[I-D.ietf-mpls-ldp-multi-topology] for the following: Default Profile
MRT-Red MT-ID (TBA-MRT-ARCH-1) and Default Profile MRT-Blue MT-ID
(TBA-MRT-ARCH-2). Please allocate MT-ID values less than 4096 so
that they can also be signalled in PIM.
16. Security Considerations 16. Security Considerations
This architecture is not currently believed to introduce new security This architecture is not currently believed to introduce new security
concerns. concerns.
17. References 17. References
17.1. Normative References 17.1. Normative References
[I-D.ietf-rtgwg-mrt-frr-algorithm] [I-D.ietf-rtgwg-mrt-frr-algorithm]
Envedi, G., Csaszar, A., Atlas, A., Bowers, C., and A. Envedi, G., Csaszar, A., Atlas, A., Bowers, C., and A.
Gopalan, "Algorithms for computing Maximally Redundant Gopalan, "Algorithms for computing Maximally Redundant
Trees for IP/LDP Fast- Reroute", draft-ietf-rtgwg-mrt-frr- Trees for IP/LDP Fast- Reroute", draft-ietf-rtgwg-mrt-frr-
algorithm-05 (work in progress), July 2015. algorithm-05 (work in progress), July 2015.
[RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for
Reroute: Loop-Free Alternates", RFC 5286, September 2008. IP Fast Reroute: Loop-Free Alternates", RFC 5286,
DOI 10.17487/RFC5286, September 2008,
<http://www.rfc-editor.org/info/rfc5286>.
[RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework",
5714, January 2010. RFC 5714, DOI 10.17487/RFC5714, January 2010,
<http://www.rfc-editor.org/info/rfc5714>.
17.2. Informative References 17.2. Informative References
[EnyediThesis] [EnyediThesis]
Enyedi, G., "Novel Algorithms for IP Fast Reroute", Enyedi, G., "Novel Algorithms for IP Fast Reroute",
Department of Telecommunications and Media Informatics, Department of Telecommunications and Media Informatics,
Budapest University of Technology and Economics Ph.D. Budapest University of Technology and Economics Ph.D.
Thesis, February 2011, Thesis, February 2011,
<http://timon.tmit.bme.hu/theses/thesis_book.pdf>. <http://timon.tmit.bme.hu/theses/thesis_book.pdf>.
skipping to change at page 37, line 46 skipping to change at page 38, line 41
Tantsura, "Intermediate System to Intermediate System (IS- Tantsura, "Intermediate System to Intermediate System (IS-
IS) Extensions for Maximally Redundant Trees (MRT)", IS) Extensions for Maximally Redundant Trees (MRT)",
draft-ietf-isis-mrt-00 (work in progress), February 2015. draft-ietf-isis-mrt-00 (work in progress), February 2015.
[I-D.ietf-mpls-ldp-mrt] [I-D.ietf-mpls-ldp-mrt]
Atlas, A., Tiruveedhula, K., Bowers, C., Tantsura, J., and Atlas, A., Tiruveedhula, K., Bowers, C., Tantsura, J., and
I. Wijnands, "LDP Extensions to Support Maximally I. Wijnands, "LDP Extensions to Support Maximally
Redundant Trees", draft-ietf-mpls-ldp-mrt-00 (work in Redundant Trees", draft-ietf-mpls-ldp-mrt-00 (work in
progress), January 2015. progress), January 2015.
[I-D.ietf-mpls-ldp-multi-topology]
Zhao, Q., Raza, K., Zhou, C., Fang, L., Li, L., and D.
King, "LDP Extensions for Multi Topology", draft-ietf-
mpls-ldp-multi-topology-12 (work in progress), April 2014.
[I-D.ietf-ospf-mrt] [I-D.ietf-ospf-mrt]
Atlas, A., Hegde, S., Bowers, C., Tantsura, J., and Z. Li, Atlas, A., Hegde, S., Bowers, C., Tantsura, J., and Z. Li,
"OSPF Extensions to Support Maximally Redundant Trees", "OSPF Extensions to Support Maximally Redundant Trees",
draft-ietf-ospf-mrt-00 (work in progress), January 2015. draft-ietf-ospf-mrt-00 (work in progress), January 2015.
[I-D.ietf-rtgwg-ipfrr-notvia-addresses] [I-D.ietf-rtgwg-ipfrr-notvia-addresses]
Bryant, S., Previdi, S., and M. Shand, "A Framework for IP Bryant, S., Previdi, S., and M. Shand, "A Framework for IP
and MPLS Fast Reroute Using Not-via Addresses", draft- and MPLS Fast Reroute Using Not-via Addresses", draft-
ietf-rtgwg-ipfrr-notvia-addresses-11 (work in progress), ietf-rtgwg-ipfrr-notvia-addresses-11 (work in progress),
May 2013. May 2013.
skipping to change at page 38, line 42 skipping to change at page 39, line 31
<http://opti.tmit.bme.hu/~tapolcai/papers/ <http://opti.tmit.bme.hu/~tapolcai/papers/
retvari2011lfa_infocom.pdf>. retvari2011lfa_infocom.pdf>.
[LightweightNotVia] [LightweightNotVia]
Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP
Fast ReRoute: Lightweight Not-Via without Additional Fast ReRoute: Lightweight Not-Via without Additional
Addresses", Proceedings of IEEE INFOCOM , 2009, Addresses", Proceedings of IEEE INFOCOM , 2009,
<http://mycite.omikk.bme.hu/doc/71691.pdf>. <http://mycite.omikk.bme.hu/doc/71691.pdf>.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328,
DOI 10.17487/RFC2328, April 1998,
<http://www.rfc-editor.org/info/rfc2328>.
[RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D.
McPherson, "OSPF Stub Router Advertisement", RFC 3137, McPherson, "OSPF Stub Router Advertisement", RFC 3137,
June 2001. DOI 10.17487/RFC3137, June 2001,
<http://www.rfc-editor.org/info/rfc3137>.
[RFC5443] Jork, M., Atlas, A., and L. Fang, "LDP IGP [RFC5443] Jork, M., Atlas, A., and L. Fang, "LDP IGP
Synchronization", RFC 5443, March 2009. Synchronization", RFC 5443, DOI 10.17487/RFC5443, March
2009, <http://www.rfc-editor.org/info/rfc5443>.
[RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free [RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free
Convergence", RFC 5715, January 2010. Convergence", RFC 5715, DOI 10.17487/RFC5715, January
2010, <http://www.rfc-editor.org/info/rfc5715>.
[RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B., [RFC6571] Filsfils, C., Ed., Francois, P., Ed., Shand, M., Decraene,
Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free B., Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free
Alternate (LFA) Applicability in Service Provider (SP) Alternate (LFA) Applicability in Service Provider (SP)
Networks", RFC 6571, June 2012. Networks", RFC 6571, DOI 10.17487/RFC6571, June 2012,
<http://www.rfc-editor.org/info/rfc6571>.
[RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running
Code: The Implementation Status Section", RFC 6982, July Code: The Implementation Status Section", RFC 6982,
2013. DOI 10.17487/RFC6982, July 2013,
<http://www.rfc-editor.org/info/rfc6982>.
[RFC7307] Zhao, Q., Raza, K., Zhou, C., Fang, L., Li, L., and D.
King, "LDP Extensions for Multi-Topology", RFC 7307,
DOI 10.17487/RFC7307, July 2014,
<http://www.rfc-editor.org/info/rfc7307>.
[RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N.
So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)",
RFC 7490, April 2015. RFC 7490, DOI 10.17487/RFC7490, April 2015,
<http://www.rfc-editor.org/info/rfc7490>.
Appendix A. General Issues with Area Abstraction Appendix A. General Issues with Area Abstraction
When a multi-homed prefix is connected in two different areas, it may When a multi-homed prefix is connected in two different areas, it may
be impractical to protect them without adding the complexity of be impractical to protect them without adding the complexity of
explicit tunneling. This is also a problem for LFA and Remote-LFA. explicit tunneling. This is also a problem for LFA and Remote-LFA.
50 50
|----[ASBR Y]---[B]---[ABR 2]---[C] Backbone Area 0: |----[ASBR Y]---[B]---[ABR 2]---[C] Backbone Area 0:
| | ABR 1, ABR 2, C, D | | ABR 1, ABR 2, C, D
 End of changes. 41 change blocks. 
118 lines changed or deleted 168 lines changed or added

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