tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search     info

RFC 7811

 
 
 

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

Part 3 of 6, p. 36 to 61
Prev RFC Part       Next RFC Part

 


prevText      Top      ToC       Page 36 
5.8.  Identify MRT Alternates

   At this point, a computing router S knows its MRT-Blue next hops and
   MRT-Red next hops for each destination in the MRT Island.  The
   primary next hops along the SPT are also known.  It remains to
   determine for each primary next hop to a destination D, which MRT
   avoids the primary next-hop node F.  This computation depends upon
   data set in Compute_MRT_NextHops such as each node y's

Top      Up      ToC       Page 37 
   y.blue_next_hops, y.red_next_hops, y.order_proxy, y.higher, y.lower,
   and topo_orders.  Recall that any router knows only which are the
   nodes greater and lesser than itself, but it cannot decide the
   relation between any two given nodes easily; that is why we need
   topological ordering.

   For each primary next-hop node F to each destination D, S can call
   Select_Alternates(S, D, F, primary_intf) to determine whether to use
   the MRT-Blue or MRT-Red next hops as the alternate next hop(s) for
   that primary next hop.  The algorithm is given in Figure 24 and
   discussed afterwards.

  Select_Alternates_Internal(D, F, primary_intf,
                                 D_lower, D_higher, D_topo_order):
      if D_higher and D_lower
          if F.HIGHER and F.LOWER
              if F.topo_order < D_topo_order
                  return USE_RED
              else
                  return USE_BLUE
          if F.HIGHER
              return USE_RED
          if F.LOWER
              return USE_BLUE
          //F unordered wrt S
          return USE_RED_OR_BLUE

      else if D_higher
          if F.HIGHER and F.LOWER
              return USE_BLUE
          if F.LOWER
              return USE_BLUE
          if F.HIGHER
              if (F.topo_order > D_topo_order)
                  return USE_BLUE
              if (F.topo_order < D_topo_order)
                  return USE_RED
          //F unordered wrt S
          return USE_RED_OR_BLUE

      else if D_lower
          if F.HIGHER and F.LOWER
              return USE_RED
          if F.HIGHER
              return USE_RED
          if F.LOWER
              if F.topo_order > D_topo_order
                  return USE_BLUE

Top      Up      ToC       Page 38 
              if F.topo_order < D_topo_order
                  return USE_RED
          //F unordered wrt S
          return USE_RED_OR_BLUE

      else  //D is unordered wrt S
          if F.HIGHER and F.LOWER
              if primary_intf.OUTGOING and primary_intf.INCOMING
                  return USE_RED_OR_BLUE
              if primary_intf.OUTGOING
                  return USE_BLUE
              if primary_intf.INCOMING
                  return USE_RED
              //primary_intf not in GADAG
              return USE_RED
          if F.LOWER
              return USE_RED
          if F.HIGHER
              return USE_BLUE
          //F unordered wrt S
          if F.topo_order > D_topo_order:
              return USE_BLUE
          else:
              return USE_RED

  Select_Alternates(D, F, primary_intf)
      if not In_Common_Block(F, S)
          return PRIM_NH_IN_DIFFERENT_BLOCK
      if (D is F) or (D.order_proxy is F)
          return PRIM_NH_IS_D_OR_OP_FOR_D
      D_lower = D.order_proxy.LOWER
      D_higher = D.order_proxy.HIGHER
      D_topo_order = D.order_proxy.topo_order
      return Select_Alternates_Internal(D, F, primary_intf,
                                        D_lower, D_higher, D_topo_order)

      Figure 24: Select_Alternates() and Select_Alternates_Internal()

   It is useful to first handle the case where F is also D, or F is the
   order proxy for D.  In this case, only link protection is possible.
   The MRT that doesn't use the failed primary next hop is used.  If
   both MRTs use the primary next hop, then the primary next hop must be
   a cut-link, so either MRT could be used but the set of MRT next hops
   must be pruned to avoid the failed primary next-hop interface.  To
   indicate this case, Select_Alternates returns
   PRIM_NH_IS_D_OR_OP_FOR_D.  Explicit pseudocode to handle the three
   sub-cases above is not provided.

Top      Up      ToC       Page 39 
   The logic behind Select_Alternates_Internal() is described in
   Figure 25.  As an example, consider the first case described in the
   table, where the D>>S and D<<S.  If this is true, then either S or D
   must be the block root, R.  If F>>S and F<<S, then S is the block
   root.  So the blue path from S to D is the increasing path to D, and
   the red path S to D is the decreasing path to D.  If the
   F.topo_order>D.topo_order, then either F is ordered higher than D or
   F is unordered with respect to D.  Therefore, F is either on a
   decreasing path from S to D, or it is on neither an increasing nor a
   decreasing path from S to D.  In either case, it is safe to take an
   increasing path from S to D to avoid F.  We know that when S is R,
   the increasing path is the blue path, so it is safe to use the blue
   path to avoid F.

   If instead F.topo_order<D.topo_order, then either F is ordered lower
   than D, or F is unordered with respect to D.  Therefore, F is either
   on an increasing path from S to D, or it is on neither an increasing
   nor a decreasing path from S to D.  In either case, it is safe to
   take a decreasing path from S to D to avoid F.  We know that when S
   is R, the decreasing path is the red path, so it is safe to use the
   red path to avoid F.

   If F>>S or F<<S (but not both), then D is the block root.  We then
   know that the blue path from S to D is the increasing path to R, and
   the red path is the decreasing path to R.  When F>>S, we deduce that
   F is on an increasing path from S to R.  So in order to avoid F, we
   use a decreasing path from S to R, which is the red path.  Instead,
   when F<<S, we deduce that F is on a decreasing path from S to R.  So
   in order to avoid F, we use an increasing path from S to R, which is
   the blue path.

   All possible cases are systematically described in the same manner in
   the rest of the table.

Top      Up      ToC       Page 40 
+------+------------+------+------------------------------+------------+
| D    | MRT blue   | F    | additional      | F          | Alternate  |
| wrt  | and red    | wrt  | criteria        | wrt        |            |
| S    | path       | S    |                 | MRT        |            |
|      | properties |      |                 | (deduced)  |            |
+------+------------+------+-----------------+------------+------------+
| D>>S | Blue path: | F>>S | additional      | F on an    | Use Red    |
| and  | Increasing | only | criteria        | increasing | to avoid   |
| D<<S,| path to R. |      | not needed      | path from  | F          |
| D is | Red path:  |      |                 | S to R     |            |
| R,   | Decreasing +------+-----------------+------------+------------+
|      | path to R. | F<<S | additional      | F on a     | Use Blue   |
|      |            | only | criteria        | decreasing | to avoid   |
|      |            |      | not needed      | path from  | F          |
| or   |            |      |                 | S to R     |            |
|      |            +------+-----------------+------------+------------+
|      |            | F>>S | topo(F)>topo(D) | F on a     | Use Blue   |
| S is | Blue path: | and  | implies that    | decreasing | to avoid   |
| R    | Increasing | F<<S,| F>>D or F??D    | path from  | F          |
|      | path to D. |      |                 | S to D or  |            |
|      | Red path:  |      |                 | neither    |            |
|      | Decreasing |      +-----------------+------------+------------+
|      | path to D. |      | topo(F)<topo(D) | F on an    | Use Red    |
|      |            |      | implies that    | increasing | to avoid   |
|      |            |      | F<<D or F??D    | path from  | F          |
|      |            |      |                 | S to D or  |            |
|      |            |      |                 | neither    |            |
|      |            +------+-----------------+------------+------------+
|      |            | F??S | Can only occur  | F is on    | Use Red    |
|      |            |      | when link       | neither    | or Blue    |
|      |            |      | between         | increasing | to avoid   |
|      |            |      | F and S         | nor decr.  | F          |
|      |            |      | is marked       | path from  |            |
|      |            |      | MRT_INELIGIBLE  | S to D or R|            |

Top      Up      ToC       Page 41 
+------+------------+------+-----------------+------------+------------+
| D>>S | Blue path: | F<<S | additional      | F on       | Use Blue   |
| only | Increasing | only | criteria        | decreasing | to avoid   |
|      | shortest   |      | not needed      | path from  | F          |
|      | path from  |      |                 | S to R     |            |
|      | S to D.    +------+-----------------+------------+------------+
|      | Red path:  | F>>S | topo(F)>topo(D) | F on       | Use Blue   |
|      | Decreasing | only | implies that    | decreasing | to avoid   |
|      | shortest   |      | F>>D or F??D    | path from  | F          |
|      | path from  |      |                 | R to D     |            |
|      | S to R,    |      |                 | or         |            |
|      | then       |      |                 | neither    |            |
|      | decreasing |      +-----------------+------------+------------+
|      | shortest   |      | topo(F)<topo(D) | F on       | Use Red    |
|      | path from  |      | implies that    | increasing | to avoid   |
|      | R to D.    |      | F<<D or F??D    | path from  | F          |
|      |            |      |                 | S to D     |            |
|      |            |      |                 | or         |            |
|      |            |      |                 | neither    |            |
|      |            +------+-----------------+------------+------------+
|      |            | F>>S | additional      | F on Red   | Use Blue   |
|      |            | and  | criteria        |            | to avoid   |
|      |            | F<<S,| not needed      |            | F          |
|      |            | F is |                 |            |            |
|      |            | R    |                 |            |            |
|      |            +------+-----------------+------------+------------+
|      |            | F??S | Can only occur  | F is on    | Use Red    |
|      |            |      | when link       | neither    | or Blue    |
|      |            |      | between         | increasing | to avoid   |
|      |            |      | F and S         | nor decr.  | F          |
|      |            |      | is marked       | path from  |            |
|      |            |      | MRT_INELIGIBLE  | S to D or R|            |

Top      Up      ToC       Page 42 
+------+------------+------+-----------------+------------+------------+
| D<<S | Blue path: | F>>S | additional      | F on       | Use Red    |
| only | Increasing | only | criteria        | increasing | to avoid   |
|      | shortest   |      | not needed      | path from  | F          |
|      | path from  |      |                 | S to R     |            |
|      | S to R,    +------+-----------------+------------+------------+
|      | then       | F<<S | topo(F)>topo(D) | F on       | Use Blue   |
|      | increasing | only | implies that    | decreasing | to avoid   |
|      | shortest   |      | F>>D or F??D    | path from  | F          |
|      | path from  |      |                 | R to D     |            |
|      | R to D.    |      |                 | or         |            |
|      | Red path:  |      |                 | neither    |            |
|      | Decreasing |      +-----------------+------------+------------+
|      | shortest   |      | topo(F)<topo(D) | F on       | Use Red    |
|      | path from  |      | implies that    | increasing | to avoid   |
|      | S to D.    |      | F<<D or F??D    | path from  | F          |
|      |            |      |                 | S to D     |            |
|      |            |      |                 | or         |            |
|      |            |      |                 | neither    |            |
|      |            +------+-----------------+------------+------------+
|      |            | F>>S | additional      | F on Blue  | Use Red    |
|      |            | and  | criteria        |            | to avoid   |
|      |            | F<<S,| not             |            | F          |
|      |            | F is | needed          |            |            |
|      |            | R    |                 |            |            |
|      |            +------+-----------------+------------+------------+
|      |            | F??S | Can only occur  | F is on    | Use Red    |
|      |            |      | when link       | neither    | or Blue    |
|      |            |      | between         | increasing | to avoid   |
|      |            |      | F and S         | nor decr.  | F          |
|      |            |      | is marked       | path from  |            |
|      |            |      | MRT_INELIGIBLE  | S to D or R|            |
+------+------------+------+-----------------+------------+------------+
| D??S | Blue path: | F<<S | additional      | F on a     | Use Red    |
|      | Decr. from | only | criteria        | decreasing | to avoid   |
|      | S to first |      | not needed      | path from  | F          |
|      | node K<<D, |      |                 | S to K.    |            |
|      | then incr. +------+-----------------+------------+------------+
|      | to D.      | F>>S | additional      | F on an    | Use Blue   |
|      | Red path:  | only | criteria        | increasing | to avoid   |
|      | Incr. from |      | not needed      | path from  | F          |
|      | S to first |      |                 | S to L     |            |
|      | node L>>D, |      |                 |            |            |
|      | then decr. |      |                 |            |            |

Top      Up      ToC       Page 43 
|      |            +------+-----------------+------------+------------+
|      |            | F??S | topo(F)>topo(D) | F on decr. | Use Blue   |
|      |            |      | implies that    | path from  | to avoid   |
|      |            |      | F>>D or F??D    | L to D or  | F          |
|      |            |      |                 | neither    |            |
|      |            |      +-----------------+------------+------------+
|      |            |      | topo(F)<topo(D) | F on incr. | Use Red    |
|      |            |      | implies that    | path from  | to avoid   |
|      |            |      | F<<D or F??D    | K to D or  | F          |
|      |            |      |                 | neither    |            |
|      |            +------+-----------------+------------+------------+
|      |            | F>>S | GADAG link      | F on an    | Use Blue   |
|      |            | and  | direction       | incr. path | to avoid   |
|      |            | F<<S,| S->F            | from S     | F          |
|      |            | F is +-----------------+------------+------------+
|      |            | R    | GADAG link      | F on a     | Use Red    |
|      |            |      | direction       | decr. path | to avoid   |
|      |            |      | S<-F            | from S     | F          |
|      |            |      +-----------------+------------+------------+
|      |            |      | GADAG link      | Either F is the order   |
|      |            |      | direction       | proxy for D (case       |
|      |            |      | S<-->F          | already handled) or D   |
|      |            |      |                 | is in a different block |
|      |            |      |                 | from F, in which case   |
|      |            |      |                 | Red or Blue avoids F    |
|      |            |      +-----------------+-------------------------+
|      |            |      | S-F link not    | Relies on special       |
|      |            |      | in GADAG,       | construction of GADAG   |
|      |            |      | only when       | to demonstrate that     |
|      |            |      | S-F link is     | using Red avoids F      |
|      |            |      | MRT_INELIGIBLE  | (see text)              |
+------+------------+------+-----------------+-------------------------+

    Determining MRT next hops and alternates based on the partial order
         and topological sort relationships between the source(S),
     destination(D), primary next hop(F), and block root(R).  topo(N)
   indicates the topological sort value of node N.  X??Y indicates that
    node X is unordered with respect to node Y.  It is assumed that the
    case where F is D, or where F is the order proxy for D, has already
                               been handled.

            Figure 25: Determining MRT Next Hops and Alternates

   The last case in Figure 25 requires additional explanation.  The fact
   that the red path from S to D in this case avoids F relies on a
   special property of the GADAGs that we have constructed in this
   algorithm, a property not shared by all GADAGs in general.  When D is
   unordered with respect to S, and F is the localroot for S, it can

Top      Up      ToC       Page 44 
   occur that the link between S and F is not in the GADAG only when
   that link has been marked MRT_INELIGIBLE.  For an arbitrary GADAG, S
   doesn't have enough information based on the computed order
   relationships to determine if the red path or blue path will hit F
   (which is also the localroot) before hitting K or L, and making it
   safely to D.  However, the GADAGs that we construct using the
   algorithm in this document are not arbitrary GADAGs.  They have the
   additional property that incoming links to a localroot come from only
   one other node in the same block.  This is a result of the method of
   construction.  This additional property guarantees that the red path
   from S to D will never pass through the localroot of S.  (That would
   require the localroot to play the role of L, the first node in the
   path ordered higher than D, which would in turn require the localroot
   to have two incoming links in the GADAG, which cannot happen.)
   Therefore, it is safe to use the red path to avoid F with these
   specially constructed GADAGs.

   As an example of how Select_Alternates_Internal() operates, consider
   the ADAG depicted in Figure 26 and first suppose that G is the
   source, D is the destination, and H is the failed next hop.  Since
   D>>G, we need to compare H.topo_order and D.topo_order.  Since
   D.topo_order>H.topo_order, D must be either higher than H or
   unordered with respect to H, so we should select the decreasing path
   towards the root.  If, however, the destination were instead J, we
   must find that H.topo_order>J.topo_order, so we must choose the
   increasing Blue next hop to J, which is I.  In the case, when instead
   the destination is C, we find that we need to first decrease to avoid
   using H, so the Blue, first decreasing then increasing, path is
   selected.

                             [E]<-[D]<-[H]<-[J]
                              |    ^    ^    ^
                              V    |    |    |
                             [R]  [C]  [G]->[I]
                              |    ^    ^    ^
                              V    |    |    |
                             [A]->[B]->[F]---|


            Figure 26: ADAG Rooted at R for a 2-Connected Graph

5.9.  Named Proxy-Nodes

   As discussed in Section 11.2 of [RFC7812], it is necessary to find
   MRT-Blue and MRT-Red next hops and MRT-FRR alternates for named
   proxy-nodes.  An example use case is for a router that is not part of
   that local MRT Island, when there is only partial MRT support in the
   domain.

Top      Up      ToC       Page 45 
5.9.1.  Determining Proxy-Node Attachment Routers

   Section 11.2 of [RFC7812] discusses general considerations for
   determining the two proxy-node attachment routers for a given proxy-
   node, corresponding to a prefix.  A router in the MRT Island that
   advertises the prefix is a candidate for being a proxy-node
   attachment router, with the associated named-proxy-cost equal to the
   advertised cost to the prefix.

   An Island Border Router (IBR) is a router in the MRT Island that is
   connected to an Island Neighbor (IN), which is a router not in the
   MRT Island but in the same area/level.  An (IBR,IN) pair is a
   candidate for being a proxy-node attachment router, if the shortest
   path from the IN to the prefix does not enter the MRT Island.  A
   method for identifying such Loop-Free Island Neighbors (LFINs) is
   given below.  The named-proxy-cost assigned to each (IBR, IN) pair is
   cost(IBR, IN) + D_opt(IN, prefix).

   From the set of prefix-advertising routers and the set of IBRs with
   at least one LFIN, the two routers with the lowest named-proxy-cost
   are selected.  Ties are broken based upon the lowest Router ID.  For
   ease of discussion, the two selected routers will be referred to as
   proxy-node attachment routers.

5.9.2.  Computing If an Island Neighbor (IN) Is Loop-Free

   As discussed above, the IN needs to be loop-free with respect to the
   whole MRT Island for the destination.  This can be accomplished by
   running the usual SPF algorithm while keeping track of which shortest
   paths have passed through the MRT island.  Pseudocode for this is
   shown in Figure 27.  The Island_Marking_SPF() is run for each IN that
   needs to be evaluated for the loop-free condition, with the IN as the
   spf_root.  Whether or not an IN is loop-free with respect to the MRT
   island can then be determined by evaluating node.PATH_HITS_ISLAND for
   each destination of interest.

Top      Up      ToC       Page 46 
    Island_Marking_SPF(spf_root)
        Initialize spf_heap to empty
        Initialize nodes' spf_metric to infinity and next_hops to empty
            and PATH_HITS_ISLAND to false
        spf_root.spf_metric = 0
        insert(spf_heap, spf_root)
        while (spf_heap is not empty)
            min_node = remove_lowest(spf_heap)
            foreach interface intf of min_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
                    if intf.remote_node.IN_MRT_ISLAND
                        intf.remote_node.PATH_HITS_ISLAND = true
                    else
                        intf.remote_node.PATH_HITS_ISLAND =
                            min_node.PATH_HITS_ISLAND
                    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)
                    if intf.remote_node.IN_MRT_ISLAND
                        intf.remote_node.PATH_HITS_ISLAND = true
                    else
                        intf.remote_node.PATH_HITS_ISLAND =
                            min_node.PATH_HITS_ISLAND

   Figure 27: Island_Marking_SPF() for Determining If an Island Neighbor
                               Is Loop-Free

   It is also possible that a given prefix is originated by a
   combination of non-island routers and island routers.  The results of
   the Island_Marking_SPF() computation can be used to determine if the
   shortest path from an IN to reach that prefix hits the MRT Island.
   The shortest path for the IN to reach prefix P is determined by the
   total cost to reach prefix P, which is the sum of the cost for the IN
   to reach a prefix-advertising node and the cost with which that node
   advertises the prefix.  The path with the minimum total cost to
   prefix P is chosen.  If the prefix-advertising node for that minimum
   total cost path has PATH_HITS_ISLAND set to True, then the IN is not
   loop-free with respect to the MRT Island for reaching prefix P.  If

Top      Up      ToC       Page 47 
   there are multiple minimum total cost paths to reach prefix P, then
   all of the prefix-advertising routers involved in the minimum total
   cost paths MUST have PATH_HITS_ISLAND set to False for the IN to be
   considered loop-free to reach P.

   Note that there are other computations that could be used to
   determine if paths from a given IN _might_ pass through the MRT
   Island for a given prefix or destination.  For example, a previous
   draft version of this document specified running the SPF algorithm on
   modified topology that treats the MRT Island as a single node (with
   intra-island links set to zero cost) in order to provide input to
   computations to determine if the path from IN to non-island
   destination hits the MRT Island in this modified topology.  This
   computation is enough to guarantee that a path will not hit the MRT
   Island in the original topology.  However, it is possible that a path
   that is disqualified for hitting the MRT Island in the modified
   topology will not actually hit the MRT Island in the original
   topology.  The algorithm described in Island_Marking_SPF() above does
   not modify the original topology, and will only disqualify a path if
   the actual path does in fact hit the MRT Island.

   Since all routers need to come to the same conclusion about which
   routers qualify as LFINs, this specification requires that all
   routers computing LFINs MUST use an algorithm whose result is
   identical to that of the Island_Marking_SPF() in Figure 27.

5.9.3.  Computing MRT Next Hops for Proxy-Nodes

   Determining the MRT next hops for a proxy-node in the degenerate case
   where the proxy-node is attached to only one node in the GADAG is
   trivial, as all needed information can be derived from that proxy-
   node attachment router.  If there are multiple interfaces connecting
   the proxy-node to the single proxy-node attachment router, then some
   can be assigned to MRT-Red and others to MRT_Blue.

   Now, consider the proxy-node P that is attached to two proxy-node
   attachment routers.  The pseudocode for Select_Proxy_Node_NHs(P,S) in
   Figure 28 specifies how a computing-router S MUST compute the MRT red
   and blue next hops to reach proxy-node P.  The proxy-node attachment
   router with the lower value of mrt_node_id (as defined in Figure 15)
   is assigned to X, and the other proxy-node attachment router is
   assigned to Y.  We will be using the relative order of X,Y, and S in
   the partial order defined by the GADAG to determine the MRT red and
   blue next hops to reach P, so we also define A and B as the order
   proxies for X and Y, respectively, with respect to S.  The order
   proxies for all nodes with respect to S were already computed in
   Compute_MRT_NextHops().

Top      Up      ToC       Page 48 
 def Select_Proxy_Node_NHs(P,S):
     if P.pnar1.node.node_id < P.pnar2.node.node_id:
         X = P.pnar1.node
         Y = P.pnar2.node
     else:
         X = P.pnar2.node
         Y = P.pnar1.node
     P.pnar_X = X
     P.pnar_Y = Y
     A = X.order_proxy
     B = Y.order_proxy
     if (A is S.localroot
         and B is S.localroot):
         // case 1.0
         Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
         Copy_List_Items(P.red_next_hops, Y.red_next_hops)
         return
     if (A is S.localroot
         and B is not S.localroot):
         // case 2.0
         if B.LOWER:
             // case 2.1
             Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
             Copy_List_Items(P.red_next_hops, Y.red_next_hops)
             return
         if B.HIGHER:
             // case 2.2
             Copy_List_Items(P.blue_next_hops, X.red_next_hops)
             Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
             return
         else:
             // case 2.3
             Copy_List_Items(P.blue_next_hops, X.red_next_hops)
             Copy_List_Items(P.red_next_hops, Y.red_next_hops)
             return
     if (A is not S.localroot
         and B is S.localroot):
         // case 3.0
         if A.LOWER:
             // case 3.1
             Copy_List_Items(P.blue_next_hops, X.red_next_hops)
             Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
             return
         if A.HIGHER:
             // case 3.2
             Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
             Copy_List_Items(P.red_next_hops, Y.red_next_hops)
             return

Top      Up      ToC       Page 49 
         else:
             // case 3.3
             Copy_List_Items(P.blue_next_hops, X.red_next_hops)
             Copy_List_Items(P.red_next_hops, Y.red_next_hops)
             return
     if (A is not S.localroot
         and B is not S.localroot):
         // case 4.0
         if (S is A.localroot or S is B.localroot):
             // case 4.05
             if A.topo_order < B.topo_order:
                 // case 4.05.1
                 Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
                 Copy_List_Items(P.red_next_hops, Y.red_next_hops)
                 return
             else:
                 // case 4.05.2
                 Copy_List_Items(P.blue_next_hops, X.red_next_hops)
                 Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
                 return
         if A.LOWER:
             // case 4.1
             if B.HIGHER:
                 // case 4.1.1
                 Copy_List_Items(P.blue_next_hops, X.red_next_hops)
                 Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
                 return
             if B.LOWER:
                 // case 4.1.2
                 if A.topo_order < B.topo_order:
                     // case 4.1.2.1
                     Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
                     Copy_List_Items(P.red_next_hops, Y.red_next_hops)
                     return
                 else:
                     // case 4.1.2.2
                     Copy_List_Items(P.blue_next_hops, X.red_next_hops)
                     Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
                     return
             else:
                 // case 4.1.3
                 Copy_List_Items(P.blue_next_hops, X.red_next_hops)
                 Copy_List_Items(P.red_next_hops, Y.red_next_hops)
                 return
         if A.HIGHER:
             // case 4.2

Top      Up      ToC       Page 50 
             if B.HIGHER:
                 // case 4.2.1
                 if A.topo_order < B.topo_order:
                     // case 4.2.1.1
                     Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
                     Copy_List_Items(P.red_next_hops, Y.red_next_hops)
                     return
                 else:
                     // case 4.2.1.2
                     Copy_List_Items(P.blue_next_hops, X.red_next_hops)
                     Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
                     return
             if B.LOWER:
                 // case 4.2.2
                 Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
                 Copy_List_Items(P.red_next_hops, Y.red_next_hops)
                 return
             else:
                 // case 4.2.3
                 Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
                 Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
                 return
         else:
             // case 4.3
             if B.LOWER:
                 // case 4.3.1
                 Copy_List_Items(P.blue_next_hops, X.red_next_hops)
                 Copy_List_Items(P.red_next_hops, Y.red_next_hops)
                 return
             if B.HIGHER:
                 // case 4.3.2
                 Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
                 Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
                 return
             else:
                 // case 4.3.3
                 if A.topo_order < B.topo_order:
                     // case 4.3.3.1
                     Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
                     Copy_List_Items(P.red_next_hops, Y.red_next_hops)
                     return

Top      Up      ToC       Page 51 
                 else:
                     // case 4.3.3.2
                     Copy_List_Items(P.blue_next_hops, X.red_next_hops)
                     Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
                     return
     assert(False)

                    Figure 28: Select_Proxy_Node_NHs()

   It is useful to understand up front that the blue next hops to reach
   proxy-node P produced by Select_Proxy_Node_NHs() will always be the
   next hops that reach proxy-node attachment router X, while the red
   next hops to reach proxy-node P will always be the next hops that
   reach proxy-node attachment router Y.  This is different from the red
   and blue next hops produced by Compute_MRT_NextHops() where, for
   example, blue next hops to a destination that is ordered with respect
   to the source will always correspond to an INCREASING next hop on the
   GADAG.  The exact choice of which next hops chosen by
   Select_Proxy_Node_NHs() as the blue next hops to reach P (which will
   necessarily go through X on its way to P) does depend on the GADAG,
   but the relationship is more complex than was the case with
   Compute_MRT_NextHops().

   There are 21 different relative order relationships between A, B, and
   S that Select_Proxy_Node_NHs() uses to determine red and blue next
   hops to P.  This document does not attempt to provide an exhaustive
   description of each case considered in Select_Proxy_Node_NHs().
   Instead, we provide a high-level overview of the different cases, and
   we consider a few cases in detail to give an example of the reasoning
   that can be used to understand each case.

   At the highest level, Select_Proxy_Node_NHs() distinguishes between
   four different cases depending on whether or not A or B is the
   localroot for S.  For example, for case 4.0, neither A nor B is the
   localroot for S.  Case 4.05 addresses the case where S is the
   localroot for either A or B, while cases 4.1, 4.2, and 4.3 address
   the cases where A is ordered lower than S, A is ordered higher than
   S, or A is unordered with respect to S on the GADAG.  In general,
   each of these cases is then further subdivided into whether or not B
   is ordered lower than S, B is ordered higher than S, or B is
   unordered with respect to S.  In some cases, we also need a further
   level of discrimination, where we use the topological sort order of A
   with respect to B.

   As a detailed example, let's consider case 4.1 and all of its sub-
   cases, and explain why the red and blue next hops to reach P are
   chosen as they are in Select_Proxy_Node_NHs().  In case 4.1, neither
   A nor B is the localroot for S, S is not the localroot for A or B,

Top      Up      ToC       Page 52 
   and A is ordered lower than S on the GADAG.  In this situation, we
   know that the red path to reach X (as computed in
   Compute_MRT_NextHops()) will follow DECREASING next hops towards A,
   while the blue path to reach X will follow INCREASING next hops to
   the localroot, and then INCREASING next hops to A.

   Now consider sub-case 4.1.1 where B is ordered higher than S.  In
   this situation, we know that the blue path to reach Y will follow
   INCREASING next hops towards B, while the red next hops to reach Y
   will follow DECREASING next hops to the localroot, and then
   DECREASING next hops to B.  So, to reach X and Y by two disjoint
   paths, we can choose the red next hops to X and the blue next hops to
   Y.  We have chosen the convention that blue next hops to P are those
   that pass through X, and red next hops to P are those that pass
   through Y, so we can see that case 4.1.1 produces the desired result.
   Choosing blue to X and red to Y does not produce disjoint paths
   because the paths intersect at least at the localroot.

   Now consider sub-case 4.1.2 where B is ordered lower than S.  In this
   situation, we know that the red path to reach Y will follow
   DECREASING next hops towards B, while the BLUE next hops to reach Y
   will follow INCREASING next hops to the localroot, and then
   INCREASING next hops to A.  The choice here is more difficult than in
   4.1.1 because A and B are both on the DECREASING path from S towards
   the localroot.  We want to use the direct DECREASING(red) path to the
   one that is nearer to S on the GADAG.  We get this extra information
   by comparing the topological sort order of A and B.  If
   A.topo_order<B.topo_order, then we use red to Y and blue to X, since
   the red path to Y will DECREASE to B without hitting A, and the blue
   path to X will INCREASE to A without hitting B.  Instead, if
   A.topo_order>B.topo_order, then we use red to X and blue to Y.

   Note that when A is unordered with respect to B, the result of
   comparing A.topo_order with B.topo_order could be greater than or
   less than.  In this case, the result doesn't matter because either
   choice (red to Y and blue to X or red to X and blue to Y) would work.
   What is required is that all nodes in the network give the same
   result when comparing A.topo_order with B.topo_order.  This is
   guaranteed by having all nodes run the same algorithm
   (Run_Topological_Sort_GADAG()) to compute the topological sort order.

   Finally, we consider case 4.1.3, where B is unordered with respect to
   S.  In this case, the blue path to reach Y will follow the DECREASING
   next hops towards the localroot until it reaches some node (K) which
   is ordered less than B, after which it will take INCREASING next hops
   to B.  The red path to reach Y will follow the INCREASING next hops
   towards the localroot until it reaches some node (L) which is ordered
   greater than B, after which it will take DECREASING next hops to B.

Top      Up      ToC       Page 53 
   Both K and A are reached by DECREASING from S, but we don't have
   information about whether or not that DECREASING path will hit K or A
   first.  Instead, we do know that the INCREASING path from S will hit
   L before reaching A.  Therefore, we use the red path to reach Y and
   the red path to reach X.

   Similar reasoning can be applied to understand the other 17 cases
   used in Select_Proxy_Node_NHs().  However, cases 2.3 and 3.3 deserve
   special attention because the correctness of the solution for these
   two cases relies on a special property of the GADAGs that we have
   constructed in this algorithm, a property not shared by all GADAGs in
   general.  Focusing on case 2.3, we consider the case where A is the
   localroot for S, while B is not, and B is unordered with respect to
   S.  The red path to X DECREASES from S to the localroot A, while the
   blue path to X INCREASES from S to the localroot A.  The blue path to
   Y DECREASES towards the localroot A until it reaches some node (K)
   which is ordered less than B, after which the path INCREASES to B.
   The red path to Y INCREASES towards the localroot A until it reaches
   some node (L) which is ordered greater than B, after which the path
   DECREASES to B.  It can be shown that for an arbitrary GADAG, with
   only the ordering relationships computed so far, we don't have enough
   information to choose a pair of paths to reach X and Y that are
   guaranteed to be disjoint.  In some topologies, A will play the role
   of K, the first node ordered less than B on the blue path to Y.  In
   other topologies, A will play the role of L, the first node ordered
   greater than B on the red path to Y.  The basic problem is that we
   cannot distinguish between these two cases based on the ordering
   relationships.

   As discussed Section 5.8, the GADAGs that we construct using the
   algorithm in this document are not arbitrary GADAGs.  They have the
   additional property that incoming links to a localroot come from only
   one other node in the same block.  This is a result of the method of
   construction.  This additional property guarantees that localroot A
   will never play the role of L in the red path to Y, since L must have
   at least two incoming links from different nodes in the same block in
   the GADAG.  This, in turn, allows Select_Proxy_Node_NHs() to choose
   the red path to Y and the red path to X as the disjoint MRT paths to
   reach P.

5.9.4.  Computing MRT Alternates for Proxy-Nodes

   After finding the red and the blue next hops for a given proxy-node
   P, it is necessary to know which one of these to use in the case of
   failure.  This can be done by Select_Alternates_Proxy_Node(), as
   shown in the pseudocode in Figure 29.

Top      Up      ToC       Page 54 
  def Select_Alternates_Proxy_Node(P,F,primary_intf):
      S = primary_intf.local_node
      X = P.pnar_X
      Y = P.pnar_Y
      A = X.order_proxy
      B = Y.order_proxy
      if F is A and F is B:
          return 'PRIM_NH_IS_OP_FOR_BOTH_X_AND_Y'
      if F is A:
          return 'USE_RED'
      if F is B:
          return 'USE_BLUE'

      if not In_Common_Block(A, B):
          if In_Common_Block(F, A):
              return 'USE_RED'
          elif In_Common_Block(F, B):
              return 'USE_BLUE'
          else:
              return 'USE_RED_OR_BLUE'
      if (not In_Common_Block(F, A)
          and not In_Common_Block(F, A) ):
          return 'USE_RED_OR_BLUE'

      alt_to_X = Select_Alternates(X, F, primary_intf)
      alt_to_Y = Select_Alternates(Y, F, primary_intf)

      if (alt_to_X == 'USE_RED_OR_BLUE'
          and alt_to_Y == 'USE_RED_OR_BLUE'):
          return 'USE_RED_OR_BLUE'
      if alt_to_X == 'USE_RED_OR_BLUE':
          return 'USE_BLUE'
      if alt_to_Y == 'USE_RED_OR_BLUE':
          return 'USE_RED'

      if (A is S.localroot
          and B is S.localroot):
          // case 1.0
          if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'):
              return 'USE_RED_OR_BLUE'
          if alt_to_X == 'USE_BLUE':
              return 'USE_BLUE'
          if alt_to_Y == 'USE_RED':
              return 'USE_RED'
          assert(False)
      if (A is S.localroot
          and B is not S.localroot):
          // case 2.0

Top      Up      ToC       Page 55 
          if B.LOWER:
              // case 2.1
              if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'):
                  return 'USE_RED_OR_BLUE'
              if alt_to_X == 'USE_BLUE':
                  return 'USE_BLUE'
              if alt_to_Y == 'USE_RED':
                  return 'USE_RED'
              assert(False)
          if B.HIGHER:
              // case 2.2
              if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'):
                  return 'USE_RED_OR_BLUE'
              if alt_to_X == 'USE_RED':
                  return 'USE_BLUE'
              if alt_to_Y == 'USE_BLUE':
                  return 'USE_RED'
              assert(False)
          else:
              // case 2.3
              if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'):
                  return 'USE_RED_OR_BLUE'
              if alt_to_X == 'USE_RED':
                  return 'USE_BLUE'
              if alt_to_Y == 'USE_RED':
                  return 'USE_RED'
              assert(False)
      if (A is not S.localroot
          and B is S.localroot):
          // case 3.0
          if A.LOWER:
              // case 3.1
              if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'):
                  return 'USE_RED_OR_BLUE'
              if alt_to_X == 'USE_RED':
                  return 'USE_BLUE'
              if alt_to_Y == 'USE_BLUE':
                  return 'USE_RED'
              assert(False)
          if A.HIGHER:
              // case 3.2
              if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'):
                  return 'USE_RED_OR_BLUE'
              if alt_to_X == 'USE_BLUE':
                  return 'USE_BLUE'
              if alt_to_Y == 'USE_RED':
                  return 'USE_RED'
              assert(False)

Top      Up      ToC       Page 56 
          else:
              // case 3.3
              if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'):
                  return 'USE_RED_OR_BLUE'
              if alt_to_X == 'USE_RED':
                  return 'USE_BLUE'
              if alt_to_Y == 'USE_RED':
                  return 'USE_RED'
              assert(False)
      if (A is not S.localroot
          and B is not S.localroot):
          // case 4.0
          if (S is A.localroot or S is B.localroot):
              // case 4.05
              if A.topo_order < B.topo_order:
                  // case 4.05.1
                  if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'):
                      return 'USE_RED_OR_BLUE'
                  if alt_to_X == 'USE_BLUE':
                      return 'USE_BLUE'
                  if alt_to_Y == 'USE_RED':
                      return 'USE_RED'
                  assert(False)
              else:
                  // case 4.05.2
                  if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'):
                      return 'USE_RED_OR_BLUE'
                  if alt_to_X == 'USE_RED':
                      return 'USE_BLUE'
                  if alt_to_Y == 'USE_BLUE':
                      return 'USE_RED'
                  assert(False)
          if A.LOWER:
              // case 4.1
              if B.HIGHER:
                  // case 4.1.1
                  if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'):
                      return 'USE_RED_OR_BLUE'
                  if alt_to_X == 'USE_RED':
                      return 'USE_BLUE'
                  if alt_to_Y == 'USE_BLUE':
                      return 'USE_RED'
                  assert(False)
              if B.LOWER:
                  // case 4.1.2
                  if A.topo_order < B.topo_order:
                      // case 4.1.2.1
                      if (alt_to_X == 'USE_BLUE'

Top      Up      ToC       Page 57 
                          and alt_to_Y == 'USE_RED'):
                          return 'USE_RED_OR_BLUE'
                      if alt_to_X == 'USE_BLUE':
                          return 'USE_BLUE'
                      if alt_to_Y == 'USE_RED':
                          return 'USE_RED'
                      assert(False)
                  else:
                      // case 4.1.2.2
                      if (alt_to_X == 'USE_RED'
                          and alt_to_Y == 'USE_BLUE'):
                          return 'USE_RED_OR_BLUE'
                      if alt_to_X == 'USE_RED':
                          return 'USE_BLUE'
                      if alt_to_Y == 'USE_BLUE':
                          return 'USE_RED'
                      assert(False)
              else:
                  // case 4.1.3
                  if (F.LOWER and not F.HIGHER
                      and F.topo_order > A.topo_order):
                      // case 4.1.3.1
                      return 'USE_RED'
                  else:
                      // case 4.1.3.2
                      return 'USE_BLUE'
          if A.HIGHER:
              // case 4.2
              if B.HIGHER:
                  // case 4.2.1
                  if A.topo_order < B.topo_order:
                      // case 4.2.1.1
                      if (alt_to_X == 'USE_BLUE'
                          and alt_to_Y == 'USE_RED'):
                          return 'USE_RED_OR_BLUE'
                      if alt_to_X == 'USE_BLUE':
                          return 'USE_BLUE'
                      if alt_to_Y == 'USE_RED':
                          return 'USE_RED'
                      assert(False)
                  else:
                      // case 4.2.1.2
                      if (alt_to_X == 'USE_RED'
                          and alt_to_Y == 'USE_BLUE'):
                          return 'USE_RED_OR_BLUE'
                      if alt_to_X == 'USE_RED':
                          return 'USE_BLUE'
                      if alt_to_Y == 'USE_BLUE':

Top      Up      ToC       Page 58 
                          return 'USE_RED'
                      assert(False)
              if B.LOWER:
                  // case 4.2.2
                  if (alt_to_X == 'USE_BLUE'
                      and alt_to_Y == 'USE_RED'):
                      return 'USE_RED_OR_BLUE'
                  if alt_to_X == 'USE_BLUE':
                      return 'USE_BLUE'
                  if alt_to_Y == 'USE_RED':
                      return 'USE_RED'
                  assert(False)
              else:
                  // case 4.2.3
                  if (F.HIGHER and not F.LOWER
                      and F.topo_order < A.topo_order):
                      return 'USE_RED'
                  else:
                      return 'USE_BLUE'
          else:
              // case 4.3
              if B.LOWER:
                  // case 4.3.1
                  if (F.LOWER and not F.HIGHER
                      and F.topo_order > B.topo_order):
                      return 'USE_BLUE'
                  else:
                      return 'USE_RED'
              if B.HIGHER:
                  // case 4.3.2
                  if (F.HIGHER and not F.LOWER
                      and F.topo_order < B.topo_order):
                      return 'USE_BLUE'
                  else:
                      return 'USE_RED'
              else:
                  // case 4.3.3
                  if A.topo_order < B.topo_order:
                      // case 4.3.3.1
                      if (alt_to_X == 'USE_BLUE'
                          and alt_to_Y == 'USE_RED'):
                          return 'USE_RED_OR_BLUE'
                      if alt_to_X == 'USE_BLUE':
                          return 'USE_BLUE'
                      if alt_to_Y == 'USE_RED':
                          return 'USE_RED'
                      assert(False)

Top      Up      ToC       Page 59 
                  else:
                      // case 4.3.3.2
                      if (alt_to_X == 'USE_RED'
                          and alt_to_Y == 'USE_BLUE'):
                          return 'USE_RED_OR_BLUE'
                      if alt_to_X == 'USE_RED':
                          return 'USE_BLUE'
                      if alt_to_Y == 'USE_BLUE':
                          return 'USE_RED'
                      assert(False)
      assert(False)

                 Figure 29: Select_Alternates_Proxy_Node()

   Select_Alternates_Proxy_Node(P,F,primary_intf) determines whether it
   is safe to use the blue path to P (which goes through X), the red
   path to P (which goes through Y), or either, when the primary_intf to
   node F (and possibly node F) fails.  The basic approach is to run
   Select_Alternates(X,F,primary_intf) and
   Select_Alternates(Y,F,primary_intf) to determine which of the two MRT
   paths to X and which of the two MRT paths to Y is safe to use in the
   event of the failure of F.  In general, we will find that if it is
   safe to use a particular path to X or Y when F fails, and
   Select_Proxy_Node_NHs() used that path when constructing the red or
   blue path to reach P, then it will also be safe to use that path to
   reach P when F fails.  This rule has one exception which is covered
   below.  First, we give a concrete example of how
   Select_Alternates_Proxy_Node() works in the common case.

   The 21 ordering relationships used in Select_Proxy_Node_NHs() are
   repeated in Select_Alternates_Proxy_Node().  We focus on case 4.1.1
   to give a detailed example of the reasoning used in
   Select_Alternates_Proxy_Node().  In Select_Proxy_Node_NHs(), we
   determined for case 4.1.1 that the red next hops to X and the blue
   next hops to Y allow us to reach X and Y by disjoint paths, and are
   thus the blue and red next hops to reach P.  Therefore, if
   Select_Alternates(X, F, primary_intf) is run and we find that it is
   safe to USE_RED to reach X, then we also conclude that it is safe to
   use the MRT path through X to reach P (the blue path to P) when F
   fails.  Similarly, if we run Select_Alternates(Y, F, primary_intf)
   and we find that it is safe to USE_BLUE to reach Y, then we also
   conclude that it is safe to use the MRT path through Y to reach P
   (the red path to P) when F fails.  If both of the paths that were
   used in Select_Proxy_Node_NHs() to construct the blue and red paths
   to P are found to be safe to use to use to reach X and Y, t then we
   conclude that we can use either the red or the blue path to P.

Top      Up      ToC       Page 60 
   This simple reasoning gives the correct answer in most of the cases.
   However, additional logic is needed when either A or B (but not both
   A and B) is unordered with respect to S.  This applies to cases
   4.1.3, 4.2.3, 4.3.1, and 4.3.2.  Looking at case 4.1.3 in more
   detail, A is ordered less than S, but B is unordered with respect to
   S.  In the discussion of case 4.1.3 above, we saw that
   Select_Proxy_Node_NHs() chose the red path to reach Y and the red
   path to reach X.  We also saw that the red path to reach Y will
   follow the INCREASING next hops towards the localroot until it
   reaches some node (L) which is ordered greater than B, after which it
   will take DECREASING next hops to B.  The problem is that the red
   path to reach P (the one that goes through Y) won't necessarily be
   the same as the red path to reach Y.  This is because the next hop
   that node L computes for its red next hop to reach P may be different
   from the next hop it computes for its red next hop to reach Y.  This
   is because B is ordered lower than L, so L applies case 4.1.2 of
   Select_Proxy_Node_NHs() in order to determine its next hops to reach
   P.  If A.topo_order<B.topo_order (case 4.1.2.1), then L will choose
   DECREASING next hops directly to B, which is the same result that L
   computes in Compute_MRT_NextHops() to reach Y.  However, if
   A.topo_order>B.topo_order (case 4.1.2.2), then L will choose
   INCREASING next hops to reach B, which is different from what L
   computes in Compute_MRT_NextHops() to reach Y.  So, testing the
   safety of the path for S to reach Y on failure of F as a surrogate
   for the safety of using the red path to reach P is not reliable in
   this case.  It is possible construct topologies where the red path to
   P hits F even though the red path to Y does not hit F.

   Fortunately, there is enough information in the order relationships
   that we have already computed to still figure out which alternate to
   choose in these four cases.  The basic idea is to always choose the
   path involving the ordered node, unless that path would hit F.
   Returning to case 4.1.3, we see that since A is ordered lower than S,
   the only way for S to hit F using a simple DECREASING path to A is
   for F to lie between A and S on the GADAG.  This scenario is covered
   by requiring that F be lower than S (but not also higher than S) and
   that F.topo_order>A.topo_order in case 4.1.3.1.

   We just need to confirm that it is safe to use the path involving B
   in this scenario.  In case 4.1.3.1, either F is between A and S on
   the GADAG, or F is unordered with respect to A and lies on the
   DECREASING path from S to the localroot.  When F is between A and S
   on the GADAG, then the path through B chosen to avoid A in
   Select_Proxy_Node_NHs() will also avoid F.  When F is unordered with
   respect to A and lies on the DECREASING path from S to the localroot,
   then we consider two cases.  Either F.topo_order<B.topo_order or
   F.topo_order>B.topo_order.  In the first case, since
   F.topo_order<B.topo_order and F.topo_order>A.topo_order, it must be

Top      Up      ToC       Page 61 
   the case that A.topo_order<B.topo_order.  Therefore, L will choose
   DECREASING next hops directly to B (case 4.1.2.1), which cannot hit F
   since F.topo_order<B.topo_order.  In the second case, where
   F.topo_order>B.topo_order, the only way for the path involving B to
   hit F is if it DECREASES from L to B through F, i.e., it must be that
   L>>F>>B.  However, since S>>F, this would imply that S>>B.  However,
   we know that S is unordered with respect to B, so the second case
   cannot occur.  So we have demonstrated that the red path to P (which
   goes via B and Y) is safe to use under the conditions of 4.1.3.1.
   Similar reasoning can be applied to the other three special cases
   where either A or B is unordered with respect to S.



(page 61 continued on part 4)

Next RFC Part