Tech-invite3GPPspaceIETF RFCsSIP
in Index   Prev   Next

RFC 7811

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

Pages: 118
Proposed Standard
Part 4 of 6 – Pages 61 to 69
First   Prev   Next

Top   ToC   RFC7811 - Page 61   prevText

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.

7. Broadcast Interfaces

When broadcast interfaces are used to connect nodes, the broadcast 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
Top   ToC   RFC7811 - Page 62
   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.
Top   ToC   RFC7811 - Page 63
   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
   the GADAG, we lose information about which links actually correspond
   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

   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 Broadcast Networks

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 involving broadcast networks. 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 avoids the broadcast network can be computed by using the broadcast 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
Top   ToC   RFC7811 - Page 64
   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.
Top   ToC   RFC7811 - Page 65
   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

   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
   different GADAG construction methods.
Top   ToC   RFC7811 - Page 66
   |        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].
Top   ToC   RFC7811 - Page 67

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.

9.2. Destination-Rooted GADAGs

The MRT Lowpoint algorithm constructs a single GADAG rooted at a single node selected as the GADAG root. It is also possible to construct a different GADAG for each destination, with the GADAG 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- rooted GADAGs.

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].
Top   ToC   RFC7811 - Page 68

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, <>. [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, <>.

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, < 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, < 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, <>.
Top   ToC   RFC7811 - Page 69
              Enyedi, G., Retvari, G., and A. Csaszar, "On Finding
              Maximally Redundant Trees in Strictly Linear Time", IEEE
              Symposium on Computers and Communications (ISCC), 2009,

   [RFC2328]  Moy, J., "OSPF Version 2", STD 54, RFC 2328,
              DOI 10.17487/RFC2328, April 1998,

(next page on part 5)

Next Section