Subject: The end of the world as we know it (was IPv6 address space shortages)

From: Pedro Roque Marques <[email-masked]>
Date: 03 May 2003 15:01:24 -0700

[email-masked] (Dean Anderson) writes:

> We are still not out of IPv4 address space. I don't know the projections
> for address space depletion, but I think the IPv6 problem won't be so much
> address space depletion as route space depletion. I think it will be
> unwieldy to have a million or 2 million or 10 million distinct routes.
> Aggregation won't happen the way things are currently organized.
> 

- "route space depletion" seems to be an argument postulated on the
idea that exterior routing scalability depends mostly on the number of
prefixes carried.

I tend to hold the somehow heretic view that that is not really the
case. imho, exterior routing scaling depends much more on the number
of distinct topologic information that is carried (i.e. distinct BGP
path attributes).

This much is subject to experimentation: take N distinct prefixes and
advertise them in BGP w/ the exact same path attributes; compare the
result w/ the same N advertised w/ different attributes.

I believe that you will find that using a reasonable implementation
that not only the latter consumes more memory but it also does consume
a significant higher ammount of CPU resources. I would also argue that
contrary to the pre-CIDR years, todays networking equipment is
"shorter" on CPU than on memory.

Note that topologic information (path attributes) is already the
smallest ammount of information required to express the "problem at
hand".

Thus routing information reduction should probably focus much more on
the aggregation of topology information, when possible, than reducing
the number of prefixes.

In current internet routing tables, the number of prefixes to distinct
path attributes is usually around [5-10] interval. So it is often
arguable how much effort an implementation wants to put on
concentrating on the basic information (path/topology attributes). One
can reasonably expect that if the ration of prefixes to attributes
where to increase substantially more effort would be made to
concentrate on this topologic information.

Aparently this notion that path attributes may be more relevant to
exterior routing scaling that number of prefixes is actually gaining
popularity. See for instance http://www.caida.org/projects/routing/atoms/

Of course there is a number N of prefixes that will overload your
memories, both in terms of routing and forwarding databases. But i
believe it is rather simplistic to assume this is the main scaling
factor w/ exterior routing.  

There is another point i would like to raise... today's top of the
line networking equipment has the requirement to do 40Gb of traffic on
a single line card, which should translate roughly to ~100 Mpps.
The corolary of some of the arguments applied to the routing problem
would be to say that since it is impossible to do 100Mpps using a
3-year old general purpose CPU we should all go home and declare this
packet switched experiment to be utterly unscalable.

The clever reader will point out that there is an economic value
attached to forwarding of packets while there isn't one attached to
carrying routes per se. 

But it is sort of impossible to determine the scale to which you can
engineer a given problem without considering the ammount of resources
you can throw at it...

Regardless of how you skin the cat, the discussion is going to come
back to the forum of economy and politics, be it in terms of how much
you can scale the routing systems or in terms of shifting some of the
burden to the end user networks via NAT, aggressive renumbering or any
other proposal i'm familiar with.

This rambling is rather long already, but i wouldn't want to end with
out taking my turn at the crystal ball...

Neither address or routing space exaustion seem to be realistic
enought scenarios in the medium term. There are plenty of economic
incentives for all involved (SPs, end users, vendors) to find
solutions that allow for anyone of the planet to use the main services
the internet is supposed to provide today: https and a spam-full inbox.

regards,
  Pedro.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Mon, 5 May 2003 15:57:32 +0200

On zondag, mei 4, 2003, at 00:01 Europe/Amsterdam, Pedro Roque Marques 

> I would also argue that

Two sides of the same coin: not just because you can optimize for one 
at the expense of the other, but mainly because the memory doesn't just 
sit there inertly, it holds information that must be processed. So all 
else being equal, more memory means more information means more 
processing means more CPU usage.

> smallest ammount of information required to express the "problem at

I don't necessarily agree. BGP could save a lot of overhead by 
differentiating between transit networks and leaf networks. For the 
latter, there is no need keep much information. It should be possible 
to bring this down to just a few bits.

> path attributes is usually around [5-10] interval.

Note that this will change for the better in IPv6 as there is no longer 
much need to keep the assignments to ISPs artificially small.

Also, in order for your assertion to be correct, it requires the 
processing that is unique for each set of path attributes to be at 
least five times as expensive as prefix processing. The former is 
mostly loop detection and AS path filtering, the latter is obviously 
prefix filtering and deleting/inserting prefixes, but also running the 
BGP path selection algorithm, which is AFAIK done per-prefix even 
though it mostly looks at the path attributes. I'm not making any 
claims either way, but I'd like to see some figures here. (Any vendors 
in the room?)

Iljitsch van Beijnum