Subject: Re: [Idr] multiple-next-hops vs add-paths : AS confed example

From: Enke Chen <[email-masked]>
Date: Thu, 31 Aug 2006 22:13:07 -0700

Hi, Curtis:

I went through your example, and agreed that the (prefix, nexthop) is 
not adequate to disambiguate paths in your example.

It seems to me that there is a problem with using (prefix, nexthop) as 
key even in this simplified version:
 
                               |
   ASe1 - R1/NH1 |----- R3/AS65001
                               |                                    \
                               |                                     
R5/AS65003 - R6/AS65004
                               |                                     /
                               | -------  R4/AS65002 

R5 would receive paths from R3 and R4 with the same nexthop but 
different as-paths. If we were to emulate full-mesh, R5 would need to 
advertise both paths to R6, which would not be possible with (prefix, 
nexthop) as the key.

As the full-mesh is the most robust BGP configuraiton we know, it seems 
fundamental that a multi-path extension should offer the ability to 
emulate the full-mesh.

-- Enke         

Curtis Villamizar wrote:

>There was no response to my AS confed example probably since it was at
>the end of a long message and changed the topic.  So I'm resending the
>example as a separate message.
>
>Curtis
>
>
>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.
>
>_______________________________________________
>Idr mailing list
>[email-masked]
>https://www1.ietf.org/mailman/listinfo/idr
>  
>

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

---

From: Enke Chen <[email-masked]>
Date: Thu, 31 Aug 2006 22:22:21 -0700

Well, the drawing (for the simplified version) did not come out right.  
The simplified version basically merged R2 into R1, and put R1, R3 and 
R4 on a LAN.

                       R1  -----|------- R3 ---\
                                     |                      R5 - R6
                                     |--------R4 ---/

-- Enke

Enke Chen wrote:

> As the full-mesh is the most robust BGP configuraiton we know, it 
> seems fundamental that a multi-path extension should offer the ability 
> to emulate the full-mesh.
>
> -- Enke        
> Curtis Villamizar wrote:
>

---

From: Paul Jakma <[email-masked]>
Date: Fri, 1 Sep 2006 08:02:19 +0100 (IST)

Hi Curtis,

On Thu, 31 Aug 2006, Curtis Villamizar wrote:

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

> the components of this multipath.

Right, as they are in fact the same path, so they can not be 
disambiguated. The same path has been received with differing 
attributes.

Aside: Note that R5 would not receive the above paths. R3 and R4 will 
each only describe one (NLRI,nexthop) to R5. However, I don't think 
it's of consequence to your point - it just shifts to R3/R4 (right?).

> the AS path is correct.

That's a question which speakers have long faced, hence which is 
answered already by the existing BGP RFC.

> It seems that the <peering,prefix,path-id> tuple adds an ability to 
> disambiguate this case.

Except the very notion of wanting to disambiguate the exact same 
path, in order to flood multiple copies of the same path onward to 
the same neighbours, is undesireable at best.

It has substantial implications for convergence, see my previous 
email to you. Implications which Enke seems to accept, and has 
indicated are to be addressed in a new revision of add-path.

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
Being a mime means never having to say you're sorry.

---

From: Curtis Villamizar <[email-masked]>
Date: Fri, 01 Sep 2006 13:30:07 -0400

> answered already by the existing BGP RFC.

The existing BGP RFC does not accommodate multipath.

> indicated are to be addressed in a new revision of add-path.

Given the choice between "doesn't work" and "might converge slowly"
I'll take door number two.  Thank you.  :-)

A provider can always configure either one for no BGP multipath and
get the plain old BGP behaviour.  In one case things don't work
otherwise and in the other case convergence might be slower.

With multiple-next-hops R5 either cannot advertise the multipath
correctly or must advertise it with an AS-Set.  It gets a little
messier if there is more than one AS in the parallel part of the
path but still doable.  In this case the advertisement would have to
be:

  AS65003 [AS65001 AS65002] ASexternal1 NH1
  AS65003 [AS65001 AS65002] ASexternal1 NH2

If the connection through R4/AS65002 went down then the multipath
would have to be changed to:

  AS65003 AS65001 ASexternal1 NH1
  AS65003 AS65001 ASexternal1 NH2

The same thing is happenning except add-path allows the four
components to remain separated and allows the two that broke to be
explicitly withdrawn rather than changing the AS-Set.

I thought we were trying to avoid using AS-Set and changing the AS-Set
as the route changes.  Policy is usually not an issue with confeds
since policy is usually to accept everything but the objection to
using AS-Set was that policy may accept one AS in the set and reject
another.

Curtis

---

From: Paul Jakma <[email-masked]>
Date: Sun, 3 Sep 2006 00:14:04 +0100 (IST)

On Thu, 31 Aug 2006, Enke Chen wrote:

> As the full-mesh is the most robust BGP configuraiton we know,

Agreed.

> it seems fundamental that a multi-path extension should offer the 
> ability to emulate the full-mesh.

Let's be quite clear here, /neither/ proposal before the WG emulates 
full-mesh.

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
Money is truthful.  If a man speaks of his honor, make him pay cash.
 		-- Lazarus Long

---

From: Enke Chen <[email-masked]>
Date: Sat, 02 Sep 2006 16:42:22 -0700

> Let's be quite clear here, /neither/ proposal before the WG emulates 

I disagree. Granted there are ambiguties on the path-id and that is 
being fixed.  However, if RRs use the router-id as the path-id, and 
advertise all the (prefix, router-id) in a network, that would result in 
the same amount of routing information available in a network as the 
current full ibgp mesh. (By full-mesh I meant "full ibgp mesh".)

-- Enke

---

From: Paul Jakma <[email-masked]>
Date: Sun, 3 Sep 2006 01:24:53 +0100 (IST)

On Sat, 2 Sep 2006, Enke Chen wrote:

> I disagree.

Fair enough. Let me explain why, so. :)

E.g. to refer to an example given against next-hop (path is 
originated/sent by A on):

           B
          / \
 	A   C--E
          \ /
           D

- The objection to next-hop was that C would have to lose path
   information, and pick between either A_B or A_D, before advertising
   the path onward to E.

   Note that using router-ID has the *same* restriction.

   (indeed for any topology of identifiers (i.e. no matter what
   identifier you pick), the above holds true within that topology - a
   trivial conclusion).

- If there were a full-mesh, there would be no such 'intermediate'
   path-information.

- If instead you allow unrestricted flooding, you are propogating
   /more/ paths than a full-mesh would. You are instead having the
   protocol describe the /full/ complexity of the topology - far more
   so than full-mesh, and that complexity scales at amazing rates
   (even more than full-mesh..)

The whole point of introducing intermediaries (such as RRs) is to 
allow one to take advantage of the topology to *reduce* the 
information that needs to be carried between speakers.

If you go with the "pick IDs out of thin air" approach[2], it would 
be more efficient to *get rid of RRs altogether* and revert to 
full-mesh, other than for the most trivial topologies, as full-mesh 
is a more efficient distribution mechanism than unrestricted 
flooding[1].

If you pick a specific and stable ID, then you are accepting 
essentially the same restrictions which apparently are so problematic 
for multiple-hop.

> being fixed.

We await the next revision with interest! :) I'm curious what 
restrictions you are going to add..

> However, if RRs use the router-id as the path-id, and 
> advertise all the (prefix, router-id) in a network, that would 
> result in the same amount of routing information available in a 
> network as the current full ibgp mesh.

Nope. You're subject to the /same/ flooding restrictions as next-hop 
(but in the 'plane' of router-ID, rather than next-hop).

A speaker has only one router-ID though, where it potentially may 
have multiple nexthop identifiers it already is using in the messages 
it sends...

1. Indeed, rather than adopt some unrestricted-flooding multiple-path
    draft, a better solution instead would be to investigate how
    peering session configuration could be made more automated,
    something which speakers can implement locally, not much need for
    any IDR RFC at all. (4271 already mentions 'wildcard' sessions
    too).

2. "Use Router-ID when possible, but pick out of thin air if there's
     a clash" is the same thing, obviously.

mise le meas,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
For a man to truly understand rejection, he must first be ignored by a cat.

---

From: Curtis Villamizar <[email-masked]>
Date: Sat, 02 Sep 2006 20:56:55 -0400

In message <[email-masked]>
Paul Jakma writes:

> Fair enough. Let me explain why, so. :)

Lost a lot of context here but ..

I have to agree with Paul on this.  The idea of using the router-id as
a path id is at least as seriously flawed than using the next-hop.

Curtis

---

From: Jeffrey Haas <[email-masked]>
Date: Tue, 5 Sep 2006 12:34:31 -0400

> information that needs to be carried between speakers.

I would suggest a little cautious thinking about this.

Route reflectors and confederations reduce the meshiness of a 
peering topology.  I wasn't around while these mechanisms were
being developed, so I couldn't comment on whether the inherent
reduction in routes was an intentional feature or not.  Certainly
reducing the number of peering sessions was a consideration.

It is possible that damping of MED oscillations can be done
striclty within the reflection mesh.  The edges of the network
may not need to be aware of the additional route instances.

I would suggest that before we get crazy about saying a solution
is "as bad as full mesh" that we ponder the problems and solutions
a bit more first.  Don't put words in other people's proposals, comment
on what's actually there. :-)

Personally, I'm waiting to see add-paths++.

-- Jeff

---

From: "Tony Li" <[email-masked]>
Date: Tue, 5 Sep 2006 10:13:45 -0700

> reducing the number of peering sessions was a consideration.

Yes, reducing the number of routes was a consideration, but was
secondary to reducing peerings.  One early iteration at route reflectors
simply reflected ALL information.  We decided that the RR should prune
as best it could instead.

Tony

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 05 Sep 2006 13:56:25 -0400

> reducing the number of peering sessions was a consideration.

-- A history lesson.  Probably about as accurate as the history
   lessons of the famous Professor Peabody [1].
   [1] Rockie and Bullwinkle
   We all know that using a format that looks like citations makes
   your email more credible - right Paul.  :-)

In ancient times prior to RR or confed the NSFNET used one AS per POP.
Only the core was in the backbone AS, AS690 (or whatever it was in T1
days, I forgot already).  The separate AS served two purpose.  One
that may have come by accident was that it allowed an easy transition
from the T1 backbone to the T3 backbone in 1991/1992.  The other is
that it greatly reduced the number of peerings.  [Yakov would problably
know the motivations which may have to do with the way ISIS was seen
as evolving - NSFNET used a pre-ISIS IGP later given the name SLSP
(simple link state protocol) by Dennis Furgusson before it was
replaced with OSPF).]

The network close to the edges (called regions by some) for all
providers, not just the NSFNET, were from a practical standpooint star
topologies, with customers backhauled to the POP.  In these regions
there were two kinds of customer, those that did BGP and those that
didn't.  Those that didn't were easy to handle.  Before RR to do it
right every customer that did BGP would have to peer with every other
BGP speaking customer in that region.  Adding a BGP speaking customer
involved changing the configuration at every other BGP speaking
customer's CPE router.  RR was born initially as a Cisco feature but
wasn't standardized until much later (and evolved a bit).

There were complaints that the NSFNET was hoarding AS numbers by using
nearly 20 for their backbone.  Other providers were seeing problems
with too many IBGP peerings and too many routes resolved at the IGP
step pushing the limits of their router memory so it was hard to
complain too vigorously.  These routes resolved at IGP step were
responsible for duplicate copies of lots of routes in the Adj-In RIB.
The idea of using private AS numbers was proposed.  AS confeds was
born and UUNET may have been the first to make use of them.  Again, it
was standardized later, but in this case soon after.  [Again others
may have more accurate memory of this evolution.]

However is came about, at that point some of the major providers were
either using lots of AS (only NSFNET afaik) or confeds in the core and
almost all providers were using RR near the edges of their network.

Somewhere along the line people started using RR within the core
rather than confeds and then we had to deal with oscillation problems.
Some people think that RR or confed is somehow broken and that's why
we have oscillations.  I personally think that the definition of MED,
comparing only within the same AS, was broken from the start, but
we're stuck with it.  So here we are trying to fix it.

> may not need to be aware of the additional route instances.

Originally RR was intended for just the star network at the edges.
There was nothing to prevent it from being used elsewhere.

BGP certainly has been successful in providing plenty of rope with
which to hang oneselves.

> Personally, I'm waiting to see add-paths++.

Yes.  Lets wait for add-paths++ and ignore all versions prior to
that.

Curtis