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>

    >> the Internet has to be up to way over 1M "nodes" by now, where "nodes"
    >> only include[s] routers and networks

    > Well the IPv4 routing table is only a little over 100k

Perhaps I should have said "physical routers and networks". In other words,
I'm counting all the routers and subnets in the entire Internet. That's the
actual problem the routing has to deal with.

You see *only* 100K destinations in DFZ routing tables because some large
percentage of the informaion has *already* been hidden (through use of
hierarchical information hiding, e.g. subnets, etc).


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

    > I'm wondering whether the solution isn't worse that the original
    > problem.

See comments below about the tradeoff between routing efficiency (i.e. path
length) and routing overhead (i.e. storage/computation/messages).

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

Look, when getting packets from host A to host B - which *inevitably* means
finding a path to get packets from host A to host B - it's *completely*
irrelevant if host A is only 3mm from host B, iff the shortest path between
them *through the actual network* is 117 hops.

Addresses (in the sense of routing-names, and IPv4/6 addresses are
routing-names) are nothing more than the data that routing uses, and the
routing won't scale unless the routing-names are properly aligned with the
actual topology (see previous message).

*** For path selection, *actual network connectivity* is the *only* thing that
*** matters. Therefore, FOR ADDRESSES, *ACTUAL NETWORK CONNECTIVITY* IS THE
*** *ONLY* THING THAT MATTERS.

Yeah, I dismiss "geographical aggregation" of routing-names for extremely
large networks. Competent mechanical engineers dismiss perpetual motion
machines without examining them closely too. There's a very good reason in
both cases.


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

What is "simple" forwarding, or "simple" routing, for that matter? These are
not terms with any clear meaning that I am aware of. I was talking about
"scalable" routing, which I carefully defined.


    >> Please read this seminal paper:

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

The tradeoff between routing efficiency (i.e. path length) and routing
overhead (i.e. storage/computation/messages) is central to large-scale routing.

To really cover this topic is a PhD thesis (and that's for the mono-metric
case), but in general if you want to be absolutely sure of getting optimal
routes, you have to get rid of information hiding; i.e. flat route the entire
network. Needles to say, this doesn't scale well. The whole art in large-scale
routing is managing that tradeoff between routing efficiency and overhead.

The K/K paper does show that, given certain reasonable assumptions about
topology, that the increase in path length due to their information hiding
scheme grows very small as the network gets larger, although of course their
whole paper is about mono-metric systems.

	Noel