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

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

   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
   different GADAG construction methods.

   +-------------------------------------------------------------------+
   |        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.

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].

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