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

[Gyan Mishra <[e-mail]>]

With RR performing the tie breaking you end up with the issue ORR is
solving with the issue of hot potato routing in the case with add paths
where the RR is performing the best paths 2 and not selecting all and
advertising all paths to the clients to avoid additional possible memory
and resources with many paths for a prefix.  So in a RR environment as the
location of the RRs we have to assume in an operators network may not be
optimal and with add paths we don’t want the RR to perform the tie breaking
and always want the client to do the tie breaking based on its IGP location
to exit point and not RR location to exit point to avoid sub optimal
routing.

RFC 6774  analyses the RR planes with multiple RRs in comparison to add
paths as an alternative to add paths in case where add paths is not yet
fully deployed.  In the current modern scenario add paths would be fully
deployed along with many RRs spread throughout the operators core with
assumptions that RRs have not been placed in optimal position which could
result in hot potato routing.  Assumption here as well in this scenario is
the all paths are selected and advertised by the RR to avoid RR hot potato
routing or ORR is deployed as most all vendors have implemented.

Based on the deterministic versus not, the tie breaking rule to prevent RFC
4271 g> peer IP address randomness, RFC 5004 introduces best path compare
BGP-ID as the tie breaker as pointed out in this thread for deterministic
routing.

As no loops are will form as the peer IP g> would be the same in the add
path case RFC 5004 compare BGP-ID only comes into play with different peers
for deterministic routing, I don’t think the add paths tie path-id breaker
is really necessary and is random similar to g>  as compare to stability
achieved with RFC 5004 which does not apply here.

As the paths come from the same peer g> is what we are talking about, does
it really matter which path is picked as it’s the same peer, I don’t think
that would impact stability not having a tie breaker.

i don’t think that there is any benefit to using the path-id as a tie
breaker as it’s still random and not deterministic.

I think we could add a comment to considerations section in RFC 7911 about
not having an add paths tie breaker if anything or not do a bis at all.

Kind Regards

Gyan


On Fri, Jun 25, 2021 at 7:09 AM <[e-mail]> wrote:

> Robert,
>
>
>
> Your scenario would only require RR implementing RFC6774 to perform a
> common tie-breaking. So the bug/fix would rather be on RFC 6774 ;-)  (rather
> than on 7911)
>
>
>
> More seriously/importantly Path-Id is not guaranteed to be the same on
> both RR. Hence the output of the tie-breaking would not be common across
> those RR.
>
> For your use case, it seems it would be more effective to do the final
> tie-break on whatever criteria you want to be diverse. E.g. the BGP
> Next-Hop (which is both deterministic and diverse while Path-Id is not)
>
>
>
> Thanks,
>
> --Bruno
>
>
>
>
>
> *From**:* Robert Raszuk [mailto:[e-mail]]
> *Sent:* Friday, June 25, 2021 12:19 PM
> *To:* DECRAENE Bruno INNOV/NET <[e-mail]>
> *Cc:* Claudio Jeker <[e-mail]>; John Scudder <jgs=
> [e-mail]>; idr@ietf. org <[e-mail]>;
> [e-mail]
> *Subject:* Re: [Idr] Bug in RFC 7911 (add-paths) and tie-breaking
>
>
>
> Bruno,
>
>
>
> To your main question ...
>
>
>
> > I'm not sure what the goal of those final tie-breakers is.
>
>
>
> Well imagine a case of some RR peers not capable of add-paths or operator
> does not want to enable it there for some reasons.
>
>
>
> Such peers are however connected to two RRs.
>
>
>
> So when using RFC6774 https://datatracker.ietf.org/doc/html/rfc6774 it
> would be useful to consistently select one path of the presented here two
> paths and 2nd best path on the other RR when advertising to the peer.
>
>
>
> Such paths may be different in next hop as coming from different peer's
> ASBRs  (both next hops being of same IGP distance) and all other attributes
> to be equal.
>
>
>
> Without consistent tie breaker backup RR can not select 2nd best and this
> breaks RFC6774. It may also mess some add-paths scenarios when you choose
> to not send all paths.
>
>
>
> Hence "random" is not an option and it is a spec bug which needs to be
> fixed.
>
>
>
> Thx,
> R.
>
>
>
>
>
> On Fri, Jun 25, 2021 at 11:22 AM <[e-mail]> wrote:
>
> 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.
>
> _______________________________________________
> 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
>
-- 

<http://www.verizon.com/>

*Gyan Mishra*

*Network Solutions A**rchitect *

*Email [e-mail] <[e-mail]>*



*M 301 502-1347*