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.
- changes to pseudocode and explanation of Select_A… Chris Bowers
- RE: changes to pseudocode and explanation of Sele… Anil Kumar S N (VRP Network BL)