BGP4/CIDR/aggregation presentations

Fri Feb 11 20:30:17 UTC 1994

These are some notes that I made as I was preparing my presentations
for the RegTechs meeting in San Diego Jan31/Feb 1.  I have revised them
(some what) in light of some of the conversations & presentations made
at the RegTechs meeting.

There are undoubtably holes & inaccuracies in these notes; please
correct any that you see.
	--asp at uunet.uu.net (Andrew Partan)

BGP4 deployment status

There are not that many folks that have deployed BGP4 yet.  This
is not good.

So far, AlterNet, Ebone, SprintLink, ICMnet, EUnet, TIPnet, PIPEX, and
AS1133 (CERN) have deployed BGP4 (that I know of).  ANS is behind their
announced schedule.  This list is incomplete (I sure hope that there
are other folks out there that are running BGP4 that I do not know
of).  Europe seems to be further ahead than the US (I have heard that a
number of European networks are using BGP4; but I don't have a list).

Not all of these folks are running BGP4 between them yet - e.g.: the
AlterNet/AS1133 link is still BGP3.

People are not making public their BGP4 deployment plans, nor are they
making their routing plans public (ala the RIPE routing registry
database).  Without this data, it is really hard to know when or if we
can announce CIDR routes safely.

There are already CIDR-routes (non A/B/C routes) that are being
announced in the Internet today.  When I last checked (Sunday 1/30/94),
all but one of the more specific routes (the A/B/C nets) were also
being announced.

BGP4 is real; BGP4 works; people need to deploy it; people need to
deploy it now.

We still don't know all of the folks that need to deploy BGP4.
We still don't know what will break if CIDR routes are used.

Implementation status:

Cisco code is working & deployed in most of the nets that are
running BGP4.  Gated code is working & deployed on AS 1133.  3com
code is working on the BGP4 test net.  I don't know the status of
any other code.

Why is it so important that we get BGP4 & CIDR working & working now?

Routing table growth.

16 Meg ciscos may only be able to support 25K-30K routes.  [The
jury is still out on this one; cisco is continuing to improve their
code to put more routes into the same amount of memory.  cisco is
also looking at 64 Meg routers.]

Peter Lothburg took a look at his routers (Ebone & ICMnet) and found
that he could only support approx 18K routes total!

On ciscos (at least), the number of routes that you can support depends
on how much free memory you have - memory is used for the forwarding
table, the routing table, and for updates (and other things).  The more
destinations you see the larger your forwarding table is - so central
routers (like ICMnet & Ebone) will have more memory used for forwarding
tables.  Routing table size is the total number of routes you have plus
how many different paths you have to each of those routes (the Ebone
and ICMnet see nearly every route with something like 5 paths).
Routing updates use memory for both incoming updates from your peers
(eBGP & iBGP) and for outgoing updates (most notably for iBGP peers -
since every incoming update from an eBGP peer is (typically) sent to
every iBGP peer).  The more routing updates you get (the more unstable
the overall network is), the more memory you will use.  Central routes
tend to see lots more updates (this is not entirely true since cisco's
BGP4 code has some dampening of updates - they delay forwarding updates
for a short while, so that if a net goes down & then back up fairly
quickly, you may not see any update at all downstream).

When ciscos start running out of memory, they try to conserve memory by
delaying processing of incoming updates and sending of outgoing updates
(rather than just hitting the wall & tipping over).  This means that
routing may take longer to stablize & may not ever stablize as things
get really bad.

In any case, Peter's routers have about 1.9 Meg free today; AlterNet
routers have approx 4 Meg free - the same number of total routes, but
different routing policy and (probably) fewer destinations, updates,
and paths.

The ANS ENSSs may only be able to support 25K routes.  [ANS thinks that
they can up this by another 5K routes to a total of 30K.]

We are now at 16,788 routes (as of 1/30/94 17:00 EST).
[17,410 as of 2/11/94, 14:00 EST.]

I did some analysis of routing table growth from a number of
different angles, and all pointed to running out of memory by mid
summer (unless we do something).  [This used 25K as the drop dead date -
we should be hitting 18K in about 1.5-2 weeks.]

The growth rate seems to be 1000 net every 3 weeks.

[I looked at routing table sizes & growth over the last few months;
also at current doubling time (9 months; ref ALE working group);
also at free memory usage in my routers.  All of my projections
came out with approx the same drop dead date of mid summer.  I also
did not leave any memory for things like packets, so my dates are
overly optimistic.]

[I also looked at some data provided by Merit (their active net
counts), and their projections agree very closely with mine - approx
mid summer for 25K routes and 1000 nets every 3 weeks.]

We need to attack the routing table size on a number of fronts -
router vendor code changes (to use less memory per route), router
hardware changes (to add more memory), changes in routing policies
(things like more use of default routes & suboptimal routing),
newer routing protocols (that do not need full routing tables on
a large number of routers; things like route servers), and BGP4/CIDR
deployment.

The one that seems to be the easiest & quickest to deploy is
BGP4/CIDR.

The problem is that if I CIDRize my own routes, I can save about
1000 routes in my own tables (and push death off by maybe a month
or so).

I need you to CIDRize your routes to save space in my routing
tables.

I could also proxy aggregate your routes, but proxy aggregation is
hard.  If I hear your routes via several possible paths, and if
the same aggregation is not done in the same way on all of the
paths, then traffic may go over suboptimal paths (since traffic
always takes a more specific route over a less specific route).

Proxy aggregation is doubly hard, if I don't know about all of the
possible paths that I could hear your routes over.

[There was some discussion about where it was safe (or safer) to do
proxy aggregation - basically it all boils down to knowing the (local)
topology and lots of communication between the parties involved.]

This gets to routing registries.

People have to publish their routing policies in some public place
so that other people can look at these policies and try to figure
out if some change that they are contemplating (like announcing
CIDR routes) will cause problems elsewhere in the Internet.

These routing policies need to be in some common format, so that
tools can use them.

The only such database that I know of is the RIPE database.  People
should use this.  Two folks from RIPE will be giving a talk on this
later (Daniel Karrenburg & Tony Bates).  [Merit will also be doing a
routing policy database & is going to coordinate with the RIPE folks.
The Merit & RIPE folks should be able to say more on this.]

A bit more on proxy aggregation.

If you know the local topology well enough, and if there is
communications & coordinations among the people involved, you can do
proxy aggregation safely.

A couple of examples:

BGP4 network 'B' connects to non-BGP4 stub network 'S'.
S has no other connections to the rest of the world.
	B --- S
B can do proxy aggregation of S's nets.  [Note that B can probably
proxy aggregate w/o even talking to S, but this is probably a bad
idea.]

BGP4 network 'B' connects to non-BGP4 network 'S'.
'S' has just one other connection to non-BGP4 network 'T'.
T has no other connections to the rest of the world.
	B --- S --- T
B can do proxy aggregation of S's and T's nets.

BGP4 network 'A' connects to non-BGP4 network 'S'.
BGP4 network 'B' connects to non-BGP4 network 'S'.
S has no other connections to the rest of the world.
	A --- S --- B
A & B can do proxy aggregation of S's nets.  Note that A and B need to
do the *same* proxy aggregation, or things may not work (routing follows
the most specific route).

There are other examples; they all depend on complete knowledge of the
(local) topology and coordination between all of the parties involved.

Obviously as the topology gets more complex, and the number of parties
grows, this gets to be a harder & harder problem.

Some of the conclusions on deployment of BGP4/CIDR

People are deploying BGP4; the code seems to be working just fine.

People are going to be announcing CIDR routes and doing proxy
aggregation fairly shortly (like w/in the next week or so).  Partially
this is a matter of self defense, so that routers don't tip over.

It looks like things will work, if there is a large enough BGP4 core,
and if people are either part of the BGP4 core or have a default route
to the BGP4 core, or have a default route to someone who has a default
route to the BGP4 core (basically a path of defaults, all going towards
the BGP4 core).

I think that the sites that are currently doing BGP4 form a large
enough core for things to work.  If ANS can get things working to join
the BGP4 core, then things will be better; however ANS already has code
deployed that can use a default route (most likely to AS1133).  It
would also be very useful for the CIX-West routers to be part of the
BGP4 core.

I also think that everyone either is already part of the BGP4 or has a
default route towards it.  This point was brought up at the RegTechs
meeting, and no one voiced any objections.

So, I think (& hope) that we are in (more-or-less) good shape.

The next step: publish your plans for BGP4 and CIDR!