Re: PI/metro/geo [Re: The state of IPv6 multihoming development]

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

On Mon, 28 Oct 2002, J. Noel Chiappa wrote:

>     > So what is it that makes "connectivity-based" names so good and
>     > everything else so bad?

> Because the only way to make the routing scale to extremely large sizes (and
> the Internet has to be up to way over 1M "nodes" by now,

Well the IPv4 routing table is only a little over 100k and there should
be a one time gain when moving to IPv6, so I'm not sure about the "now"
part, but soon, yes. I think we're all in agreement about that and the
fact that 1M is just a starting point.

>     > Unless I'm much more mistaken than I thought possible

> I will exercise great restraint and not touch this straight line...  :-)

I appreciate it.

> Anyway, if the routing is to scale, the actual connectivity relationships
> between the abstractions *have* to be embodied, to a certain degree (long
> side-dissertation suppressed) in the routing-names. This is generally done by
> having the routing-names have a hierarchical structure which generally (same
> long side-dissertation suppressed) mimics the abstraction hierarchy.

I'm wondering whether the solution isn't worse that the original
problem. And so are you (at least to some degree) as you dismiss
geographical aggregation, despite the fact that geography is much
structured much more hierarchical than any aspect of IP and the routing
thereof. See draft-py-multi6-gapi-00.txt, which was posted earlier
today.

>     > There is
>     > absolutely no way to make real-world interdomain routing fit inside a
>     > hierarchy.

> Nobody said it should. Just like the connectivity doesn't have to be a tree
> (or hierarchy), the routes don't follow a tree (or hierarchy) either. However,
> the *naming* has to follow a hierarchy. If you do that, you get scalable
> routing; i.e. routing where the overhead grows as something like ln(N), where
> N is the number of "nodes" (as defined above) in the network.

It seems to me that in order to have simple routing, you have to live
with simple forwarding, which has many undesireable properties, such as
a longer path and less redundancy.

> Please read this seminal paper:

> 	Leonard Kleinrock and Farouk Kamoun, "Hierarchical Routing for Large
> 	    Networks: Performance Evaluation and Optimization",
> 	    Computer Networks 1 (1977),
> 	    North-Holland Publishing Co., pp. 155-174.

That's going to take a while as it seems noone ever bothered to put it
online, not even Kleinrock himself who isn't otherwise very modest about
his accomplishments.

From what I gather from other stuff that refers to this, the down side
is a longer path.

> And it does *not* have to be hierarchical routing (as in the K-K paper),
> either, if information about the internal structure of an abstraction is
> allowed to leak out a *limited* distance beyond the naming boundary of that
> abstraction - as opposed to suppressing it at the naming boundary, which is
> the most common case.

Yes, being able to control how far the more specific information leaks
out is a very useful property.

If we can make sure a multihomed network connects to two places that are
close together in the hierarchy, the problems with the number of
multihomed routes would be solved. However, this means we can no longer
aggregate based on ownership of the routers (as it is done today) but
rather routers from different networks that connect the same customers
must be close together in the hierarchy.