Subject: RE: [Idr] Progressing draft-bhatia-bgp-multiple-next-hops-01.txt

From: "Manav Bhatia" <[email-masked]>
Date: Thu, 24 Aug 2006 11:20:47 +0530

> PS. The stated issue with add-path's drawback to require uniqe
> identifier to be generated by BGP speaker is not IMHO at all a problem.

It is really.

The suggested scheme becomes mucky and fragile when one has to readvertise
the multiple paths that it has received, because it can then no longer use
the Router ID to disambiguate the paths. The speaker is then left to
construct some unique arbitrary identifier specific to the peer the speaker
is sending the path to, for those paths.

A
|
B   C
 \  /
  D

Assume A sends two routes x1:10/8, x2:10/8, where x1 and x2 are the router
IDs of the peers A received these routes from, to B. 

How does B announce these routes forward to D? 

It has to generate and manage unique path IDs which now, are neither based
on router IDs nor derived from AS numbers, etc. Something that the draft
conveniently prefers to skim over. The use of arbitrary path IDs can
influence the amount of memory required to hold the routes on both the
routers. If different path IDs are used, the amount of memory needed to
store all the routes increases. You cannot simply ignore the path IDs that
you send/receive as you need to store them for performing implicit/complete
withdrawals.

The claim therefore that add-paths "requires only minor software changes for
the vast majority of the BGP speakers in a network" is misleading and
incorrect. [1]

We believe that introducing a new arbitrary identifier is redundant, complex
and prone to implementation quirks and can fail in interesting ways. We
instead use the next_hop (which is already exchanged) as the "unique
identifier".

>In general I think your draft may work well for IPv4/v6 unicast address
>family. I don't think that it works well for any other address families
>already proposed in this WG.

I have already replied as to how this proposal would work for VPNv4 routes,
and other AFI, SAFI routes. Let me know if there is any ambiguity there.

Cheers,
Manav

[1] The last paragraph in section 3 from
draft-walton-bgp-route-oscillation-stop-01.txt

_______________________________________________
Idr mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/idr

---

From: Enke Chen <[email-masked]>
Date: Thu, 24 Aug 2006 00:55:14 -0700

>is sending the path to, for those paths.

Depends on the application, a speaker may or may not be able to use the 
same path identifier it has received. What exactly is the problem of 
constructing an identifier?

>How does B announce these routes forward to D? 

Router-ids are unique only with an AS. Since you did not specify the 
application, the fact that Router A uses the router-id as the identifier 
seems to suggest that this is a route reflection case (full-mesh), and 
it is ibgp between A and B.

How does B announce these routes to D?   It depends on the application 
again. If D is an ibgp peer, B can use the same router-id.   If D is an 
ebgp peer and ebgp multipath is involved, B needs to assign an unique id.

>instead use the next_hop (which is already exchanged) as the "unique

It is all relative, and I am afraid that your description of "mucky, 
fragile, redundant, complex, prone to error" might be relevant in the 
current discussion.

-- Enke

---

From: Enke Chen <[email-masked]>
Date: Thu, 24 Aug 2006 01:28:12 -0700

Let me comment on the memory issue that I forgot to address in the 
previous message:

So how much additional memory are we talking about:  I think the max  is 
8 bytes per path (4bytes for receiving, and 4bytes for allocating).  For 
some applications (such as RR) the memory overhead for the path 
identifier is zero. Regarding the memory overhead in allocating a path 
identifier, it should be no more than 4 bytes per prefix.

I am actually not concerned about the memory overhead for allocating and 
storing the path identifier because they are small compared to the 
memory that would be needed to store the per-path advertisement state 
for supporting multi-path in general.

-- Enke

Manav Bhatia wrote:

[snip]

---

From: Enke Chen <[email-masked]>
Date: Thu, 24 Aug 2006 01:28:12 -0700

-- Enke

Manav Bhatia wrote:

[snip]

---

From: "John G. Scudder" <[email-masked]>
Date: Thu, 24 Aug 2006 13:54:29 -0400

At 11:20 AM +0530 8/24/06, Manav Bhatia wrote:
>The suggested scheme becomes mucky

I won't take that personally, but I do suggest that you may want to 
consider your choice of adjectives in the future.  Glass houses, 
stones, etc.

>and fragile when one has to readvertise
>conveniently prefers to skim over.

Actually, something that the draft deliberately chooses to remain 
silent on because we didn't care to over-specify.

I'm dumbfounded that so many people seem to believe that associating 
a unique identifier with a datum is a hard problem.  I guess if we 
resurrect add-path, we could add an appendix with a sample algorithm, 
or we can just provide a reference to a standard algorithms textbook.

>The use of arbitrary path IDs can
>routers.

Omelette, eggs, etc.  The additional overhead isn't very much 
(neighborhood of 8 bytes/route -- 4 for rx'd identifier, 4 for tx'd), 
but yes it does exist.

>If different path IDs are used, the amount of memory needed to

Well, sure.  I'm not sure this is an interesting point of comparison 
though -- see follow up to Enke's message.

>the vast majority of the BGP speakers in a network" is misleading and

Only speakers which wish to advertise multiple paths have to know how 
to generate unique path identifiers.  The rest just need to know how 
to consume them.  I guess it's in the eye of the beholder what 
constitutes "minor".  Or maybe it's "vast".  In any case, I'd rather 
debate specific merits rather than argue about whether it's 
misleading if vast is more elegant than minor.

>instead use the next_hop (which is already exchanged) as the "unique

Regarding redundancy (which is the only claim above which is 
substantive enough to debate at this point) see my previous message 
to Paul.

--John

---

From: Enke Chen <[email-masked]>
Date: Thu, 24 Aug 2006 11:19:36 -0700

> silent on because we didn't care to over-specify.

Exactly, as it is trivial and implementation specific.

>
> I'm dumbfounded that so many people seem to believe that associating a 
> unique identifier with a datum is a hard problem. I guess if we 

Let us give a trivial algorithm:

For a prefix, allocate the path identifiers for paths sequentially 
starting from 0, do not reuse until it wraps (that will take many many 
years).

-- Enke

---

From: "John G. Scudder" <[email-masked]>
Date: Thu, 24 Aug 2006 16:08:45 -0400

At 8:44 PM +0100 8/24/06, Paul Jakma wrote:
>On Thu, 24 Aug 2006, Enke Chen wrote:
>
>>starting from 0, do not reuse until it wraps (that will take many 
>>many years).
>
>Now you receive a path update and must pass it on to this peer, how 
>do you find out whether a previous path was advertised?

The referent of "this" isn't clear but I'll take a shot at answering anyway.

>Bear in mind, you can't just compare against peer path was received 
>from, because there can be multiple such paths.

- Peer A sends us route R for prefix P with path ID N.
- If peer A has not previously sent us a route for P with ID N,
   this is a new route.  We store it, allocating it local ID M
   calculated as P->local_id++ (you get the idea I hope).  Now
   that we have a local ID for it, we can advertise it using that
   ID, following whatever normal procedures we have for
   advertising a route to a peer.
- If peer A has previously sent us a route for prefix
   P with path ID N, this is a replacement.  We replace our
   local copy -- there is no need to recompute our local ID as we
   already have one -- and re-advertise the route using our local
   ID, following whatever normal procedures we have for advertising
   a route to a peer.

I'm not sure if that answers your question or not.  If the question 
was "how do you know if the peer previously advertised a route to 
us?" the answer is "you look it up, just like you do now, only 
considering the path ID as well".  If the question was "how do you 
know if you previously advertised the route to your (other) peer?" 
the answer is "just like you do now".  If I've missed the sense of 
your question altogether, please ask again.

--John

---

From: Paul Jakma <[email-masked]>
Date: Thu, 24 Aug 2006 20:44:15 +0100 (IST)

On Thu, 24 Aug 2006, Enke Chen wrote:

> For a prefix, allocate the path identifiers for paths sequentially starting 
> from 0, do not reuse until it wraps (that will take many many years).

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
It is easier for a camel to pass through the eye of a needle if it is
lightly greased.
 		-- Kehlog Albran, "The Profit"

---

From: Paul Jakma <[email-masked]>
Date: Fri, 25 Aug 2006 00:59:54 +0100 (IST)

> The referent of "this" isn't clear but I'll take a shot at answering anyway.

Oops, and cheers. :)

[snip]

Right, an unstable per-path counter is what add-path boils down to, 
if you refuse to use information from the path itself.

Could either yourself or Enke explain why the coupled-state objection 
does not apply here? The specific quote I have in mind (from Enke) 
is:

  "It means that at the time of sending update the info (such as the
   nexthop) for the old path may no longer available."

With an unstable identifier you lose ability for a temporaly 
decoupled update sending process to 'bunch' a series of withdraws and 
readvertisements into one implicit withdrawal.

Unless of course you add state to remember the IDs of removed paths 
(not too terrible) and a way to 'lose' that info once it becomes 
irrelevant (should be easy, but..).

Why do none of these concerns apply to add-path and unstable IDs?

And still, this counter seems redundant to us given next-hop appears 
to suffice for all known uses of BGP.

1. To Multiple-Hop, but which state actually does not need to be kept
    for Multiple-Hop.

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
Why can't you be a non-conformist like everyone else?

---

From: "John G. Scudder" <[email-masked]>
Date: Thu, 24 Aug 2006 20:24:31 -0400

At 12:59 AM +0100 8/25/06, Paul Jakma wrote:
>Right, an unstable

Unstable?  Not sure what you mean by that -- perhaps that the path ID 
isn't (necessarily) derived from anything in the path, nor is the 
initial value it will get be predictable.  It's not unstable in the 
sense of shifting arbitrarily once assigned -- it remains the same 
for the life of the route (though should the peer withdraw and then 
later re-advertise the route, it'd change).

>per-path counter is what add-path boils down to, if you refuse to 
>use information from the path itself.
>
>Could either yourself or Enke explain why the coupled-state 
>objection does not apply here? The specific quote I have in mind 
>(from Enke) is:
>
>decoupled update sending process to 'bunch' a series of withdraws 
>and readvertisements into one implicit withdrawal.

I don't understand why you should say so.  (N.b. a more familiar term 
than 'bunch' -- to me, anyway -- is 'pack'.)  Again, perhaps you're 
saying this because you think the identifier changes with 
re-advertisement?  Not so.

>irrelevant (should be easy, but..).

I'll defer to Enke for the real answer, but I think you've got it in 
the paragraph above.

>Why do none of these concerns apply to add-path and unstable IDs?

Because the "should be easy" paragraph is effectively something any 
existing BGP implementation already does.  And because it only 
applies in the case of outright withdraws, not replacement by 
different next hop.  Indeed, the replacement by different next hop 
case could be termed an "unstable identifier" (in the second sense I 
defined above).

>1. To Multiple-Hop, but which state actually does not need to be kept

This footnote seems to be a non-sequitur?

--John

---

From: Paul Jakma <[email-masked]>
Date: Fri, 25 Aug 2006 02:06:42 +0100 (IST)

On Thu, 24 Aug 2006, John G. Scudder wrote:

> Unstable?  Not sure what you mean by that -- perhaps that the path 
> ID isn't (necessarily) derived from anything in the path,

Yes, that is what I meant.

> remains the same for the life of the route (though should the peer 
> withdraw and then later re-advertise the route, it'd change).

Right.

> I don't understand why you should say so.  (N.b. a more familiar 
> term than 'bunch' -- to me, anyway -- is 'pack'.)

I'll use that term so. :)

> Again, perhaps you're saying this because you think the identifier 
> changes with re-advertisement?  Not so.

Unless it had been withdrawn before.

> case could be termed an "unstable identifier" (in the second sense 
> I defined above).

Sure, but if the next-hop "changes" it is really a different path (in 
that plane anyway). It's fundamental to the concept of a path surely?

To go back to add-path: If the path identity is to be temporal in 
nature, are we abandoning the concept of dampening[1] for BGP?

 	A
 	 \
 	  RS--B
 	 /
 	C

A and C advertise P to the Route-Server. A withdraws and updates P at 
intervals. B sees:

   UPDATE: feasible   P:1, nexthop A
   UPDATE: feasible   P:2, nexthop C
   UPDATE: unfeasible P:3
   UPDATE: feasible   P:4, nexthop C
   UPDATE: unfeasible P:5
   <etc>

The path identity of the flapping path keeps changing, so B can not 
damp it (unless it goes by the nexthop..).

Maybe dampening isn't relevant anymore today. What about BGP data 
collectors and analysers (RIS, etc..)?

To be honest: I'm as uncomfortable with constantly changing 
identities for paths as you are with using nexthop as the identity.

> This footnote seems to be a non-sequitur?

Oops, that was intended to apply to text about Enke's state/coupling 
comment.

1. Ok, this might be a good thing ;).

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
"All my life I wanted to be someone; I guess I should have been more specific."
-- Jane Wagner