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

From: John Scudder <[email-masked]>
Date: Thu, 24 Jun 2021 18:14:55 +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.

---

From: Gyan Mishra <[email-masked]>
Date: Thu, 24 Jun 2021 15:44:17 -0400

Hi John

I agree that the tie breaking bug won’t form a loop as you stated as the
lowest IGP metric in the PE receiving the additional paths will ensue that
no loop will form.

So even though the tie breaker is not specified with RFC 7911, with all
attributes equal scenario, the oldest versus newest, first path received is
as you mentioned is the way most vendors implement the tie breaker.
However, even if done differently or arbitrarily it won’t form a loop due
to lowest IGP metric further up in the best path selection process.

Using the path-id as the tie breaker for add paths from the same peer makes
sense for the bis update.

Kind Regards

Gyan

On Thu, Jun 24, 2021 at 2:15 PM John Scudder <jgs=
[email-masked]> wrote:

> 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.
>
> [*] 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
> [email-masked]
> https://www.ietf.org/mailman/listinfo/idr
>
-- 

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

*Gyan Mishra*

*Network Solutions A**rchitect *

*Email [email-masked] <[email-masked]>*

*M 301 502-1347*

---

From: Robert Raszuk <[email-masked]>
Date: Thu, 24 Jun 2021 22:39:57 +0200

John,

> 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

While this is not about risk of loops, those paths may possibly contain
different optional attributes otherwise they would be rather duplicates.

More specifically one of them may contain additional optional attributes
while the other may not.

Perhaps with add-paths while we are at this discussion it may make sense to
choose the path with a longer list of BGP path attributes as such path may
be more useful to receivers.

Only then when the number of such attributes  is the same fall to path_id
as tie-break.

Thx,
Robert

---

From: "Jakob Heitz (jheitz)" <[email-masked]>
Date: Thu, 24 Jun 2021 22:20:05 +0000

Then the code would have to compute the attribute length for each path, carry it along and pass it to the bestpath compare function.
For what? To increase convergence time?
Because simple byte length will not be good enough and people will start arguing that
an extended community is just as valuable as a regular community and count the number of communities
rather than bytes and then the tunnel attribute is longer and on and on.
I vote for path-id.

Regards,
Jakob.

From: Idr <[email-masked]> On Behalf Of Robert Raszuk
Sent: Thursday, June 24, 2021 1:40 PM
To: John Scudder <jgs=[email-masked]>
Cc: [email-masked]; idr@ietf. org <[email-masked]>
Subject: Re: [Idr] Bug in RFC 7911 (add-paths) and tie-breaking

John,

> 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

While this is not about risk of loops, those paths may possibly contain different optional attributes otherwise they would be rather duplicates.

More specifically one of them may contain additional optional attributes while the other may not.

Perhaps with add-paths while we are at this discussion it may make sense to choose the path with a longer list of BGP path attributes as such path may be more useful to receivers.

Only then when the number of such attributes  is the same fall to path_id as tie-break.

Thx,
Robert

On Thu, Jun 24, 2021 at 8:15 PM John Scudder <jgs=[email-masked]<mailto:[email-masked]>> wrote:
Hi Folks,

—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
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/idr

---

From: "Jakob Heitz (jheitz)" <[email-masked]>
Date: Thu, 24 Jun 2021 22:27:40 +0000

And then when the attribute length is equal, you'll need another tie-breaker.

Regards,
Jakob.

From: Idr <[email-masked]> On Behalf Of Jakob Heitz (jheitz)
Sent: Thursday, June 24, 2021 3:20 PM
To: Robert Raszuk <[email-masked]>; John Scudder <jgs=[email-masked]>
Cc: [email-masked]; idr@ietf. org <[email-masked]>
Subject: Re: [Idr] Bug in RFC 7911 (add-paths) and tie-breaking

Regards,
Jakob.

From: Idr <[email-masked]<mailto:[email-masked]>> On Behalf Of Robert Raszuk
Sent: Thursday, June 24, 2021 1:40 PM
To: John Scudder <jgs=[email-masked]<mailto:jgs=[email-masked]>>
Cc: [email-masked]<mailto:[email-masked]>; idr@ietf. org <[email-masked]<mailto:[email-masked]>>
Subject: Re: [Idr] Bug in RFC 7911 (add-paths) and tie-breaking

John,

Thx,
Robert

—John

---

From: Gyan Mishra <[email-masked]>
Date: Thu, 24 Jun 2021 19:19:54 -0400

RFC 7911 section 2

   The assignment of the Path Identifier for a path by a BGP speaker is
   purely a local matter.  However, the Path Identifier MUST be assigned
   in such a way that the BGP speaker is able to use the (Prefix, Path
   Identifier) to uniquely identify a path advertised to a neighbor.  A
   BGP speaker that re-advertises a route MUST generate its own Path
   Identifier to be associated with the re-advertised route.  A BGP
   speaker that receives a route should not assume that the identifier
   carries any particular semantics.

As the path-is is locally generated it should always be unique - 32
bit unsigned integer.

Gyan

On Thu, Jun 24, 2021 at 6:28 PM Jakob Heitz (jheitz) <jheitz=
[email-masked]> wrote:

> *From:* Idr <[email-masked]> *On Behalf Of * Jakob Heitz (jheitz)
> *Sent:* Thursday, June 24, 2021 3:20 PM
> *To:* Robert Raszuk <[email-masked]>; John Scudder <jgs=
> [email-masked]>
> *Cc:* [email-masked]; idr@ietf. org <[email-masked]>
> *Subject:* Re: [Idr] Bug in RFC 7911 (add-paths) and tie-breaking
>
>
>
> Then the code would have to compute the attribute length for each path,
> carry it along and pass it to the bestpath compare function.
>
> *From:* Idr <[email-masked]> *On Behalf Of *Robert Raszuk
> *Sent:* Thursday, June 24, 2021 1:40 PM
> *To:* John Scudder <jgs=[email-masked]>
> *Cc:* [email-masked]; idr@ietf. org <[email-masked]>
> *Subject:* Re: [Idr] Bug in RFC 7911 (add-paths) and tie-breaking
>
>
>
> John,
>
>
>
> Perhaps with add-paths while we are at this discussion it may make sense
> to choose the path with a longer list of BGP path attributes as such
> path may be more useful to receivers.
>
>
>
-- 

*Gyan Mishra*

*M 301 502-1347*

---

From: <[email-masked]>
Date: Fri, 25 Jun 2021 07:57:10 +0000

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

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

> -----Original Message-----
> From: Idr [mailto:[email-masked]] On Behalf Of John Scudder
> Sent: Thursday, June 24, 2021 8:15 PM
> To: idr@ietf. org <[email-masked]>
> Cc: [email-masked]
> 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.”
> 
> 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.
> 
> [*] 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.

_________________________________________________________________________________________________________________________

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.

---

From: Claudio Jeker <[email-masked]>
Date: Fri, 25 Jun 2021 10:37:35 +0200

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

Reagrds
-- 
:wq Claudio

---

From: Claudio Jeker <[email-masked]>
Date: Fri, 25 Jun 2021 10:43:38 +0200

> rather than bytes and then the tunnel attribute is longer and on and on.

I agree, also the total attribute length can be equal if e.g. if one path
uses 3 communities and the other has one large-community. Checking on
attribute length is not a good tie-breaker.

In my opinion the check is here to select between two equal path that are
sent from the same peer. Because of this it makes sense to use path_id as
a tie-breaker. Since path-id is the one thing that distinguishes these two
paths.

-- 
:wq Claudio

---

From: <[email-masked]>
Date: Fri, 25 Jun 2021 09:21:48 +0000

Hi Claudio,

> From: Claudio Jeker [mailto:[email-masked]]
> 

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.

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

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

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

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

> 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

> router in
> sense
> > > For the moment, this is just an FYI for the WG. Thanks very much to Claudio
> for
> > > pointing out the bug!
> > >
> > > —John
> > >
> ______________________________________________________________________
> ___________________________________________________
> >
> > Ce message et ses pieces jointes peuvent contenir des informations
> confidentielles ou privilegiees et ne doivent donc
> > a l'expediteur et le detruire ainsi que les pieces jointes. Les messages
> electroniques etant susceptibles d'alteration,
> > This message and its attachments may contain confidential or privileged
> information that may be protected by law;

---

From: Robert Raszuk <[email-masked]>
Date: Fri, 25 Jun 2021 12:18:41 +0200

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 <[email-masked]> wrote:

> > > 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
> > ;-) ).
> > >
> 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)
>
>
> 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.
>
>
> I think that a random value is fine for our goal. (even the local_pref
> could be picked at random by the egress ASBR)
> 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.
>
>
> - 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.
> > > > Claudio recently pointed out a bug in RFC 7911 to the authors, and
> we thought
> > we
> > > > 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
> > > > 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
> > > > - The peer is closer to both destinations, in which case it can make
> any choice
> > it
> > > > - The peer is further from both destinations, in which case it can
> make any
> > choice it
> > > > - 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).
> > > >
> > > > everything is static routed?) or if IGP distances don’t follow the
> usual rules of
> > IGP
> > > > 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
> > > > [*] 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
> > > pas etre diffuses, exploites ou copies sans autorisation. Si vous avez
> recu ce
> > message par erreur, veuillez le signaler
> > > Orange decline toute responsabilite si ce message a ete altere,
> deforme ou
> > falsifie. Merci.
> > >
> > > 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.
> > >
> pas etre diffuses, exploites ou copies sans autorisation. Si vous avez
> recu ce message par erreur, veuillez le signaler

---

From: <[email-masked]>
Date: Fri, 25 Jun 2021 11:08:26 +0000

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:[email-masked]]
Sent: Friday, June 25, 2021 12:19 PM
To: DECRAENE Bruno INNOV/NET <[email-masked]>
Cc: Claudio Jeker <[email-masked]>; John Scudder <jgs=[email-masked]>; idr@ietf. org <[email-masked]>; [email-masked]
Subject: Re: [Idr] Bug in RFC 7911 (add-paths) and tie-breaking

Bruno,

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

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 <[email-masked]<mailto:[email-masked]>> wrote:
Hi Claudio,

> From: Claudio Jeker [mailto:[email-masked]<mailto:[email-masked]>]
>
> On Fri, Jun 25, 2021 at 07:57:10AM +0000, [email-masked]<mailto:[email-masked]> wrote:
> > Hi John, all
> >
> > Thanks for sharing.
> >

Regards,
--Bruno

> > > From: Idr [mailto:[email-masked]<mailto:[email-masked]>] On Behalf Of John Scudder
> > > To: idr@ietf. org <[email-masked]<mailto:[email-masked]>>
> > > Cc: [email-masked]<mailto:[email-masked]>

---

From: Gyan Mishra <[email-masked]>
Date: Fri, 25 Jun 2021 08:25:13 -0400

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 <[email-masked]> 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:[email-masked]]
> *Sent:* Friday, June 25, 2021 12:19 PM
> *To:* DECRAENE Bruno INNOV/NET <[email-masked]>
> *Cc:* Claudio Jeker <[email-masked]>; John Scudder <jgs=
> [email-masked]>; idr@ietf. org <[email-masked]>;
> [email-masked]
> delete this message and its attachments.
-- 

*Gyan Mishra*

*M 301 502-1347*

---

From: Robert Raszuk <[email-masked]>
Date: Fri, 25 Jun 2021 15:12:00 +0200

Hi Bruno,

> common tie-breaking. So the bug/fix would rather be on RFC 6774 ;-)  (rather

That is debatable.

> both RR. Hence the output of the tie-breaking would not be common across

Don't agree. If a BGP speaker spends two paths with path_id they will be
identical on both RRs. Path_IDs are not ad hoc random numbers generated on
the fly when you advertise. They are attached to paths and do not change
regardless where the paths are advertised with add-path.

So this will work fine for RFC6774.

> Next-Hop (which is both deterministic and diverse while Path-Id is not)

For the described case path_id will work. But in general case, surely
selecting path with different next hop as 2nd best will be a good option.
In fact some implementations already do that already :)

Thx,
R.

---

From: <[email-masked]>
Date: Fri, 25 Jun 2021 14:37:46 +0000

Inline [Bruno]

Sent: Friday, June 25, 2021 3:12 PM

Hi Bruno,

That is debatable.

Don't agree. If a BGP speaker spends two paths with path_id they will be identical on both RRs.

[Bruno] You are assuming that your two “diverses RR” learn the paths from the same (set of) peers. I agree that this is typical, but this is not guaranteed. If not, the path-id would not be comparable.

Path_IDs are not ad hoc random numbers generated on the fly when you advertise. They are attached to paths and do not change regardless where the paths are advertised with add-path.

[Bruno] I’d assume that this would be the case on implementations as this seems more optimal.
However, this is not how this is specified in RFC 7911. There is no statement that the path_ID be ‘per plateform’ (rather than per-peer) and the RFC is clear that it’s a local choice of the sender and the receiver should not make any assumption. So you can’t make any claim on this.

For the described case path_id will work. But in general case, surely selecting path with different next hop as 2nd best will be a good option. In fact some implementations already do that already :)
[Bruno] If you want diverse paths, better to compute for path diversity, rather than use a random BGP tie break (e.g. peer address, path-id, local_pref). You could have 3 paths, with 3 different path-id and only 2 NH (Next Hop Self on the ASBR advertising two path). Picking the diverse a second path from the same ASBR is less diverse and will not protect from ASBR failure.

Thanks
--Bruno

Thx,
R.

---

From: Robert Raszuk <[email-masked]>
Date: Fri, 25 Jun 2021 17:39:40 +0200

Bruno,

> identical on both RRs.
>
>
>
> [Bruno] You are assuming that your two “diverses RR” learn the paths from
> the same (set of) peers. I agree that this is typical, but this is not
> guaranteed. If not, the path-id would not be comparable.
>

If they are from different peers there is no problem to start with as best
path already picks path from lowest neighbor address.

Thx,
R.

---

From: <[email-masked]>
Date: Fri, 25 Jun 2021 15:54:37 +0000

Sent: Friday, June 25, 2021 5:40 PM

Bruno,

If they are from different peers there is no problem to start with as best path already picks path from lowest neighbor address.

I meant two Add Path RR peers. Each peer/session advertising both paths in one session. Cf below topology

Add Path RR1a --- Diverse RR1
Add Path RR1b -----+

Add Path RR2a --- Diverse RR2
Add Path RR2b -----+

Notes:
- “—“ is a IBGP sessions advertising the two paths.
- I agree that the topology is debatable and does not match typical deployments. That’s all I found so far to find a counter example for your Diverse Path use case, so let’s call my example weak and close the Divers Path discussion

Thanks,
Bruno

Thx,
R.

---

From: Claudio Jeker <[email-masked]>
Date: Fri, 25 Jun 2021 18:25:55 +0200

> regardless where the paths are advertised with add-path.

RFC7911 has no such requirement. At least Section 2 allows to assign
different path-ids for the same path sent to different peers.
It would be perfectly fine to use random path ids as long as all
updates and the final withdraw of this path use the same id.
Once the path has been withdrawn a new path_id could actually be selected
again.  This is how I interpret Section 2 of RFC7911 especially this bit:

> In fact some implementations already do that already :)

In my opinon it would be great to have this documented somewhere so that
all implementations are able to behave the same.
Using the nexthop as a tie-breaker makes sense to me. I agree that path-id
is not the best criteria but it is the only one that can actually
distinguish two paths that are equal. RFC7911 does not specify that a
peer MUST NOT send paths with equivalent attributes over add-path.
So I guess one has to assume that a system may actually do that.

-- 
:wq Claudio

---

From: Robert Raszuk <[email-masked]>
Date: Fri, 25 Jun 2021 19:45:29 +0200

Hi Claudio,

> again.  This is how I interpret Section 2 of RFC7911 especially this bit:

Right I was referring to some implementations then the spec.

> all implementations are able to behave the same.

FWIW we did document it clearly in RF6774.

The "Nth best path" really
describes set of N paths with different BGP next hops.

But I realize this discussion is about RFC7911.

I recall the intention was to keep the spec short but provide guidelines in
separate document:

Namely in draft-ietf-idr-add-paths-guidelines-08.

There you can see section 4.3.1.1 is very clear on what paths should be
selected based on the three criteria:

     (a) not selected during a previous iteration

     (b)_diverse with respect to previously selected paths (see
section <https://datatracker.ietf.org/doc/html/draft-ietf-idr-add-paths-guidelines-08#section-2>
     2 <https://datatracker.ietf.org/doc/html/draft-ietf-idr-add-paths-guidelines-08#section-2>
for the definition of a diverse path)
     (c) not rejected by route filters or split horizon advertisement
     rules

for us key is (b) and diverse path definition says:

   Diverse path: A BGP path associated with a different BGP next-hop and
   BGP router than some other set of paths. The BGP router associated
   with a path is inferred from the ORIGINATOR_ID attribute or, if there
   is none, the BGP Identifier of the peer that advertised the path.

making it clear that sending N paths should have different next hops.

I am not sure why this draft was not progressed though. At least it is WG
document.

Many thx,
R.

---

From: Jeffrey Haas <[email-masked]>
Date: Sat, 26 Jun 2021 10:49:48 -0400

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

IMO, path-id is a lousy thing to tie-break on.

** blows the dust off prior discussion **

https://datatracker.ietf.org/doc/html/draft-pmohapat-idr-fast-conn-restore-03

In general, when a given peer is passing along multiple paths, the case that
gives us grief is when we get them from ebgp.  The draft above discusses the
problem nicely.

If there are common scenarios where a given BGP speaker will locally
originate multiple paths without having gotten them from somewhere else, I'm
not currently aware of it.

-- Jeff

---

From: Robert Raszuk <[email-masked]>
Date: Sat, 26 Jun 2021 16:41:33 +0200

Jeff,

> not currently aware of it.

I think it is pretty common to connect PE (for simplicity assume non VPN
case) to two customer CEs.

Those CEs are over static + bfd.

Further those may be connected with different link bw.

So if you redistribute those two static routes to different CE's next hops
you will likely end up with two paths in BGP. Normally sending one will be
cool as you set next hop self, normally repair any failure, locally load
balance across links to CEs etc ... life is good.

But the moment you enable add-paths, adventure (not to say pollution)
starts.

I think this could be a pretty common case this discussion could get
triggered off.

And thx for bringing up the  conn-restore draft. I guess it matured
sufficiently to perhaps refresh it and start WG adoption call ? Either
Pradosh or myself should have the latest xml for it.

Thx,
R.

---

From: John Scudder <[email-masked]>
Date: Sat, 26 Jun 2021 15:13:09 +0000

Hi Jeff,

> On Jun 26, 2021, at 10:49 AM, Jeffrey Haas <[email-masked]> wrote:
> 
> https://urldefense.com/v3/__https://datatracker.ietf.org/doc/html/draft-pmohapat-idr-fast-conn-restore-03__;!!NEt6yMaO-gk!Tu7ZQLzHLMryoAz1GQuACoeSVHsC_MEDFDbTs7fDdavcj2sCxQOCHvmVnXxQHQ$
> 

I won’t try to argue that this is a common case (although Robert has provided an argument). My perspective is that whether common or uncommon, ideally the protocol would cover the case. Now, my previous argument was that because leaving the tie-break underspecified/implementation-specific is safe to do, we don’t urgently need to fix the oversight; your assertion that it’s an uncommon case bolsters that position. But, I think it’s clear that if the oversight had been noticed while we were developing 7911, we’d have fixed it.

As for whether path-id is a “good" or “bad" tie-break, again I think that’s beside the point. I think it would be good to introduce something along the lines of fast-conn-restore to cover that use case, no doubt. The point of the path-id tie-break, if we did it, would be to make the outcome fully specified in all cases, even those missed by fast-conn-restore.

$0.02,

—John

---

From: Jeffrey Haas <[email-masked]>
Date: Sat, 26 Jun 2021 12:18:43 -0400

Robert,

> > not currently aware of it.

It's peculiar that your mail software consistently eats the first part of
the quote above.  Anyway...

> I think this could be a pretty common case this discussion could get

Agreed.

For my part, I see it as an example of the draft.  The nexthops could
arguably be considered the peer-id for purposes of that proposal.

> Pradosh or myself should have the latest xml for it.

I won't make a specific argument for maturity.  I have personally brought it
out repeatedly over the years because it summarizes this problem well.

It has issues with incremental deployment that would need to be addressed in
the text.  How should a domain that has a mix of BGP speakers that
understands this or not work together?  Probably fine since as John notes
it's basically "good enough".

The reason I haven't pressed on advancing the draft in my day job capacity
over the years is largely the observation John ends up making with one
possible refinement:  Locally, do whatever you like to pick a consistent
active route.  As long as you're getting to the endpoint via tunneling
rather than hop-by-hop along the way it's likely fine.

Depending on how this conversation advances, it might be worth bringing the
document back for adoption consideration.

-- Jeff

---

From: Jeffrey Haas <[email-masked]>
Date: Sat, 26 Jun 2021 12:26:27 -0400

John,

On Sat, Jun 26, 2021 at 03:13:09PM +0000, John Scudder wrote:
> Now, my previous argument was that because leaving the tie-break
> underspecified/implementation-specific is safe to do, we don’t urgently
> need to fix the oversight; your assertion that it’s an uncommon case
> bolsters that position. But, I think it’s clear that if the oversight had
> been noticed while we were developing 7911, we’d have fixed it.

There's a fair chance I brought out the fast-conn document during that
discussion.  The hand-waving we'd done at the time was effectvely the caveat
of "don't inject routes from ebgp".

> As for whether path-id is a “good" or “bad" tie-break, again I think
> that’s beside the point. I think it would be good to introduce something
> along the lines of fast-conn-restore to cover that use case, no doubt. The
> point of the path-id tie-break, if we did it, would be to make the outcome
> fully specified in all cases, even those missed by fast-conn-restore.

Path-ids are by protocol behavior permitted to be effectively random numbers
as long as they're consistently used.

The Juniper implementation tries to conserve the path-id space and will
pretty aggressively re-use the ids.  A result is that we'd deterministically
pick a random winner.

Another implementation I have accidental exposure to embeds either the BGP
identifier or neighbor address in the path-id.  For a single hop ebgp
leaking case via add-paths, it can proxy for one of the steps and lead to
more deterministic tie-breaking.  However, it only does so at that first
step.

With the path attribute from fast-conn-restore, you get that tie-breaking
behavior more deterministically across an AS.

The minute you start going multi-AS or start looking at the considerations
of the attribute as specified in that document as it leaks, the situation
becomes messier.  Effectively the attribute has meaning until the next point
you do a next-hop reset.  Now, how do you prove that the last party that
reset the nexthop stripped the attribute or reset it appropriately?

-- Jeff

---

From: Nick Hilliard <[email-masked]>
Date: Sat, 26 Jun 2021 18:53:37 +0100

John Scudder wrote on 26/06/2021 16:13:
> The point of the path-id tie-break, if we did it, would be to make
> the outcome fully specified in all cases, even those missed by
> fast-conn-restore.
^^^^ that.  It's operationally important to have an option to have 
deterministic routing.

Nick

---

From: Gyan Mishra <[email-masked]>
Date: Sat, 26 Jun 2021 14:24:10 -0400

+1 on deterministic routing similar to bestpath compare routerid

-- 

*Gyan Mishra*

*M 301 502-1347*

---

From: Gyan Mishra <[email-masked]>
Date: Wed, 30 Jun 2021 00:15:24 -0400

Robert / All

Is the plan to revive fast-connection-restore draft with new Edge
Discriminator attribute tie breaker,  and not update RFC 7911 w/ path-id as
the tie breaker.

I support this plan and would be happy to contribute and collaborate  on
the fast-connection-restore draft.

Kind Regards

Gyan

*Gyan Mishra*

*M 301 502-1347*