[e2e] Overly Overlay; Peer to peer is commonplace

[Bob Briscoe]

David,

At 20:14 07/01/02 -0500, David P. Reed wrote:
>Bob -
>
>Considering wired networks, it's not obvious to me that every packet put 
>into a network must take the shortest path through the network.
>
>For all A, B pairs, there will be some in the hierachical decomposition 
>that will not be able to use hierarchical addresses to discover a set of 
>routes that do particularly well in spreading the traffic along disjoint, 
>non-interfering routes.  Or so I would think.  Not a proof.

But we're not talking about using the address alone as the way to route the data. The routing alogorithm does that, but it needs to /use/ addresses to describe routes. We're merely talking about ensuring there is an extremely succinct and efficient way to represent a large set of addresses in some distant, far-off land where we don't care about whether there are disjoint routes 99.9% of the time. But when we /do/ want to discriminate between routes to different addresses in that far-off land, we have the option to describe the destination addresses more precisely to discriminate between routes to them. 

Most alternate path routing can be done locally, but we can use paths that take completely different routes through most of the world if we need to (at extra cost). But most of the time, we probably won't do alternate path routing at all.

So for both reasons this isn't the broken assumption that invalidates the motivation for hierarchical routing.

>All I mean to point out by this is that hierarchy of addresses is 
>intimately tied with other assumptions about what routing will be used, and 
>what the load looks like 

True, but only because any decision is tied to the assumptions behind it. All that is important is whether there are *invalid* assumptions.

And... what I tried to prove is that physical distance and connectedness will be closely matched for economic reasons, (until one of our implicit assumptions is broken). Therefore hierarchical addressing is useful, because it /is/ intimately tied to foreseeable assumptions about what routing will be used for.

If anyone can come up with an assumption being made:
a) that is broken under some important scenario we can foresee
 AND
b) is intrinsic to the logic that I tried to expound for why hierarchical addresses are necessary for global network scaling

...then it's worth carrying on this thread.

>(as well as what I really care about, which is 
>that topology changes end up being reflected in application-visible 
>addresses, and thus end up pushing the problem onto the higher levels which 
>have no better way to deal with the problems.)

If I can characterise this as the multi-homing (or alternate-homing) problem, there's a different issue here which concerns address usage in higher layers, not the network/routing layer, but first let's keep on the hierarchical routing issue:

When topology changes are made, the economic arguments I went through tend to mean a new or second connection is not entirely random, but is physically closer to the old connection than the rest of the connection possibilities. So most topology changes are hidden from most of the rest of the world by good hierarchical addressing. Seen in this light, IP addressing is not hierarchical enough.

Now the different issue:
* When I make a topology change, my address changes. Because this address is used by higher layers anywhere in the world, they all have to re-configure. But the whole world doesn't have to. Just a sprinkling of end systems anywhere in the world that happen to be part of my community of interest. This is nothing to do with hierarchy. Even if just the last bit of my address changes, the other ends will need to re-configure if they are addressing directly to me. 

Hierarchy isn't relevant because describing sets of addresses isn't relevant to this problem.

Yes, an addressing architecture needs to trade-off:
i) the costs associated with re-config of higher layers as their correspondent addresses change against 
ii) the costs to the network routing process of not being able to abstract away from distant routing changes...

...but I'm not convinced this is a fruitful subject to discuss in abstract terms on any mailing list. For that sort of trade-off, I think we have to see proposals worked out quietly and evaluate them on their merits. Talking about requirements in the abstract for that sort of trade-off doesn't seem fruitful.

Whatever, a solution to this second problem that breaks the solution to the first problem (the ability of a network to abstract away from non-local routing changes) wouldn't be a solution worth getting out of bed for. And we don't (yet) have anything better than addressing hierarchy for the latter.

Bob
____________________________________________________________________________
Bob Briscoe         http://www.btexact.com/people/briscorj/