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

From: "J. Noel Chiappa" <[email-masked]>
Date: Tue, 29 Oct 2002 16:51:46 -0500

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

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

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 29 Oct 2002 23:42:25 +0100 (CET)

> actual problem the routing has to deal with.

Any particular reason for this?

> them *through the actual network* is 117 hops.

Absolutely true. However, if we can build a naming hierarchy in which
most multihomed networks connect to two places that are very close in
the hierarchy, this buys us aggregatability. Obviously, this is never
going to be a long term solution, but it makes for a very good short
term solution as it can work pretty much immediately by just adopting a
new address allocation scheme and some creative BGP filtering.

> machines without examining them closely too. There's a very good reason in

It's hardly the same thing, as perpetual motion is something that
doesn't work in theory or practice, no matter which way you slice it.
(Obviously I'm not saying something can't move "forever", but rather
that you can't derive energy from something forever.) You can make
routing work in any way you want, it's just that some ways are cheaper
or faster than others. That's one of the problems with networking: even
if done wrong it can work so people don't even see they're doing it
wrong. But then sometimes this is an advantage as you can still get
things to work even if there is a reason why it can't be done right.

> "scalable" routing, which I carefully defined.

Simple = using little information. Flat routing gives you all the
information you need. Depening on aggregates leads to less optimal
forwarding decisions.

> whole paper is about mono-metric systems.

It seems to me you have some very clear opinions on how this should
work. Can we expect a draft?

---

From: Masataka Ohta <[email-masked]>
Date: Wed, 30 Oct 2002 22:35:44 +0859 ()

Noel;

> hierarchical information hiding, e.g. subnets, etc).

Agreed, strongly.

> overhead (i.e. storage/computation/messages) is central to large-scale routing.

Considering geographically large, such as intercontinental, subnets,
host route is, technically, the only way to minimize the shortest path.

However, practically, the minimization for inter-ISP traffic is
impossible, as we can not expect all ISPs use consistent routing
metric, not because there is no consistent metric (e.g. geographycal
distance is an internationally consistent metric) but because there
is no metric to be compatible with all the business models of various
ISPs, which is why BGP does not use any metric.

Many, if not all, ISPs are assuming ASes are local with mostly same
diameter and untimately relies on AS-path length, down side of which
is, of course, a longer path.

							Masataka Ohta