# An Algorithm for Computing IP/LDP Fast Reroute Using Maximally Redundant Trees (MRT-FRR)

Part 4 of 6, p. 61 to 69

```6.  MRT Lowpoint Algorithm: Next-Hop Conformance

This specification defines the MRT Lowpoint algorithm, which includes
the construction of a common GADAG and the computation of MRT-Red and
MRT-Blue next hops to each node in the graph.  An implementation MAY
select any subset of next hops for MRT-Red and MRT-Blue that respect
the available nodes that are described in Section 5.7 for each of the
MRT-Red and MRT-Blue and the selected next hops are further along in
the interval of allowed nodes towards the destination.

For example, the MRT-Blue next hops used when the destination Y >> X,
the computing router, MUST be one or more nodes, T, whose topo_order
is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y
is T.  Similarly, the MRT-Red next hops MUST be have a topo_order in
the interval [R-small.topo_order, X.topo_order] or [Y.topo_order,
R-big.topo_order].

Implementations SHOULD implement the Select_Alternates() function to
pick an MRT-FRR alternate.

network MUST be represented as a pseudonode, where each real node
connects to the pseudonode.  The interface metric in the direction
from real node to pseudonode is the non-zero interface metric, while
the interface metric in the direction from the pseudonode to the real
node is set to zero.  This is consistent with the way that broadcast
interfaces are represented as pseudonodes in IS-IS and OSPF.

Pseudonodes MUST be treated as equivalent to real nodes in the
network graph used in the MRT Lowpoint algorithm with a few
exceptions detailed below.

The pseudonodes MUST be included in the computation of the GADAG.
The neighbors of the pseudonode need to know the mrt_node_id of the
```
```   pseudonode in order to consistently order interfaces, which is needed
to compute the GADAG.  The mrt_node_id for IS-IS is the 7-octet
neighbor system ID and pseudonode number in TLV 22 or TLV 222.  The
mrt_node_id for OSPFv2 is the 4-octet interface address of the
Designated Router found in the Link ID field for the link type 2
(transit network) in the Router-LSA.  The mrt_node_id for OSPFv3 is
the 4 octet interface address of the Designated Router found in the
Neighbor Interface ID field for the link type 2 (transit network) in
the Router-LSA.  Note that this is different from the Neighbor Router
ID field used for the mrt_node_id for point-to-point links in OSPFv3
Router-LSAs given in Figure 15.

Pseudonodes MUST NOT be considered candidates for selection as GADAG
root.  This rule is intended to result in a more stable network-wide
selection of GADAG root by removing the possibility that the change
of Designated Router or Designated Intermediate System on a broadcast
network can result in a change of GADAG root.

7.1.  Computing MRT Next Hops on Broadcast Networks

The pseudonode does not correspond to a real node, so it is not
actually involved in forwarding.  A real node on a broadcast network
cannot simply forward traffic to the broadcast network.  It must
specify another real node on the broadcast network as the next hop.
On a network graph where a broadcast network is represented by a
pseudonode, this means that if a real node determines that the next
hop to reach a given destination is a pseudonode, it must also
determine the next-next-hop for that destination in the network
graph, which corresponds to a real node attached to the broadcast
network.

It is interesting to note that this issue is not unique to the MRT
algorithm, but is also encountered in normal SPF computations for
IGPs.  Section 16.1.1 of [RFC2328] describes how this is done for
OSPF.  When OSPF runs its shortest-path tree calculation, it deals
with pseudonodes in the following manner.  Whenever the calculating
router finds a shorter path to reach a real destination node and the
shorter path to the destination is a single pseudonode hop, then the
next hop for that destination is taken from the interface IP address
in the Router-LSA correspond to the link to the real destination
node.

For IS-IS, in the example pseudocode implementation of Dijkstra's
algorithm in Annex C of [ISO10589-Second-Edition], whenever the
algorithm encounters an adjacency from a real node to a pseudonode,
it gets converted to a set of adjacencies from the real node to the
neighbors of the pseudonode.  In this way, the computed next hops
point all the way to the real node, and not the pseudonode.
```
```   We could avoid the problem of determining next hops across
pseudonodes in MRT by converting the pseudonode representation of
broadcast networks to a full mesh of links between real nodes on the
same network.  However, if we make that conversion before computing
to a single physical interface into the broadcast network.  This
could result computing red and blue next hops that use the same
broadcast interface, in which case neither the red nor the blue next
hop would be usable as an alternate on failure of the broadcast
interface.

Instead, we take the following approach, which maintains the property
that either the red and blue next hop will avoid the broadcast
network, if topologically allowed.  We run the MRT Lowpoint algorithm
treating the pseudonodes as equivalent to real nodes in the network
graph, with the exceptions noted above.  In addition to running the
MRT Lowpoint algorithm from the point of view of itself, a computing
router connected to a pseudonode MUST also run the MRT Lowpoint
algorithm from the point of view of each of its pseudonode neighbors.
For example, if a computing router S determines that its MRT red next
hop to reach a destination D is a pseudonode P, S looks at its MRT
Lowpoint algorithm computation from P's point of view to determine
P's red next hop to reach D, say interface 1 on node X.  S now knows
that its real red next hop to reach D is interface 1 on node X on the
broadcast network represented by P, and it can install the
corresponding entry in its FIB.

7.2.  Using MRT Next Hops as Alternates in the Event of Failures on

In the previous section, we specified how to compute MRT next hops
when broadcast networks are involved.  In this section, we discuss
how a PLR can use those MRT next hops in the event of failures

A PLR attached to a broadcast network running only OSPF or IS-IS with
large Hello intervals has limited ability to quickly detect failures
on a broadcast network.  The only failure mode that can be quickly
detected is the failure of the physical interface connecting the PLR
to the broadcast network.  For the failure of the interface
connecting the PLR to the broadcast network, the alternate that
network pseudonode as F, the primary next-hop node, in
Select_Alternates().  This will choose an alternate path that avoids
the broadcast network.  However, the alternate path will not
necessarily avoid all of the real nodes connected to the broadcast
network.  This is because we have used the pseudonode to represent
the broadcast network.  And we have enforced the node-protecting
```
```   property of MRT on the pseudonode to provide protection against
failure of the broadcast network, not the real next-hop nodes on the
broadcast network.  This is the best that we can hope to do if
failure of the broadcast interface is the only failure mode that the
PLR can respond to.

We can improve on this if the PLR also has the ability to quickly
detect a lack of connectivity across the broadcast network to a given
IP-layer node.  This can be accomplished by running BFD between all
pairs of IGP neighbors on the broadcast network.  Note that in the
case of OSPF, this would require establishing BFD sessions between
all pairs of neighbors in the 2-WAY state.  When the PLR can quickly
detect the failure of a particular next hop across a broadcast
network, the PLR can be more selective in its choice of alternates.
For example, when the PLR observes that connectivity to an IP-layer
node on a broadcast network has failed, the PLR may choose to still
use the broadcast network to reach other IP-layer nodes that are
still reachable.  Or, if the PLR observes that connectivity has
failed to several IP-layer nodes on the same broadcast network, it
may choose to treat the entire broadcast network as failed.  The
choice of MRT alternates by a PLR for a particular set of failure
conditions is a local decision, since it does not require
coordination with other nodes.

8.  Evaluation of Alternative Methods for Constructing GADAGs

This document specifies the MRT Lowpoint algorithm.  One component of
the algorithm involves constructing a common GADAG based on the
network topology.  The MRT Lowpoint algorithm computes the GADAG
using the method described in Section 5.5.  This method aims to
minimize the amount of computation required to compute the GADAG.  In
the process of developing the MRT Lowpoint algorithm, two alternative
methods for constructing GADAGs were also considered.  These
alternative methods are described in Appendices B and C.  In general,
these other two methods require more computation to compute the
GADAG.  The analysis below was performed to determine if the
alternative GADAG construction methods produce shorter MRT alternate
paths in real network topologies, and if so, to what extent.

Figure 30 compares results obtained using the three different methods
for constructing GADAGs on five different service provider network
topologies.  MRT_LOWPOINT indicates the method specified in
Section 5.5, while MRT_SPF and MRT_HYBRID indicate the methods
specified in Appendices B and C, respectively.  The columns on the
right present the distribution of alternate path lengths for each
GADAG construction method.  Each MRT computation was performed using
a same GADAG root chosen based on centrality.
```
```   For three of the topologies analyzed (T201, T206, and T211), the use
of MRT_SPF or MRT_HYBRID methods does not appear to provide a
significantly shorter alternate path lengths compared to the
MRT_LOWPOINT method.  However, for two of the topologies (T216 and
T219), the use of the MRT_SPF method resulted in noticeably shorter
alternate path lengths than the use of the MRT_LOWPOINT or MRT_HYBRID
methods.

It was decided to use the MRT_LOWPOINT method to construct the GADAG
in the algorithm specified in this document, in order to initially
offer an algorithm with lower computational requirements.  These
results indicate that in the future it may be useful to evaluate and
potentially specify other MRT Lowpoint algorithm variants that use
```
```   +-------------------------------------------------------------------+
|        Topology name         |   percentage of failure scenarios  |
|                              |  protected by an alternate N hops  |
|      GADAG construction      |   longer than the primary path     |
|            method            +------------------------------------+
|                              |   |   |   |   |   |   |   |   | no |
|                              |   |   |   |   |   |10 |12 |14 | alt|
|                              |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16|
+------------------------------+---+---+---+---+---+---+---+---+----+
|  T201(avg primary hops=3.5)  |   |   |   |   |   |   |   |   |    |
|  MRT_HYBRID                  | 33| 26| 23|  6|  3|   |   |   |    |
|  MRT_SPF                     | 33| 36| 23|  6|  3|   |   |   |    |
|  MRT_LOWPOINT                | 33| 36| 23|  6|  3|   |   |   |    |
+------------------------------+---+---+---+---+---+---+---+---+----+
|  T206(avg primary hops=3.7)  |   |   |   |   |   |   |   |   |    |
|  MRT_HYBRID                  | 50| 35| 13|  2|   |   |   |   |    |
|  MRT_SPF                     | 50| 35| 13|  2|   |   |   |   |    |
|  MRT_LOWPOINT                | 55| 32| 13|   |   |   |   |   |    |
+------------------------------+---+---+---+---+---+---+---+---+----+
|  T211(avg primary hops=3.3)  |   |   |   |   |   |   |   |   |    |
|  MRT_HYBRID                  | 86| 14|   |   |   |   |   |   |    |
|  MRT_SPF                     | 86| 14|   |   |   |   |   |   |    |
|  MRT_LOWPOINT                | 85| 15|  1|   |   |   |   |   |    |
+------------------------------+---+---+---+---+---+---+---+---+----+
|  T216(avg primary hops=5.2)  |   |   |   |   |   |   |   |   |    |
|  MRT_HYBRID                  | 23| 22| 18| 13| 10|  7|  4|  2|   2|
|  MRT_SPF                     | 35| 32| 19|  9|  3|  1|   |   |    |
|  MRT_LOWPOINT                | 28| 25| 18| 11|  7|  6|  3|  2|   1|
+------------------------------+---+---+---+---+---+---+---+---+----+
|  T219(avg primary hops=7.7)  |   |   |   |   |   |   |   |   |    |
|  MRT_HYBRID                  | 20| 16| 13| 10|  7|  5|  5|  5|   3|
|  MRT_SPF                     | 31| 23| 19| 12|  7|  4|  2|  1|    |
|  MRT_LOWPOINT                | 19| 14| 15| 12| 10|  8|  7|  6|  10|
+------------------------------+---+---+---+---+---+---+---+---+----+

Figure 30: The Length of Alternate Paths for Various GADAG
Construction Methods

9.  Operational Considerations

This section discusses operational considerations related to the MRT
Lowpoint algorithm and other potential MRT algorithm variants.  For a
discussion of operational considerations related to MRT-FRR in
general, see the "Operational Considerations" section of [RFC7812].
```
```9.1.  GADAG Root Selection

The Default MRT Profile uses the GADAG Root Selection Priority
advertised by routers as the primary criterion for selecting the
GADAG root.  It is RECOMMENDED that an operator designate a set of
routers as good choices for selection as GADAG root by setting the
GADAG Root Selection Priority for that set of routers to lower (more
preferred) numerical values.  Criteria for making this designation
are discussed below.

Analysis has shown that the centrality of a router can have a
significant impact on the lengths of the alternate paths computed.
Therefore, it is RECOMMENDED that off-line analysis that considers
the centrality of a router be used to help determine how good a
choice a particular router is for the role of GADAG root.

If the router currently selected as GADAG root becomes unreachable in
the IGP topology, then a new GADAG root will be selected.  Changing
the GADAG root can change the overall structure of the GADAG as well
the paths of the red and MRT-Blue trees built using that GADAG.  In
order to minimize change in the associated red and MRT-Blue
forwarding entries that can result from changing the GADAG root, it
is RECOMMENDED that operators prioritize for selection as GADAG root
those routers that are expected to consistently remain part of the
IGP topology.

The MRT Lowpoint algorithm constructs a single GADAG rooted at a
single node selected as the GADAG root.  It is also possible to
rooted at the destination.  A router can compute the MRT-Red and MRT-
Blue next hops for that destination based on the GADAG rooted at that
destination.  Building a different GADAG for each destination is
computationally more expensive, but it may give somewhat shorter
alternate paths.  Using destination-rooted GADAGs would require a new
MRT profile to be created with a new MRT algorithm specification,
since all routers in the MRT Island would need to use destination-

10.  Security Considerations

The algorithm described in this document does not introduce new
security concerns beyond those already discussed in the document
describing the MRT FRR architecture [RFC7812].
```
```11.  References

11.1.  Normative References

[RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>.

[RFC7812]  Atlas, A., Bowers, C., and G. Enyedi, "An Architecture for
IP/LDP Fast Reroute Using Maximally Redundant Trees
(MRT-FRR)", RFC 7812, DOI 10.17487/RFC7812, June 2016,
<http://www.rfc-editor.org/info/rfc7812>.

11.2.  Informative References

[EnyediThesis]
Enyedi, G., "Novel Algorithms for IP Fast Reroute",
Department of Telecommunications and Media Informatics,
Budapest University of Technology and Economics Ph.D.
Thesis, February 2011,
<https://repozitorium.omikk.bme.hu/bitstream/
handle/10890/1040/ertekezes.pdf>.

[IEEE8021Qca]
IEEE, "IEEE Standard for Local and metropolitan area
networks - Bridges and Bridged Networks - Amendment 24:
Path Control and Reservation", IEEE 802.1Qca-2015,
DOI 10.1109/IEEESTD.2016.7434544, 2016,
<https://standards.ieee.org/findstds/
standard/802.1Qca-2015.html>.

[ISO10589-Second-Edition]
International Organization for Standardization,
"Intermediate system to Intermediate system intra-domain
routeing information exchange protocol for use in
conjunction with the protocol for providing the
connectionless-mode Network Service (ISO 8473)", ISO/
IEC 10589:2002, Second Edition, November 2002.

[Kahn_1962_topo_sort]
Kahn, A., "Topological sorting of large networks",
Communications of the ACM, Volume 5, Issue 11 DOI
10.1145/368996.369025, November 1962,
<http://dl.acm.org/citation.cfm?doid=368996.369025>.
```
```   [MRTLinear]
Enyedi, G., Retvari, G., and A. Csaszar, "On Finding
Maximally Redundant Trees in Strictly Linear Time", IEEE
Symposium on Computers and Communications (ISCC), 2009,
<http://opti.tmit.bme.hu/~enyedi/ipfrr/
distMaxRedTree.pdf>.

[RFC2328]  Moy, J., "OSPF Version 2", STD 54, RFC 2328,
DOI 10.17487/RFC2328, April 1998,
<http://www.rfc-editor.org/info/rfc2328>.
```