Subject: Re: [Idr] Advancing add-path

From: Andy Davidson <[email-masked]>
Date: Tue, 18 Mar 2014 10:59:39 +0000

Hi,

Nick Hilliard wrote in November 2013:
> the ixp community is interested in add-path/ebgp, as it solves
> a bunch of rather nasty scaling issues on route servers.

Sorry for email latency but the nasty scaling issues just got a plug at an IX Operators meeting (as it feels like it has every few months for the last five years), leading to me wanting to offer support for any useful add-path/ebgp work.  We'd really appreciate it.

Best wishes,
Andy Davidson
(LONAP/IXLeeds/Euro-IX)

---

From: "Susan Hares" <[email-masked]>
Date: Tue, 18 Mar 2014 10:30:27 -0400

Andy:

Thank you for this note.  John and I will look at putting this put
standardizing this work on a fast path.

Sue Hares

-----Original Message-----
From: Idr [mailto:[email-masked]] On Behalf Of Andy Davidson
Sent: Tuesday, March 18, 2014 7:00 AM
To: [email-masked]
Subject: Re: [Idr] Advancing add-path

Hi,

Nick Hilliard wrote in November 2013:
> the ixp community is interested in add-path/ebgp, as it solves a bunch 
> of rather nasty scaling issues on route servers.

Sorry for email latency but the nasty scaling issues just got a plug at an
IX Operators meeting (as it feels like it has every few months for the last
five years), leading to me wanting to offer support for any useful
add-path/ebgp work.  We'd really appreciate it.

Best wishes,
Andy Davidson
(LONAP/IXLeeds/Euro-IX)

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

---

From: "Juan Camilo Cardona" <[email-masked]>
Date: Tue, 18 Mar 2014 15:59:24 +0100

Hello Andy, all,

At the last IETF, we presented draft-francois-idr-rs-addpaths-00
(https://datatracker.ietf.org/doc/draft-francois-idr-rs-addpaths/). The idea
of the draft is to describe in detail the use of add-path between an EBGP
route server and its clients. If possible, please take a look at it. Any
feedback on the document would be greatly appreciated.

Best regards,

Camilo Cardona

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] 
Sent: viernes, 07 de febrero de 2014 16:11
To: Jeffrey Haas; Jeffrey Haas; Pierre Francois; Adam Simpson; Camilo
Cardona; Adam Simpson; Camilo Cardona; Pierre Francois
Subject: New Version Notification for draft-francois-idr-rs-addpaths-00.txt

A new version of I-D, draft-francois-idr-rs-addpaths-00.txt
has been successfully submitted by Camilo Cardona and posted to the IETF
repository.

Name:		draft-francois-idr-rs-addpaths
Revision:	00
Title:		ADD-PATH for Route Servers
Document date:	2014-02-07
Group:		Individual Submission
Pages:		6
URL:
http://www.ietf.org/internet-drafts/draft-francois-idr-rs-addpaths-00.txt
Status:
https://datatracker.ietf.org/doc/draft-francois-idr-rs-addpaths/
Htmlized:       http://tools.ietf.org/html/draft-francois-idr-rs-addpaths-00

Abstract:
   BGP speakers in Internet Exchange Points exchange routes with a large
   number of peers.  To reduce the burden of maintaining many sessions,
   IXPs implement and administrate BGP route servers.  Route servers
   announce to their clients the paths of multiple peers by using a
   single eBGP session.  Route servers, however, are restricted to
   propagating a single path per NLRI per eBGP session.  This constraint
   affects the path diversity received by clients, which could use paths
   that they would not have chosen, had they known all possible paths.
   To overcome this limitation, we propose in this draft the extension
   of ADD-PATH to eBGP peers in the context of route servers.

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

The IETF Secretariat

-----Original Message-----
From: Idr [mailto:[email-masked]] On Behalf Of Andy Davidson
Sent: martes, 18 de marzo de 2014 12:00
To: [email-masked]
Subject: Re: [Idr] Advancing add-path

Hi,

Best wishes,
Andy Davidson
(LONAP/IXLeeds/Euro-IX)

---

From: Thomas Mangin <[email-masked]>
Date: Tue, 18 Mar 2014 15:14:13 +0000

Hello Camilo,

I would like the document to cover more clearly the "mix mode" operation (when only some of the peers do support the feature).

I believe the draft could could gain from more clarity on how the RS should select which path to select if draft-francois-idr-addpath-limit is implemented too.
At least one RS operator reported having over 90k best path already and were wondering how it would affect the RS.

Following the very positive feedback of IX operators at Euro-IX today, I will be adding RS support for ExaBGP with support of your draft and will share with you any relevant experience  ..

Sincerely,

Thomas

---

From: Pierre Francois <[email-masked]>
Date: Tue, 18 Mar 2014 16:15:46 +0100

Thomas, 

We'll do that (mixed mode operation)

Great to hear about the feedback you received at Euro-IX ;)

Cheers, 

Pierre.

---

From: Andy Davidson <[email-masked]>
Date: Wed, 19 Mar 2014 08:14:41 +0000

Hi,

Juan Camilo Cardona wrote:
> The idea of the draft is to describe in detail the use of add-path 
> between an EBGP route server and its clients. If possible, please 
> take a look at it. Any feedback on the document would be greatly
> appreciated.

It's a great description of the problem statement.  Thanks for your hard work.  I have a number of small suggestions which I hope are not contentious.

I would perhaps recommend explicitly stating in the abstract that multiple paths *and next hops* are distributed in a single session for clarity because newcomers to the subject may otherwise spend time trying to figure out how path selection can be communicated between peers when in the context of a route-server it's simply necessary to select one next-hop or another.  This is hinted in section 4 (Error conditions) but may help clarity to drop into the abstract.

In the motivation section there is a third motivation to perform this work - a peer that advertises a route to the route-server, which is selected as the best path by the route-server, may be hidden from a second IXP peer due to policy which is expressed between the sending party and the route-server even though an alternative path exists and is valid for the same second IXP peer.  This is subtlety different from the first motivation, which implies the peer may get both paths and next hops and makes a policy decision.  In this case the peer does not get the option of selecting the prefix at all.  This is combatted today using multiple RIBs (one best path selection per participant).  This is a scaling challenge that IXPs would like to avoid with ebgp addpath.

I think that "we" need to do some work on the handling of withdraws as I would like to see :
 - Consistent behaviour explicitly defined so that route-server implementations behave the same way.  IXPs tend to have a preference to run multiple route-server vendors for resilience.
 - Implicit withdraw behaviour on clients should be tested to ensure that the route-server client behaves in the same way
 - It may be that consistency can only be assured if withdraws for routes advertised in add-path enabled route-server sessions are all explicit ?

Thanks again for your hard work.
Andy

---

From: "Juan Camilo Cardona" <[email-masked]>
Date: Wed, 19 Mar 2014 13:00:51 +0100

Andy, all,

Thank you very much for your comments. We will sure consider all of them for
the next version of the document. More comments inline. 

Camilo Cardona

-----Original Message-----
From: Andy Davidson [mailto:[email-masked]] 
Sent: miércoles, 19 de marzo de 2014 9:15
To: Juan Camilo Cardona; [email-masked]
Subject: RE: [Idr] Advancing add-path

Hi,

Juan Camilo Cardona wrote:
> At the last IETF, we presented draft-francois-idr-rs-addpaths-00 The 
> idea of the draft is to describe in detail the use of add-path between 
> an EBGP route server and its clients. If possible, please take a look 
> at it. Any feedback on the document would be greatly appreciated.

It's a great description of the problem statement.  Thanks for your hard
work.  I have a number of small suggestions which I hope are not
contentious.

I would perhaps recommend explicitly stating in the abstract that multiple
paths *and next hops* are distributed in a single session for clarity
because newcomers to the subject may otherwise spend time trying to figure
out how path selection can be communicated between peers when in the context
of a route-server it's simply necessary to select one next-hop or another.
This is hinted in section 4 (Error conditions) but may help clarity to drop
into the abstract.

CC: Agree

In the motivation section there is a third motivation to perform this work -
a peer that advertises a route to the route-server, which is selected as the
best path by the route-server, may be hidden from a second IXP peer due to
policy which is expressed between the sending party and the route-server
even though an alternative path exists and is valid for the same second IXP
peer.  This is subtlety different from the first motivation, which implies
the peer may get both paths and next hops and makes a policy decision.  In
this case the peer does not get the option of selecting the prefix at all.
This is combatted today using multiple RIBs (one best path selection per
participant).  This is a scaling challenge that IXPs would like to avoid
with ebgp addpath.

CC: Agree. This was a big motivation we had when writing this draft and we
will make sure that it is clearly stated in the text.

I think that "we" need to do some work on the handling of withdraws as I
would like to see :
 - Consistent behaviour explicitly defined so that route-server
implementations behave the same way.  IXPs tend to have a preference to run
multiple route-server vendors for resilience.
 - Implicit withdraw behaviour on clients should be tested to ensure that
the route-server client behaves in the same way
 - It may be that consistency can only be assured if withdraws for routes
advertised in add-path enabled route-server sessions are all explicit ?

CC: Don't you think that the ADD-PATH draft already defines the procedures
that take care of handling withdraws (using path-ids) and these should also
apply to an IXP-RS environment?

---

From: "Chris Hall" <[email-masked]>
Date: Fri, 21 Mar 2014 15:54:41 -0000

Thomas Mangin wrote (on Tue 18-Mar-2014 at 15:14 +0000):
...
> I would like the document to cover more clearly the "mix mode"
> operation (when only some of the peers do support the feature).

RS-Clients which don't support add-paths would continue to need the
services of a draft-ietf-idr-ix-bgp-route-server-04, wouldn't they ?

> I believe the draft could could gain from more clarity on how the
> RS should select which path to select if draft-francois-idr-
> addpath-limit is implemented too.

It seems to me that limiting the number of paths which the RS may
advertise Add-Paths-wise is the worst of all possible worlds :-(

Add-Paths is most useful if the RS is no longer required to do *any*
selection at all on behalf of its clients.

If the RS is required to limit the number of paths for prefix 'p'
advertised to client 'Z' on a first-come-first-served basis that would
complicate things, but perhaps not hugely.

But if the RS is required to select the "best" 'n' paths out of the
'm' which are available to client 'Z', then this looks like *more*
work than the current situation where n==1 !

> At least one RS operator reported having over 90k best path already
> and were wondering how it would affect the RS.

Not as easy a question to answer as one would hope :-(

Your current RS is doing proxy route selection on behalf of the
client, so there is the cost of the per-client Loc-RIB and selection
process.  In theory the RS should also do proxy 'In' filtering -- as
if the clients were peering directly (though this does not seem to be
done much in practice).  The RS also needs to implement the "peering
matrix" -- some clients want to control the distribution of all or
some of their routes.  It is common practice to implement the "peering
matrix" function in the extra 'In' filtering stage... Communities
control which clients each route is announced to.  So, the other cost
is the extra filter stage(s) on the way into the per-client Loc-RIB.

Moving *all* the selection work out to the client removes the need for
the extra 'In' filtering and the per-client Loc-RIBs.  Yay !

In a "pure peering" IXP most prefixes only have one route, so the
selection process itself is not a lot of work, but managing the
per-client Loc-RIB is a memory overhead.  Much of the cost in the RS
is on the outbound side... sending ~100k+ routes to ~400+ clients and
managing the Adj-Out.  (With only one route per prefix there is not
much difference between the per-client Loc-RIB and the per-client
Adj-Out.)

To reduce the work inside the RS to a minimum, the trick might be to
ditch the Adj-Out as well: no MRAI, no tracking outbound updates, no
debouncing changes, no packing of prefixes into UPDATE messages... So
that the RS operates as a straight "broadcaster" of
Announcements/Withdrawals as they appear on the Adj-In side -- subject
only to the "peering-matrix" filtering on the way out.  (The Add-Paths
"Path Identifier" would effectively be a "Client Identifier", until
such time as the RS allowed multiple in-coming paths per client.)  Of
course, this assumes that the client's BGP doesn't get too twitchy
about repeat announcements or withdrawals without a previous
announcement.

Chris

---

From: Thomas Mangin <[email-masked]>
Date: Fri, 21 Mar 2014 16:22:12 +0000

> services of a draft-ietf-idr-ix-bgp-route-server-04, wouldn't they ?

IMHO, it should simply continue to behave as it does currently, as peers will only send one path the the RS, only the RS will send multiple path.

> complicate things, but perhaps not hugely.

It was my initial thought but others may see things differently.

> the extra 'In' filtering and the per-client Loc-RIBs.  Yay !

it is likely that community filtering will still be required, but this is trivial.

> ditch the Adj-Out

Resending extra NLRI should not harm the router but this point is quite orthogonal to this draft.

> [...] no packing of prefixes into UPDATE messages...

I am not following you here. The incoming UPDATE will only contain one route per NLRI. I can not see the gain you see.
The capability negotiated may be different between each peer too so update generation is not affected neither AFAICS.

Thomas

---

From: "Chris Hall" <[email-masked]>
Date: Fri, 21 Mar 2014 17:58:11 -0000

Thomas Mangin wrote (on Fri 21-Mar-2014 at 16:22 +0000):
....
> On 21 Mar 2014, at 15:54, Chris Hall wrote:
....
> > advertised to client 'Z' on a first-come-first-served basis that
> > would complicate things, but perhaps not hugely.

> It was my initial thought but others may see things differently.

I cannot say this is an approach I much like... I think it would be
better if the RS sent everything it had available (for each client)
without having to think much (or at all).  But if clients live in fear
and trembling of being bombarded with an indefinite number of routes,
then some kind of clamp is required -- which is not too too
terrifying, provided the result is understood to be "less than
optimal".  But it does require some adj-out to be retained :-(

> > Moving *all* the selection work out to the client removes the
> > need for the extra 'In' filtering and the per-client Loc-RIBs.
 
> it is likely that community filtering will still be required, but

To implement the "peering matrix" ?  Or for other reasons ?  For the
"peering matrix" the community filtering would move from the current
extra 'In' filtering to the 'Out' filtering.  This doesn't save work,
it just moves it from one place to another.

[I have seen RS configurations where the "peering matrix" filtering
was done at the 'Out' stage... but that leads to "Path Hiding" and
possibly other states of sin :-(]

> > To reduce the work inside the RS to a minimum, the trick might
> > be to ditch the Adj-Out

> quite orthogonal to this draft.

If the RS is to be given licence to send duplicate announcements and
unnecessary withdraws, which the RFCs at the very least discourage,
and which might be flagged as exceptions by some implementations, then
I would like to see that acknowledged somewhere.  (I agree that such
licence is not strictly anything to do with using Add-Paths, but the
wish for such licence is.)

> I am not following you here. The incoming UPDATE will only contain
> one route per NLRI. I can not see the gain you see.

The adj-out implementation I am most familiar with has a mechanism to
collect together pending NLRI which share the same outgoing
attributes.  Ditching the adj-out altogether would dispense with that
too.  So, what I'm thinking is that incoming UPDATEs would be
broadcast to clients almost verbatim... without attempting to improve
on the packing of NLRI in UPDATE messages.

Chris

---

From: Ondrej Zajicek <[email-masked]>
Date: Sun, 23 Mar 2014 03:23:14 +0100

On Tue, Mar 18, 2014 at 10:59:39AM +0000, Andy Davidson wrote:
> Sorry for email latency but the nasty scaling issues just got a plug
> at an IX Operators meeting (as it feels like it has every few months for
> the last five years), leading to me wanting to offer support for any
> useful add-path/ebgp work.  We'd really appreciate it.

Hello

There is a simpler way how to fix scaling issues on route servers than
add-path - it is based on idea that instead of keeping N routing tables
and doing N best path selections for each prefix, RS would keep just one
table with paths for each prefix sorted according to path selection
criteria [*] and for each client it exports the first path (in that
order) that is accepted by client's export filter.

This implements per-client policy control without the overhead of
maintaining multiple route server RIBs. Overhead of this solution is (i
guess) even smaller than overhead of a solution based on add-path
(executing export filters vs. propagation of all available paths). It
could also be easily combined with the add-path approach (some neighbors
receive just best paths, some receive all paths using add-path)

We have implemented and tested this approach and it cuts down memory
consumption on NIX.CZ RS to 1/7 compared to the usual multiple RIBs
approach. See slides 13-18 of:
http://www.nanog.org/meetings/nanog57/presentations/Wednesday/wed.general.Filip.BIRD.16.pdf

There are applications for add-path on route servers, but instead of
scalability, add-path is useful for two other reasons:

1) It allows to keep client-specific routing policy completely on
clients, no need to propagate it to RS through communities or other
means. Note that to use this advantage, add-path cannot be limited to
fixed number of paths.

2) Load balancing / multipath for clients' traffic. For this usage,
just a few equally good paths are needed so limited add-path
is enough, but diverse-path approach could also be used here.

[*] although path selection criteria as specified by RFC 4271 are not
proper ordering, there are some issues with MED selection vs. IGP
metric, but these could be ignored in RS use case.

-- 
Ondrej 'Santiago' Zajicek

---

From: Robert Raszuk <[email-masked]>
Date: Sun, 23 Mar 2014 11:01:11 +0100

Hi Ondrej,

> RS would keep just one

Are you applying the client't policy at the update generation or you
run multiple best paths (one for each client) ?

When exactly do you set the advertise bit to keep track which client
got which path ?

-- 

Implementation of RS I have proposed and which has been deployed uses
a hybrid approach.

It keeps global table just like in your case for vast majority of
paths/clients.

However for those clients with specific policy we only export the nets
subject to such policy with all the paths to dedicated contexts (you
may call it bRIBs or VRFs). That way in most deployments we do not
need to have full RIB per client.

During update generation we walk two tables .. global and the delta
context one so client get's fully customized view without any
significant burden on the RS scale and cpu.

To make it more interesting if we would get into scaling there is
always an idea to export to contexts only references rather then
copying the actual bgp data across memory.  But for all tests based on
the production deployments of RS we were pretty far from any scaling
limits.

Best,
R.

On Sun, Mar 23, 2014 at 3:23 AM, Ondrej Zajicek <[email-masked]> wrote:
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.9 (GNU/Linux)
>
> iEYEARECAAYFAlMuRZIACgkQw1GB2RHercOhAwCeMGQuo9yeShUUVNqB1b1tFS3o
> p0wAmgJdJFpqqnVuTK2vv0/5aG4mtvZO
> =LaJB
> -----END PGP SIGNATURE-----
>