Subject: changes to pseudocode and explanation of Select_Alternates_Internal( ) in draft-ietf-rtgwg-mrt-frr-algorithm

From: Chris Bowers <[email-masked]>
Date: Tue, 30 Jun 2015 20:42:00 +0000

All,

I found the existing text and pseudo-code for Select_Alternates_Internal to be difficult to understand.  So I rewrote them in a more systematic way that hopefully makes it easier to reason about.  Anil also had some questions a few weeks ago on this part of the code, which I hope this helps to clarify.

The diff of the changes can be found at:

https://github.com/cbowers/draft-ietf-rtgwg-mrt-frr-algorithm/commit/6c66de45bafe64e7e68469e60e9930115ce749d2

The next text is also copied below.

Please tell me if there are any errors or things that can be improved.

Chris

-------------

  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
      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
      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
              if F.topo_order < D_topo_order
                  return USE_RED
      else  //D is unordered wrt S
          if F.HIGHER and F.LOWER
              if primary_intf.OUTGOING and primary_intf.INCOMING
                  // this case should not occur
              if primary_intf.OUTGOING
                  return USE_BLUE
              if primary_intf.INCOMING
                  return USE_RED
          if F.LOWER
              return USE_RED
          if F.HIGHER
              return USE_BLUE

  Select_Alternates(D, F, primary_intf)
      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

   It is useful to first handle the case where 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.

   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.

+------+------------+------+------------------------------+------------+
| 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    |            |
+------+------------+------+-----------------+------------+------------+
| 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    |                 |            |            |
+------+------------+------+-----------------+------------+------------+
| 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    |                 |            |            |
+------+------------+------+-----------------+------------+------------+
| 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 H>>D, |      |                 | S to H.    |            |
|      | 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 G     |            |
|      | node G<<D, |      |                 |            |            |
|      | then decr. |      |                 |            |            |
|      |            +------+-----------------+------------+------------+
|      |            | 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      | Implies F is the order  |
|      |            |      | direction       | proxy for D, which has  |
|      |            |      | S<-->F          | already been handled.   |
+------+------------+------+-----------------+------------+------------+

     Figure 25: 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.