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 2 of 6 – Pages 18 to 36
First   Prev   Next

Top   ToC   RFC7811 - Page 18   prevText

5. MRT Lowpoint Algorithm Specification

The MRT Lowpoint algorithm computes one GADAG that is then used by a router to determine its MRT-Blue and MRT-Red next hops to all destinations. Finally, based upon that information, alternates are selected for each next hop to each destination. The different parts of this algorithm are described below. o Order the interfaces in the network graph. See Section 5.1. o Compute the local MRT Island for the particular MRT Profile. See Section 5.2. o Select the root to use for the GADAG. See Section 5.3. o Initialize all interfaces to UNDIRECTED. See Section 5.4. o Compute the DFS value, e.g., D(x), and lowpoint value, L(x). See Figure 8. o Construct the GADAG. See Section 5.5. o Assign directions to all interfaces that are still UNDIRECTED. See Section 5.6. o From the computing router x, compute the next hops for the MRT- Blue and MRT-Red. See Section 5.7. o Identify alternates for each next hop to each destination by determining which one of the MRT-Blue and the MRT-Red the computing router x should select. See Section 5.8. A Python implementation of this algorithm is given in Appendix A.

5.1. Interface Ordering

To ensure consistency in computation, all routers MUST order interfaces identically down to the set of links with the same metric to the same neighboring node. This is necessary for the DFS in Lowpoint_Visit in Section 4.3, where the selection order of the interfaces to explore results in different trees. Consistent interface ordering is also necessary for computing the GADAG, where the selection order of the interfaces to use to form ears can result in different GADAGs. It is also necessary for the topological sort described in Section 5.8, where different topological sort orderings can result in undirected links being added to the GADAG in different directions.
Top   ToC   RFC7811 - Page 19
   The required ordering between two interfaces from the same router x
   is given in Figure 14.

      Interface_Compare(interface a, interface b)
        if a.metric < b.metric
           return A_LESS_THAN_B
        if b.metric < a.metric
           return B_LESS_THAN_A
        if a.neighbor.mrt_node_id < b.neighbor.mrt_node_id
           return A_LESS_THAN_B
        if b.neighbor.mrt_node_id < a.neighbor.mrt_node_id
           return B_LESS_THAN_A
        // Same metric to same node, so the order doesn't matter for
        // interoperability.
        return A_EQUAL_TO_B

    Figure 14: Rules for Ranking Multiple Interfaces (Order Is from Low
                                 to High)

   In Figure 14, if two interfaces on a router connect to the same
   remote router with the same metric, the Interface_Compare function
   returns A_EQUAL_TO_B.  This is because the order in which those
   interfaces are initially explored does not affect the final GADAG
   produced by the algorithm described here.  While only one of the
   links will be added to the GADAG in the initial traversal, the other
   parallel links will be added to the GADAG with the same direction
   assigned during the procedure for assigning direction to UNDIRECTED
   links described in Section 5.6.  An implementation is free to apply
   some additional criteria to break ties in interface ordering in this
   situation, but those criteria are not specified here since they will
   not affect the final GADAG produced by the algorithm.

   The Interface_Compare function in Figure 14 relies on the
   interface.metric and the interface.neighbor.mrt_node_id values to
   order interfaces.  The exact source of these values for different
   IGPs and applications is specified in Figure 15.  The metric and
   mrt_node_id values for OSPFv2, OSPFv3, and IS-IS provided here is
   normative.  The metric and mrt_node_id values for IS-IS Path Control
   and Reservation (PCR) in this table should be considered
   informational.  The normative values are specified in [IEEE8021Qca].
Top   ToC   RFC7811 - Page 20
  | IGP/flooding | mrt_node_id           | metric of                   |
  | protocol     | of neighbor           | interface                   |
  | and          | on interface          |                             |
  | application  |                       |                             |
  | OSPFv2 for   | 4-octet Neighbor      | 2-octet Metric field        |
  | IP/LDP FRR   | Router ID in          | for corresponding           |
  |              | Link ID field for     | point-to-point link         |
  |              | corresponding         | in Router-LSA               |
  |              | point-to-point link   |                             |
  |              | in Router-LSA         |                             |
  | OSPFv3 for   | 4-octet Neighbor      | 2-octet Metric field        |
  | IP/LDP FRR   | Router ID field       | for corresponding           |
  |              | for corresponding     | point-to-point link         |
  |              | point-to-point link   | in Router-LSA               |
  |              | in Router-LSA         |                             |
  | IS-IS for    | 7-octet neighbor      | 3-octet metric field        |
  | IP/LDP FRR   | system ID and         | in Extended IS              |
  |              | pseudonode number     | Reachability TLV (type 22)  |
  |              | in Extended IS        | or Multi-Topology           |
  |              | Reachability TLV (type| IS Neighbor TLV (type 222)  |
  |              | 22) or Multi-Topology |                             |
  |              | IS Neighbor TLV (type |                             |
  |              | 222)                  |                             |
  | IS-IS PCR for| 8-octet Bridge ID     | 3-octet SPB-LINK-METRIC in  |
  | protection   | created from  2-octet | SPB-Metric sub-TLV (type 29)|
  | of traffic   | Bridge Priority in    | in Extended IS Reachability |
  | in bridged   | Shortest Path Bridging| TLV (type 22) or            |
  |              |SPB Instance sub-TLV   | Multi-Topology              |
  | networks     | (type 1) carried in   | Intermediate Systems        |
  |              | MT-Capability TLV     | TLV (type 222).  In the case|
  |              | (type 144) and 6-octet| of asymmetric link metrics, |
  |              | neighbor system ID in | the larger link metric      |
  |              | Extended IS           | is used for both link       |
  |              | Reachability TLV (type| directions.                 |
  |              | 22) or Multi-Topology | (informational)             |
  |              | Intermediate Systems  |                             |
  |              | TLV (type 222)        |                             |
  |              | (informational)       |                             |

          Figure 15: Value of interface.neighbor.mrt_node_id and
     interface.metric to Be Used for Ranking Interfaces, for Different
                    Flooding Protocols and Applications
Top   ToC   RFC7811 - Page 21
   The metrics are unsigned integers and MUST be compared as unsigned
   integers.  The results of mrt_node_id comparisons MUST be the same as
   would be obtained by converting the mrt_node_ids to unsigned integers
   using network byte order and performing the comparison as unsigned
   integers.  In the case of IS-IS for IP/LDP FRR with point-to-point
   links, the pseudonode number (the 7th octet) is zero.  Broadcast
   interfaces will be discussed in Section 7.

5.2. MRT Island Identification

The local MRT Island for a particular MRT profile can be determined by starting from the computing router in the network graph and doing a breadth-first-search (BFS). The BFS explores only links that are in the same area/level, are not IGP-excluded, and are not MRT- ineligible. The BFS explores only nodes that support the particular MRT profile. See Section 7 of [RFC7812] for more-precise definitions of these criteria. MRT_Island_Identification(topology, computing_rtr, profile_id, area) for all routers in topology rtr.IN_MRT_ISLAND = FALSE computing_rtr.IN_MRT_ISLAND = TRUE explore_list = { computing_rtr } while (explore_list is not empty) next_rtr = remove_head(explore_list) for each intf in next_rtr if (not intf.IN_MRT_ISLAND and not intf.MRT-ineligible and not intf.remote_intf.MRT-ineligible and not intf.IGP-excluded and (intf in area) and (intf.remote_node supports profile_id) ) intf.IN_MRT_ISLAND = TRUE intf.remote_intf.IN_MRT_ISLAND = TRUE if (not intf.remote_node.IN_MRT_ISLAND)) intf.remote_node.IN_MRT_ISLAND = TRUE add_to_tail(explore_list, intf.remote_node) Figure 16: MRT Island Identification

5.3. GADAG Root Selection

In Section 8.3 of [RFC7812], the GADAG Root Selection Policy is described for the Default MRT Profile. This selection policy allows routers to consistently select a common GADAG Root inside the local MRT Island, based on advertised priority values. The MRT Lowpoint algorithm simply requires that all routers in the MRT Island MUST select the same GADAG Root; the mechanism can vary based upon the MRT profile description. Before beginning computation, the network graph
Top   ToC   RFC7811 - Page 22
   is reduced to contain only the set of routers that support the
   specific MRT profile whose MRTs are being computed.

   As noted in Section 7, pseudonodes MUST NOT be considered for GADAG
   root selection.

   It is expected that an operator will 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.  For guidance on setting the GADAG Root Selection
   Priority values, refer to Section 9.1.

5.4. Initialization

Before running the algorithm, there is the standard type of initialization to be done, such as clearing any computed DFS-values, lowpoint-values, DFS parents, lowpoint-parents, any MRT-computed next hops, and flags associated with algorithm. It is assumed that a regular SPF computation has been run so that the primary next hops from the computing router to each destination are known. This is required for determining alternates at the last step. Initially, all interfaces MUST be initialized to UNDIRECTED. Whether they are OUTGOING, INCOMING, or both is determined when the GADAG is constructed and augmented. It is possible that some links and nodes will be marked using standard IGP mechanisms to discourage or prevent transit traffic. Section 7.3.1 of [RFC7812] describes how those links and nodes are excluded from MRT Island formation. MRT-FRR also has the ability to advertise links MRT-Ineligible, as described in Section 7.3.2 of [RFC7812]. These links are excluded from the MRT Island and the GADAG. Computation of MRT next hops will therefore not use any MRT-ineligible links. The MRT Lowpoint algorithm does still need to consider MRT-ineligible links when computing FRR alternates, because an MRT-ineligible link can still be the shortest-path next hop to reach a destination. When a broadcast interface is advertised as MRT-ineligible, then the pseudonode representing the entire broadcast network MUST NOT be included in the MRT Island. This is equivalent to excluding all of the broadcast interfaces on that broadcast network from the MRT Island.
Top   ToC   RFC7811 - Page 23

5.5. Constructing the GADAG Using Lowpoint Inheritance

As discussed in Section 4.2, it is necessary to find ears from a node x that is already in the GADAG (known as IN_GADAG). Two different methods are used to find ears in the algorithm. The first is by going to a DFS-child that is not IN_GADAG and then following the chain of lowpoint parents until an IN_GADAG node is found. The second is by going to a neighbor that is not IN_GADAG and then following the chain of DFS parents until an IN_GADAG node is found. As an ear is found, the associated interfaces are marked based on the direction taken. The nodes in the ear are marked as IN_GADAG. In the algorithm, first the ears via DFS-children are found and then the ears via DFS-neighbors are found. By adding both types of ears when an IN_GADAG node is processed, all ears that connect to that node are found. The order in which the IN_GADAG nodes are processed is, of course, key to the algorithm. The order is a stack of ears so the most recent ear is found at the top of the stack. Of course, the stack stores nodes and not ears, so an ordered list of nodes, from the first node in the ear to the last node in the ear, is created as the ear is explored and then that list is pushed onto the stack. Each ear represents a partial order (see Figure 4) and processing the nodes in order along each ear ensures that all ears connecting to a node are found before a node higher in the partial order has its ears explored. This means that the direction of the links in the ear is always from the node x being processed towards the other end of the ear. Additionally, by using a stack of ears, this means that any unprocessed nodes in previous ears can only be ordered higher than nodes in the ears below it on the stack. In this algorithm that depends upon Lowpoint inheritance, it is necessary that every node has a lowpoint parent that is not itself. If a node is a cut-vertex, that may not yet be the case. Therefore, any nodes without a lowpoint parent will have their lowpoint parent set to their DFS parent and their lowpoint value set to the DFS-value of their parent. This assignment also properly allows an ear between two cut-vertices. Finally, the algorithm simultaneously computes each node's localroot, as described in Figure 12. This is further elaborated as follows. The localroot can be inherited from the node at the end of the ear unless the end of the ear is x itself, in which case the localroot for all the nodes in the ear would be x. This is because whenever the first cycle is found in a block, or an ear involving a bridge is computed, the cut-vertex closest to the root would be x itself. In all other scenarios, the properties of lowpoint/dfs parents ensure
Top   ToC   RFC7811 - Page 24
   that the end of the ear will be in the same block, and thus
   inheriting its localroot would be the correct localroot for all newly
   added nodes.

   The pseudocode for the GADAG algorithm (assuming that the adjustment
   of lowpoint for cut-vertices has been made) is shown in Figure 17.

           Construct_Ear(x, Stack, intf, ear_type)
              ear_list = empty
              cur_node = intf.remote_node
              cur_intf = intf
              not_done = true

              while not_done
                 cur_intf.UNDIRECTED = false
                 cur_intf.OUTGOING = true
                 cur_intf.remote_intf.UNDIRECTED = false
                 cur_intf.remote_intf.INCOMING = true

                 if cur_node.IN_GADAG is false
                    cur_node.IN_GADAG = true
                    add_to_list_end(ear_list, cur_node)
                    if ear_type is CHILD
                       cur_intf = cur_node.lowpoint_parent_intf
                       cur_node = cur_node.lowpoint_parent
                    else  // ear_type must be NEIGHBOR
                       cur_intf = cur_node.dfs_parent_intf
                       cur_node = cur_node.dfs_parent
                    not_done = false

              if (ear_type is CHILD) and (cur_node is x)
                 // x is a cut-vertex and the local root for
                 // the block in which the ear is computed
                 x.IS_CUT_VERTEX = true
                 localroot = x
                 // Inherit localroot from the end of the ear
                 localroot = cur_node.localroot
              while ear_list is not empty
                 y = remove_end_item_from_list(ear_list)
                 y.localroot = localroot
                 push(Stack, y)

           Construct_GADAG_via_Lowpoint(topology, gadag_root)
             gadag_root.IN_GADAG = true
             gadag_root.localroot = None
             Initialize Stack to empty
Top   ToC   RFC7811 - Page 25
             push gadag_root onto Stack
             while (Stack is not empty)
                x = pop(Stack)
                foreach ordered_interface intf of x
                   if ((intf.remote_node.IN_GADAG == false) and
                       (intf.remote_node.dfs_parent is x))
                       Construct_Ear(x, Stack, intf, CHILD)
                foreach ordered_interface intf of x
                   if ((intf.remote_node.IN_GADAG == false) and
                       (intf.remote_node.dfs_parent is not x))
                       Construct_Ear(x, Stack, intf, NEIGHBOR)

           Construct_GADAG_via_Lowpoint(topology, gadag_root)

              Figure 17: Lowpoint Inheritance GADAG Algorithm

5.6. Augmenting the GADAG by Directing All Links

The GADAG, regardless of the method used to construct it, at this point could be used to find MRTs, but the topology does not include all links in the network graph. That has two impacts. First, there might be shorter paths that respect the GADAG partial ordering and so the alternate paths would not be as short as possible. Second, there may be additional paths between a router x and the root that are not included in the GADAG. Including those provides potentially more bandwidth to traffic flowing on the alternates and may reduce congestion compared to just using the GADAG as currently constructed. The goal is thus to assign direction to every remaining link marked as UNDIRECTED to improve the paths and number of paths found when the MRTs are computed. To do this, we need to establish a total order that respects the partial order described by the GADAG. This can be done using Kahn's topological sort [Kahn_1962_topo_sort], which essentially assigns a number to a node x only after all nodes before it (e.g., with a link incoming to x) have had their numbers assigned. The only issue with the topological sort is that it works on DAGs and not ADAGs or GADAGs. To convert a GADAG to a DAG, it is necessary to remove all links that point to a root of block from within that block. That provides the necessary conversion to a DAG and then a topological sort can be done. When adding undirected links to the GADAG, links connecting the block root to other nodes in that block need special handling because the topological order will not always give the right answer for those links. There are three cases to consider. If the undirected link in question has another parallel link between the
Top   ToC   RFC7811 - Page 26
   same two nodes that is already directed, then the direction of the
   undirected link can be inherited from the previously directed link.
   In the case of parallel cut links, we set all of the parallel links
   to both INCOMING and OUTGOING.  Otherwise, the undirected link in
   question is set to OUTGOING from the block root node.  A cut-link can
   then be identified by the fact that it will be directed both INCOMING
   and OUTGOING in the GADAG.  The exact details of this whole process
   are captured in Figure 18.

     Add_Undirected_Block_Root_Links(topo, gadag_root)
         foreach node x in topo
             if x.IS_CUT_VERTEX or x is gadag_root
                 foreach interface i of x
                     if (i.remote_node.localroot is not x
                                         or i.PROCESSED )
                     Initialize bundle_list to empty
                     bundle.UNDIRECTED = true
                     bundle.OUTGOING = false
                     bundle.INCOMING = false
                     foreach interface i2 in x
                         if i2.remote_node is i.remote_node
                             add_to_list_end(bundle_list, i2)
                             if not i2.UNDIRECTED:
                                 bundle.UNDIRECTED = false
                                 if i2.INCOMING:
                                     bundle.INCOMING = true
                                 if i2.OUTGOING:
                                     bundle.OUTGOING = true
                     if bundle.UNDIRECTED
                         foreach interface i3 in bundle_list
                             i3.UNDIRECTED = false
                             i3.remote_intf.UNDIRECTED = false
                             i3.PROCESSED = true
                             i3.remote_intf.PROCESSED = true
                             i3.OUTGOING = true
                             i3.remote_intf.INCOMING = true
                         if (bundle.OUTGOING and bundle.INCOMING)
                             foreach interface i3 in bundle_list
                                 i3.UNDIRECTED = false
                                 i3.remote_intf.UNDIRECTED = false
                                 i3.PROCESSED = true
                                 i3.remote_intf.PROCESSED = true
                                 i3.OUTGOING = true
                                 i3.INCOMING = true
                                 i3.remote_intf.INCOMING = true
                                 i3.remote_intf.OUTGOING = true
Top   ToC   RFC7811 - Page 27
                         else if bundle.OUTGOING
                             foreach interface i3 in bundle_list
                                 i3.UNDIRECTED = false
                                 i3.remote_intf.UNDIRECTED = false
                                 i3.PROCESSED = true
                                 i3.remote_intf.PROCESSED = true
                                 i3.OUTGOING = true
                                 i3.remote_intf.INCOMING = true
                         else if bundle.INCOMING
                             foreach interface i3 in bundle_list
                                 i3.UNDIRECTED = false
                                 i3.remote_intf.UNDIRECTED = false
                                 i3.PROCESSED = true
                                 i3.remote_intf.PROCESSED = true
                                 i3.INCOMING = true
                                 i3.remote_intf.OUTGOING = true

     Modify_Block_Root_Incoming_Links(topo, gadag_root)
         foreach node x in topo
             if x.IS_CUT_VERTEX or x is gadag_root
                 foreach interface i of x
                     if i.remote_node.localroot is x
                         if i.INCOMING:
                             i.INCOMING = false
                             i.INCOMING_STORED = true
                             i.remote_intf.OUTGOING = false
                             i.remote_intf.OUTGOING_STORED = true

     Revert_Block_Root_Incoming_Links(topo, gadag_root)
         foreach node x in topo
             if x.IS_CUT_VERTEX or x is gadag_root
                 foreach interface i of x
                     if i.remote_node.localroot is x
                         if i.INCOMING_STORED
                             i.INCOMING = true
                             i.remote_intf.OUTGOING = true
                             i.INCOMING_STORED = false
                             i.remote_intf.OUTGOING_STORED = false

     Run_Topological_Sort_GADAG(topo, gadag_root)
         Modify_Block_Root_Incoming_Links(topo, gadag_root)
         foreach node x in topo
             node.unvisited = 0
             foreach interface i of x
                 if (i.INCOMING)
                     node.unvisited += 1
         Initialize working_list to empty
         Initialize topo_order_list to empty
Top   ToC   RFC7811 - Page 28
         add_to_list_end(working_list, gadag_root)
         while working_list is not empty
             y = remove_start_item_from_list(working_list)
             add_to_list_end(topo_order_list, y)
             foreach ordered_interface i of y
                 if intf.OUTGOING
                     i.remote_node.unvisited -= 1
                     if i.remote_node.unvisited is 0
                         add_to_list_end(working_list, i.remote_node)
         next_topo_order = 1
         while topo_order_list is not empty
             y = remove_start_item_from_list(topo_order_list)
             y.topo_order = next_topo_order
             next_topo_order += 1
         Revert_Block_Root_Incoming_Links(topo, gadag_root)

     def Set_Other_Undirected_Links_Based_On_Topo_Order(topo)
         foreach node x in topo
             foreach interface i of x
                 if i.UNDIRECTED:
                     if x.topo_order < i.remote_node.topo_order
                         i.OUTGOING = true
                         i.UNDIRECTED = false
                         i.remote_intf.INCOMING = true
                         i.remote_intf.UNDIRECTED = false
                         i.INCOMING = true
                         i.UNDIRECTED = false
                         i.remote_intf.OUTGOING = true
                         i.remote_intf.UNDIRECTED = false

     Add_Undirected_Links(topo, gadag_root)
         Add_Undirected_Block_Root_Links(topo, gadag_root)
         Run_Topological_Sort_GADAG(topo, gadag_root)

     Add_Undirected_Links(topo, gadag_root)

            Figure 18: Assigning Direction to UNDIRECTED Links

   Proxy-nodes do not need to be added to the network graph.  They
   cannot be transited and do not affect the MRTs that are computed.
   The details of how the MRT-Blue and MRT-Red next hops are computed
   for proxy-nodes and how the appropriate alternate next hops are
   selected is given in Section 5.9.
Top   ToC   RFC7811 - Page 29

5.7. Compute MRT Next Hops

As was discussed in Section 4.1, once an ADAG is found, it is straightforward to find the next hops from any node X to the ADAG root. However, in this algorithm, we will reuse the common GADAG and find not only the one pair of MRTs rooted at the GADAG root with it, but find a pair rooted at each node. This is useful since it is significantly faster to compute. The method for computing differently rooted MRTs from the common GADAG is based on two ideas. First, if two nodes X and Y are ordered with respect to each other in the partial order, then an SPF along OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a decreasing-SPF) can be used to find the increasing and decreasing paths. Second, if two nodes X and Y aren't ordered with respect to each other in the partial order, then intermediary nodes can be used to create the paths by increasing/decreasing to the intermediary and then decreasing/increasing to reach Y. As usual, the two basic ideas will be discussed assuming the network is 2-connected. The generalization to multiple blocks is discussed in Section 5.7.4. The full algorithm is given in Section 5.7.5.

5.7.1. MRT Next Hops to All Nodes Ordered with Respect to the Computing Node

Finding two node-disjoint paths from the computing router X to any node Y depends upon whether Y>>X or Y<<X. As shown in Figure 19, if Y>>X, then there is an increasing path that goes from X to Y without crossing R; this contains nodes in the interval [X,Y]. There is also a decreasing path that decreases towards R and then decreases from R to Y; this contains nodes in the interval [X,R-small] or [R-great,Y]. The two paths cannot have common nodes other than X and Y. [Y]<---(Cloud 2)<--- [X] | ^ | | V | (Cloud 3)--->[R]--->(Cloud 1) MRT-Blue path: X->Cloud 2->Y MRT-Red path: X->Cloud 1->R->Cloud 3->Y Figure 19: Y>>X
Top   ToC   RFC7811 - Page 30
   Similar logic applies if Y<<X, as shown in Figure 20.  In this case,
   the increasing path from X increases to R and then increases from R
   to Y to use nodes in the intervals [X,R-great] and [R-small, Y].  The
   decreasing path from X reaches Y without crossing R and uses nodes in
   the interval [Y,X].

                    [X]<---(Cloud 2)<--- [Y]
                     |                    ^
                     |                    |
                     V                    |
                  (Cloud 3)--->[R]--->(Cloud 1)

                 MRT-Blue path: X->Cloud 3->R->Cloud 1->Y
                 MRT-Red path: X->Cloud 2->Y

                              Figure 20: Y<<X

5.7.2. MRT Next Hops to All Nodes Not Ordered with Respect to the Computing Node

When X and Y are not ordered, the first path should increase until we get to a node G, where G>>Y. At G, we need to decrease to Y. The other path should be just the opposite: we must decrease until we get to a node H, where H<<Y, and then increase. Since R is smaller and greater than Y, such G and H must exist. It is also easy to see that these two paths must be node disjoint: the first path contains nodes in interval [X,G] and [Y,G], while the second path contains nodes in interval [H,X] and [H,Y]. This is illustrated in Figure 21. It is necessary to decrease and then increase for the MRT-Blue and increase and then decrease for the MRT-Red; if one simply increased for one and decreased for the other, then both paths would go through the root R.
Top   ToC   RFC7811 - Page 31
                 (Cloud 6)<---[Y]<---(Cloud 5)<------------|
                   |                                       |
                   |                                       |
                   V                                       |
                  [G]--->(Cloud 4)--->[R]--->(Cloud 1)--->[H]
                   ^                                       |
                   |                                       |
                   |                                       |
                  (Cloud 3)<---[X]<---(Cloud 2)<-----------|

              MRT-Blue path: decrease to H and increase to Y
                   X->Cloud 2->H->Cloud 5->Y
              MRT-Red path:  increase to G and decrease to Y
                   X->Cloud 3->G->Cloud 6->Y

                       Figure 21: X and Y Unordered

   This gives disjoint paths as long as G and H are not the same node.
   Since G>>Y and H<<Y, if G and H could be the same node, that would
   have to be the root R.  This is not possible because there is only
   one incoming interface to the root R that is created when the initial
   cycle is found.  Recall from Figure 6 that whenever an ear was found
   to have an end that was the root R, the ear was directed from R so
   that the associated interface on R is outgoing and not incoming.
   Therefore, there must be exactly one node M that is the largest one
   before R, so the MRT-Red path will never reach R; it will turn at M
   and decrease to Y.

5.7.3. Computing Redundant Tree Next Hops in a 2-Connected Graph

The basic ideas for computing RT next hops in a 2-connected graph were given in Sections 5.7.1 and 5.7.2. Given these two ideas, how can we find the trees? If some node X only wants to find the next hops (which is usually the case for IP networks), it is enough to find which nodes are greater and less than X, and which are not ordered; this can be done by running an increasing-SPF and a decreasing-SPF rooted at X and not exploring any links from the ADAG root. In principle, a traversal method other than SPF could be used to traverse the GADAG in the process of determining blue and red next hops that result in maximally redundant trees. This will be the case as long as one traversal uses the links in the direction specified by the GADAG and the other traversal uses the links in the direction opposite of that specified by the GADAG. However, a different traversal algorithm will generally result in different blue and red
Top   ToC   RFC7811 - Page 32
   next hops.  Therefore, the algorithm specified here requires the use
   of SPF to traverse the GADAG to generate MRT blue and red next hops,
   as described below.

   An increasing-SPF rooted at X and not exploring links from the root
   will find the increasing next hops to all Y>>X.  Those increasing
   next hops are X's next hops on the MRT-Blue to reach Y.  A
   decreasing-SPF rooted at X and not exploring links from the root will
   find the decreasing next hops to all Z<<X.  Those decreasing next
   hops are X's next hops on the MRT-Red to reach Z.  Since the root R
   is both greater than and less than X, after this increasing-SPF and
   decreasing-SPF, X's next hops on the MRT-Blue and on the MRT-Red to
   reach R are known.  For every node Y>>X, X's next hops on the MRT-Red
   to reach Y are set to those on the MRT-Red to reach R.  For every
   node Z<<X, X's next hops on the MRT-Blue to reach Z are set to those
   on the MRT-Blue to reach R.

   For those nodes that were not reached by either the increasing-SPF or
   the decreasing-SPF, we can determine the next hops as well.  The
   increasing MRT-Blue next hop for a node that is not ordered with
   respect to X is the next hop along the decreasing MRT-Red towards R,
   and the decreasing MRT-Red next hop is the next hop along the
   increasing MRT-Blue towards R.  Naturally, since R is ordered with
   respect to all the nodes, there will always be an increasing and a
   decreasing path towards it.  This algorithm does not provide the
   complete specific path taken but just the appropriate next hops to
   use.  The identities of G and H are not determined by the computing
   node X.

   The final case to consider is when the GADAG root R computes its own
   next hops.  Since the GADAG root R is << all other nodes, running an
   increasing-SPF rooted at R will reach all other nodes; the MRT-Blue
   next hops are those found with this increasing-SPF.  Similarly, since
   the GADAG root R is >> all other nodes, running a decreasing-SPF
   rooted at R will reach all other nodes; the MRT-Red next hops are
   those found with this decreasing-SPF.
Top   ToC   RFC7811 - Page 33
                 E---D---|              E<--D<--|
                 |   |   |              |   ^   |
                 |   |   |              V   |   |
                 R   F   C              R   F   C
                 |   |   |              |   ^   ^
                 |   |   |              V   |   |
                 A---B---|              A-->B---|

                    (a)                    (b)
            A 2-connected graph    A spanning ADAG rooted at R

                                 Figure 22

   As an example, consider the situation depicted in Figure 22.  Node C
   runs an increasing-SPF and a decreasing-SPF on the ADAG.  The
   increasing-SPF reaches D, E, and R; the decreasing-SPF reaches B, A,
   and R.  E>>C.  So, towards E the MRT-Blue next hop is D, since E was
   reached on the increasing path through D.  The MRT-Red next hop
   towards E is B, since R was reached on the decreasing path through B.
   Since E>>D, D will similarly compute its MRT-Blue next hop to be E,
   ensuring that a packet on MRT-Blue will use path C-D-E.  B, A, and R
   will similarly compute the MRT-Red next hops towards E (which is
   ordered less than B, A and R), ensuring that a packet on MRT-Red will
   use path C-B-A-R-E.

   C can determine the next hops towards F as well.  Since F is not
   ordered with respect to C, the MRT-Blue next hop is the decreasing
   one towards R (which is B) and the MRT-Red next hop is the increasing
   one towards R (which is D).  Since F>>B, for its MRT-Blue next hop
   towards F, B will use the real increasing next hop towards F.  So a
   packet forwarded to B on MRT-Blue will get to F on path C-B-F.
   Similarly, D will use the real decreasing next hop towards F as its
   MRT-Red next hop, a packet on MRT-Red will use path C-D-F.

5.7.4. Generalizing for a Graph That Isn't 2-Connected

If a graph isn't 2-connected, then the basic approach given in Section 5.7.3 needs some extensions to determine the appropriate MRT next hops to use for destinations outside the computing router X's blocks. In order to find a pair of maximally redundant trees in that graph, we need to find a pair of RTs in each of the blocks (the root of these trees will be discussed later) and combine them.
Top   ToC   RFC7811 - Page 34
   When computing the MRT next hops from a router X, there are three
   basic differences:

   1.  Only nodes in a common block with X should be explored in the
       increasing-SPF and decreasing-SPF.

   2.  Instead of using the GADAG root, X's localroot should be used.
       This has the following implications:

       A.  The links from X's localroot should not be explored.

       B.  If a node is explored in the outgoing SPF so Y>>X, then X's
           MRT-Red next hops to reach Y uses X's MRT-Red next hops to
           reach X's localroot and if Z<<X, then X's MRT-Blue next hops
           to reach Z uses X's MRT-Blue next hops to reach X's

       C.  If a node W in a common block with X was not reached in the
           increasing-SPF or decreasing-SPF, then W is unordered with
           respect to X.  X's MRT-Blue next hops to W are X's decreasing
           (aka MRT-Red) next hops to X's localroot.  X's MRT-Red next
           hops to W are X's increasing (aka MRT-Blue) next hops to X's

   3.  For nodes in different blocks, the next hops must be inherited
       via the relevant cut-vertex.

   These are all captured in the detailed algorithm given in
   Section 5.7.5.

5.7.5. Complete Algorithm to Compute MRT Next Hops

The complete algorithm to compute MRT Next Hops for a particular router X is given in Figure 23. In addition to computing the MRT- Blue next hops and MRT-Red next hops used by X to reach each node Y, the algorithm also stores an "order_proxy", which is the proper cut- vertex to reach Y if it is outside the block, and which is used later in deciding whether the MRT-Blue or the MRT-Red can provide an acceptable alternate for a particular primary next hop.
Top   ToC   RFC7811 - Page 35
   In_Common_Block(x, y)
     if ( (x.block_id is y.block_id)
          or (x is y.localroot) or (y is x.localroot) )
        return true
     return false

   Store_Results(y, direction)
      if direction is FORWARD
         y.higher = true
         y.blue_next_hops = y.next_hops
      if direction is REVERSE
         y.lower = true
         y.red_next_hops = y.next_hops

   SPF_No_Traverse_Block_Root(spf_root, block_root, direction)
      Initialize spf_heap to empty
      Initialize nodes' spf_metric to infinity and next_hops to empty
      spf_root.spf_metric = 0
      insert(spf_heap, spf_root)
      while (spf_heap is not empty)
          min_node = remove_lowest(spf_heap)
          Store_Results(min_node, direction)
          if ((min_node is spf_root) or (min_node is not block_root))
             foreach interface intf of min_node
                if ( ( ((direction is FORWARD) and intf.OUTGOING) or
                     ((direction is REVERSE) and intf.INCOMING) )
                     and In_Common_Block(spf_root, intf.remote_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)
                        intf.remote_node.next_hops = min_node.next_hops
                      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)

     if y.blue_next_hops is empty and y.red_next_hops is empty
        y.blue_next_hops = y.localroot.blue_next_hops
        y.red_next_hops = y.localroot.red_next_hops
        y.order_proxy = y.localroot.order_proxy
Top   ToC   RFC7811 - Page 36
   Compute_MRT_NextHops(x, gadag_root)
      foreach node y
        y.higher = y.lower = false
        clear y.red_next_hops and y.blue_next_hops
        y.order_proxy = y
      SPF_No_Traverse_Block_Root(x, x.localroot, FORWARD)
      SPF_No_Traverse_Block_Root(x, x.localroot, REVERSE)

      // red and blue next hops are stored to x.localroot as different
      // paths are found via the SPF and reverse-SPF.
      // Similarly, any node whose localroot is x will have its
      // red_next_hops and blue_next_hops already set.

      // Handle nodes in the same block that aren't the localroot
      foreach node y
        if (y.IN_MRT_ISLAND and (y is not x) and
             (y.block_id is x.block_id) )
           if y.higher
              y.red_next_hops = x.localroot.red_next_hops
           else if y.lower
              y.blue_next_hops = x.localroot.blue_next_hops
              y.blue_next_hops = x.localroot.red_next_hops
              y.red_next_hops = x.localroot.blue_next_hops

      // Inherit next hops and order_proxies to other components
      if (x is not gadag_root) and (x.localroot is not gadag_root)
         gadag_root.blue_next_hops = x.localroot.blue_next_hops
         gadag_root.red_next_hops = x.localroot.red_next_hops
         gadag_root.order_proxy = x.localroot
      foreach node y
         if (y is not gadag_root) and (y is not x) and y.IN_MRT_ISLAND

   max_block_id = 0
   Assign_Block_ID(gadag_root, max_block_id)
   Compute_MRT_NextHops(x, gadag_root)

          Figure 23: Complete Algorithm to Compute MRT Next Hops

(page 36 continued on part 3)

Next Section