Python implementation of MRT lowpoint algorithm

Chris Bowers <> Sat, 18 July 2015 17:02 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 9E8301A1BB8 for <>; Sat, 18 Jul 2015 10:02:44 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id HhS5XvqkIlaz for <>; Sat, 18 Jul 2015 10:02:42 -0700 (PDT)
Received: from ( [IPv6:2a01:111:f400:fc10::1:759]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 695791A1B57 for <>; Sat, 18 Jul 2015 10:02:42 -0700 (PDT)
Received: from ( by ( with Microsoft SMTP Server (TLS) id; Sat, 18 Jul 2015 17:02:24 +0000
Received: from ([]) by ([]) with mapi id 15.01.0213.021; Sat, 18 Jul 2015 17:02:24 +0000
From: Chris Bowers <>
To: "" <>
Subject: Python implementation of MRT lowpoint algorithm
Thread-Topic: Python implementation of MRT lowpoint algorithm
Thread-Index: AdC03HdZUZQ8fh7yTGaiehX+BznWFA==
Date: Sat, 18 Jul 2015 17:02:24 +0000
Message-ID: <>
Accept-Language: en-US
Content-Language: en-US
authentication-results:; dkim=none (message not signed) header.d=none;
x-originating-ip: []
x-microsoft-exchange-diagnostics: 1; BLUPR05MB289; 5:APLcpOQabhwkXdn3niPYxzrG6EDu0jmE+QwI8IFOWdnE2Vlj6IgIuD7iTLDrf2XheNoAcaThi0b0kHkhKHwBHLhiYDabmvnoNbaEdLsInt/iYV0NUAEZqgylO+IRqq/06cLAI5yNA3RAuaWdFFNYuA==; 24:uxRNcRYy3Rj5/03rcf1empu3L1kaGkgf1lEhn+0DYq2DLWbMg67576YIQfQXdgOp4R9ga3n4Td7NIXYKnZ0y3KouO4XKW2RoCi0nPa6TEQo=; 20:Rg1FF4lbrbed33Sas6hy2R35XahZVewkwu6t8mUP9zvxPN9PGu24Aup9dvqt5Nk8yS2lLNh3mCTwlehBrARNbw==
x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:BLUPR05MB289;
blupr05mb289: X-MS-Exchange-Organization-RulesExecuted
x-microsoft-antispam-prvs: <>
x-exchange-antispam-report-test: UriScan:(108003899814671);
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(601004)(5005006)(3002001); SRVR:BLUPR05MB289; BCL:0; PCL:0; RULEID:; SRVR:BLUPR05MB289;
x-forefront-prvs: 0641678E68
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(6009001)(164054003)(50986999)(5002640100001)(107886002)(33656002)(5001960100002)(110136002)(189998001)(2351001)(229853001)(2501003)(46102003)(5003600100002)(76576001)(99286002)(2656002)(87936001)(19580395003)(86362001)(77096005)(74316001)(122556002)(15975445007)(92566002)(102836002)(2900100001)(66066001)(450100001)(62966003)(77156002)(40100003)(54356999); DIR:OUT; SFP:1102; SCL:1; SRVR:BLUPR05MB289;; FPR:; SPF:None; MLV:sfv; LANG:en;
Content-Type: multipart/alternative; boundary="_000_BLUPR05MB29221453D3E8FCF26F841DFA9870BLUPR05MB292namprd_"
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-originalarrivaltime: 18 Jul 2015 17:02:24.8107 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: bea78b3c-4cdb-4130-854a-1d193232e5f4
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BLUPR05MB289
Archived-At: <>
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Routing Area Working Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Sat, 18 Jul 2015 17:02:44 -0000


We wrote a Python implementation of the MRT lowpoint algorithm following the pseudo-code in the draft, and have included it in the text of draft-ietf-rtgwg-mrt-frr-algorithm-05.

The code is also posted on github at:

At this point, the Python implementation is included in the draft as additional information, with the pseudo-code text representing the normative version of the algorithm.  For the next revision of the draft, I think it makes sense to make the Python implementation the normative version of the algorithm since it can actually be run to produce a definitive result for any input topology.  However, I want to elicit feedback from the WG as to whether or not it makes sense to do this.

We can also discuss this point at the RTGWG session on Wednesday where I will give an update on the MRT-related drafts.