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

From: "Manav Bhatia" <[email-masked]>
Date: Tue, 22 Aug 2006 18:46:12 +0530

Hi,

The revised edition of draft-bhatia-bgp-multiple-next-hops-01.txt addresses 
all of the concerns and suggestions that were given in the past IETFs and 
the mailing list and we believe its in a reasonable form to be progressed 
further in the WG.

The proposal is compatible with IPv6 support, MPLS label advertisement, and 
BGP multi-protocol support.

We would like to ask for the working group status for this document, so that 
the working group may determine what revisions it wishes to make.

Thanks,

Joel, Paul and Manav

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

---

From: "Glen Kent" <[email-masked]>
Date: Tue, 22 Aug 2006 21:51:25 +0530

I support this.

---

From: Tulip Rasputin <[email-masked]>
Date: Tue, 22 Aug 2006 13:09:47 -0700 (PDT)

Its got my vote as i think there is a lot that we can explore with this. For one, we have only been suggesting kludges to fix the MED oscillation problem and i think this is the first real attempt to actually fix the problem in the protocol itself. Then it helps in the classical case where the route reflector has to choose one best route from the available equally valid choices.
 
Best Regards,
 
Tulip

----- Original Message ----
From: Manav Bhatia <[email-masked]>
To: [email-masked]
Cc: [email-masked]; Yakov Rekhter <[email-masked]>; Joel M. Halpern <[email-masked]>; Paul Jakma <[email-masked]>
Sent: Tuesday, August 22, 2006 6:46:12 PM
Subject: [Idr] Progressing draft-bhatia-bgp-multiple-next-hops-01.txt

Hi,

Thanks,

Joel, Paul and Manav

---

From: Enke Chen <[email-masked]>
Date: Tue, 22 Aug 2006 14:17:21 -0700

Hi, Tulip:

Your statement "this is the first real attempt to actually fix the 
problem in the protocol itself" got me interested :-)

I am not sure if you are aware of the "add-path" draft 
(draft-walton-bgp-add-paths-05.txt) that proposes a protocol revision to 
advertise multiple paths in BGP. The protocol work in the draft was 
completed years ago. IMO the add-path proposal is more flexible, and has 
few changes to BGP and how it is operates.

-- Enke

---

From: Enke Chen <[email-masked]>
Date: Tue, 22 Aug 2006 17:56:52 -0700

Hi, Manav:

Manav Bhatia wrote:

> Hi Enke,
>
>> (draft-walton-bgp-add-paths-05.txt) that proposes a protocol revision 
>> to advertise multiple paths in BGP. The protocol work in the draft 
>> was completed years ago.
>> IMO the add-path proposal is more flexible, and has few changes to 
>> BGP and how it is operates.
>
>
> I would be interested in knowing as to what makes you think that this 
> proposal is any less flexible?

The add-path draft introduces a path identifier so that a path from a 
neighbor can be identified by (prefix, path identifier), and the 
implicit replacement/withdraw behavior (and thus the update efficiency) 
in BGP is maintained. The path identifier can be a neighbor-AS, or a 
router-id, or an opaque number suitable for a particular application.

It is not clear to me how the implicit replacement/withdraw can be 
achieved with your proposal.

-- Enke

>
> Manav
>
>>
>> -- Enke
>>
>> Tulip Rasputin wrote:
>>
>>> Its got my vote as i think there is a lot that we can explore with 
>>> this. For one, we have only been suggesting kludges to fix the MED 
>>> oscillation problem and i think this is the first real attempt to 
>>> actually fix the problem in the protocol itself. Then it helps in 
>>> the classical case where the route reflector has to choose one best 
>>> route from the available equally valid choices.
>>> Best Regards,
>>> Tulip
>>>
>>> Cc: [email-masked]; Yakov Rekhter <[email-masked]>; Joel M. 
>>> Halpern <[email-masked]>; Paul Jakma <[email-masked]>
>>> The revised edition of draft-bhatia-bgp-multiple-next-hops-01.txt 
>>> addresses all of the concerns and suggestions that were given in the 
>>> past IETFs and the mailing list and we believe its in a reasonable 
>>> form to be progressed further in the WG.
>>>
>>> The proposal is compatible with IPv6 support, MPLS label 
>>> advertisement, and BGP multi-protocol support.
>>>
>>>
>>> We would like to ask for the working group status for this document, 
>>> so that the working group may determine what revisions it wishes to 
>>> make.
>>>
>>> Thanks,
>>>
>>> Joel, Paul and Manav
>>>
>>>
>>>

---

From: "Manav Bhatia" <[email-masked]>
Date: Wed, 23 Aug 2006 06:34:29 +0530

Hi Enke,

> neighbor can be identified by (prefix, path identifier), and the implicit 
> replacement/withdraw behavior (and thus the update efficiency) in BGP is 
> maintained. The path identifier can be a neighbor-AS, or a router-id, or 
> an opaque number suitable for a particular application.
>

Simple. You look at the prefix and the nexthop to perform implicit withdraw 
as this tuple would always be uniquely learnt from each BGP speaker.

Manav

---

From: Mach Chen <[email-masked]>
Date: Wed, 23 Aug 2006 10:18:21 +0800

Hi, Manav

Please see inline.

> as this tuple would always be uniquely learnt from each BGP speaker.

So, how  to carry the nexthop attribute , using MULTIPLE_HOP attribute or any other attribute?

Could tell me the detailed procedure about implicit replacement/withdraw ?

Your decription in section 3.5 is too simple, I also have same doubt as Enke Chen.

Thanks,

Mach

---

From: "Manav Bhatia" <[email-masked]>
Date: Wed, 23 Aug 2006 08:09:51 +0530

Hi Mach,

> So, how  to carry the nexthop attribute , using MULTIPLE_HOP attribute or
^^^^^^^^^^^^^^^^^^
I am sorry I could not parse this.

> Could tell me the detailed procedure about implicit replacement/withdraw ?

Try section 3.2

3.2 Withdrawal Procedures

   An UPDATE message which contains an IP address prefix in the
   WITHDRAWN ROUTES marks all the associated routes as being no longer
   available for use.

   An UPDATE message consisting of an IP address prefix in the NLRI
   field and only the NEXT_HOP attribute implicitly withdraws all the
   routes to that address prefix and replaces it with the one advertised
   by the NEXT_HOP.

   An UPDATE message which contains an IP address prefix in the
   WITHDRAWN ROUTES and the MULTIPLE_HOP attribute only removes the path
   associated with that next-hop.

   An UPDATE message announced with a MULTIPLE_HOP attribute for a given
   IP address prefix implicitly withdraws any previous route announced
   with the same next-hop.

> Your decription in section 3.5 is too simple, I also have same doubt as

Let us know if its still unclear. We should be able to explain it to you
with an aid of an example.

Cheers,
Manav

---

From: Paul Jakma <[email-masked]>
Date: Wed, 23 Aug 2006 03:57:38 +0100 (IST)

Hi Enke,

On Tue, 22 Aug 2006, Enke Chen wrote:

> (draft-walton-bgp-add-paths-05.txt) that proposes a protocol 
> revision to advertise multiple paths in BGP.

FWIW this draft is a respin of 
draft-bhatia-ecmp-routes-in-bgp-00.txt, but sans detailed 
consideration of ECMP (which can build upon it).

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
Nothing will dispel enthusiasm like a small admission fee.
 		-- Kim Hubbard

---

From: Mach Chen <[email-masked]>
Date: Wed, 23 Aug 2006 11:21:29 +0800

Hi manav,

Please see below inline
----- Original Message ----- 
From: "Manav Bhatia" <[email-masked]>
To: "Mach Chen" <[email-masked]>
Cc: <[email-masked]>
Sent: Wednesday, August 23, 2006 10:39 AM
Subject: Re: [Idr] Progressing draft-bhatia-bgp-multiple-next-hops-01.txt

>> So, how  to carry the nexthop attribute , using MULTIPLE_HOP attribute or

OK,but I want to know how to perform implicitly withdraw when partial nexthop attribute changed.

---

From: "Manav Bhatia" <[email-masked]>
Date: Wed, 23 Aug 2006 06:14:14 +0530

Hi Enke,

> completed years ago.
> IMO the add-path proposal is more flexible, and has few changes to BGP and 
> how it is operates.

Manav

>
> -- Enke
>
> Tulip Rasputin wrote:
>
>>Its got my vote as i think there is a lot that we can explore with this. 
>>For one, we have only been suggesting kludges to fix the MED oscillation 
>>problem and i think this is the first real attempt to actually fix the 
>>problem in the protocol itself. Then it helps in the classical case where 
>>the route reflector has to choose one best route from the available 
>>equally valid choices.
>> Best Regards,
>> Tulip
>>
>>Cc: [email-masked]; Yakov Rekhter <[email-masked]>; Joel M. Halpern 
>><[email-masked]>; Paul Jakma <[email-masked]>
>>addresses all of the concerns and suggestions that were given in the past 
>>IETFs and the mailing list and we believe its in a reasonable form to be 
>>progressed further in the WG.
>>
>>The proposal is compatible with IPv6 support, MPLS label advertisement, 
>>and BGP multi-protocol support.
>>
>>
>>We would like to ask for the working group status for this document, so 
>>that the working group may determine what revisions it wishes to make.
>>
>>Thanks,
>>
>>Joel, Paul and Manav
>>
>>
>>

---

From: Enke Chen <[email-masked]>
Date: Wed, 23 Aug 2006 00:45:39 -0700

Hi, Manav:

Manav Bhatia wrote:

>> implicit replacement/withdraw behavior (and thus the update 
>> efficiency) in BGP is maintained. The path identifier can be a 
>> neighbor-AS, or a router-id, or an opaque number suitable for a 
>> particular application.
>>
> Simple. You look at the prefix and the nexthop to perform implicit 
> withdraw as this tuple would always be uniquely learnt from each BGP 
> speaker.

Sorry I do not follow you, and I went back to your draft and got more 
confused. As you stated here, as well as in the draft,  a path  is 
identified by  (prefix , nexthop-address) in your proposal.  Then how 
can a path identified by (prefix, neighbor-As), or (prefix, router-id), 
or (prefix, opaque-number) be implicitly replaced/withdrawn by a 
mechanism that identifies a path by (prefix, nexthop-address)?

Regarding the need for identifying a path by (prefix, neighbor_AS) or 
(prefix, route-id),  I am not sure if you have read the companion draft 
of add-path (draft-walton-bgp-route-oscillation-stop-01.txt), which has 
expired unfortunately, but is still readily available on the Internet, 
for example:

http://ietfreport.isoc.org/idref/draft-walton-bgp-route-oscillation-stop-01.txt 

Two approaches are presented in the draft to address the ibgp route 
oscillation:

     1) advertise the available paths (equivalent to full ibgp mesh): in 
this case a path is identified by (prefix, router-id).
     2) advertise the (neighboring-AS based) group bestpaths: in this 
case a path is identified by (prefix, neighboring-AS).

They have different scaling properties, and a provider may choose to 
deploy one or another. In both cases, however, the nexthop addresses of 
the multiple paths being advertised would most likely be different.

Since we are comparing the drafts, I think it is fair to ask this question:

    As the add-path draft has existed for a long time, and the spec is 
pretty simple, complete, fairly elegant (sure, relatively), I am 
wondering if you have spotted certain issues with it that can not be 
fixed, or if the solution proposed failed to address a particular 
problem that requires multiple paths?

-- Enke

---

From: Enke Chen <[email-masked]>
Date: Wed, 23 Aug 2006 00:50:09 -0700

Had a cut-n-paste error. Here is a correct pointer to the add-path 
application draft:

http://ietfreport.isoc.org/all-ids/draft-walton-bgp-route-oscillation-stop-01.txt

-- Enke

Enke Chen wrote:

> Hi, Manav:
>
> Manav Bhatia wrote:
>
>> Hi Enke,
>>
>>>
>>> The add-path draft introduces a path identifier so that a path from 
>>> a neighbor can be identified by (prefix, path identifier), and the 
> can a path identified by (prefix, neighbor-As), or (prefix, 
> router-id), or (prefix, opaque-number) be implicitly 
> replaced/withdrawn by a mechanism that identifies a path by (prefix, 
> nexthop-address)?
>
> (prefix, route-id),  I am not sure if you have read the companion 
> draft of add-path (draft-walton-bgp-route-oscillation-stop-01.txt), 
> which has expired unfortunately, but is still readily available on the 
> Internet, for example:
>
>        
>     1) advertise the available paths (equivalent to full ibgp mesh): 
> in this case a path is identified by (prefix, router-id).
> deploy one or another. In both cases, however, the nexthop addresses 
> of the multiple paths being advertised would most likely be different.
>

---

From: "Manav Bhatia" <[email-masked]>
Date: Wed, 23 Aug 2006 13:38:54 +0530

Hi Mach,

>partial nexthop attribute changed.

Assume A has 3 routes to X (with next-hops N1, N2 and N3) that it wants to
announce to B.
 
A does this by sending the following UPDATE messages to B:

UPDATE: feasible nlri X, next_hop N1, <other attributes>
UPDATE: feasible nlri X, multiple_hop N2, <other attributes>
UPDATE: feasible nlri X, multiple_hop N3, <other attributes>

Case I:

Some path attributes change for the route associated with next-hop N2 and it
wants to replace the new route with the earlier announcement.

A sends the following UPDATE message:

UPDATE: feasible nlri X, multiple_hop N2, <new attributes>

B upon receiving this message searches its RIB for the route associated with
the tuple <X, N2>. If it doesn't find a route, then it appends this in its
RIB. In this case, it finds the route that it had received earlier from A
and considers this as an implicit withdrawal.

Case II:

A wants to selectively remove the route associated with the next_hop N2.

A sends the following UPDATE message:

UPDATE: unfeasible nlri X, multiple_next_hop N2

Hope this helps.

Manav

---

From: "Joel M. Halpern" <[email-masked]>
Date: Wed, 23 Aug 2006 07:58:02 -0400

Enke, I have real trouble with your characterization of your draft.
You claim it is simple and elegant.
 From where I sit, it introduces a new identifier that must be shared 
between the routers.  That identifier has to be assigned and managed 
by the advertising router in such a way that it is unique for each 
path that needs advertised (under all possible circumstances).  But 
it has to be used by the receiver no matter how the sender has chosen 
to allocate / create it.  As such, if the two happen to have the same 
implementation view they may find it simple.  But it is quite 
dependent upon that implementation.
While our draft makes use of information that was already being 
exchanged to provide the necessary disambiguation.  I would argue 
that such is in fact both simpler and more elegant.

At the same time, your claim of greater flexibility is in fact not 
backed up by need.  We previously had support for advertising paths 
with different attributes but the same NLRI and the same 
next-hop.  In discussion with folks we realized that there was no 
actual use case where you need the differentiation.  Either the 
advertiser is in the path (next-hop self) in which case preserving 
the paths does not add information, even for the route oscillation 
case, or the advertiser is preserving the next-hop information in 
which case the next hops provide the needed differentiation.  Thus, 
using the next-hop as an added differentiator provides exactly the 
flexibility needed by the problem, and is much simpler, more amenable 
to variations in implementations strategies, and more robust.

Yours,
Joel M. Halpern

At 03:45 AM 8/23/2006, Enke Chen wrote:
>Hi, Manav:
>
>Manav Bhatia wrote:
>
>>Hi Enke,
>>
>>>
>>>The add-path draft introduces a path identifier so that a path 
>>>from a neighbor can be identified by (prefix, path identifier), 
>>>and the implicit replacement/withdraw behavior (and thus the 
>>>update efficiency) in BGP is maintained. The path identifier can 
>>>be a neighbor-AS, or a router-id, or an opaque number suitable for 
>>>a particular application.
>>>
>>withdraw as this tuple would always be uniquely learnt from each BGP speaker.
>
>
>Sorry I do not follow you, and I went back to your draft and got 
>more confused. As you stated here, as well as in the draft,  a 
>path  is identified by  (prefix , nexthop-address) in your 
>proposal.  Then how can a path identified by (prefix, neighbor-As), 
>or (prefix, router-id), or (prefix, opaque-number) be implicitly 
>Regarding the need for identifying a path by (prefix, neighbor_AS) 
>or (prefix, route-id),  I am not sure if you have read the companion 
>which has expired unfortunately, but is still readily available on 
>the Internet, for example:
>
>
>     1) advertise the available paths (equivalent to full ibgp 
> mesh): in this case a path is identified by (prefix, router-id).
>     2) advertise the (neighboring-AS based) group bestpaths: in 
> this case a path is identified by (prefix, neighboring-AS).
>
>    As the add-path draft has existed for a long time, and the spec 
> is pretty simple, complete, fairly elegant (sure, relatively), I am 
> wondering if you have spotted certain issues with it that can not 
> be fixed, or if the solution proposed failed to address a 
> particular problem that requires multiple paths?
>
>-- Enke
>
>
>

---

From: Paul Jakma <[email-masked]>
Date: Wed, 23 Aug 2006 15:01:16 +0100 (IST)

Hi Enke,

> neighbor-AS, or a router-id, or an opaque number suitable for a 

We[1] considered that approach very carefully. It was not clear at 
all to us what this identifier should be from the draft.

The simple approach, it seemed to us, would be to derive the 
Add-Path-ID in some way from the identity of the speaker the path was 
learnt from. This approach would work fine for 
route-reflectors/servers, where only a single central speaker is 
propogating additional paths.

Such simple choice of Add-Path-ID does not though, as far as we can 
tell, work for propogating multiple paths further than that (e.g. 
between two RR or RSes, or in potential future ECMP applications).

The next-hop of a path though would work. The combination of 
(NLRI,next-hop) serves as a natural extension of path-identity 
between any two speakers, we feel; reasonably stable, can be 
determined without reference to other paths for the NRLI, etc..

If the next-hop is a suitable additional identifier, then there is no 
need to encode it seperately (as add-path does). A list of next-hops 
would suffice (as it does for the NLRI). This also allows 
announcements which differ only by (NLRI,next-hop) to be bunched 
together into one UPDATE, where the add-path approach must send an 
UPDATE with full path-attributes per NRLI:Add-Path-ID.

It does mean that if the next-hop of a path changes either the 
(NRLI,next-hop) must be withdrawn and re-announced (with all 
attributes) again (two UPDATEs), or all (NLRI,nexthop)'s must be 
implicitely withdrawn+reannounced in full (would be better, but only 
if it can be done in one UPDATE). This could be avoided by adding 
some more state with each nexthop to allow implicit withdrawals of 
specific (NLRI,nexthop) tuples, but we felt this would be optimising 
for an uncommon case at the expense of the common case and 
complexity.

In summary:

- The fundamental difference is that Add-Path appears to leave the
   identifier as a local issue (an operational one even?), where the
   draft of this subject explicitely uses the next-hop.

- We think next-hop is the only determinable additional
   path-identifier, and we see only problems in leaving the
   determination of this additional identifier as a local issue.

The remaining differences are not fundamental, but consequential of 
mechanism (seperate path-id versus "list of nexthops" approach):

- Add-path can implicitely withdraw+update a path, but can not bunch
   paths which differ only by next-hop into one UPDATE.

- multiple-nexthop can implicitely withdraw all paths for an NLRI, it
   can implicitely withdraw a (NLRI,nexthop) as long as the nexthop
   remains the same.

   However, it can not implicitely withdraw a (NRLI,nexthop) if the
   nexthop changes. An explicit withdraw of the (NLRI,nexthop) and
   reannouncement of that particular path would be the common case.

   Note that as these are considered different paths (different
   (NLRI,nexthop) tuples), one can /first/ announce the updated
   (NLRI,nexthop) /before/ withdrawing the old (NLRI,nexthop).

> It is not clear to me how the implicit replacement/withdraw can be achieved 
> with your proposal.

Presence or absence of NEXT_HOP signals whether outstanding 
announcements of the path are withdrawn or not.

Additionally, next-hops can be individually withdrawn by an UPDATE 
with only unfeasible NRLIs (traditional or MP_UNREACH) and the 
MULTIPLE_NEXT_HOP attribute. I.e.:

- UPDATE with NEXT_HOP:
   -> implicit withdrawal of all paths for the NLRI
   -> one or more paths announced for:
      - (NRLI,NEXT_HOP)
      - expansion of (NLRI,<list in MULTIPLE_NEXT_HOP>)

- feasible routes without NEXT_HOP:
   -> no general implicit withdrawal
   -> additional paths for (NLRI,<list in MULTIPLE_NEXT_HOP>)
   -> implicit withdrawal for specific (NLRI,nexthop)

- unfeasible routes with only the MULTIPLE_NEXT_HOP attribute:
   -> withdrawal of paths in expansion of (NLRI,<list in MULTIPLE_NEXT_HOP>)

1. Hopefully if I misrepresent the other authors they will correct me.

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
Farnsworth: Oh my God!!
Fry: What is it?
Farnsworth: It's..It's...It's my new pager!

---

From: Robert Raszuk <[email-masked]>
Date: Wed, 23 Aug 2006 07:13:11 -0700

Joel, Paul

I am looking at the version -01 and can't find any encoding how are you
proposing to send multiple vpnv4/v6 paths each with different next hop
and a different VPN labels.

Can you clarify ?

And operationally this is common request for SPs providing same RD
across VPN type of configurations or in few scenarios of inter-as
topologies.

Cheers,
R.

> between the routers.  That identifier has to be assigned and managed by
> the advertising router in such a way that it is unique for each path
> that needs advertised (under all possible circumstances).  But it has to
> be used by the receiver no matter how the sender has chosen to allocate
> / create it.  As such, if the two happen to have the same implementation
> view they may find it simple.  But it is quite dependent upon that
> implementation.
> exchanged to provide the necessary disambiguation.  I would argue that
> such is in fact both simpler and more elegant.
> 
> backed up by need.  We previously had support for advertising paths with
> different attributes but the same NLRI and the same next-hop.  In
> discussion with folks we realized that there was no actual use case
> where you need the differentiation.  Either the advertiser is in the
> path (next-hop self) in which case preserving the paths does not add
> information, even for the route oscillation case, or the advertiser is
> preserving the next-hop information in which case the next hops provide
> the needed differentiation.  Thus, using the next-hop as an added
> differentiator provides exactly the flexibility needed by the problem,
> and is much simpler, more amenable to variations in implementations
> strategies, and more robust.
> 
> Yours,
> Joel M. Halpern
>

---

From: Paul Jakma <[email-masked]>
Date: Wed, 23 Aug 2006 15:51:26 +0100 (IST)

> and a different VPN labels.

The label is encoded with the NLRI according to RFC3107. This draft 
extends the identity of a path to:

 	(NLRI, next-hop)

That the NLRI can be decomposed to (prefix,label) is of no interest, 
it is an opaque identity as far as this draft is concerned.

So for say:

 	( (P, label1), N1)
 	( (P, label2), N2)
 	.
 	.
 	( (P, labeln), Nn)

would be advertised as:

UPDATE:
   feasible NLRI: (P,label1),
   NEXT_HOP: N1
   <other attributes>
UPDATE:
   feasible NLRI: (P,label2),
   MULTIPLE_NEXT_HOP: N2
   <other attributes>
.
.
UPDATE:
   feasible NLRI: (P,labeln),
   MULTIPLE_NEXT_HOP: Nn
   <other attributes>

If <other attributes> are identical, this draft can not though bunch 
the UPDATEs together (it would be ambigious which nexthops were 
associated with which NLRI obviously).

A seperate UPDATE is needed for each distinct NLRI.

NB: Read "NEXT_HOP or next-hop from MP_REACH_NLRI, whichever is
     appropriate" for any use of NEXT_HOP. I.e. I refer to the logical
     next-hop, be it from the traditional NEXT_HOP or from MP
     extensions.

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
No man is useless who has a friend, and if we are loved we are indispensable.
 		-- Robert Louis Stevenson

---

From: Robert Raszuk <[email-masked]>
Date: Wed, 23 Aug 2006 08:42:59 -0700

Paul,

I am not talking about RFC3107 but RFC4364. Yes in both the label is
encoded in the NLRI, but meaning of the VPN label can not be decoupled
from the next hop information who advertised it.

If you send as you propose in separate updates this is implicit withdraw
in most implementations I am aware so I don't see the multipath in action.

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. Moreover I don't think it is flexible
enough to offer requested functionality for new AFI/SAFIs coming soon.
In many cases of new SAFIs next hop is irrelevant what matters is NLRI +
neighbor for example.

IMHO this is premature to accept this as WG document.

Cheers,
R.

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.

> That the NLRI can be decomposed to (prefix,label) is of no interest, it
> is an opaque identity as far as this draft is concerned.
> 
> So for say:
> 
>     ( (P, label1), N1)
>     ( (P, label2), N2)
>     .
>     .
>     ( (P, labeln), Nn)
> 
> would be advertised as:
> 
> UPDATE:
> If <other attributes> are identical, this draft can not though bunch the
> UPDATEs together (it would be ambigious which nexthops were associated
> with which NLRI obviously).
>

---

From: Paul Jakma <[email-masked]>
Date: Wed, 23 Aug 2006 17:26:16 +0100 (IST)

On Wed, 23 Aug 2006, Jeffrey Haas wrote:

> If I might ask the authors, is this a fair summary of the mechanism?

Almost: The implicit withdrawal is dependent on presence or absence 
of the existing next-hop attribute (NEXT_HOP or MP_REACH_NLRI as 
appropriate), not on the new attribute.

Implicit withdrawal is unchanged from normal BGP if the normal 
NEXT_HOP/MP_REACH_NLRI next-hop is present.

The Multiple-nexthop attribute is essentially additive to existing 
paths for the NLRI, for UPDATES with feasible routes.

Multiple-nexthop acts as a selector for withdrawal for an UPDATE with 
only unfeasible routes and that attribute.

> 1. When the multiple nexthop attribute is present, it suppresses
>   the normal implicit withdrawal behavior of BGP.

1. When the normal nexthop attribute (NEXT_HOP or MP_REACH_NLRI) is
    present, normal implicit withdrawal behavior of BGP remains -
    all prior announcements of paths for the NLRI are implicitely
    withdrawn.

    The UPDATE replaces all existing paths for the NLRI with the
    paths of identities (NLRI,next-hop) as given by the
    'normal' next-hop attribute and those nexthops in the
    MULTIPLE_NEXT_HOP, if that attribute is present.

    (with path attributes of each path equivalent to the remaining
     path attributes given in the UPDATE obviously)

> 2. When the multiple nexthop is absent, it implicitly withdraws all
>   previously advertised routes matching that prefix and replaces
>   it with the single route matching the advertised prefix.

2. When the normal nexthop (NEXT_HOP or MP equivalent) attribute is
    absent, presuming there are feasible routes, it suppresses the
    normal implicit withdrawal behavior of BGP.

    The paths with identity of (NLRI,next-hop), as given in the
    Multiple-Nexthop attribute are added to RIB.

    No implicit withdrawal of paths of the NLRI is needed, other than
    for any /specific/ (NLRI,nexthop) paths already received.

> 3. Similarly, if you're missing the multiple nexthop attribute, a withdraw
>   removes all routes matching that prefix.

Yep.

> 4. A withdraw with the multiple nexthop attribute withdraws only routes
>   matching those nexthops.

Yep.

> (Note that I consider 4 problematic.  That can be discussed later if
> my summary is correct.)

Please do.

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
Don't take life seriously, you'll never get out alive.

---

From: "Glen Kent" <[email-masked]>
Date: Wed, 23 Aug 2006 22:01:09 +0530

Robert,

How does your proposal solve the problem of carrying the new AFIs and
new SAFIs? When you do that would you also mind elucidating on what
new AFIs and SAFIs we're discussing here?

Are those proposals indiviudal submissions or have those been accepted
in the WG?

Glen

---

From: Robert Raszuk <[email-masked]>
Date: Wed, 23 Aug 2006 09:52:47 -0700

Glen,

> new SAFIs? 

It does by defining a new element Path Identifier (rather then using one
of the existing attributes to create a tuple) which may or may not be
needed in new SAFIs.

> When you do that would you also mind elucidating on what

While I gave the example of VPNv4 SAFI 128 what we are discussing is the
attempt to come with mechanism for sending multiple paths in MP-BGP
protocol in a simple and universal way for any AFI/SAFI combination.

Cheers,
R.

---

From: Jeffrey Haas <[email-masked]>
Date: Wed, 23 Aug 2006 13:24:16 -0400

On Wed, Aug 23, 2006 at 05:26:16PM +0100, Paul Jakma wrote:
> Almost: The [...]

Thanks for the summary.  My understanding wasn't off too much.

Here are my concerns with the mechanism at a meta level:

- By keying on NLRI, nexthop (rather than just NLRI), you are precluding
  the sending of multiple distinct paths that share the same nexthop.
  We'll likely want to be able to do this for ECMP.  Additionally,
  without the ability to do this, I believe we wont be able to suppress
  some of the MED oscillation scenarios.
- The mechanism doesn't give us a way to distinguish routes that are
  being sent to preclude oscillation, but may not be relevant to
  forwarding.  More generally, routes need to be marked as to whether
  they are being used for forwarding or not.
- The protocol mechanism has withdraws utilizing path attributes as
  part of their keying mechanism.  While this is intentional, it's very
  much out of character with BGP.  Primarily, this is because it preclude
  the mixing of simultaneous advertisement of feasible and unfeasible
  routes.

I would suggest that the application components of this draft be
split into a separate draft.  Mixing the applications with the
protocol descriptions makes it a bit more complicated than is warranted.

Interaction of speakers of this mechanism with non-speakers needs
to be documented, both within an AS (or confederation) and outside.
This means that the ecmp/aggregation case needs to be documented.

General note to the IDR community: We're spending a lot of time discussing
the protocol mechanisms of passing around additional routes.  I think
we'd benefit from more discussion of the implications of doing this
at a generic level before we start debating how to sling bits on the wire.
The complex AS_PATH aggregation for ecmp that was a previous topic
is a good example of the discussion I think we need.

-- Jeff

---

From: "Glen Kent" <[email-masked]>
Date: Wed, 23 Aug 2006 23:22:24 +0530

I think we need to disassociate the reason why a BGP speaker may want
to advertise multiple paths with how it can do so.

IMO this is a cause of some confusion.

We should treat this as only a mechanism for advertising multiple
paths (atleast this is how i was reading this all this time) and let
the other applications (ecmp, med oscillation, add your favorite
application here .. ) define how they want to use this extension.

For example, ecmp does not care how I advertise multiple paths to a
remote peer. What it should care for is the as_path that i construct
when i cross the ecmp capable domain to the non ecmp capable domain
covers all the AS numbers. Similarly med oscillation draft needs to do
it in its own way. I dont think these applications should really care
if the underlying mechanism to advertise multiple routes is through
multiple_hop or add-paths.

So, lets focus on just one thing here: Is the mechanism to advertise
multiple paths okay here?

some comments inline ..

>  We'll likely want to be able to do this for ECMP.  Additionally,

an RR cant set next-hop-self so it would never send paths with same
next-hop. You could send this in EBGP, but then for EBGP would you
really send separate individual path attributes?

> - The mechanism doesn't give us a way to distinguish routes that are
[].
> protocol descriptions makes it a bit more complicated than is warranted.

I agree to this.

> to be documented, both within an AS (or confederation) and outside.

Again, if this draft is only going to talk about how a speaker needs
to announce multiple paths then the only interaction with an uncapable
peer would be that of not advertising anything!

> This means that the ecmp/aggregation case needs to be documented.

This is application specific and should find place in some other document.

> the protocol mechanisms of passing around additional routes.  I think

Which is what the draft is all about.

> is a good example of the discussion I think we need.

Depends on which side you're on. I think a healthy discussion of how
we can advertise multiple paths is important and required before we
proceed on complex applications like ecmp ..

I vividly remember a draft on ecmp and its repurcussions by the same
authors. That could be a good starting point, if thats what you meant.

Glen.

---

From: Jeffrey Haas <[email-masked]>
Date: Wed, 23 Aug 2006 11:15:43 -0400

Manav,

I will admit to not having read this draft in detail enough to 
comment on whether your procedures are complete.  I've read
enough to believe that it looks like the proposed mechanism
is sufficient to add and delete multiple paths.  However, one
key mechanism that isn't obvious when skimming this draft is
how the active route (the path or paths actually being used)
of the advertising speaker is denoted from other paths.

Have I missed something?

-- Jeff

---

From: Jeffrey Haas <[email-masked]>
Date: Wed, 23 Aug 2006 14:11:50 -0400

Glen,

> to advertise multiple paths with how it can do so.

Agreed.

> multiple paths okay here?

I don't think so.  I've documented two reasons I think the mechanism
needs to address.

Catching up on this thread made me go read the add-paths document.
I think that mechanism is cleaner from a protocol standpoint.

> really send separate individual path attributes?

Consider the case of confederation's setting next-hop-self at a
confederation border.  It is used, although not commonly.

I also think precluding the mechanism between external bgp speakers
is excessive - from a protocol standpoint, not an application standpoint.

> peer would be that of not advertising anything!

Well, no.  If you have multiple paths and are using some subset
of those for forwarding, and that subset is > 1, what do you advertise
to a speaker that can't receive more than one path?

The answer to this question may be documented in an ecmp document.

The protocol mechanism must support noting which paths are used in forwarding.
(This is a concern in the add-paths document as well, IMO.)

> authors. That could be a good starting point, if thats what you meant.

Passing around more than one path, regardless of mechanism, fundamentally
changes a core component of BGP: route selection.  Documenting protocol
before behavior seems very much like putting the cart before the horse.
As a specific example, I've suggested we need to flag routes that are
used for forwarding.  If the consensus is that this is required,
do we put together yet another per-route-instance draft that covers
this or simply put it into the mechanism that distributes the multiple
routes?

-- Jeff

---

From: Jeffrey Haas <[email-masked]>
Date: Wed, 23 Aug 2006 11:56:32 -0400

Robert,

> in most implementations I am aware so I don't see the multipath in action.

I wont pretend to speak for the authors, nor speak for my preference
in the encodings in this draft.

However, the relevant bit of their draft:

   When advertising multiple paths which do not have identical path 
   attributes, separate BGP UPDATE messages MUST be sent, each with a 
   MULTIPLE_HOP attribute even if there is only one next-hop in each 
   MULTIPLE_HOP attribute. Presence of MULTIPLE_HOP suppresses route 
   replacement at the receiving end. 

-- Jeff

---

From: Paul Jakma <[email-masked]>
Date: Wed, 23 Aug 2006 22:12:33 +0100 (IST)

On Wed, 23 Aug 2006, Robert Raszuk wrote:

> I am not talking about RFC3107 but RFC4364.

Ah apologies.

Though, to the best of our knowledge, the approach in this draft 
works perfectly well with VPNv4. Why would it not?

> Yes in both the label is encoded in the NLRI, but meaning of the 
> VPN label can not be decoupled from the next hop information who 
> advertised it.

And the draft does not require it to be decoupled.

> If you send as you propose in separate updates this is implicit 
> withdraw in most implementations I am aware so I don't see the 
> multipath in action.

This is covered, see the sub-thread of Jeff's reply.

> address families already proposed in this WG. Moreover I don't 
> think it is flexible enough to offer requested functionality for 
> new AFI/SAFIs coming soon. In many cases of new SAFIs next hop is 
> irrelevant what matters is NLRI + neighbor for example.

Which would those be? If there is no notional equivalent to a 
next-hop, are these things even routes?

- If not, why try to bend non-routing information into UPDATE
   messages? Use a different BGP message more suited to the purpose..

   (I'm thinking particularly of some of the "Use BGP to exchange VPN
    /configuration/ information" proposals floated, I can't remember
    whether or not they wanted to use UPDATE).

- If yes, what kind of route does not have a notional 'target' (ie
   nexthop) for a destination?

E.g. "NLRI + neighbour" sounds like the VPN-config stuff, which 
(IMHO) isn't routing related at all, but

 	"Host + tunnel configuration information"

I'd much rather not see that kind of thing not be shoe-horned into 
routing UPDATEs, regardless of the draft of this subject. However, if 
it must be, then it's a simple matter to require the next-hop be 
filled in with nexthop self.

Also: I'd question why you'd need to advertise VPN configuration 
information for a given host multiple times. If it has no equivalent 
to next-hop, it likely has no use for multiple-advertisements.

> identifier to be generated by BGP speaker is not IMHO at all a problem.

The draft should perhaps say how.

We are reasonably certain there are issues with all but simple 
reflector cases - any case where one wishes multiple paths to be 
/readvertised/ can not use identifiers derived from the identity of 
from whom the route was learnt (e.g. router-ID). So the speaker is 
left to construct some identifier specific to the peer the speaker is 
sending the path to, for that path.

Which seems redundant to us as such an identifier already exists in 
all the BGP AFI/SAFIs we have considered -> the nexthop.

NB: As with all my replies in this thread, I am to a great extent
     paraphrasing things Joel and Manav pointed out to me in private
     discussions. Mistakes are my own though. ;)

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
Help a swallow land at Capistrano.

---

From: "Joel M. Halpern" <[email-masked]>
Date: Wed, 23 Aug 2006 17:14:59 -0400

We probably do need to fold the path compression description (what 
you do when using multiple paths and talking to a peer who does not 
speak this extension.)  We wanted to get the base description out, 
and we wanted to confirm that the working group actually wanted the 
description in the draft (since that was confusing to some people.)

With regard to the case where paths differ on something other than 
NLRI or next-hop, I could not construct a case where there was a need 
to advertise them.  All the cases I have seen for the oscillation 
also have differing next-hops.  I had originally wanted to support 
broader variation, but realized that any time you are advertising 
multiple paths with the same next hop, you might as well compress 
them before advertising, rather than after.

As to using the next-hop for advertisement identification, something 
has to identify the advertisement.  After all, even if you do not 
have any implicit withdrawls, there has to be some way to explicitly 
withdraw the individual routes.

Yours,
Joel M. Halpern

---

From: "Joel M. Halpern" <[email-masked]>
Date: Wed, 23 Aug 2006 17:18:42 -0400

When the multiple next hops attribute is used, the advertisement is 
not an implicit withdrawl of anything other than an advertisement for 
the same NLRI / Next-Hop pair.

RFC4364 makes use of RFC 3107.
RFC 3107 defines that the label is part of the NLRI.
Therefore, frankly, in most cases, neither our draft nor add-path is 
needed.  The different next hops will typically use different labels.
However, as defined, if two next hops happen to use the same label 
for the same prefix within a VPN, a reflector would have to choose 
one. By using our extension, the reflector can advertise both routes 
(next hops with NLRI and label) even when the NLRI and label match 
within the VPN.  (Obviously, for different VPNs there is no problem 
as different RDs induce separation in BGP anyway.

Our proposal works for any address family that advertises NLRI and 
meaningful next-hops.
What hypothetical address family do you believe has problems?

Yours,
Joel M. Halpern

---

From: "Joel M. Halpern" <[email-masked]>
Date: Wed, 23 Aug 2006 17:40:53 -0400

You are asking about whether the receiver can tell whether the 
advertised paths are usable.
given that paths must differ either on NLRI or Next-Hop, receiving an 
advertisement means that the indicated next hop is providing that 
advertised next hop (and is pro forma presumed to be using it if you 
send packets to that next-hop.)

In earlier versions, where theoretically paths could share next hop 
and NLRI, while differing on other attributes, there was indeed a 
problem of knowing whether a received advertisement was usable.

Yours,
Joel

At 11:15 AM 8/23/2006, Jeffrey Haas wrote:
> addresses

---

From: Paul Jakma <[email-masked]>
Date: Wed, 23 Aug 2006 23:46:39 +0100 (IST)

Hi Jeffrey,

> Thanks for the summary.  My understanding wasn't off too much.

Indeed.

Also note that the mechanism is fairly arbitrary. There are a number 
of variations possible, with different tradeoffs (e.g. we considered 
explicitely encoding whether a next-hop was to be withdrawn or not, 
but decided against).

The fundamental question here, as per previous email to Enke, is of 
path identity and whether next-hop (or notionally equivalent "route 
target" in the abstract) is intrinsic to routes, because if so it 
makes an excellent identifier for this purpose.

Obviously we believe it to be so.

>  the sending of multiple distinct paths that share the same nexthop.

Yes.

We argued privately about this but could not come up with any 
plausible case where one would need to advertise multiple paths for 
an NLRI with the same next-hop, in practice or conceptually.

>  We'll likely want to be able to do this for ECMP.

Well, bear in mind the draft started life as Manav's ECMP draft. :)

The draft now no longer explores ECMP, that's something to be covered 
in an additional draft if desired, but we obviously feel ECMP can 
build on top of this.

>  Additionally, without the ability to do this, I believe we wont be
>  able to suppress some of the MED oscillation scenarios.

Hmm, can you explain further? That's been considered - see the 
appendices in the draft.

>  they are being used for forwarding or not.

This isn't an issue. Only useable paths can be advertised. See Joel's 
reply.

>  the mixing of simultaneous advertisement of feasible and unfeasible

Yes. That's a limitation of UPDATE really. It's in keeping with 
the MP extensions though.

Though, several other RFCs and drafts already modify UPDATE, so.. But 
it just seems terribly bad form (to me anyway, I can't speak for 
other authors) to redefine established formats.

UPDATEv2 one day will clean all this up, one wishes at least.

> protocol descriptions makes it a bit more complicated than is 

Yes.

> is a good example of the discussion I think we need.

Yes. But that's not needed right now for this draft. :) There are 
uses besides ECMP (IX route-servers, iBGP reflectors).

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
USENET would be a better laboratory is there were more labor and less oratory.
 		-- Elizabeth Haley

---

From: "Manav Bhatia" <[email-masked]>
Date: Thu, 24 Aug 2006 06:28:48 +0530

Robert,

> from the next hop information who advertised it.

This has already been addressed here.

http://www1.ietf.org/mail-archive/web/idr/current/msg01906.html

I dont see any problem in advertsing multiple VPNv4 routes.

The first route is advertised using normal MP_REACH_NLRI. The second is 
advertised in the following manner:

MP_REACH_NLRI that encodes X:

afi = x1
safi = VPVv4
length of next hop address = 0
reserved = 0
nlri = L2:RD:X

MULTIPLE_HOP is encoded as:

afi = x1
safi = VPVv4
number of nexthops = 1
length of nexthop = length of N2
network address = N2

> enough to offer requested functionality for new AFI/SAFIs coming soon.

Again, look at 
http://www1.ietf.org/mail-archive/web/idr/current/msg01906.html

For any given <AFI, SAFI> that is advertised using MP_REACH_NLRI one can 
advertise supplementary paths using MULTIPLE_HOP.

> In many cases of new SAFIs next hop is irrelevant what matters is NLRI +

See Paul's reply.

Cheers,
Manav

---

From: "Manav Bhatia" <[email-masked]>
Date: Thu, 24 Aug 2006 06:59:05 +0530

Jeff,

Indicating which subset of the multiple routes being advertised are actually 
being used in FIB is fairly easy in our approach. We had discussed this 
offline and we had introduced a flags field in MULTIPLE_HOP field, where one 
of the bits set would indicate that the route is actually being used in 
forwarding. The idea was shot down and we put text in our ecmp draft wherein 
if a BGP speaker uses multiple paths then it *has* to forward all of those 
to a ecmp-capable peer. And if its peered up with a non ecmp capable peer, 
then it has to advertise a single path with a synthetic AS_PATH. The idea is 
that if you are using multiple paths then you are doing ecmp.
I suggest you read draft-bhatia-ecmp-routes-in-bgp-02.txt for more details.

A simple addition of the following text would perhaps fix the issue that you 
have:

Between Multiple-Hop capable speakers, the MULTIPLE_HOP attribute MUST be 
used in addition to the existing NEXT_HOP/MP_REACH_NLRI in order to announce 
multiple next-hops for the destinations listed in the NLRI/MP_REACH_NLRI of 
the UPDATE message. If the speaker has installed one of the next-hops 
concerned in its FIB, then that particular next-hop MUST be listed in the 
NEXT_HOP/MP_REACH_NLRI attribute.

This is possible in our approach, but can *never* be done in add-paths btw.

However, we must also keep in mind that there are applications that require 
multiple BGP paths where none of them are actually installed in the FIB 
(eBGP IXes).

Cheers,
Manav

---

From: Enke Chen <[email-masked]>
Date: Wed, 23 Aug 2006 23:35:24 -0700

Hi, Joel:

Joel M. Halpern wrote:

> path that needs advertised (under all possible circumstances).  But it 
> has to be used by the receiver no matter how the sender has chosen to 
> allocate / create it.  As such, if the two happen to have the same 

I am not sure what you meant by  "same implementation view, and 
dependent upon a particular implementation".  In the add-path proposal, 
the advertiser is responsible for allocating  the identifier suitable 
for a particular application, and the receiver needs to use the (prefix, 
path-identifier) to identify a path to be replaced.  I believe that part 
is clear in the proposal, but if it is not, we'll need to make it clear.

> with different attributes but the same NLRI and the same next-hop.  In 
> preserving the next-hop information in which case the next hops 
> provide the needed differentiation.  Thus, using the next-hop as an 
> added differentiator provides exactly the flexibility needed by the 
> problem, and is much simpler, more amenable to variations in 
> implementations strategies, and more robust.

I keep hearing that (prefix, nexthop) as the key to identify a path, and 
here you also mentioned "using the next-hop as an added differentiator". 
For several applications I cited, (prefix, nexthop) is actually not the 
right one. Considering the case in which the route reflector would 
advertising all the routes (simulating full-mesh).  It is actually the 
(prefix, router-id) that would identify a path instead of the prefix itself.

As the issue of how to identify a path is so fundamental to a solution,  
I hope that it can be clarified before we dive into other details.

Regards,

-- Enke

---

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

Manav:

In your example it seems that a path is replaced by another path with an 
identical nexthop. Would that be a bit too restrictive?

In addition, it is desirable and typical in implementations to have the 
receiving processing de-coupled from the sending processing  (in order 
to keep less state).   It means that at the time of sending update the 
info (such as the nexthop) for the old path may no longer available.  I 
am not sure if your proposal requires an implementation to keep track of 
the nexthops advertised to a peer for the purpose of figuring out when 
to use the NEXTHOP attribute or the MULTI-NEXTHOP attribute.

Let us consider a specific example:

                         RR1  ---------------- RR2
                         /     \
                        /       \
                      B1      B2

in which RR1 and RR2 are route reflectors, and B1 and B2 are clients of 
RR1, and they do not use "next-hop-self". The router-id for B1 and B2 
are B1-ID, and B2-ID respectively. RR1 advertises all routes to RR2 
(emulating full mesh).

      Initially B1 advertise X with N1 as the nexthop to RR1, and later 
advertise X with N11 to RR1.
      Initially B2 advertise X with N2 to RR1, and later advertise X 
with N22 to RR1.

With the add-path proposal, RR1 would initially advertise (X, B1-ID) 
with N1, and (X, B2-ID) with N2, to RR2 using the router-id as the path 
identifier.  Later, RR1 would advertise (X, B1-ID) with N11, and (X, 
B2-ID) with N22 to RR2. Four updates are involved.

How does your proposal work with respect to the updates in this example?

-- Enke

Manav Bhatia wrote:

>Hi Mach,
>
>  
>
>>>  An UPDATE message announced with a MULTIPLE_HOP attribute 
>>>      
>>>
>>for a given
>>    
>>

---

From: "Manav Bhatia" <[email-masked]>
Date: Thu, 24 Aug 2006 13:43:10 +0530

Enke,

>Let us consider a specific example:

[ .. ]

>      Initially B2 advertise X with N2 to RR1, and later advertise X 

[ .. ]

>How does your proposal work with respect to the updates in 

RR1 would advertise the following UPDATEs to RR2.

UPDATE: feasible nlri X, next_hop N1, <other attributes>
UPDATE: feasible nlri X, multiple_hop N11, <other attributes>
UPDATE: feasible nlri X, multiple_hop N2, <other attributes>
UPDATE: feasible nlri X, multiple_hop N22, <other attributes>

>B2-ID) with N22 to RR2. Four updates are involved.

Same here.

If OTOH the different UPDATEs share the same path attributes, then the
announcements can be clubbed in a single UPDATE message. 

For eg., If B1 and B2 are redundantly connected to other BGP speakers then
its possible that the announcements share common path attributes. In that
case RR1 can announce the following UPDATE message to RR2.

UPDATE: feasible nlri X, next_hop N1, <other attributes>
UPDATE: feasible nlri X, multiple_hop N11, N2, N22 <other attributes>

Or in the best case, can be done with only one UPDATE message.

UPDATE: feasible nlri X, multiple_hop N1, N11, N2, N22 <other attributes>

Cheers,
Manav

---

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

Manav:

>UPDATE: feasible nlri X, multiple_hop N22, <other attributes>

Please note that B1 and B2 are clients and do not advertise 
multi-paths.  How do (X, N1) and (X, N2) got withdrawn on RR2 as they 
are no longer valid (replaced by B1 and B2), in other words how does RR2 
figure out (X, N11) is a replacement of (X, N1), and (X, N22) a 
replacement of (X, N2)?

-- Enke

---

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

Manav:

-- Enke

---

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

Enke,

>figure out (X, N11) is a replacement of (X, N1), and (X, N22) a 

UPDATE: unfeasible nlri X, multiple_hop N1
UPDATE: unfeasible nlri X, multiple_hop N2
UPDATE: feasible nlri X, multiple_hop N11, <other attributes>
UPDATE: feasible nlri X, multiple_hop N12, <other attributes>

I think we can each come up with a scenario where one scheme would be more
optimal and would involve lesser number of UPDATEs than the other.

Cheers,
Manav

---

From: "Joel M. Halpern" <[email-masked]>
Date: Thu, 24 Aug 2006 08:02:47 -0400

A route reflector does not insert itself into the data path.  Rather, 
it preserves the next-hop on all routes it receives.
Therefore, when a route reflector reflects all routes it receives, 
all the routes for a given NLRI have distinct next-hops.

So, in fact, the (NLRI, next-hop) pair does uniquely identify each 
advertisement generated by the route reflector.

Yours,
Joel M. Halpern

At 02:35 AM 8/24/2006, Enke Chen wrote:
>I keep hearing that (prefix, nexthop) as the key to identify a path, 
>and here you also mentioned "using the next-hop as an added 
>differentiator". For several applications I cited, (prefix, nexthop) 
>is actually not the right one. Considering the case in which the 
>route reflector would advertising all the routes (simulating 
>full-mesh).  It is actually the (prefix, router-id) that would 
>identify a path instead of the prefix itself.
>

---

From: Enke Chen <[email-masked]>
Date: Thu, 24 Aug 2006 09:35:09 -0700

Manav:

>UPDATE: feasible nlri X, multiple_hop N12, <other attributes>

Ok, so (X, N1) and (X, N2) have to be explicitly withdrawn in your 
scheme. That means more updates. Perhaps what is more challenging here 
is that RR1 must withdraw (X, N1) before advertising (X, N11). How do 
you guarantee the ordering in an imploementation?
 
     - maintain extra state to keep track of which nexthop address was 
advertised to which peer. This would mean more states and more memory, or

    -  hanging on the path (X, N1) replaced by (X, N11) until (X, N1) is 
explicitly withdraw from RR2? The means keeping both (X, N1) and (X, 
N11) which incurs more memory, and couples the Tx and Rx. What happens 
if (X, N111) is received before (X, N1) is withdrawn?   Do you keep (X, 
N111) and in order as well?  This can easily get out of hand.

Please see my previous comment on de-coupling Tx from Rx:

---------------------------------------------------------------------------
---------------------------------------------------------------------------

>optimal and would involve lesser number of UPDATEs than the other.

I strongly disagree because of these reasons:

    1) More updates are generated by your proposal due to the need for 
explicit withdraws as shown in the example.

    2) As a new attribute is introduced in your proposal, the efficiency 
of prefix packing will be lower, resulting in more updates.
        It's shown that the prefix packing efficiency has a huge impact 
on the performance of update processing  (both Tx and Rx).
I would welcome an example that shows otherwise.

-- Enke

---

From: Paul Jakma <[email-masked]>
Date: Thu, 24 Aug 2006 18:16:29 +0100 (IST)

Hi Enke,

On Wed, 23 Aug 2006, Enke Chen wrote:

> dependent upon a particular implementation". In the add-path 
> proposal, the advertiser is responsible for allocating the 
> identifier suitable for a particular application, and the receiver 
> needs to use the (prefix, path-identifier) to identify a path to be 
> replaced.  I believe that part is clear in the proposal, but if it 
> is not, we'll need to make it clear.

That the sender must pick the identifier is quite clear. It's also 
clear the draft leaves that as an implementation matter.

The problem, and Joel's point (I think), is that in not giving any 
guidance on how this identifier is to be picked, implementations will 
settle on picking this identifier in a deficient way. E.g. 
particularly as the draft suggests that router-ID is one possible 
choice of such identifier (and indeed you suggest same the below).

Such a choice would not work for re-advertising multiple paths, e.g. 
a cluster of route-reflectors:

 	RR1-RR2
        / |   |
       A  B   C

Say A, B and C all advertise a certain NLRI, P.

RR1 and RR2 use add-path with their clients and between themselves so 
as to allow all paths to be distributed to all RR-clients. Both the 
RR implementations go for the simple approach (as suggested in the 
draft and your email) of using the router-ID of the speaker a path 
was received from as the Add-Path-ID. So RR1 sends to RR2:

 	UPDATE: feasible P:A, <attributes>
 	UPDATE: feasible P:B, <attributes>

Where X:Y is: add-path NLRI for Prefix X and add-path-id of Y.

Now, how should RR2 advertise these to its clients?

It clearly can not blindly just use the Router-ID of the speaker it 
received the paths from (RR1 in both cases).

It could however just reuse the path-ids. So the RR's add-path 
implementation now becomes (wrt choosing Add-Path-ID):

 	"If the received path already has a path-ID, and no other
          received paths have the same, just re-use that path-id.

          Otherwise, use the Router-ID of speaker the path was
          received from"

So now RR2 /can/ easily advertise the two paths received from RR1 to 
C and D.

However, our friendly BGP network administrator now figures out he 
really ought to have clients peer with both RRs, he does so for B 
(e.g. A and C's sessions to other RR may be broken for some reason):

 	RR1-RR2
        /  |/ |
       A   B  C

RR2 now has recieved:

>From RR1:

 	P:A
 	P:B

>From B:

 	P

What should it advertise to C?

The choices seem to be:

- Figure out that P and P:B are the exact same path (e.g. they'll
   have the exact same next-hop..), and advertise just P:B to C.

   - remember, that RR1 used 'B' as the path-ID is wholly at the
     discretion of RR1

   - the nexthop however...

or

- Advertise both P:B and P:B' to C

   - where B' is some constructed identifier for the path
     for P received from B

It seems to us that behaviour of the add-path draft with RR clusters 
may be quite indeterminable, given that the issue of the additional 
path-identifier is left completely at the discretion of speakers.

One could say "Ah, but ORIGINATOR_ID can be used!", but that's a 
route-reflection specific attribute. It won't work for other cases 
that could make use of add-path, e.g. ECMP..

Also, for ECMP, a lot of the details of whether not multiple-paths 
should be advertised or else whether or not the AS_PATH must be 'ECMP 
aggregated' revolve around next-hop.

> the routes (simulating full-mesh).  It is actually the (prefix, 
> router-id) that would identify a path instead of the prefix itself.

And see above :)

> As the issue of how to identify a path is so fundamental to a solution,  I 
> hope that it can be clarified before we dive into other details.

Yep, fully agreed.

And for any two paths to the same destination a speaker may have, the 
next-hop(s) serve(s) as an identity, regardless of other attributes 
of the paths.

- if they are not to the same remote speaker, the paths obviously are
   different (at least in that "plane" of routing)

- if they are the same, the two paths are effectively the same,
   regardless of the other attributes.

We maintain so anyway and think it to be fundamental to routing.

In which case, we might as well make use of this property, rather 
than having speakers left to reinvent identifiers, which we think is 
not quite as easy and problem-free in the general case as it is for 
simple RR cases.

So the question is how to settle the matter of the additional 
identifier..

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
Populus vult decipi.
 	[The people like to be deceived.]

---

From: Paul Jakma <[email-masked]>
Date: Thu, 24 Aug 2006 18:55:46 +0100 (IST)

On Thu, 24 Aug 2006, Enke Chen wrote:

> multi-paths.  How do (X, N1) and (X, N2) got withdrawn on RR2 as 
> they are no longer valid (replaced by B1 and B2), in other words 
> how does RR2 figure out (X, N11) is a replacement of (X, N1), and 
> (X, N22) a replacement of (X, N2)?

They don't need to.

The first above, with NEXT_HOP (or MP_REACH for MP) continues to 
imply a full implicit withdrawal of the NLRI. So with that first 
UPDATE all the previous (NLRI,nexthops) are withdrawn.

Further, if <other attributes> are the same for the above paths, it 
can be done in just one UPDATE.

UPDATE: feasible nlri X,
         NEXT_HOP N1,
 	MULTIPLE_HOP N11, N2, N22
 	<other attributes>

If, say, all but (X,N22) had the same attributes, then the following 
would be sent:

UPDATE: feasible nlri X,
         NEXT_HOP N1,
 	MULTIPLE_HOP N11, N2
 	<other attributes>
UPDATE: feasible nlri X,
 	MULTIPLE_HOP N22
 	<(X,N22) attributes>

regards,
Snow Day -- stay home.

---

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

>really send separate individual path attributes?

Perhaps not (though you never know).  However, to a confederation 
peer (i.e. in a different AS within your own confederation)?  Yes.

I agree with Jeff that the lack of ability to send multiple paths for 
a given next hop is a deficiency -- if for no other reason that it's 
an unnecessary restriction.

--John

---

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

>optimal and would involve lesser number of UPDATEs than the other.

Sure.  In terms of implementation overhead, I don't think you've 
addressed Enke's original point though, which was that the full 
sequence on the RR is:

- Receive X, N1 from client
- Advertise X, N1 to peer RR
- Receive X, N11 from client
==> at this point a conventional implementation might simply free the
     memory used to store N1 and somehow queue the replacement,
     X, N11 for advertisement.  However, a multiple-hop implementation
     would have to retain N1 (marked as deleted or the like) until all
     peers had been updated -- since N1 is used as part of the key in
     the withdrawal.
- Followed by updates as you've noted above

The point here isn't that this is necessarily a show-stopper. 
However, I think  it does demonstrate that until one carefully 
considers the implications in a real implementation, it's dangerous 
to make sweeping statements about how one proposal is simpler than 
other.

--John

---

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

Paul,

At 10:12 PM +0100 8/23/06, Paul Jakma wrote:
>left to construct some identifier specific to the peer the speaker 
>is sending the path to, for that path.
>

It's been quite a while since we wrote that draft so I'm having to 
refresh my memory, but we did consider the concerns you describe 
while writing it.  Some responses:

As to "say how" -- we specifically wanted to avoid prescribing how to 
derive the path identifier, since what's the point of a 
semantics-free identifier if the specification goes and forces a 
particular algorithm on you?  As I said in my note to Joel, I just 
don't see this as a very difficult problem.  Do you?

As to the re-advertisement case -- yes, the path identifier has to be 
reconstructed.  Again, this seems to me a simple problem.

As to redundancy -- if you can make the case convincingly that there 
is never, under any circumstance, a case where one might want to 
advertise more than a single route with a given next hop, then I 
think you have a strong argument.  I'm not convinced of this premise 
yet, however.  (See previous message with example involving 
confederations, for one.)

If indeed there is ever a case where you want to advertise two routes 
with the same next hop, then the path identifier is not redundant.

Regards,

--John

---

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

At 6:59 AM +0530 8/24/06, Manav Bhatia wrote:
>Between Multiple-Hop capable speakers, the MULTIPLE_HOP attribute 
>MUST be used in addition to the existing NEXT_HOP/MP_REACH_NLRI in 
>order to announce multiple next-hops for the destinations listed in 
>the NLRI/MP_REACH_NLRI of the UPDATE message. If the speaker has 
>installed one of the next-hops concerned in its FIB, then that 
>particular next-hop MUST be listed in the NEXT_HOP/MP_REACH_NLRI 
>attribute.
>

If indeed it's important to flag installed vs. non-installed routes, 
it's clearly easy enough to extend either proposal to do so.  I don't 
think this is an interesting point of comparison.

Also, see my other message for why I think using NEXT_HOP in this way 
is a bad idea.

--John

---

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

Joel,

Elegance is very much in the eye of the beholder, which is why I'd 
rather not appeal to it in discussing these things, but rather stick 
to facts.  What I like about the add-path approach is exactly that it 
doesn't impute any particular semantics to the path identifier.  I 
think it's instructive that OSPF used to use the prefix as its 
database key and has finally moved away from that in OSPFv3.

I don't understand your apparent concern about how to choose the path 
identifier.  Surely this is a problem that can be solved by any 
moderately skilled undergraduate.

--John

At 7:58 AM -0400 8/23/06, Joel M. Halpern wrote:
>it has to be used by the receiver no matter how the sender has 
>chosen to allocate / create it.  As such, if the two happen to have 
>the same implementation view they may find it simple.  But it is 
>quite dependent upon that implementation.
>with different attributes but the same NLRI and the same next-hop. 
>In discussion with folks we realized that there was no actual use 
>case where you need the differentiation.  Either the advertiser is 
>in the path (next-hop self) in which case preserving the paths does 
>not add information, even for the route oscillation case, or the 
>advertiser is preserving the next-hop information in which case the 
>next hops provide the needed differentiation.  Thus, using the 
>next-hop as an added differentiator provides exactly the flexibility 
>needed by the problem, and is much simpler, more amenable to 
>variations in implementations strategies, and more robust.
>
>Yours,
>Joel M. Halpern
...

---

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

--John

---

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

Joel,

--John

...

---

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

At 11:46 PM +0100 8/23/06, Paul Jakma wrote:
>This isn't an issue. Only useable paths can be advertised.

If true that seems like a deficiency, since it may be desirable in 
some cases to advertise non-used but feasible routes (e.g., "best 
external") for reasons of fast convergence.

I'm not sure whether such routes need to be explicitly labeled as not 
used for forwarding, but I am moderately sure we don't want to 
preclude them.

--John

---

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

A few other points regarding the draft --

First, the draft isn't terribly clear on the usage of "legacy" 
next_hop on a connection over which the multiple-hop capability has 
been exchanged.  To take one example, if I announce:

     R1: (P, next_hop N1, other attributes)
     R2: (P, multiple_next_hop N2, other attributes)

can I subsequently withdraw R1 by means of an update which lists N1 
in the multiple_next_hop attribute?  I'd assume so, but the mixing of 
next_hop and multiple_next_hop leaves room for confusion.  (Other 
comments to the list have exhibited the same confusion so I think 
it's not just me.)

I'd suggest dropping use of next_hop at all on multiple-hop 
connections, for clarity.  Instead, mandate that all next hop 
information is carried in multiple_next_hop.  As far as I can tell, 
the only well-defined use of next_hop in the document right now is if 
you want to implicitly withdraw N routes and replace them with M 
routes (but where all M share one set of path attributes).  That 
seems like an unnecessary corner case optimization, especially since 
you've already disclaimed interest in other implicit withdraw cases 
(where the next hop changes).

If you don't want to make this change then I think you at least need 
to clarify the implicit withdraw semantics in the presence of 
next_hop, as Paul did --

>    MULTIPLE_NEXT_HOP, if that attribute is present.

This is NOT clear in the doc.

Second, the draft specifies a set of flags in the multiple-hop 
capability.  The only defined flag is the "receive multiple" flag. 
Under what circumstances would a router ever advertise the capability 
without setting the RM flag?

Third, you misspelled "Traina" in your references section.

--John

---

From: Paul Jakma <[email-masked]>
Date: Thu, 24 Aug 2006 19:04:30 +0100 (IST)

On Thu, 24 Aug 2006, Enke Chen wrote:

> scheme.

Either that or resend all remaining paths for the NLRI in their 
entirety (implicitely withdrawing all previous paths for same NLRI).

See other reply too.

> That means more updates. Perhaps what is more challenging here is 
> that RR1 must withdraw (X, N1) before advertising (X, N11).

It doesn't, the UPDATE for (X,N11) can be sent before explicitely 
withdrawing (X, N1), if an implementation wishes.

> How do you guarantee the ordering in an imploementation?

Not needed. They are different paths in this scheme.

I don't actually see a difference in the implementation requirements 
here between the two drafts. Either implementation must either be 
able to reliably construct the identifier from (path, speaker path is 
to be sent to), or else keep state specific to each (path,speaker 
sent to).

> Please see my previous comment on de-coupling Tx from Rx:

Yes, agree this is highly desirable.

The multiple-hops case occasionally will have to generate multiple 
messages in the Tx path for one path change, which shouldn't be a 
problem. But there's no need for it to be coupled to Rx.

> receiving processing de-coupled from the sending processing  (in order to 
> keep less state).   It means that at the time of sending update the info 
> (such as the nexthop) for the old path may no longer available.  I am not 
> sure if your proposal requires an implementation to keep track of the 
> nexthops advertised to a peer for the purpose of figuring out when to use the 
> NEXTHOP attribute or the MULTI-NEXTHOP attribute.

If the implementation has the ability to advertise the same path with 
different nexthops to different speakers, yes it almost certainly 
would have to keep state on that.

I don't think this is much different from add-path, which also would 
need to keep state on identifiers it has used for each peer and path.

> explicit withdraws as shown in the example.

Though, this would be true only when the nexthop changes for a path.

- If the nexthop is the same, multiple-hops can update it with with
   an implicit withdraw.

- On the flip side, multiple-hops can bunch together paths whose
   attributes are all (bar nexthop(s)) equal.

- Add-path must always send distinct UPDATEs (with all attributes)
   for all paths which differ only by (NLRI,nexthop).

I don't know which would use more or less bandwidth in the real 
world. But we suspect next-hops are comparitively stable compared to 
full path changes.

>   2) As a new attribute is introduced in your proposal, the efficiency of 
> prefix packing will be lower, resulting in more updates.
>       It's shown that the prefix packing efficiency has a huge impact on the 
> performance of update processing  (both Tx and Rx).

We could encode the nexthop identifiers in the NRLI quite easily.

I, personally, hate to see message formats redefined. If the 
'traditional' NLRI in BGP-4 no longer meets todays needs, we ought to 
deprecate it and properly define a new UPDATE message, but hey.

But if mushing UPDATE is fine, multiple-hop could do so too.

The identity question is still the tricky one here :).

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
Question: Is it better to abide by the rules until they're changed or
help speed the change by breaking them?

---

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

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

> I don't understand your apparent concern about how to choose the 
> path identifier.  Surely this is a problem that can be solved by 
> any moderately skilled undergraduate.

:)

Yes, it undoubtedly is. And they should reach the following 
conclusion:

   for readvertisement of multiple-paths to the same destination to
   be feasible you need to be able to determine the identity of the
   path from the path itself

As you can not construct the additional path identifier solely from 
the identity of the speaker from whom you received the path, 
obviously, if they are to advertise multiple-paths.

Hence it follows that some additional aspect of each path itself must 
be used to discriminate between paths to the same destination (e.g. 
the hash value of certain key values, or even one key value directly, 
such as nexthop)[1].

Our point therefore is that we should simply use next-hop as this 
additional path-identity, as it is emminently suited to the task.

There is no value in leaving the additional identifier to local 
implementations, as they're going to have to come to the same 
conclusion, with the risk that if they do not[2] they will unable to 
cope with RR clusters and various other multiple-readvertisement 
scenarios.

1. Note that this means the stability of the Add-Path-ID depends on
    the stability of whatever aspect of the path is chosen to mix into the
    Add-Path-ID.

    Consider this with the point raised against Multiple-Hop by Enke
    that if next-hop changes, Multiple-Hop must withdraw and
    reannounce. The same likely will be true for add-path implementations.

2. E.g. by choosing to use identity of the speaker (Router-ID,
    etc..) from whom a path was received solely as the Add-Path-ID, as
    the add-path draft hints at, and as Enke gave as an example in
    this thread.

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
Oh, `no attitude,' eh?  Not `in your face,' huh?  Well, you can cram it
with walnuts, ugly!

 		-- Homer Simpson
 		   The Itchy & Scratchy & Poochie Show

---

From: Paul Jakma <[email-masked]>
Date: Thu, 24 Aug 2006 21:04:53 +0100 (IST)

Hi John,

> I'm not sure whether such routes need to be explicitly labeled as 
> not used for forwarding, but I am moderately sure we don't want to 
> preclude them.

We potentially could add a flag field to MULTIPLE_HOP for this, to 
signal this on a per-nexthop basis (and then could be used for a 
per-nexthop implicit withdrawal flag too), if thought to be 
desireable.

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
I think we're all Bozos on this bus.
 		-- Firesign Theatre

---

From: "Joel M. Halpern" <[email-masked]>
Date: Thu, 24 Aug 2006 17:01:45 -0400

I would not have raised elegance and simplicity as issues, except 
that Mr. Chen chose to assert thoser properties for his solution.

As for choosing the identifiers, part of the problem is that in fact 
several of the proposed techniques (such as using the router-ID of 
the router you receive the advertisement from) will not work.
The other aspect is that introducing a new identifier shared between 
communicating devices is natural for certain architectures, but not 
particularly natural for others.

Yours,
Joel M. Halpern

At 12:30 PM 8/24/2006, John G. Scudder wrote:
>to facts.  What I like about the add-path approach is exactly that 
>it doesn't impute any particular semantics to the path 
>identifier.  I think it's instructive that OSPF used to use the 
>prefix as its database key and has finally moved away from that in OSPFv3.
>
>path identifier.  Surely this is a problem that can be solved by any 
>>between the routers.  That identifier has to be assigned and 
>>managed by the advertising router in such a way that it is unique 
>>for each path that needs advertised (under all possible 
>>circumstances).  But it has to be used by the receiver no matter 
>>how the sender has chosen to allocate / create it.  As such, if the 
>>two happen to have the same implementation view they may find it 
>>simple.  But it is quite dependent upon that implementation.
>>next-hop as an added differentiator provides exactly the 
>>flexibility needed by the problem, and is much simpler, more 
>>amenable to variations in implementations strategies, and more robust.
>>
>>Yours,
>>Joel M. Halpern
>...

---

From: "Joel M. Halpern" <[email-masked]>
Date: Thu, 24 Aug 2006 18:00:47 -0400

In once sense one can argue that it is deficiency.
However, I want to avoid designing for hypothetical goals which will 
not be needed.
Note that in the confederation border case you suggested, if the 
rotuer is setting next-hop to itself, then it can compress the 
advertisements.  (In fact, typically the advertisements will have the 
same AS path and so the compression is not even needed.)

Yours,
Joel M. Halpern

---

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

>that Mr. Chen chose to assert thoser properties for his solution.

OK.  And I'm suggesting to all concerned that assertions of elegance, 
simplicity, etc, are not likely to lead to productive discussion.

>the router you receive the advertisement from) will not work.

I beg to differ, with one caveat: I see that at least the -05 
add-path draft doesn't mention that the path identifier is a 
per-connection value (really, it can be per-speaker, the point is 
that it may be regenenerated by anyone who advertises the route).  As 
long as that's understood (and I hope it'll be fixed in -06), then 
any algorithm whatsoever that ensures uniqueness in the local context 
will work just fine.

>particularly natural for others.

I really don't understand this point.

--John

---

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

Hi John,

> reconstructed.  Again, this seems to me a simple problem.

If it's simple, could you give one solution? The add-path draft could 
then incorporate it as an example, retaining the freedom of 
implementation the draft has as a goal. (Obviously, next-hop is one 
answer).

The draft though seems to encourage use of speaker identities as the 
additional identifier. That, above all else, is what worries us.

> As to redundancy -- if you can make the case convincingly that there is 
> never, under any circumstance, a case where one might want to advertise more 
> than a single route with a given next hop, then I think you have a strong 
> argument.  I'm not convinced of this premise yet, however.  (See previous 
> message with example involving confederations, for one.)

Thanks, will have a look.

> If indeed there is ever a case where you want to advertise two 
> routes with the same next hop, then the path identifier is not 
> redundant.

Agreed. We can't see how such cases would arise, but let me consider 
your other email.

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
"The pathology is to want control, not that you ever get it, because of
course you never do."
-- Gregory Bateson

---

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

Hi, Paul:

Paul Jakma wrote:

>> are no longer valid (replaced by B1 and B2), in other words how does 
>> RR2 figure out (X, N11) is a replacement of (X, N1), and (X, N22) a 
>> replacement of (X, N2)?
>
>
> They don't need to.
>
> The first above, with NEXT_HOP (or MP_REACH for MP) continues to imply 
> a full implicit withdrawal of the NLRI. So with that first UPDATE all 
> the previous (NLRI,nexthops) are withdrawn.

The update sequence described by Manav is the following:

You seem to be talking about a different approach. Could you detail the sequence of updates?

-- Enke

---

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

Hi, John:

John G. Scudder wrote:

> I beg to differ, with one caveat: I see that at least the -05 add-path 
> draft doesn't mention that the path identifier is a per-connection 
> value (really, it can be per-speaker, the point is that it may be 
> regenenerated by anyone who advertises the route). As long as that's 
> understood (and I hope it'll be fixed in -06), then any algorithm 
> whatsoever that ensures uniqueness in the local context will work just 
> fine.

We will emphasize the "local significance" of the path identifier in the 
next revision, something along these text (as you suggested):

The Path Identifier is locally significant. Any BGP speaker
which re-advertises a route (for example, a route reflector)
MAY generate its own Path Identifier to associate with the
re-advertised route.

Thanks. -- Enke

---

From: Paul Jakma <[email-masked]>
Date: Thu, 24 Aug 2006 23:46:52 +0100 (IST)

> The update sequence described by Manav is the following:

Ah, I missed the unfeasible's in my quoting somehow.

> UPDATE: feasible nlri X, next_hop N1, <other attributes>

This would implicitely withdraw all previously advertised paths for 
the NLRI (as it does for BGP today). And announces (X,N1).

RIB under X:

 	N1: <attributes>

> UPDATE: feasible nlri X, multiple_hop N2, <other attributes>

This adds the path of (X,N2). (No 'traditional' next-hop, no implicit 
withdraw).

RIB under X:

 	N1: .....
 	N2: .....

> UPDATE: unfeasible nlri X, multiple_hop N2

Explicit withdraw of (X,N1) and (X,N2)

> UPDATE: feasible nlri X, multiple_hop N12, <other attributes>

Advertisements of (X,N11) and (X,N12).

There is no particular ordering requirement between the withdrawals 
of (X,N1) and (X,N2), and the advertisement of (X,N11) and (X,N12).

Additionally, advertisements of paths for an NLRI whose attributes 
are all the same, next-hop excepted, can be sent together in the same 
UPDATE (as an opportunistic optimisation, same as with different 
NLRIs but same attrs).

> You seem to be talking about a different approach. Could you detail the 

See above. :)

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
I found Rome a city of bricks and left it a city of marble.
 		-- Augustus Caesar

---

From: Paul Jakma <[email-masked]>
Date: Thu, 24 Aug 2006 23:57:18 +0100 (IST)

> You seem to be talking about a different approach. Could you detail the 

Err, you may have meant "detail the sequence for the other approach" 
rather than "detail the sequence above". I'm not sure what other 
approach you mean, unless you refer to the opportunistic bunching 
that is possible when, for a specific NLRI, the paths differ only by 
nexthop.

E.g. if for all the above <other attributes> are equal, then it 
is possible to 'bunch' some of the UPDATEs together:

- the first two UPDATEs differ only by nexthop, so they can be
   opportunistically bunched together into:

UPDATE: feasible nlri X,
         next_hop N1,
 	multiple_hop N2
 	<other attributes>

- The second two explicit withdrawal UPDATEs can be bunched together:

UPDATE: unfeasible nlri X,
 	multiple_hop N1, N2

- The last two UPDATEs can be bunched together:

UPDATE: feasible nlri X
 	multiple_hop N11, N12
 	<other attributes>

Whether it's possible obviously depends on timing, as it does today 
for UPDATE bunching.

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
petribar:
 	Any sun-bleached prehistoric candy that has been sitting in
 	the window of a vending machine too long.
 		-- Rich Hall, "Sniglets"

---

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

>additional path-identity, as it is emminently suited to the task.

I think this is the single interesting point in contention: whether 
or not next hop is always suitable for the task of uniquely 
identifying a path.

Rather than responding individually to your further points about 
selection of path identifier, I'll just point to Enke:

At 11:19 AM -0700 8/24/06, Enke Chen wrote:
>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).

--John

---

From: "Manav Bhatia" <[email-masked]>
Date: Fri, 25 Aug 2006 14:18:33 +0530

>Apart from any other issue the paragraph above seems incorrect as 
>written.  I presume that you don't mean an update that has only 
>(fixed header, NLRI, NEXT_HOP) but rather an update that has all of 
>the required attributes but doesn't have MULTIPLE_HOP.

Yes, precisely.

---

From: "Manav Bhatia" <[email-masked]>
Date: Fri, 25 Aug 2006 14:38:09 +0530

John,

>without setting the RM flag?

   RR 
  / | \
 A  B  C

The RR may not be interested in learning *all* the routes from each client
(A, B and C). It may only want the client to advertise its best path, which
would be reflected to other clients/non clients.

This bit provides the granularity for a speaker to indicate that it is NOT
willing to accept multiple paths. This was done because learning and
advertising multiple paths consumes resources and should only be done if
necessary. This is beneficial as it can avoid generation of unwanted routing
updates at the source itself.

Cheers,
Manav

---

From: "Manav Bhatia" <[email-masked]>
Date: Fri, 25 Aug 2006 15:06:59 +0530

>However, I want to avoid designing for hypothetical goals which will 

Couldn't have been stated any better.

Also next-hop-self is set on an EBGP router when its advertising routes to
IBGP so that they use this router as the next hop for all the EBGP learnt
routes. I am unable to envisage a case when we would have the same <nlri,
nexthop> for multiple paths. I don't think we should be optimizing a
protocol design for the unknown. I call it unknown as we're thinking that
some day we may come up with an AFI/SAFI in which we'll have multiple routes
of the same  <nlri, nexthop> that need to be passed on.

However, if the majority thinks that it's a worthy case that should be
handled then this can be easily incorporated in the multiple hop attribute.

Thanks,
Manav

---

From: "Manav Bhatia" <[email-masked]>
Date: Fri, 25 Aug 2006 15:40:06 +0530

I didn't see a reply on how add-path proposal aims to address an issue
raised by Paul below? This illustrates the general concern that we have with
arbitrarily picking up a path ID. I think it has been disambiguated that the
Router ID will not work as a Path Id and an implementation needs to pick up
its own unique numbers ..

---

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

--John

P.S.:  Also, a nit: the draft is full of characters that don't render 
properly.  I assume that at some point these were curly quotation 
marks and apostrophes, but now they're just textual junk.  (For 
example, "Author's Address" in the ToC contains one such in place of 
the apostrophe.)

---

From: Jeffrey Haas <[email-masked]>
Date: Fri, 25 Aug 2006 11:15:04 -0400

> it preserves the next-hop on all routes it receives.

To state something that is obvious and somewhat tangential,
route reflectors still perform route selection.  This means that
while they may not (in the absence of a next-hop-self behavior)
insert themselves into the forwarding path, they currently prune
available paths for a given destination within an AS in some
circumstances.  This is part of the reason why we have MED oscillation
issues.

Since a route reflector prunes paths, injecting other paths into
the AS may lead to convergence of reflector clients to different
route instances than they may have previously selected.  Is this ever bad?
That's what I'm trying to figure out.

-- Jeff

---

From: Jeffrey Haas <[email-masked]>
Date: Fri, 25 Aug 2006 11:15:04 -0400

-- Jeff

---

From: Robert Raszuk <[email-masked]>
Date: Fri, 25 Aug 2006 08:34:06 -0700

Manav,

> The RR may not be interested in learning *all* the routes from each
> client (A, B and C). It may only want the client to advertise its best
> path, which would be reflected to other clients/non clients.

Then RR would negotiate the corresponding capability with only those
peers he is willing to accept all/external paths from ? Would not that
serve the same purpose ?

Thx,
R.

---

From: Jeffrey Haas <[email-masked]>
Date: Fri, 25 Aug 2006 11:23:30 -0400

On Thu, Aug 24, 2006 at 06:59:05AM +0530, Manav Bhatia wrote:
> A simple addition of the following text would perhaps fix the issue that 
> you have:
> 
> used in addition to the existing NEXT_HOP/MP_REACH_NLRI in order to 
> announce multiple next-hops for the destinations listed in the 
> NLRI/MP_REACH_NLRI of the UPDATE message. If the speaker has installed one 
> of the next-hops concerned in its FIB, then that particular next-hop MUST 
> be listed in the NEXT_HOP/MP_REACH_NLRI attribute.

Unless I am grossly mis-understanding your proposal, this allows for
an ecmp case of the same path, same destination but multiple nexthops.

The scenario I am concerned with is same destination, different path, 
different nexthop.  The above doesn't seem to cover that.

> This is possible in our approach, but can *never* be done in add-paths btw.

I'm not sure that's the case.  The add-paths mechanism allows for
multiple BGP routes with any attributes as long as they have distinct
keys.  The key simply identifies a given route instance.

I think that point may be understood now, but I'm responding to this
point a bit further back in the thread history.

> multiple BGP paths where none of them are actually installed in the FIB 

I'm well aware of the requirements for a route server. :-)

-- Jeff

---

From: "Manav Bhatia" <[email-masked]>
Date: Fri, 25 Aug 2006 22:15:52 +0530

Robert,

> peers he is willing to accept all/external paths from ? Would not that

No. We may want the RR to reflect all the routes that it learns from the 
other clients. Not negotiating this capability would lead to the RR 
advertising only the one best path to its client.

Cheers,
Manav

---

From: Paul Jakma <[email-masked]>
Date: Fri, 25 Aug 2006 17:49:26 +0100 (IST)

> different nexthop.  The above doesn't seem to cover that.

Can we think of an example involving two paths that are "the same but 
different" in this way? E.g. (and apologies for any obviousness, but 
just to ensure its all clear):

 	A---\
 	     C---D
 	B---/

A and B originate a path for P.

D, potentially, could get:

   P via C, path C_B

or

   P via C, path A_D

Why would we ever want C to be able to advertise both these paths to 
D? Only of them is useable by D.

Indeed, we're pretty sure no plausible counter examples exist[1], as 
the (destination,nexthop(s)) identity simply is fundamental to D-V. 
As such, there really is no conceptual need for an additional 
identifier[2].

We'd be happy to hear of a counter-example, but the authors of the 
draft are unable to (and believe me, we have tried for quite a while 
to find one), and none has yet been raised in the spirited discussion 
here this week[3].

I'll finish with a quote from an earlier email of Joel's:

   "I want to avoid designing for hypothetical goals which will not be
    needed."

Look forward to your reply! :)

--paulj

1. The only examples so far that come close are the "Use BGP as a
    flooding mechanism for information unrelated to paths" cases, but
    no multiple-advertisements will ever be needed for flooding such -
    again as this is fundamental to flooding.

2. Not even for 'feasible but unuseable' paths.

3. Though, good humoured, interesting and useful, whatever the
    outcome is to be, I feel.

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
Everyone is more or less mad on one point.
 		-- Rudyard Kipling

---

From: "Manav Bhatia" <[email-masked]>
Date: Fri, 25 Aug 2006 23:24:40 +0530

Robert,

Yes this can be done via ORFs, outbound routemaps, etc.

We had some feedback from the IX operators where they wanted asymmetric 
routes exchange. That is, while the IX clients would advertise their best 
routes, the route server needs to advertise *all* the routes learnt from all 
its IX clients to each client. Adding a bit in the capability that does this 
didn't seem to be much of an overhead! :)

Cheers,
Manav

----- Original Message ----- 
From: "Robert Raszuk" <[email-masked]>
To: "Manav Bhatia" <[email-masked]>
Cc: "'John G. Scudder'" <[email-masked]>; <[email-masked]>
Sent: Friday, August 25, 2006 11:09 PM
Subject: Re: [Idr] Progressing draft-bhatia-bgp-multiple-next-hops-01.txt

> Manav,
>
> Well this has been already solved in the ORF capability where we
> explicitly say send/receive willingness.
>
> Then negotiating one does not prevent from not negotiating the other :).
>
> Cheers,
> R.

---

From: Robert Raszuk <[email-masked]>
Date: Fri, 25 Aug 2006 10:39:53 -0700

Manav,

Cheers,
R.

---

From: Enke Chen <[email-masked]>
Date: Fri, 25 Aug 2006 12:54:20 -0700

Manav:

Manav Bhatia wrote:

>
> We had some feedback from the IX operators where they wanted 
> asymmetric routes exchange. That is, while the IX clients would 
> advertise their best routes, the route server needs to advertise *all* 
> the routes learnt from all its IX clients to each client. Adding a bit 
> in the capability that does this didn't seem to be much of an 
> overhead! :)
>

Here you emphasize the need for the route server to advertise *all* the 
routes.  I think that is valid, and a solution must be able to 
accomplish that. This point is also presented in your proposal:

-----------------------------------------------------------------------------------------------------------

9.3 eBGP mesh scaling at IXes via Route Servers 

   [...]

   If there were a mechanism in BGP to allow an IX route-server to pass   
   all other advertisements to a customer peer, without performing any   
   path selection or applying any policy, then ...

-----------------------------------------------------------------------------

Let us look at this example:

                              (X)
                     R1       R2        R3
                      |        |        |
                   --------------------------
                               |
                               RS

The RS peers with R1, R2, and R3 and advertise *all* the routes back.

However, once R1 and R2 start to peer with each other:

    - R1 learns X from R2.
    - Both R1 and R2 advertise X (with R2 as the nexthop) to RS.

How does RS advertise two paths from R1 and R2 for X to R3? (The two paths
have the same nexthop, but different as-path attributes).

-- Enke

---

From: "Manav Bhatia" <[email-masked]>
Date: Sat, 26 Aug 2006 09:18:12 +0530

Enke,

In addition to what Joel said.

> Let us look at this example:

Are you suggesting that R1 will advertise the route (X) it learnt from the 
RS back to the RS? This goes against the basic tenets of BGP; You cannot 
advertise a route that you learnt from a peer back to that peer.

This isnt how BGP works in the IXes. If it did this way then R3 would be 
lying by advertising X (with R2 as the nexthop) and path { R1 R2 .. } 
because the path *does not* go through R1.

Manav

---

From: Enke Chen <[email-masked]>
Date: Fri, 25 Aug 2006 21:24:25 -0700

Manav,

Manav Bhatia wrote:

> Are you suggesting that R1 will advertise the route (X) it learnt from 
> the RS back to the RS? This goes against the basic tenets of BGP; You 
> cannot advertise a route that you learnt from a peer back to that peer.

No, see above ("R1 learns X from R2" via their direct peering session).

>
> This isnt how BGP works in the IXes. If it did this way then R3 would 
> be lying by advertising X (with R2 as the nexthop) and path { R1 R2 .. 
> } because the path *does not* go through R1.

There are various types of relationships among the peers at the  IXes, 
including provider- provider, customer-provider, and 3rd party 
nexthops.  (I do know a little bit about the IXes as I used to work for 
a large ISP, and dealt with the peering issues at the IXes.)  I do not 
think it is up to us to decide what the providers can do or can not do 
at the IXes.

Clearly these are two different paths with different as-paths.  As you 
stated in your proposal, the RS should not apply policy. It is up to the 
clients of the RS to apply policy (such as filtering, assigning 
preferences). Due to the difference in the as-paths, the policy of a 
client may treat these paths differently.

I am not sure if we are getting into the debate about the definition of 
*all* routes on the RS.

-- Enke

---

From: Enke Chen <[email-masked]>
Date: Fri, 25 Aug 2006 21:30:27 -0700

Joel:

They are different routes on the RS as the AS-PATHs are different. Each 
client needs to prepend its AS number when advertising to the RS. (The 
RS may skip its own AS number in advertising.)

-- Enke

Joel M. Halpern wrote:

> I am missing something.  I don't believe that "all" the routes 
> requires the inclusion of redundancy.  Whether R1 or R2 sends the 
> advertisement, with the same AS Path and the same Next Hop (R2), there 
> is no need for the route server to send that advertisement twice.  it 
> will not add information.
> Yours,
> Joel
>
> At 03:54 PM 8/25/2006, Enke Chen wrote:
>
>> Manav:
>>
>> Manav Bhatia wrote:
>>
>>>
>>> advertise their best routes, the route server needs to advertise 
>>> *all* the routes learnt from all its IX clients to each client. 
>>> Adding a bit in the capability that does this didn't seem to be much 
>>> of an overhead! :)
>>
>>
>> Here you emphasize the need for the route server to advertise *all* 
>> the routes.  I think that is valid, and a solution must be able to

---

From: Paul Jakma <[email-masked]>
Date: Wed, 30 Aug 2006 20:26:25 +0100 (IST)

Hi Enke,

On Fri, 25 Aug 2006, Enke Chen wrote:

> There are various types of relationships among the peers at the 
> IXes, including provider- provider, customer-provider, and 3rd 
> party nexthops.  (I do know a little bit about the IXes as I used 
> to work for a large ISP, and dealt with the peering issues at the 
> IXes.)  I do not think it is up to us to decide what the providers 
> can do or can not do at the IXes.

We don't think it's a problem. The job of the RS is to propogate 
paths from the one speaker to all other participating speakers. Ergo 
only the 'exit' path needs be propogated, and the speaker providing 
that exit path can peer with the RS and advertise it to the RS if it 
wishes all other RS-client speakers to see it.

The cases I've seen of 3rd-nexthop at shared networks have been 
simply due to people not bothering to setup peering due to 
administrative overheads - the removal of such overheads being the 
reason for this draft.

For cases where the 'exit' speaker does not wish to directly provide 
the path to an RS, it likely would not want others to do so either. 
It makes no difference whether in such a case whether the RS uses 
add-path/multiple-next-hop.

In short, the RS solves the reason for much of the use of 3rd-p-n.

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
"Teacher, my shoes are making noise."

 	--Ralph Wiggum
 	  Last Tap Dance in Springfield (Episode BABF15)

---

From: Curtis Villamizar <[email-masked]>
Date: Wed, 30 Aug 2006 16:24:28 -0400

Paul,

You can't propose a protocol extension where routes cannot be
distinguished when a legitimate example is given just because the
example is in your opinion "something no one would want to do".

It is true that most peerings use "next hop self" at an exchange where
a route server is located, however if two peers did not set next hop
self and provided third party routes with the same next hop to the RS,
there would be no way to make these routes unambiguous.

So far we haven't seen a similar case that might arise with similar
slight misconfiguration of RR however RR are all within a single
administrative domain making any misconfiguration easier to fix.

If the major difference between draft-bhatia-bgp-multiple-next-hops
and draft-walton-bgp-add-paths is that the latter provides a way to
make such cases unambiguous, then IDR needs to set aside the former.

It seems that we now have an example where the path identifier in
draft-walton-bgp-add-paths-05.txt is needed.  It is a case where a RS
is in use and some routers with private peerings are not setting
next-hop-self.  It is not a likely configuration given the policies of
most public interconnects but it is a legitimate configuration.  Even
if it were considered a misconfiguration protocol extensions must
accommodate minor misconfigurations.

I don't recall seeing any objections to the use of path identifier in
draft-walton-bgp-add-paths that held up.  A clarification is needed
regarding the path identifier being only session specific and not
global but otherwise no change has been called for.

draft-walton-bgp-add-paths is also a shorter document due to the
approach being simpler.

Curtis

---

From: Paul Jakma <[email-masked]>
Date: Thu, 31 Aug 2006 10:22:46 +0100 (IST)

Hi Curtis,

> example is in your opinion "something no one would want to do".

It's not a consideration because the exit-peer can easily peer with 
the RS in Enke's example.

3-p-n generally is discouraged, it has reliability problems - it's 
the poor man's substitute for direct peering (usually administrative 
overhead of setting it up). Certainly at IXes we know of it is 
generally discouraged.

Its use tends to be primarily because of the /lack/ of eBGP RS 
solutions.

We'd be interested in any plausible cases where a peer would /not/ 
want to advertise the path to the RS, but would be happy for other 
peers to advertise the path to the RS (and hence all RS-client 
peers). We can't quite think of them.

> It is true that most peerings use "next hop self" at an exchange 
> where a route server is located, however if two peers did not set 
> next hop self and provided third party routes with the same next 
> hop to the RS, there would be no way to make these routes 
> unambiguous.

There's no ambiguity, the RS just doesn't accept paths from peers 
which won't forward the path. That's not a problem a route-server is 
there to solve.

However, if the exit peer wants to peer with the RS, and hence 
*remove* the need for others to advertise path with it as nexthop, 
then that is exactly what the RS is there for, that's exactly the 
problem the IX operators /want/ solved (they don't care about 3-p-n 
at all).

If not, then *neither* add-path nor multiple-hop can help the peers 
involved btw..

> draft-walton-bgp-add-paths-05.txt is needed.

I would tend to disagree.

> I don't recall seeing any objections to the use of path identifier 
> in draft-walton-bgp-add-paths that held up.

There are none against multiple-hop, except vague ones about some 
unspecified, unknown cases (possibly future).

E.g. where multiple-hop "restricts" paths advertisements in 
accordance with (destination,target), the add-path approach on the 
other hand can make it impossible to reconcile that two paths are 
identical[2]. In other words, add-path turns BGP into a flooding 
protocol between contiguous sets of add-path speakers[1].

The problem is, in chasing ultimate flexibility, add-path makes 
itself a quite inefficient flooding mechanism. BGP paths will be 
flooded along /every/ possible path between a contiguous set of 
add-path speakers:

        RR2
       / | \
   (P)A  |  B
       \ | /
        RR1

Based on Add-Path alone, B would receive:

 	(A->RR2->B):      P:a
 	(A->RR1->B):      P:b
 	(A->RR2->RR1->B): P:c
 	(A->RR1->RR2->B): P:d

Now think about convergence if A withdraws P. B is going to just 
switch between the different 'ghosts', as they are all equal bar the 
path-ID, until /all/ are withdrawn[3].

And that's just with two hops of add-path.

So the flexibility is not quite free.

--paulj

1. It took a while to tease out that add-path does indeed amount to
    random local IDs, rather than distinguishable IDs derived in some
    way though..

2. Other than by comparing path-attributes, but not having to care
    about path attributes (inc. nexthop) is part of the attraction of
    add-path.

3. Course, we could just say that the two RR's must never enable
    Add-Path between each other (as is the case for reflection today),
    but doesn't that seem restrictive? :) The Add-Path draft does not
    disallow 2-way add-path.

    Maybe Add-Path for inter-RR could be defined to compare
    router-ID of paths from clients against ORIGINATOR_ID of paths
    from RRs? But that defeats the point somewhat of using a new
    opaque ID as discriminator.

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
"If you want to travel around the world and be invited to speak at a lot
of different places, just write a Unix operating system."
(By Linus Torvalds)

---

From: "Glen Kent" <[email-masked]>
Date: Thu, 31 Aug 2006 19:50:10 +0530

A quick Q while we're discussing various mechanisms to advertise multiple paths.

What is a router supposed to do if it recieves two paths from a BGP
speaker as described below?

Path 1 - NLRI 192/8 AS_PATH {10 20} LOCAL_PREF 100 NEXT_HOP 1.1.1.1

Path 2 - NLRI 192/8 AS_PATH {10 20} LOCAL_PREF 189 NEXT_HOP 1.1.1.1

What useful information can any router possibly derive from this?
Which route should it select? I see now value and would appreciate if
someone can enlighten me on this.

Another day, another time, but the same BGP speakers.

This router recieves two paths for 192/8 from the same BGP speaker.

Path 1 - NLRI 192/8 AS_PATH {10 20} NEXT_HOP 1.1.1.1

Path 2 - NLRI 192/8 AS_PATH {30 20} NEXT_HOP 1.1.1.1

How does this router determine which route is being used by the
upstream? I dont think we should progress any proposal without
incorporating ways to indicate which path is being actually used in
the forwarding.

I know one of the authors of multiple_hop indicated that this could be
easily done by introducing a field in the path attribute. Its not
difficult but they need to show this to us. The same goes for
add-paths.

Curtis said:

> draft-walton-bgp-add-paths that held up.

I think its well known that silence means lack of interest, not
acceptance. You of all the persons, should be well aware of this.

Glen

---

From: "Joel M. Halpern" <[email-masked]>
Date: Thu, 31 Aug 2006 10:35:56 -0400

Both of the examples you provided highlight the fact that if one 
allows BGP to send multiple advertisements for the same NLRI and same 
next-hop then the receiver must treat them as an atomic collection 
(i.e. the receivers considers that all the advertised paths are being used.)

This means that the case where the paths differ only on local-pref 
is, as you suggest, useless.

With regard to the case where the paths differ on AS PAth, as copied 
below from your note, this requires that the receiver consider all 
the AS Paths.  For example, if the receiver appears in any of the AS 
Paths, then none of the advertisements can be used.  And when passing 
the advertisements on further, either all the advertisements must be 
sent, or the collection of advertisements must be compressed in a way 
that preserves the presence of all distinct AS values and has the 
correct AS Path length.  How to perform such aggregation of AS Paths 
if the paths might be of different lengths is not something I 
currently know how to do.  (Merging AS Paths in ways that change 
properties relevant to the mandatory BGP decision algorithm 
introduces a whole new set of oscillation risks, which is why the 
merging has to preserve the properties mandated by the decision algorithm.)

When one uses the next-hop has the differentiator, the first case 
never comes up.  And the receiver can select from among the multiple 
paths, since they each have a different next-hop.  This is what led 
to the text in the ECMP draft that restricts the set of paths a 
receiver may choose.  And the definition of how to merge those 
eligable advertisements if the receiver chooses to use them.

There is an argument that we may, for theoretical reasons still 
subject to analysis or hypothesis, want to advertise secondary paths 
that are not used.  That would require a flag to indicate which paths 
are used vs unused.

Yours,
Joel M. Halpern

---

From: "Glen Kent" <[email-masked]>
Date: Thu, 31 Aug 2006 21:44:59 +0530

Hi Joel,

I'm having trouble in understanding the notion of "all" paths here. I
think its important that we converge on this so that everyones on the
same page. Does "all paths" cover paths that describe different
forwarding paths (i.e. traces a path that a packet will actually take)
or does it include every conceivable path that exists in ones BGP
routing tables (including the kind that i had described in my earlier
mail)?

I cant think of a sound reason why anyone would possibly want to
"flood", every path that one has, to all its neighbors. More so, when
the reciever cannot make any intelligent decision based on such
routes. If nothing else, wouldnt doing this lead to serious
scalability issues (full internet tables, multiple speakers, etc) ?

Glen.

---

From: Curtis Villamizar <[email-masked]>
Date: Thu, 31 Aug 2006 14:25:06 -0400

> the RS in Enke's example.

This is true that the two peers *can* peer with the route server
only.  It is common practice that major providers rely on private
peerings rather than get their routes for other major providers from a
RS.  This is not a hypothetical, it is common practice.  You cannot
dismiss existing common practice.

> Its use tends to be primarily because of the /lack/ of eBGP RS 

Or distrust of anything that could become a single point of failure.
Some providers have more than one router at some major IX and direct
peer in pairs with other major providers.

> peers). We can't quite think of them.

The case is where the route is not a direct customer of the provider
and is not getting transit to the IX through that provider but is
peering with another major provider with agreement to exchange all
routes.  The other providers readvertising the path would be a
misconfiguration unless the route was learned at a distant exchange
and the transit provided readvertising the routes.  Avoiding
circumventing the policy of another provider was the main purpose of
"next hop self".  That exact situation existed at one point when
NSFNET readvertised Sprint routes and the remedy was the NSFNET
routers implementing and configuring "next hop self" (which Cisco
already had at the time).

> which won't forward the path. That's not a problem a route-server is 

This is solvable if the RS does not accept routes for with the BGP
identifier does not match the next-hop.

> If not, then *neither* add-path nor multiple-hop can help the peers 

add-path does solve this.  The <peering,path-id> must be unique, not
the next-hop.

> I would tend to disagree.

Clearly you do.

> unspecified, unknown cases (possibly future).

You've just dismissed a real case above.  A minor misconfiguration
(not setting next-hop self) could result in routes being ambiguous.

> protocol between contiguous sets of add-path speakers[1].

Nice try but you have a clearly flawed argument.

You can still compare attributes in the above RS example to reduce the
multipath set to a minimal set when readvertising.  You can
disambiguate the advertisements with the same next hop from different
peers with different AS path such that you know to keep two copies and
delete only one of them when one router withdraws the route.

>     opaque ID as discriminator.

You argument that multiple-next-hops is not flawed boils down to
arguing that you can never have the same next hop with other
attributes differing.

Enke's exmaple is is an EBGP peering example.  Next-hop-self is not
required by BGP.

A similar situation exists with confederations.  A route may be passed
through different private AS but with BGP confederations the next hop
is generally not changed, relying on the next hop advertised by the
router that borders the external AS and relying on the IGP rather than
the set of EIBGP advertisers.  In this case the AS Paths would be
different *until* the confederation AS were dropped before advertising
the route externally.

Consider this case.

  ASe1 - R1/NH1 -----  R3/AS65001
                 \  /             \
                   X               R5/AS65003 - R6/AS65004
                 /  \             /
  ASe2 - R2/NH2 ----  R4/AS65002

R5 gets the following routes:

   R3:  AS65001 ASexternal1  NH1
        AS65001 ASexternal2  NH2

   R4:  AS65002 ASexternal1  NH1
        AS65001 ASexternal2  NH2

It doesn't seem that based on NH there is a good way to disambiguate
the components of this multipath.

A good question is exactly what R5 should advertise to R6 such that
the AS path is correct.  It seems that the <peering,prefix,path-id>
tuple adds an ability to disambiguate this case.

My understanding of add-path is that the advertisement would be:

  R5 -> R6:

    prefix X path-id 1  AS65003 AS65001 ASexternal1  NH1
    prefix X path-id 2  AS65003 AS65001 ASexternal2  NH2
    prefix X path-id 3  AS65003 AS65002 ASexternal1  NH1
    prefix X path-id 4  AS65003 AS65001 ASexternal2  NH2

Maybe the multiple-next-hops and add-path advocates can kick this
example around for a while.

Curtis

---

From: Enke Chen <[email-masked]>
Date: Thu, 31 Aug 2006 11:35:57 -0700

Hi, Paul:

It is clear from the current discussion thread that we lost some of the 
semantics on the path-id when we merged the relevant documents and went 
through revisions. The intention was to use the router-id or the 
neighboring -AS as the natural path identifiers inside an AS, but that 
was not clear enough in the current version.

In draft-walton-bgp-add-paths-03.txt, there was a "Path Identifier Type" 
defined. With the Path Identifier Type, a BGP speaker will be able to 
tell if a path identifier is a natural id (such as router-id), and will 
not re-generate one for ibgp.

We will clarify this point in the next revision.

-- Enke

Paul Jakma wrote:

> 3-p-n generally is discouraged, it has reliability problems - it's the 
> poor man's substitute for direct peering (usually administrative 
> Its use tends to be primarily because of the /lack/ of eBGP RS solutions.
>
> peers to advertise the path to the RS (and hence all RS-client peers). 
> We can't quite think of them.
>
>> next hop self and provided third party routes with the same next hop 
>> to the RS, there would be no way to make these routes unambiguous.
>
>
> problem the IX operators /want/ solved (they don't care about 3-p-n at 
> all).
>
> E.g. where multiple-hop "restricts" paths advertisements in accordance 
> with (destination,target), the add-path approach on the other hand can 
> make it impossible to reconcile that two paths are identical[2]. In 
> other words, add-path turns BGP into a flooding protocol between 
> contiguous sets of add-path speakers[1].
>
> The problem is, in chasing ultimate flexibility, add-path makes itself 
> a quite inefficient flooding mechanism. BGP paths will be flooded 
> along /every/ possible path between a contiguous set of add-path 
> speakers:
>
> RR2
> / | \
> (P)A | B
> \ | /
> RR1
>

---

From: Curtis Villamizar <[email-masked]>
Date: Thu, 31 Aug 2006 14:50:50 -0400

> Path 2 - NLRI 192/8 AS_PATH {10 20} LOCAL_PREF 189 NEXT_HOP 1.1.1.1

If this came from the same router then complain because the sender of
this is broken.

On the priciple of "being liberal in what you accept" just toss the
second path.

> incorporating ways to indicate which path is being actually used in

If its a multipath it is considering both to be valid.  This may be
possible at an IX if next-hop-self is not set and there is an odd set
of routing policies.  btw- no where in BGP does it require that
routing policies be sane (and they can be seemingly quite wierd).  If
the AS are 65010, 65020, and 65030, this is perfectly valid in an AS
confederation setup.  In AS confederations you'd just forward to
1.1.1.1 but retain the AS paths for readvertising.

> difficult but they need to show this to us. The same goes for

With add-paths the path-id would be used to disambiguate path 1 and
path 2 in the second case so I'm not sure what your point is.

> acceptance. You of all the persons, should be well aware of this.

There seems to be equal or more people arguing in favor of add-paths.
Enke Chen, John Scuder, Robert Raszuk, Jeffrey Haas seem interested.
I'm interested.  I'm less sure about others.  The contributors to this
thread are (alphabetic by first name):

  Curtis Villamizar
  Enke Chen
  Glen Kent
  Jeffrey Haas
  Joel M. Halpern
  John G. Scudder
  Mach Chen
  Manav Bhatia
  Paul Jakma
  Robert Raszuk
  Tulip Rasputin
  Yakov Rekhter

To me it seems comments show interest in multiple-next-hops and
add-path even though the majority of the mail carried
multiple-next-hops in the subject line.

Curtis

---

From: "Glen Kent" <[email-masked]>
Date: Fri, 1 Sep 2006 05:28:52 +0530

Curtis,

> (not setting next-hop self) could result in routes being ambiguous.

Similarly, a minor misconfiguration (of setting as-override) can
result in possible occurances of routing loops.

So whats the point?

Is BGP flawed to not inherently work with misconfigurations around? I
think its a well known that there are infinite ways to axe your foot
with BGP; not setting next-hop-self in IXes would be just one of them.

> multipath set to a minimal set when readvertising.  You can

The idea behind add-paths is to NOT to look at the path attributes.
Moreover, i did not see your views on the scenario given below where
add-paths would result in a lot many Updates?

Glen.

---

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

>the RS in Enke's example.

That is incorrect.  As Enke pointed out (twice now) the AS path will 
be different depending on which peer advertises the route.  As Enke 
also pointed out, the two different AS paths may result in different 
filtering, localpref, etc, by the recipient.

If you want to deprecate third-party next hop, please raise it as a 
separate topic, but I don't think you can just pretend it's 
semantically identical to direct advertisement.

(By the way, if we're going to start deprecating our least favorite 
features of BGP, there are a few I'd like to add to the list. :-)

>overhead of setting it up). Certainly at IXes we know of it is 

N.b. neither Enke, Curtis nor I are entirely lacking in experience 
with IXes, network operations, etc.

>peers). We can't quite think of them.

Again, it's not an either-or.  As detailed above (and in several 
previous messages) since the semantics of the advertisements from the 
direct and third-party advertisers differ (in particular, different 
AS paths may reflect different business relationships) it's quite 
reasonable for both versions of the route to be of genuine use to 
various consumers of the routes.

If there were no way to support third-party next hop and still get 
multiple path support, then I'd be more sympathetic to the argument 
that it's a corner feature which regrettably has to be abandoned to 
enable progress.  But the fact is, it's entirely possible to continue 
to support it.

Also, the fact that one non-obvious casualty of using next hop as 
identifier has been identified leads me to be concerned that others, 
as yet unidentified, may also exist.  BGP is a surprisingly subtle 
protocol, and just because I can't quite think of another bad 
interaction doesn't mean there isn't one.  On the other hand, if one 
picks (or at least, retains the option to pick) an identifier which 
has no other semantics then the risk of such interactions is 
eliminated.

--John

---

From: Curtis Villamizar <[email-masked]>
Date: Thu, 31 Aug 2006 20:40:16 -0400

> result in possible occurances of routing loops.

Unless I'm mistaken, omitting next-hop-self is the default.

> add-paths would result in a lot many Updates?

This is a silly RR configuration.  Two RR within the same RR cluster
for redundancy would not send routes to each other.  If they were
different RR clusters the client A would not be in both clusters.

Anyway it would still work, just have extra routes.

Curtis

---

From: Pedro Roque Marques <[email-masked]>
Date: Thu, 31 Aug 2006 17:35:22 -0700

John G. Scudder wrote:

> identifier has been identified leads me to be concerned that others, as 
> yet unidentified, may also exist. 

I'd like to suggest that rough consensus has been reached that the 
next-hop attribute is not a viable path identifier. Except for the 
authors, is there anyone that doesn't consider this to be a "self 
evident truth" by now ?

   Pedro.

---

From: Curtis Villamizar <[email-masked]>
Date: Thu, 31 Aug 2006 21:14:00 -0400

In message <[email-masked]>
Curtis Villamizar writes:

> Unless I'm mistaken, omitting next-hop-self is the default.

Forgot to mention that configuring AS-override results in a violation
of the BGP spec and therefore need not be considered.  Third party
next hop is explicitly mentioned in the BGP spec in "5.1.3. NEXT_HOP"
on page 26 and it is perfectly legal to use this feature.

Curtis