tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Gloss.     Arch.     IMS     UICC    |    Misc.    |    search     info

RFC 7811

 
 
 

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

Part 2 of 6, p. 18 to 36
Prev RFC Part       Next RFC Part

 


prevText      Top      ToC       Page 18 
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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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
                 else
                    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
              else
                 // 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      Up      ToC       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      Up      ToC       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 )
                         continue
                     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
                     else
                         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      Up      ToC       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      Up      ToC       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
                     else
                         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)
         Set_Other_Undirected_Links_Based_On_Topo_Order(topo)

     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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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
           localroot.

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

   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      Up      ToC       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)
                      else
                        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)
                      else
                         add_list_to_list(intf.remote_node.next_hops,
                                          min_node.next_hops)

   SetEdge(y)
     if y.blue_next_hops is empty and y.red_next_hops is empty
        SetEdge(y.localroot)
        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      Up      ToC       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
           else
              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
           SetEdge(y)

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