Re: A new spin on multihoming: multihoming classes.

[Iljitsch van Beijnum <iljitsch@muada.com>]

On Fri, 7 Sep 2001, Greg Maxwell wrote:

> > > If we want an 8k routing table

> > maybe i need to be more explicit.  it is not clear to me that this is a
> > useful criterion.

> I think a more useful criterion is that we want a networks routing table
> to grow O(n) with the number of peers and customers that they have (i.e.
> ports) rather then O(x^2) or O(x log x) in the case of a meshed Internet
> which is not highly aggregated, where x is the number of user networks on
> the Internet not just the ones connected to you.

None of these represent the current size of a BGP table. I don't think
it's possible to remove the x completely from the equation, but O(log x)
(which I think more or less represents a table with just the TLAs) is
pretty good too.

However, the current size of the routing table is not nearly as bad as you
say. It's something like O((pz + 1) * x) where p is the number of eBGP
peers for a router, x the total global number of routes and z the fraction
of the global routing table received from each peer. By decreasing the
number of routers, it is possible keep the number of entries in a router's
BGP table fairly close to 2x. Unfortunately, larger numbers of routers
mean increased processing.

A small routing table has disadvantages too: the routing process has to do
its job based on less information, so paths will be longer. We shouldn't
try to limit the actual size of routing tables in networks, but only make
sure the _minimum_ routing table necessary for connectivity is kept as
small as possible, however scenic the routes may get using this table.

It would also help if we could find a way to keep regional traffic
regional without announcing every single /48 individually. Here in Europe
we have some experience in transatlantic routing for regional traffic
(this was quite common five or six years ago) and I don't think many
people want it back.