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

["J. Noel Chiappa" <jnc@ginger.lcs.mit.edu>]

    > From: Iljitsch van Beijnum <iljitsch@muada.com>

    > 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