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

Chris Bowers <cbowers@juniper.net> Tue, 30 June 2015 20:42 UTC

Return-Path: <cbowers@juniper.net>
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 946661B2DB9 for <rtgwg@ietfa.amsl.com>; Tue, 30 Jun 2015 13:42:08 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 3.198
X-Spam-Level: ***
X-Spam-Status: No, score=3.198 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, 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_NONE=-0.0001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] 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 Fe48T3xTvmWk for <rtgwg@ietfa.amsl.com>; Tue, 30 Jun 2015 13:42:04 -0700 (PDT)
Received: from na01-by2-obe.outbound.protection.outlook.com (mail-by2on0118.outbound.protection.outlook.com [207.46.100.118]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 654781B2ED8 for <rtgwg@ietf.org>; Tue, 30 Jun 2015 13:42:02 -0700 (PDT)
Received: from DM2PR05MB303.namprd05.prod.outlook.com (10.141.103.15) by DM2PR05MB303.namprd05.prod.outlook.com (10.141.103.15) with Microsoft SMTP Server (TLS) id 15.1.201.16; Tue, 30 Jun 2015 20:42:00 +0000
Received: from DM2PR05MB303.namprd05.prod.outlook.com ([10.141.103.15]) by DM2PR05MB303.namprd05.prod.outlook.com ([10.141.103.15]) with mapi id 15.01.0201.000; Tue, 30 Jun 2015 20:42:00 +0000
From: Chris Bowers <cbowers@juniper.net>
To: "rtgwg@ietf.org" <rtgwg@ietf.org>
Subject: 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: AdCzc95dm1P5GYDaSN2WmEoHhWIsrg==
Date: Tue, 30 Jun 2015 20:42:00 +0000
Message-ID: <DM2PR05MB303BDC2D1206180DED7EEB3A9A90@DM2PR05MB303.namprd05.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: ietf.org; dkim=none (message not signed) header.d=none;
x-originating-ip: [66.129.239.10]
x-microsoft-exchange-diagnostics: 1; DM2PR05MB303; 5:kep1jyDn/DaU7R2Skr5mnuWi+zBxpjECUze1NgKwbA7sVy2rMJFkQz+mP7iuqf0JnucRoPsLoMYl+qoiKtkQlTnC4xxWhcnhrBF42ZrSjrNdvq9YN2wQ91DyZdWNsNAkOuF20oHUszdVS4GiR64l+w==; 24:DSQEH1I2mWYPi7yECalo6Y7DQdcopUFnV68JAOPJ91Zi36wGcnaz4As0tmQaty85GMGKdGIeyHp/I+XzYO7K97FTzQK+/8k+Zf9mB9rRSoo=; 20:mMk+qR6/v5jFEpei/XJkWziMxnN9UHqZ16XJLplIc4hTYVMy8BcsIO6XR/zVdIpx+ENw47iQu0WidrBZC+ubMg==
x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:DM2PR05MB303;
x-microsoft-antispam-prvs: <DM2PR05MB303A677BEC17CD378988D16A9A90@DM2PR05MB303.namprd05.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:;
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(601004)(5005006)(3002001); SRVR:DM2PR05MB303; BCL:0; PCL:0; RULEID:; SRVR:DM2PR05MB303;
x-forefront-prvs: 06237E4555
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(6009001)(2656002)(87936001)(230783001)(2501003)(19580395003)(2900100001)(92566002)(77156002)(450100001)(62966003)(15975445007)(86362001)(77096005)(102836002)(122556002)(74316001)(33656002)(2351001)(229853001)(5002640100001)(5003600100002)(107886002)(5001960100002)(110136002)(5001920100001)(46102003)(189998001)(66066001)(99286002)(50986999)(54356999)(76576001); DIR:OUT; SFP:1102; SCL:1; SRVR:DM2PR05MB303; H:DM2PR05MB303.namprd05.prod.outlook.com; FPR:; SPF:None; MLV:sfv; LANG:en;
Content-Type: multipart/alternative; boundary="_000_DM2PR05MB303BDC2D1206180DED7EEB3A9A90DM2PR05MB303namprd_"
MIME-Version: 1.0
X-OriginatorOrg: juniper.net
X-MS-Exchange-CrossTenant-originalarrivaltime: 30 Jun 2015 20:42:00.0970 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: bea78b3c-4cdb-4130-854a-1d193232e5f4
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM2PR05MB303
Archived-At: <http://mailarchive.ietf.org/arch/msg/rtgwg/jHsrcFc3n26Xl2cE42v8nKpzmrM>
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: Tue, 30 Jun 2015 20:42:08 -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.