Re: Draft: PI addressing derived from AS numbers

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

On Mon, 10 Feb 2003, Randy Bush wrote:

> as we had all lived through
> cidr and thought it immensely <polite> ill-considered </polite> to
> think one could do a new addressing design without a *real* new and
> scalable routing design.

Ok, lets see what can be done in this area then.

I'm aware of two ways to make routing scale:

1. Some kind of source routing
2. A hierarchical routing system

The identifier/locator seperation thing is basically source routing.

Current aggregation mechanisms (CIDR) provide some basic hierarchy. But
we should be able to improve on this. The address space is a tree with
the default route at the top and individual hosts all the way at the
bottom as individual leaves. We're not talking about your basic binary
tree here, as many levels are missing in certain parts of the tree. For
instance, below ::/0 aren't ::0/1 and 8000::/1 but (conceptually)
2000::/3, the global unicast space (and some other less interesting
stuff). Below 2000::/3 there are one or two additional conceptual levels
but real routing info starts at xxxx:xxxx::/32, where the "top level
aggregators" live. So essentially we're doing flat routing in the first
32 bits (or rather, 29 of the first 32) of the IPv6 address space. Flat
routing in a part of the tree is not a problem, except that 29 bits is
too many as it leads to a maximum of 512M entries in flat space for this
part of the tree.

So how do we fix this? If we simply introduce a level of aggregation we
could be doing flat routing in a 64k space and then flat routing in
another 64k space. That should work well, especially as the entire space
isn't populated from the start. The trouble is that someone with a /32
must automatically buy transit service from the service provider that
has the /16 this /32 falls in. This means renumbering from time to time.
Also, not much multihoming in this scheme.

Alternatively, we could align the address hierarchy with something else
than the (largely fictional) topological hierarchy. For instance, the
/16s could be allocated to internet exchanges. This way, it's possible
to multihome and shop for transit as many ISPs can provide a path /to/
the exchange and many ISPs can provide a path /from/ the exchange to the
destination network.

Now suppose a node somewhere in the hierarchy fails. A smart
hierarchical routing protocol would repair such a failure by linking
nodes at the level below the failed node to the ones at the level above
the failed node.

Also, a smart hierarchical routing protocol would converge fast by
learning the information it needs to function at the levels it is
present quickly, but then optimize routing by adding additional
cut-through routing entries that bypass the hierarchy if resources
permit and adding this information leads to actual benefits.

Iljitsch

PS. Please no "IXes suck" flaming; if we are actually going to get into
this we can do better but the IX stuff makes for a good example.