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

[[e-mail]]

Hi Claudio,

> From: Claudio Jeker [mailto:[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.

Sure, there can only be a single best so one need to ties on something.
But "first received" works. So does locally picking a random number per path.

> I think the standard should make sure that important parts like
> tie-breaking are fully specified.

Agreed that important parts be fully specified.
Now this comes down to determining which are the parts of the tie-breaking which are important to be standardized. (IOW which are the ones which are not really important)

 
> > - 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.

That seems to indicate that standardization is not required.
IOW, pick whatever looks best for your implementation: that will give you 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.

I have the same understanding: peer address is the more IP address of the TCP session.
My point was completely independent of BGP add path. I was trying to say that in some cases plain old RFC 4271 does not guarantee global consistency. But if that's not the goal, that's not a problem.

 
> > 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.

I think that a random value is fine for our goal. (even the local_pref could be picked at random by the egress ASBR)
My question was whether the value needs to be global or local.
I was assuming that eventually the goal was to get global consistency.

If your goal is have local determinism, first received works fine. Alternatively a random value picked when the path was learned also works. Alternatively the path-id (which may be a random value picked by your peer).
Is there anything special with the path idea which makes it a better choice? If not, anything chosen locally by any implementation works. And "first received" may save churn so looks a priori better.

 
> 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.

- Path-id (and route local age) does not seem to guaranty determinism as per https://en.wikipedia.org/wiki/Deterministic_system as the choice of the path-id may not be deterministic.
- Deterministic is a new requirement that you are bringing late on the table. At the beginning of your email, you only asked to tie-break on something.
After all, God/the universe seems to play dice, so why couldn't BGP ADD PATH? ;-)


This comes back to my initial question: what is the goal of those final tie-breakers.

Thanks for the discussion.

Regards,
--Bruno

> > 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

_________________________________________________________________________________________________________________________

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.