RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03
Chris Bowers <cbowers@juniper.net> Wed, 17 June 2015 22:28 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 1C9F51B2D48; Wed, 17 Jun 2015 15:28:30 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.799
X-Spam-Level:
X-Spam-Status: No, score=0.799 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, J_CHICKENPOX_110=0.6, J_CHICKENPOX_18=0.6, J_CHICKENPOX_19=0.6, J_CHICKENPOX_48=0.6, MIME_8BIT_HEADER=0.3, 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 QucWRLXRkhT3; Wed, 17 Jun 2015 15:28:25 -0700 (PDT)
Received: from na01-bn1-obe.outbound.protection.outlook.com (mail-bn1bon0726.outbound.protection.outlook.com [IPv6:2a01:111:f400:fc10::1:726]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C39C01B2D34; Wed, 17 Jun 2015 15:28:24 -0700 (PDT)
Received: from BLUPR05MB292.namprd05.prod.outlook.com (10.141.23.27) by DM2PR0501MB1584.namprd05.prod.outlook.com (10.160.133.15) with Microsoft SMTP Server (TLS) id 15.1.190.14; Wed, 17 Jun 2015 22:28:19 +0000
Received: from BLUPR05MB292.namprd05.prod.outlook.com ([10.141.23.27]) by BLUPR05MB292.namprd05.prod.outlook.com ([10.141.23.27]) with mapi id 15.01.0190.013; Wed, 17 Jun 2015 22:28:19 +0000
From: Chris Bowers <cbowers@juniper.net>
To: "Anil Kumar S N (VRP Network BL)" <anil.sn@huawei.com>, Gábor Sándor Enyedi <gabor.sandor.enyedi@ericsson.com>, "Andras.Csaszar@ericsson.com" <Andras.Csaszar@ericsson.com>, Alia Atlas <akatlas@juniper.net>, "abishek@ece.arizona.edu" <abishek@ece.arizona.edu>
Subject: RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03
Thread-Topic: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03
Thread-Index: AdCifUFAAQ1JZlPETESLX6aiRMOLaAATVnnwACjeOWAAbkesEACHWMLQAH3w4bA=
Date: Wed, 17 Jun 2015 22:28:18 +0000
Message-ID: <BLUPR05MB2923CCD7881725EFCE3B138A9A60@BLUPR05MB292.namprd05.prod.outlook.com>
References: <327562D94EA7BF428CD805F338C31EF04FB436B4@nkgeml512-mbx.china.huawei.com> <BLUPR05MB2925A1254FC0C5726AA7372A9BE0@BLUPR05MB292.namprd05.prod.outlook.com> <327562D94EA7BF428CD805F338C31EF04FB437FD@nkgeml512-mbx.china.huawei.com> <BLUPR05MB292BAD31261D2FB5D81E2F6A9BB0@BLUPR05MB292.namprd05.prod.outlook.com> <327562D94EA7BF428CD805F338C31EF04FB43CAF@nkgeml512-mbx.china.huawei.com>
In-Reply-To: <327562D94EA7BF428CD805F338C31EF04FB43CAF@nkgeml512-mbx.china.huawei.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: huawei.com; dkim=none (message not signed) header.d=none;
x-originating-ip: [66.129.239.13]
x-microsoft-exchange-diagnostics: 1; DM2PR0501MB1584; 3:KunN0sds5rRsYTP0iQ8Y51bxgxH8kABM7r3sR8tR6ElvNVsNiNk5OYiZqqazVvCyBcwW0ooTIWf96HOajev3xfe5LwtO9zsY3HN0aafOrvr1YxNH+7crG+f4MqdEuXnNi8CFO5xgkCdVRCobUbySAA==; 10:+vAZ0+LR5Ifgd0T0++P8/iboFJTD6lqhq7/gbrCSfVMuqIcN7ZFIfuiB29ibyJVhHnYg4oGBaM1QRWAbD9xHnF8/Sr094czD7Mrry0h+080=; 6:/gTiWdxM743Vuc4OKIxNK8TA8KYiauIse6OeBKEDzKGVzIsalWITDvkETCatjeks
x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:DM2PR0501MB1584;
x-microsoft-antispam-prvs: <DM2PR0501MB15842AC6DF29679FF7F99523A9A60@DM2PR0501MB1584.namprd05.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:;
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(601004)(5005006)(520003)(3002001); SRVR:DM2PR0501MB1584; BCL:0; PCL:0; RULEID:; SRVR:DM2PR0501MB1584;
x-forefront-prvs: 0610D16BBE
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(377454003)(52604005)(2501003)(5001770100001)(76176999)(19580405001)(19580395003)(54356999)(16236675004)(77096005)(2656002)(2171001)(86362001)(575784001)(87936001)(99286002)(15975445007)(102836002)(2900100001)(2950100001)(50986999)(77156002)(19300405004)(189998001)(62966003)(92566002)(5002640100001)(5001920100001)(74316001)(5001960100002)(5003600100002)(46102003)(66066001)(76576001)(19625215002)(33656002)(230783001)(19609705001)(122556002)(19617315012)(40100003); DIR:OUT; SFP:1102; SCL:1; SRVR:DM2PR0501MB1584; H:BLUPR05MB292.namprd05.prod.outlook.com; FPR:; SPF:None; MLV:sfv; LANG:en;
Content-Type: multipart/alternative; boundary="_000_BLUPR05MB2923CCD7881725EFCE3B138A9A60BLUPR05MB292namprd_"
MIME-Version: 1.0
X-OriginatorOrg: juniper.net
X-MS-Exchange-CrossTenant-originalarrivaltime: 17 Jun 2015 22:28:18.8739 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: bea78b3c-4cdb-4130-854a-1d193232e5f4
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM2PR0501MB1584
Archived-At: <http://mailarchive.ietf.org/arch/msg/rtgwg/-BNAtBRtt46av1yfTLpgArbCTbo>
Cc: "rtgwg-owner@ietf.org" <rtgwg-owner@ietf.org>, "rtgwg@ietf.org" <rtgwg@ietf.org>
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: <http://www.ietf.org/mail-archive/web/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, 17 Jun 2015 22:28:30 -0000
Anil, Thanks for pointing this out. Construct_Ear() mentions identifying a cut-vertex in a comment, but doesn't actually set it explicitly. I added it as below, as reflected in the github diff link. Construct_Ear(x, Stack, intf, ear_type) ... if (ear_type is CHILD) and (cur_node is x) // x is a cut-vertex and the local root for // the block in which the ear is computed x.IS_CUT_VERTEX = true <<< New line here localroot = x else https://github.com/cbowers/draft-ietf-rtgwg-mrt-frr-algorithm/commit/6a92a3fe9f578af2566d0dbb042181cb22469c57 With respect to identifying cut-links, I'd like to propose the following changes to the Add_Undirected_Links() to have it deal better with parallel-links from the block root (cut-vertices or the GADAG root) to another node. When adding undirected links to the GADAG, links connecting the block root to other nodes in that block need special handling because the topological order will not always give the right answer for links involving the block root. There are three cases below. case 1a) If the undirected link in question has another parallel link between the same two nodes that is already directed, then the direction of the undirected link can be inherited from the previously directed link. case 1b) In the case of parallel cut links, we set all of the parallel links to both INCOMING and OUTGOING. case 2) Otherwise, the undirected link in question is set to OUTGOING from the block root node. With this version of Add_Undirected_Links(), a cut-link can be identified by the fact that it will be directed both INCOMING and OUTGOING in the GADAG. I put proposed pseudo-code to replace figure 18 in the github diff below. https://github.com/cbowers/draft-ietf-rtgwg-mrt-frr-algorithm/commit/5d5e5c9c74ef963195e29cb2e7b449c8884facd4 The proposed next text and pseudo-code is copied below as well. To convert a GADAG to a DAG, it is necessary to remove all links that point to a root of block from within that block. That provides the necessary conversion to a DAG and then a topological sort can be done. When adding undirected links to the GADAG, links connecting the block root to other nodes in that block need special handling because the topological order will not always give the right answer for those links. There are three cases to consider. If the undirected link in question has another parallel link between the same two nodes that is already directed, then the direction of the undirected link can be inherited from the previously directed link. In the case of parallel cut links, we set all of the parallel links to both INCOMING and OUTGOING. Otherwise, the undirected link in question is set to OUTGOING from the block root node. A cut-link can then be identified by the fact that it will be directed both INCOMING and OUTGOING in the GADAG. The exact details of this whole process are captured in Figure 18 Add_Undirected_Block_Root_Links(topo, gadag_root): foreach node x in topo if x.IS_CUT_VERTEX or x is gadag_root foreach interface i of x if (i.remote_node.localroot is not x or i.PROCESSED ) continue Initialize bundle_list to empty bundle.UNDIRECTED = true bundle.OUTGOING = false bundle.INCOMING = false foreach interface i2 in x if i2.remote_node is i.remote_node add_to_list_end(bundle_list, i2) if not i2.UNDIRECTED: bundle.UNDIRECTED = false if i2.INCOMING: bundle.INCOMING = true if i2.OUTGOING: bundle.OUTGOING = true if bundle.UNDIRECTED foreach interface i3 in bundle_list i3.UNDIRECTED = false i3.remote_intf.UNDIRECTED = false i3.PROCESSED = true i3.remote_intf.PROCESSED = true i3.OUTGOING = true i3.remote_intf.INCOMING = true else if (bundle.OUTGOING and bundle.INCOMING) foreach interface i3 in bundle_list i3.UNDIRECTED = false i3.remote_intf.UNDIRECTED = false i3.PROCESSED = true i3.remote_intf.PROCESSED = true i3.OUTGOING = true i3.INCOMING = true i3.remote_intf.INCOMING = true i3.remote_intf.OUTGOING = true else if bundle.OUTGOING foreach interface i3 in bundle_list i3.UNDIRECTED = false i3.remote_intf.UNDIRECTED = false i3.PROCESSED = true i3.remote_intf.PROCESSED = true i3.OUTGOING = true i3.remote_intf.INCOMING = true else if bundle.INCOMING foreach interface i3 in bundle_list i3.UNDIRECTED = false i3.remote_intf.UNDIRECTED = false i3.PROCESSED = true i3.remote_intf.PROCESSED = true i3.INCOMING = true i3.remote_intf.OUTGOING = true Modify_Block_Root_Incoming_Links(topo, gadag_root): foreach node x in topo if x.IS_CUT_VERTEX or x is gadag_root foreach interface i of x if i.remote_node.localroot is x if i.INCOMING: i.INCOMING = false i.INCOMING_STORED = true i.remote_intf.OUTGOING = false i.remote_intf.OUTGOING_STORED = true Revert_Block_Root_Incoming_Links(topo, gadag_root): foreach node x in topo if x.IS_CUT_VERTEX or x is gadag_root foreach interface i of x if i.remote_node.localroot is x if i.INCOMING_STORED: i.INCOMING = true i.remote_intf.OUTGOING = true i.INCOMING_STORED = false i.remote_intf.OUTGOING_STORED = false Run_Topological_Sort_GADAG(topo, gadag_root): Modify_Block_Root_Incoming_Links(topo, gadag_root) foreach node x in topo: node.unvisited = 0 foreach interface i of x: if (i.INCOMING): node.unvisited += 1 Initialize working_list to empty Initialize topo_order_list to empty add_to_list_end(working_list, gadag_root) while working_list is not empty y = remove_start_item_from_list(working_list) add_to_list_end(topo_order_list, y) foreach ordered_interface i of y if intf.OUTGOING i.remote_node.unvisited -= 1 if i.remote_node.unvisited is 0 add_to_list_end(working_list, i.remote_node) next_topo_order = 1 while topo_order_list is not empty y = remove_start_item_from_list(topo_order_list) y.topo_order = next_topo_order next_topo_order += 1 Revert_Block_Root_Incoming_Links(topo, gadag_root) def Set_Other_Undirected_Links_Based_On_Topo_Order(topo): foreach node x in topo foreach interface i of x if i.UNDIRECTED: if x.topo_order < i.remote_node.topo_order i.OUTGOING = true i.UNDIRECTED = false i.remote_intf.INCOMING = true i.remote_intf.UNDIRECTED = false else i.INCOMING = true i.UNDIRECTED = false i.remote_intf.OUTGOING = true i.remote_intf.UNDIRECTED = false Add_Undirected_Links(topo, gadag_root) Add_Undirected_Block_Root_Links(topo, gadag_root) Run_Topological_Sort_GADAG(topo, gadag_root) Set_Other_Undirected_Links_Based_On_Topo_Order(topo) Add_Undirected_Links(topo, gadag_root) Figure 18: Assigning direction to UNDIRECTED links From: Anil Kumar S N (VRP Network BL) [mailto:anil.sn@huawei.com] Sent: Monday, June 15, 2015 3:25 AM To: Chris Bowers; Gábor Sándor Enyedi; Andras.Csaszar@ericsson.com; Alia Atlas; abishek@ece.arizona.edu Cc: rtgwg@ietf.org; rtgwg-owner@ietf.org Subject: RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Hi Chris, I couldn't find psudocode for indentifying and marking a link as cut-link and vertex as cut-vertex. Please correct me if I am wrong. Thanks & Regards Anil S N "Be liberal in what you accept, and conservative in what you send" - Jon Postel
- draft-ietf-rtgwg-mrt-frr-algorithm-03 Anil Kumar S N (VRP Network BL)
- [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Anil Kumar S N (VRP Network BL)
- RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Chris Bowers
- RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Anil Kumar S N (VRP Network BL)
- RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Anil Kumar S N (VRP Network BL)
- RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Chris Bowers
- RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Anil Kumar S N (VRP Network BL)
- RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Anil Kumar S N (VRP Network BL)
- RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Chris Bowers
- RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Anil Kumar S N (VRP Network BL)
- RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Anil Kumar S N (VRP Network BL)
- [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Anil Kumar S N (VRP Network BL)
- RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Chris Bowers
- RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Anil Kumar S N (VRP Network BL)
- [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Anil Kumar S N (VRP Network BL)
- RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Anil Kumar S N (VRP Network BL)
- RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Chris Bowers
- RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Anil Kumar S N (VRP Network BL)
- RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Anil Kumar S N (VRP Network BL)
- RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03 Chris Bowers