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

From: "J. Noel Chiappa" <[email-masked]>
Date: Mon, 28 Oct 2002 20:34:51 -0500

> From: Iljitsch van Beijnum <[email-masked]>

    > 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, where "nodes" only
include routers and networks, not hosts, since hosts don't generally create
any load on the routing algorithm) is to use connectivity-based routing-names;
i.e. routing-names which express *where* you are in the network.

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

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

    > the relationship between a connection and a name/address is purely
    > contingent. Things would be different if routing were hierarchical,
    > which it isn't.

You're making a common mistake, and confusing the connection graph (which *is*
an arbitrary graph) with the "abstraction hierarchy", which is a tree (i.e. a
hierarchy). The "abstraction hierarchy" just shows the relationship between
larger and larger "abstractions"; i.e. named areas of the network connectivity
graph. This is probably easier to grasp with a picture; check out:

    http://users.exis.net/~jnc/tech/routing_slides.html#abshier

which should help make it clear.

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.

In fact, one generally simply creates those hierarchical names by stringing
together the names of the branches of the abstraction hierarchy tree leading
from the root to the thing you want to name. E.g. on the example page above,
the node X.A.1 is named that by concatenating (with dots) the names of the
branches X, A and 1.

    > If the only way to get from A to D is A -> E -> G -> F -> D everything
    > gets very simple and very scalable. However, not only does this not
    > match the way things work--it doesn't even come close. 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.

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.

which explains this all, and includes a number of key proofs.

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.

Again, an example makes this easier to see. Going back to the example in the
page above, add a second connection between A.3 and B.3. If information about
the internal structure of A is allowed to leak out a *limited* distance beyond
A, say as far as B.2, then when packets for A.2 and A.3 arrive at B.2, the
latter can forward them to the appropriate next hop (B.1 and B.3 respectively)
which leads to the optimal entry point into A for their actual ultimate
destinations.

More later, this is enough for now.

	Noel

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 29 Oct 2002 22:24:05 +0100 (CET)

> 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.

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

I appreciate it.

> 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

> 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.

> 	    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.

> abstraction - as opposed to suppressing it at the naming boundary, which is

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.