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

[Claudio Jeker <[e-mail]>]

On Fri, Jun 25, 2021 at 07:57:10AM +0000, [e-mail] wrote:
> Hi John, all
> 
> Thanks for sharing.
> 
> TL;DR: I agree that there is no risk of loop. I can live with any of the proposed options.
> 
> 
> For the pleasure of the technical discussion (although I'm likely to regret it latter ;-) ).
> 
> TBH, I'm not sure what the goal of those final tie-breakers is.

I think the goal is to always tie on something. OpenBGPD checks that the
decision process comes to a end result and fails when two prefixes compare
equal. This is why I noticed that add-path is missing something.
I think the standard should make sure that important parts like
tie-breaking are fully specified.

> - If the goal is to avoid loops, IMHO the goal is achieved after step
> "e" (IGP cost) (assuming there is an IGP optimizing for a metric, and
> that each individual metric >0.)
> - If the goal is for all nodes to select the same path (consistency),
> then it seems to me that the goal is missed at step "g" (peer address)
> [1] as "g" relies on an local information, hence I don't see how global
> consistency can be achieved. 

This is not about global consistency, it is about having a deterministic
outcome. So this is about local consistency.

>  - I guess that RFC 4271 had IBGP full mesh in mind, in which case "peer
>  address" can reasonably be assumed to be global. But that's not the
>  case with 4456 (BGP RR), not to mention with the extra tie-break rule
>  added by 4456.

Can you please explain what peer address means? RFC 4271 has only one case
of that term in the document. For me peer address is the remote IP address
of the TCP session to the peer. For bgp add-path the peer address is the
same for all paths sent. This is why an extra tie breaker is needed.
 
> Coming back to RFC 7911, path-id is a local ID/choice of the upstream,
> hence does not seem like providing either global consistency or
> implementation-independence. However, as raised by John and Jakob, in
> the end/worst case, that's all we have. (well, "first received",
> "random" probably equally works given that from the node perspective,
> the path-id can be seen as a local random number (and technically, it
> could be a random number). "First received" may even save some churn)

The same can be said about step f) comparing bgpid fields. With the
introduction of RFC6286 bgpids can also be considered random. Again the
goal here is to end up with a deterministic result. Both the pathid and
the bgpid can be considered stable during run time.

Many systems already support evaluating routes based on their age as an
extra configurable option (normally just before step f and g) but if that
option is off the tie-breaking process should be deterministic.

> A priori, I would have preferred 7911 to add the extra tie-breaker,
> however at this point, I'm not seeing a benefit for creating a bis.(but
> there is also no harm assuming chairs and IESG cycles are free and
> unlimited)
> 
>  [1] https://www.rfc-editor.org/rfc/rfc4271.html#section-9.1.2.2
> 
> --Bruno
> 

Reagrds
-- 
:wq Claudio

> > -----Original Message-----
> > From: Idr [mailto:[e-mail]] On Behalf Of John Scudder
> > Sent: Thursday, June 24, 2021 8:15 PM
> > To: idr@ietf. org <[e-mail]>
> > Cc: [e-mail]
> > Subject: [Idr] Bug in RFC 7911 (add-paths) and tie-breaking
> > 
> > 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.
> > _______________________________________________
> > Idr mailing list
> > [e-mail]
> > https://www.ietf.org/mailman/listinfo/idr
> 
> _________________________________________________________________________________________________________________________
> 
> Ce message et ses pieces jointes peuvent contenir des informations confidentielles ou privilegiees et ne doivent donc
> pas etre diffuses, exploites ou copies sans autorisation. Si vous avez recu ce message par erreur, veuillez le signaler
> a l'expediteur et le detruire ainsi que les pieces jointes. Les messages electroniques etant susceptibles d'alteration,
> Orange decline toute responsabilite si ce message a ete altere, deforme ou falsifie. Merci.
> 
> This message and its attachments may contain confidential or privileged information that may be protected by law;
> they should not be distributed, used or copied without authorisation.
> If you have received this email in error, please notify the sender and delete this message and its attachments.
> As emails may be altered, Orange is not liable for messages that have been modified, changed or falsified.
> Thank you.
> 
> _______________________________________________
> Idr mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/idr