Re: A tunneling proposal

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

On Tue, 17 Jul 2001, RJ Atkinson wrote:

> >A few weeks ago, someone posted a survey on the list. Nobody answered "we
> >can't handle the huge number or routers" on it.

> NOTE:
>         Probability of a given person answering a survey on the NANOG list 
> is inversely proportional to the probability that the person works
> for a major IP carrier and has at least one clue about routing.

I don't know about the carrier size, but from what I saw these people seemed
to have some clue at least.

> >> Modern routers don't fall over with 100,000 routes in them. 
> >> But initial table load and BGP convergence times when paths change 
> >> are both a lot longer than many would like.

> >Ok, but is that enough reason to throw out the current way of multihoming?

>         Yes.

Well, I disagree. Slow initial sync and convergence times are bad, but
outlawing current multihoming is very bad as well. And I'm certaintly not
convinced this is well-optimized. Not much is.

> >> The size of individual routing state entries in modern routers 
> >> has been the subject of a great deal of optimization over the years. 
> >> Don't expect to see it improved by an order of magnitude or even 
> >> by a factor of two. 

> >Really? 

>         Yes.

So how does this relate to my experience that the amount of memory used by
BGP table entries is the same as six years ago?

> >You have a point on the table updates. A solution for that could be to only
> >allow information about routes going down to be immediately forwarded, since
> >this is presumably an operation that can be optimized not to be very
> >expensive. New route announcements could be slowed down.

> Immediately forwarding information about routes going down
> increases the load on the overall routing system due to route flaps.

Going down just once isn't really flapping. Flapping is when routes keep
coming up and going down. Going down shouldn't have to be an expensive
operation if you leave the information in place but just mark it as
"invalid". Coming up means inserting information, which is a more expensive
operation. If we slow this down, the routes can't go back down again. When
going down means staying down for a while, people will start to pay more
attention to unnecessary flapping.

> Dealing with this system loading issue caused by route flaps
> is precisely why BGP has dampening.

Unfortunately, a major source of flapping seems to be unaddressed: when an
AS has a route coming in from a lot of different directions, a lot of iBGP
updates will start flying around when this route disappears. I wouldn't be
surprised if each of those iBGP state changes also caused an eBGP flap.

> >I don't believe memory speed is a reason to keep the routing table at its
> >current size: doing a binary search on 10,000,000 rather than 100,000 items
> >only takes 24 steps rather than 17. If this is a problem for 10,000,000
> >routes, 100,000 routes is too much as well.

> Some think that 100K prefixes is already uncomfortably large 
> for the algorithms currently being used.

Which algorithms? Forwarding or route processing?

> Others think that
> that the critical point is more nearly 200K prefixes.  Folks
> mileage varies somewhat on where the critical point lies
> with the current algorithms.  Note my phrasing.  I talk about
> "algorithms" rather than "implementations" quite deliberately.

I've read about tests with 2 million routes on some boxes.

Note that CIDR causes route lookup algorithms to be less efficient: in stead
of just finding a single match, the algorithm has to eveluate all possible
prefix lengths. Unless there is some brilliant algorithm for this I'm unaware
of, this makes the lookup about 1.5 - 2 times as expensive.

> >Do we have any inidication that the global routing table is 
> >growing faster than the Moore's Law rate?

> As I recall, tli has made precisely this claim in the past.  
> I'm strongly inclined to just take tli's word on such a point.

Well, have a look at http://www.cisco.com/warp/public/759/ipj_4-1/ipj_4-1_bgp.html

It seems the growth between the beginning of 1999 and the beginning of 2001
was a little less than a factor two, so we're a little below Moore, but not a
lot. (But enough to reach 1 billion routes in 2027 rather than 2021.) It
would be interesting to know how much of this growth is from multihoming.
Since the absolute number of routes grows much faster than the absolute
number of ASNs, most of the growth has to be from poor aggregation, probably
due to the address conservation efforts of the regional registries.

> >2. The current way of multihoming works much better for the multihomed
> >   network, what is their incentive to go with multiple addresses?

> Economics is a major constraint on the potential solution space.

I'm not even talking about economics, but just basic functionality and human
nature: how are you going to convince someone stop doing something that works
for them to help some greater good, that doesn't show obvious signs of
needing help? "Global warming? Let me turn up the airco..."

If there really is a limit above which global routing breaks down, we should
implement some policies to prevent the number of routes from reaching this
limit. This means forcing existing ASes to aggregate, and limiting the growth
in the number of ASes. That way, SCTP-like solutions become more attractive.

But I think we can:

1. optimize protocols
2. optimize implementations
3. look for alternative ways to aggregate, for instance on geography

Iljitsch van Beijnum