[Idr] Bug in RFC 7911 (add-paths) and tie-breaking

John Scudder <jgs@juniper.net> Thu, 24 June 2021 18:15 UTC

Return-Path: <jgs@juniper.net>
X-Original-To: idr@ietfa.amsl.com
Delivered-To: idr@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 2246C3A2636 for <idr@ietfa.amsl.com>; Thu, 24 Jun 2021 11:15:11 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.995
X-Spam-Level:
X-Spam-Status: No, score=-2.995 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.198, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=juniper.net header.b=s1/oVZiu; dkim=pass (1024-bit key) header.d=juniper.net header.b=cyEmr3Cd
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 beUjjsVZ9SLM for <idr@ietfa.amsl.com>; Thu, 24 Jun 2021 11:15:06 -0700 (PDT)
Received: from mx0a-00273201.pphosted.com (mx0a-00273201.pphosted.com [208.84.65.16]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id A95D03A2635 for <idr@ietf.org>; Thu, 24 Jun 2021 11:15:06 -0700 (PDT)
Received: from pps.filterd (m0108158.ppops.net [127.0.0.1]) by mx0a-00273201.pphosted.com (8.16.0.43/8.16.0.43) with SMTP id 15OI9QMi002589; Thu, 24 Jun 2021 11:14:59 -0700
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=juniper.net; h=from : to : cc : subject : date : message-id : content-type : content-id : content-transfer-encoding : mime-version; s=PPS1017; bh=QtZhaHoUTJYPLuxWtS8Jf0nH9xop+a+8Mn0a92WTc4A=; b=s1/oVZiugs+4SZ+1d1cRBLZ+bPY7gKA+HbuDysBzaiYEiPFBf1w+q/2NM2Z6Pvgih5h7 h0JzkOqUBwDyfPzT3KU+V/lg20p6DRyKtWH5xS4ONGEwLmtdKIoUrP6A4LjB0F2fukPh sSnUw3JrbO6PgeIUgQTKBwoT+smCwjW7LVos5mSJfBJrNocH3hvo2rnVFUNMtJ7JuO9l 7m+7pNUw2e/0KiVEofupt67PHltGmrkEfIe0yL10ztA+Do7ZKFmbjWNgdBdZblouY9I7 QWOMgeBbvU0K5c2hIICeNQj+EP+x7wVk878mZkScLa8Z90C5olbgFgnpoCQLJtoTIPgh UA==
Received: from nam10-mw2-obe.outbound.protection.outlook.com (mail-mw2nam10lp2102.outbound.protection.outlook.com [104.47.55.102]) by mx0a-00273201.pphosted.com with ESMTP id 39csetgtvy-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 24 Jun 2021 11:14:59 -0700
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=UPJbkAAWnno4cn5ITmTa95xVOaSw7XcD4krz0qLiILzc1KrNA773PUCbjkrzyMPkw0VJSxO0/34SUC2LaJUV4a7xScaB8el9nAumBXlNp05C5FuY08GBp+DGmIWV3nxPvaQWa5mk4If1EbsZE5qcjvBdbwmLHgqGWio45Mq5F9eZ/oY/wd39VF31/Dp5zmY7Klzk/2vAQPvhJ/vo9h7DN1Fv3FZrOYR5lXQif6sVT4c3Jx+UI0Aah2nDfGkFWFTpw030CYXTS0WTCEvyNz+owBf0jv8GXdC+wTRiYTMSmVYl/1xzI5fJiczFHuWs9gtZj/iQLKcQ5QTNPR/itd0G3A==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=QtZhaHoUTJYPLuxWtS8Jf0nH9xop+a+8Mn0a92WTc4A=; b=Ad9e4XKakZmydKFmCo2IFIMuc2S782uC8bjwRFovHULH3CR0r+IuYVCuuAzUdGdWHfQxHauMbp083LaVjINrsHIfsyxKpRfDE8pTu353TTPbVXZAOxNEIrkhxMIecA8vbja/k6YyPaeKbzBEQdG+pLU24zIWuYrKxhyUkMOl20D2WlzNp10/y5L6UhlsZDiiz4whNRpV4KWd9oW/oJe44271yeN6TKujb2B1ngOB6iHwAEaxkka6RCZYMBAHNySGQMvSfOx8J+KL82bto6s4CxsMuRgv4ifMoZQDAqPagbJ2KrZJ9u0u16qSc95xQbwozoGTyFplqcwn4OKt6SU7pg==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=juniper.net; dmarc=pass action=none header.from=juniper.net; dkim=pass header.d=juniper.net; arc=none
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=juniper.net; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=QtZhaHoUTJYPLuxWtS8Jf0nH9xop+a+8Mn0a92WTc4A=; b=cyEmr3CduGlw1w8QwrNivVxl2hytgvEAdP24aBp3gqVWKzR4qv5fLdwJIvvV/a1YAbmEe8eIorQTNMOcQ8ZbXhIvYgCceS1005MSpD3cyeXKZyuCxJF+siD6tmWkhAy9Xaena5tBi0yXMk3Okmvnc6GoKJdSieQwrY8iYHB6v6g=
Received: from MN2PR05MB6109.namprd05.prod.outlook.com (2603:10b6:208:c4::20) by MN2PR05MB7037.namprd05.prod.outlook.com (2603:10b6:208:189::12) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4264.7; Thu, 24 Jun 2021 18:14:55 +0000
Received: from MN2PR05MB6109.namprd05.prod.outlook.com ([fe80::e40e:672f:e689:cd0c]) by MN2PR05MB6109.namprd05.prod.outlook.com ([fe80::e40e:672f:e689:cd0c%7]) with mapi id 15.20.4264.020; Thu, 24 Jun 2021 18:14:55 +0000
From: John Scudder <jgs@juniper.net>
To: "idr@ietf. org" <idr@ietf.org>
CC: Claudio Jeker <cjeker@diehard.n-r-g.com>, Enke Chen <enchen@paloaltonetworks.com>, "dwalton76@gmail.com" <dwalton76@gmail.com>, Alvaro Retana <aretana.ietf@gmail.com>
Thread-Topic: Bug in RFC 7911 (add-paths) and tie-breaking
Thread-Index: AQHXaSTVEauHMW2CTEKGa0jgcKDmnA==
Date: Thu, 24 Jun 2021 18:14:55 +0000
Message-ID: <F689CF63-236D-401D-9C8E-AC1C39CDE772@juniper.net>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-mailer: Apple Mail (2.3654.100.0.2.22)
authentication-results: ietf.org; dkim=none (message not signed) header.d=none;ietf.org; dmarc=none action=none header.from=juniper.net;
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 331ec156-141d-497c-ad56-08d9373bf84e
x-ms-traffictypediagnostic: MN2PR05MB7037:
x-microsoft-antispam-prvs: <MN2PR05MB703762E7D28F6CAA26025267AA079@MN2PR05MB7037.namprd05.prod.outlook.com>
x-ms-oob-tlc-oobclassifiers: OLM:10000;
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: NYlWnMHpS7D7AMB/m4oq4CtIJH+URpI0hVBIlo03ei6hZW8sJrZAw+4GlsWgSYbHhKR11nyljru24IkgL5xSE3knc7Yu9pUsbnH2/fUpkR/eCn062p1x7llRgY8F+1ytp3yDkPP6VnevkMN71iZNe6F5tW+wZGshkp0eTW0xCpm25hPM3AndYAGUMaYFxW1mbkcDYvOS/XRnNnJkJVAbWGtk35TK1xVkKWleVKRqmbsTMf6D0VgcrH3bm/xpJHV/HHGIr2mfeY9Ka7fO4IlevH/EeWAuGWyUujf6/MsOm2n3k7BnCFR10GQ2hYteTzR2Gq3SyKiYtsM+cwkQgXx8fq8fGmGZJwoWwdFbwYq1gVy3DQZz6BSmoKskuX4gAmcsqlxVbBnJgP/OAZF73l0LWKJb7Q7xwoY43OK90Oncc4llpEt0rDgueFjpj/h8RhizhfCOlUxjB8VXuelGLh1xlLVlyhh5pIRQ/Fi2BpCtJtbWP4Gi0aMR2gVRYood2c0JeOUVZBbDgtHhX3z9UzW5qkGCIaMLEo9aHME4fe4dZsKvweRIaQYMV7QM8vwwYPUnX1/F6QwDTyxPfzTRMLaZGC2wD45kZbLBQB/ELzBzE0bWQiMxxsqCpx7XrF3Mt2rBYwAPWLFEyLnR8ZhW9CH0lN1fYkm1FOT39ywZkmo8Eao=
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:MN2PR05MB6109.namprd05.prod.outlook.com; PTR:; CAT:NONE; SFS:(4636009)(396003)(39860400002)(136003)(376002)(366004)(346002)(6506007)(36756003)(54906003)(66574015)(4326008)(8676002)(33656002)(71200400001)(83380400001)(26005)(6512007)(6916009)(86362001)(316002)(8936002)(5660300002)(2906002)(478600001)(186003)(122000001)(6486002)(66946007)(38100700002)(91956017)(64756008)(66446008)(2616005)(66476007)(66556008)(76116006)(45980500001); DIR:OUT; SFP:1102;
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0: =?utf-8?B?MzZjLzRJN1o1K1d2b1BWTnlYNDdnazM4eDNRTWVETGNJdFBhbjVVbE9qSW1L?= =?utf-8?B?YVFwQ1Q4QmpMWi94c3c1UmU4WEpYTWkyRjhxS0QzRTQ4NEowemd5TVhRS3Q1?= =?utf-8?B?ZzRSZzlKeWtxeDdzT29aOTJlMmMrcm9PcXRza1V5Q3JKN2prN3FXOGRvNVFT?= =?utf-8?B?VVVWeSttK296NmM5dWFaRWRvQXlHRTRKOWdSUzZhMGw3aTRjT3dOcUtEbVBQ?= =?utf-8?B?OVlBUElBSEFTRko2VlFNTDh6Z3dWQzNvUktTZmNWTUR5OTJIWHQ1ck95bEx6?= =?utf-8?B?MG5NRjc3SXFxY3NFeGdZV0hvWTAramdqNXFacWduMTVoVXRPQ2hZTy9oQ0c0?= =?utf-8?B?STFoaXFzZ0NTTHNtNlZFYmhDYkZKVUUyTk9oNEVzUllIY1ZFRnhhR3UxdUU0?= =?utf-8?B?YVF2V3NwbWtrNDFybWhlSWJtOTVRTzVuRS9GMHN2dC9STzdnRHo4SWRRMG5q?= =?utf-8?B?TEZCQXpMdmhSNWRGREdLWXJxRjVNUmRMWk9PNjE4YXBWbmV6aEhhaDg5cWZs?= =?utf-8?B?OHZHalNxV015eURxaEhVazluYjFabmM0eTl4R0ZkbnVJNFlzK3VTRC9udm02?= =?utf-8?B?Nk5XWWJrNUt2dmxOdDE2Nm5CRkxsUmYzeFlyUkdIQlFQUXkwakRSWG9pOHk0?= =?utf-8?B?NGNpeVRBU2JyTG9rUUFJZ3VPZUVveFlEOXdoWjJUaUhWeXhkUWdMTXRiRkls?= =?utf-8?B?REtDckVtYjVzdVJlTjhHNUJ5d2FNZnNMTkRWOVlXRW9aVDVwYVpNbHRWTVVx?= =?utf-8?B?QVdxeGZTUjNFU3RiNjVhQXM4bGszVTF3VUpOU1RrblFrSlF3ZTRFZ2NvTmJL?= =?utf-8?B?ZzNiRHN1ZTlPQWhtOXlRV0dJSWJ5OU9VUStGV1RyUUdFUFdwU3VNZzQwckZz?= =?utf-8?B?eXRobkdEaGZNSjIwdVEydWpoeGhqTFVCM21xV2ZPY2U0OGVKSENLV0lOdDUr?= =?utf-8?B?QmpTYjk0UWE3aDdPQys4end2aVphbjV0eTVXTUpqOTBjVG9VTllVdzZReW9u?= =?utf-8?B?SVBiL2FLSFNTNVFiTW52QW1ySFdCMFROK3lpcmlTWUJWamNLNlp4SVpaOWJU?= =?utf-8?B?UlMwSEFNVmN6aWxpVTRQSFo1NTE1QzhieWprTkZPQ0VUbXR4dTVLSjFFWlM3?= =?utf-8?B?SHd3VGkvM3h6RHhwc2MxakU4SVNsN1RVb2xlQnFmNnZlWVltaFloczBZOU5W?= =?utf-8?B?bzY3V0xrVy93SGpNSWN5TUp1aStUeHo3ZUFkRXN4MVhZUG45MUE3cFBFK1RC?= =?utf-8?B?SDUxanBYK0NXNElSVGlSR1BGeE5QSTFqaFNnOWwvMUdsVFdkdFVtVUVIdm9l?= =?utf-8?B?SEJJSW0rcWwvcHlWLzAvNkY1SlVyK1poKzB4N0lsZmViTXgyVW5lWkxHUnVa?= =?utf-8?B?UVNCQnh5Qmx5amcrUGxKSnU3dVJpbkkxS1lPajZHSHoxb05nMDV6dGNucm5C?= =?utf-8?B?eVNsSmg4TWtnZUJqTEZBbzRkQTZJa3doQWFkTmlhc3o4bWFpOGFtUkQrMlQ3?= =?utf-8?B?aEhudTRDeG9iZjgxdVNKVFVFNFE1cFlmWGFONHVQdVJGMENIL0xFblJnUktY?= =?utf-8?B?dWcwbWdxODVoUng0ZEFSeWRBbGtUT05SUTJ2aU96ZFhQRWczVER3WFRBMUZO?= =?utf-8?B?SDluc241dWwzWGNTa2RsQWFqeTdnNFNhNTBvb0V3R2EycUNYZStwU0dRalVy?= =?utf-8?B?YlZYSjZ3c1dOSFlxaTExNFNoaHFtVkNGU2hIQ1hNNnBzZWU2ekRyejBmT0lJ?= =?utf-8?B?aWtMVmI1VnppWUZraEk4S3lSWS94bTBIRDlmUDBhdVhweVprbEZMMElqbmNL?= =?utf-8?B?Z1VRZlNMdmNtZC8xQnRHdz09?=
x-ms-exchange-transport-forked: True
Content-Type: text/plain; charset="utf-8"
Content-ID: <FBF0316EE3E8D248AE15FE1A5241BBEF@namprd05.prod.outlook.com>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-OriginatorOrg: juniper.net
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: MN2PR05MB6109.namprd05.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 331ec156-141d-497c-ad56-08d9373bf84e
X-MS-Exchange-CrossTenant-originalarrivaltime: 24 Jun 2021 18:14:55.7460 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: bea78b3c-4cdb-4130-854a-1d193232e5f4
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: UFtsEmMWrz6JbQjYEL3d9ax7HEVzBJQbWA3153wnvL+tB2TTc7kP9qcnFrhNuNOq
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR05MB7037
X-Proofpoint-ORIG-GUID: kMzy3XzAxZzPtMH0iK9aAqdYbFCUSL18
X-Proofpoint-GUID: kMzy3XzAxZzPtMH0iK9aAqdYbFCUSL18
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.391, 18.0.790 definitions=2021-06-24_12:2021-06-24, 2021-06-24 signatures=0
X-Proofpoint-Spam-Details: rule=outbound_spam_notspam policy=outbound_spam score=0 malwarescore=0 bulkscore=0 priorityscore=1501 impostorscore=0 clxscore=1015 phishscore=0 lowpriorityscore=0 mlxscore=0 suspectscore=0 adultscore=0 spamscore=0 mlxlogscore=948 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2104190000 definitions=main-2106240100
Archived-At: <https://mailarchive.ietf.org/arch/msg/idr/E5SALPd4LgCT0RCEki8worV04ec>
Subject: [Idr] Bug in RFC 7911 (add-paths) and tie-breaking
X-BeenThere: idr@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Inter-Domain Routing <idr.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/idr>, <mailto:idr-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/idr/>
List-Post: <mailto:idr@ietf.org>
List-Help: <mailto:idr-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/idr>, <mailto:idr-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 24 Jun 2021 18:15:11 -0000

Hi Folks,

Claudio recently pointed out a bug in RFC 7911 to the authors, and we thought we should let the WG know. The gist of the bug is that the tie-breaking process is underspecified, because it’s technically possible to receive two routes for the same destination, from the same peer, with different path-id, and with all tie-break metrics the same (all the way down to peer address). My guess — but it’s only a guess, I haven’t checked — is that implementations may mostly have chosen to prefer the first path received.[*] But the only thing we can say with confidence is “it’s underspecified and therefore implementation-dependent.” 

When I worked through this, my conclusion was that whatever option an implementation chooses should be safe, since by definition the paths are equivalent all the way down. I don’t see a way to form a loop even if every router in the network makes arbitrary — and conflicting — choices in this situation, since by definition of IGP distance, if a given router A makes an arbitrary choice, none of its neighbors when presented with the same set of routes will make a conflicting arbitrary choice, since the options are:

- The peer is closer to both destinations, in which case it can make any choice it wants, the traffic will not loop back to A,
- The peer is further from both destinations, in which case it can make any choice it wants, the traffic will not loop back from A,
- The peer is closer to one and further from the other destination, in which case it isn’t faced with a dilemma, it will choose the closer (and the traffic won’t go back towards A).

I guess if you’re in a network that doesn’t have IGP distances at all (maybe everything is static routed?) or if IGP distances don’t follow the usual rules of IGP “physics”, then you could create a problem. But those are pathological cases where we’d expect BGP not to work very well anyway. 

Claudio suggested that path-id would be a good final tie-break; that makes sense to me. We could do a quick update to 7911 to standardize this new tie-break, we could do a bis of 7911 to include the new tie-break, or we could just leave things as they are, relying on my argument above that says there is no strong need to standardize a tie-break since any choice is OK. 

For the moment, this is just an FYI for the WG. Thanks very much to Claudio for pointing out the bug!

—John

[*] You may notice that it’s possible to have two such paths packed into the same update in some circumstances, which makes the choice even more arbitrary since it’s pretty notional to say one has arrived before the other.