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

"Anil Kumar S N (VRP Network BL)" <anil.sn@huawei.com> Wed, 01 July 2015 08:40 UTC

Return-Path: <anil.sn@huawei.com>
X-Original-To: rtgwg@ietfa.amsl.com
Delivered-To: rtgwg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D64301A1A03 for <rtgwg@ietfa.amsl.com>; Wed, 1 Jul 2015 01:40:59 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.01
X-Spam-Level:
X-Spam-Status: No, score=-1.01 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, J_BACKHAIR_11=1, J_BACKHAIR_14=1, J_CHICKENPOX_15=0.6, J_CHICKENPOX_16=0.6, RCVD_IN_DNSWL_MED=-2.3, SPF_PASS=-0.001, T_RP_MATCHES_RCVD=-0.01] autolearn=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id C62HFTPbwFUa for <rtgwg@ietfa.amsl.com>; Wed, 1 Jul 2015 01:40:53 -0700 (PDT)
Received: from lhrrgout.huawei.com (lhrrgout.huawei.com [194.213.3.17]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9A9791A19F2 for <rtgwg@ietf.org>; Wed, 1 Jul 2015 01:40:52 -0700 (PDT)
Received: from 172.18.7.190 (EHLO lhreml404-hub.china.huawei.com) ([172.18.7.190]) by lhrrg01-dlp.huawei.com (MOS 4.3.7-GA FastPath queued) with ESMTP id BYE81918; Wed, 01 Jul 2015 08:40:51 +0000 (GMT)
Received: from NKGEML404-HUB.china.huawei.com (10.98.56.35) by lhreml404-hub.china.huawei.com (10.201.5.218) with Microsoft SMTP Server (TLS) id 14.3.158.1; Wed, 1 Jul 2015 09:40:49 +0100
Received: from NKGEML512-MBX.china.huawei.com ([169.254.7.155]) by nkgeml404-hub.china.huawei.com ([10.98.56.35]) with mapi id 14.03.0158.001; Wed, 1 Jul 2015 16:40:46 +0800
From: "Anil Kumar S N (VRP Network BL)" <anil.sn@huawei.com>
To: Chris Bowers <cbowers@juniper.net>, "rtgwg@ietf.org" <rtgwg@ietf.org>
Subject: RE: changes to pseudocode and explanation of Select_Alternates_Internal( ) in draft-ietf-rtgwg-mrt-frr-algorithm
Thread-Topic: changes to pseudocode and explanation of Select_Alternates_Internal( ) in draft-ietf-rtgwg-mrt-frr-algorithm
Thread-Index: AdCzc95dm1P5GYDaSN2WmEoHhWIsrgAZTH7w
Date: Wed, 1 Jul 2015 08:40:45 +0000
Message-ID: <327562D94EA7BF428CD805F338C31EF06B5AEBE7@nkgeml512-mbx.china.huawei.com>
References: <DM2PR05MB303BDC2D1206180DED7EEB3A9A90@DM2PR05MB303.namprd05.prod.outlook.com>
In-Reply-To: <DM2PR05MB303BDC2D1206180DED7EEB3A9A90@DM2PR05MB303.namprd05.prod.outlook.com>
Accept-Language: en-US, zh-CN
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [10.18.212.150]
Content-Type: multipart/alternative; boundary="_000_327562D94EA7BF428CD805F338C31EF06B5AEBE7nkgeml512mbxchi_"
MIME-Version: 1.0
X-CFilter-Loop: Reflected
Archived-At: <http://mailarchive.ietf.org/arch/msg/rtgwg/h13W-THDOTpmjLe91_DO9QERmls>
X-Mailman-Approved-At: Wed, 01 Jul 2015 08:00:03 -0700
X-BeenThere: rtgwg@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Routing Area Working Group <rtgwg.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/rtgwg>, <mailto:rtgwg-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/rtgwg/>
List-Post: <mailto:rtgwg@ietf.org>
List-Help: <mailto:rtgwg-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/rtgwg>, <mailto:rtgwg-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 01 Jul 2015 08:41:00 -0000

Hi Chris,

                Thanks for addressing this. I have to tell you that my implementation MRT algorithm works perfectly fine (tested on smaller topology).

                I have a architectural question, if MT_RED and MT_BLUE ID's are allocated by IANA it would be default MT.
                How about supporting MRT for multitopology environment ?  where there exist multiple topology all of them desire MRT as backup.

Thanks & Regards
Anil S N

"Be liberal in what you accept, and conservative in what you send" - Jon Postel


From: rtgwg [mailto:rtgwg-bounces@ietf.org] On Behalf Of Chris Bowers
Sent: 01 July 2015 02:12
To: rtgwg@ietf.org
Subject: changes to pseudocode and explanation of Select_Alternates_Internal( ) in draft-ietf-rtgwg-mrt-frr-algorithm

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.