[e2e] Overly Overlay; Peer to peer is commonplace
J. Noel Chiappa
jnc at ginger.lcs.mit.edu
Wed Jan 2 09:24:19 PST 2002
> From: "David P. Reed" <dpreed at reed.com>
>> you have to impose a naming abstraction hierarchy, or the routing will
>> not scale. You can impose such an abstraction hierarchy on *any*
>> graph - it doesn't have to be hierarchically organized.
> This embodies precisely the problem I have with most routing
> discussions. Let me try to get at this from my point of view.
Your note embodies precisely the problem I have with most routing discussions,
> The problem phrase is "You can impose such an abstraction on *any*
> graph". While true, it is irrelevant in a deep way
On the contrary, you cannot build a routing architecture (i.e. a system for
finding paths between sources and destinations) that will scale to very large
sizes without a naming abstraction hierarchy *based on the real topology*.
> 1. a communications system, from its endpoints perspective, is the
> graph of capabilities for end-to-end message delivery. The internal
> structure of the network (links & nodes) is only relevant when it
> constrains that.
Exactly! It's for the problem of finding a real path (i.e. an ordered set of
real links and nodes) from a source to a destination that the routing
architecture needs those topology-based names you hate so much.
> Confusing internal structure with external function is not modular.
One person's hidden internal structure is another person's explicit
structure. If you want to treat the network as if if were an N^2 set of
direct connections between all possible endpoint pairs, fine. Those of us who
actually have to get the packets from A to B don't have that luxury.
If what you're saying is you want a namespace for interfaces (or whatever)
which doesn't have topology built into it, then fine - but you have to make
the case as to why the costs of that extra namespace (and all the mappings
to and fro to other namespaces) are worth the benefits - which are...?
> 2. The abstraction being imposed (IP's addressing) is intended to apply
> to communications systems that are not graphs at all. For example,
> radio networks have topology, but in space, time, and frequency domain
> they are continuous manifolds, not graphs.
But it's also true that one can represent the connectivity between the radio
nodes by a graph, with arcs between all nodes that can directly communicate.
One can further enhance that graph by adding attributes to the arcs, showing
bandwidth, S/N (aka error rates), etc, etc. (Of course, it may be a very
dense graph, but there are ways to deal with that which I'm going to gloss
over for the moment.) The question then becomes "which is a more useful way
to model the real world radio network".
Even for the purposes of routing within the radio network, it's not clear to
me that the continuous manifold model is better (since I doubt that the
theoretical manifold model will always accurately tell you the real bandwidth
and S/N available between any particular pair of nodes, when you take into
account buildings, trees, rain, etc, etc, etc). Won't you want to wind up
Then the question becomes "what's the best way to embed that information in a
knowledge schema that other entities which are trying to select paths can
use"? At which point we wind up back at the graph model, I suspect.
And anyway, even if it is more appropriate to use some other technique for
modelling the connectivity in some limited domain, you still face the problem
of what the appropriate model is for the system as a whole - remember, to be
much use at all, users of that radio network have to be able to get to users
anywhere else on the network. And for the larger network, a graph-based
knowledge schema still seems like the right thing.
>>> More relevant, though again as naive as GUID-based routing, is
>>> geotemporal routing.
> approaches that recognize that endpoints are embedded in a spatial and
> temporal physical world, and which calculate routes in a distributed
> manner using such information.
The physical location is completely irrelevant. What matters is the ability
And the most compact model of that communication capability, in most cases,
is a graph of the actual connectivity.
> a prehistoric ancestor of such things is Landmark Routing
Well, landmark routing is just a way of building an abstraction hierarchy
(albeit not one with fixed boundaries). It has downsides of its own, too
(which I don't feel like yapping about here).
> also included are various radio techniques such as MIT's GRID and
> low-level routing techniques such as spatial coding, joint and
> multiuser detection - depending on the topology of the available
> connectivity manifold and its embedding in 4-space).
There may well be some use for other techniques in part of the network. A
well designed routing architecture should make such things relatively easy.
However, the problem remains of what connectivity model to use for the system
as a whole - and of a naming system for that model that results in an overall
scalable routing system.
More information about the end2end-interest