Subject: Re: [rrg] Next topic: properties of identifiers

From: [email-masked] (Noel Chiappa)
Date: Sun, 26 Jul 2009 09:56:34 -0400 (EDT)

> From: Tony Li <[email-masked]>

    > for the most part we seem to be using locators to name the edges of the
    > graph, not the nodes.

All depends on how you model the network! Are the graph-nodes interfaces, and
the networks the arcs (this requires multi-drop arcs, of course), or are the
networks the nodes, and interfaces the arcs?

The latter is what it-whose-name-I-don't-like-to-utter originally did, but
that meant we had to have attributes on the arcs, which after some thought I
decided was excess hair. That's because it turned out that when you started
thinking about what data you needed, arcs started to look a lot like nodes,
at least in terms of the data structures. So that led to the next step - make
everything (networks, interfaces, etc) a graph-node; you wound up with a
graph with attribute-less arcs, which only indicated connectivity. (I.e. the
data structure for node X says "I am connected to nodes A, B and C", etc -
there are no actual arc data-structures.)

I argued with the BBN guys (and gal - hi Martha!) and proposed that we have
only attribute-less arcs, and while at first everyone thought I was kind of
crazy (what an unusual happening in my life :-), after some discussion
everyone took my point that although it was a little odd, it made the
implementation, etc simpler.

So we wound up with graphs with a number of different kinds of nodes: network
nodes, interface nodes, router nodes, and abstraction nodes. (We may have had
host nodes too, I don't recall any more.)

    > If we only have locators, it makes it very challenging to describe
    > topology.

No, not at all. A description of the connectivity has to say 'this {thing} is
connected to that {thing}', and locators are the names for the {thing}s (and
maybe for the connection between them, too). Locators are not the
connectivity model, they are just names for elements in the connectivity
model, which you use to pass the connectivity model (or parts of it) to
another entity.

In the model above, locators are simply the names of graph nodes; more
properly, they are attributes of a graph node, and a given graph node can
have more than one (e.g. if two naming abstractions overlap on the graph).

    > How do you deal with the case where there are two nodes that are both
    > connected to two edges?

It all depends on how your model maps to a real network. In the model above,
your question is non-sensical, because there cannot be two arcs between a
pair of nodes. (A pair of nodes are either connected, or they aren't. That's
alll, fffolks.)

So I'm assuming you're using a model where a node is a network, and an
interface is an arc, or something like that? There, you will be able to have
more than one arc between a pair of nodes - and you will therefore need to be
able to name both nodes _and_ arcs - because otherwise you won't be able to
distinguish between the two arcs.

"Elementary,  my dear Dr. Watson!" :-)

	Noel

---

From: "Fleischman, Eric" <[email-masked]>
Date: Mon, 27 Jul 2009 08:42:07 -0700

It would be nice if topologies could be mapped to graphs -- and it may
well be possible, even though I personally don't know how to do it.
(Alternatively, I suggested to our mathematicians many years ago that I
suspected that Matrices may be a more appropriate representation for
MANET networks than graphs, but they were not interested enough in this
suggestion to see whether it had any merit or not.)

However, I'd like to point out that for any large network the topology
(or graph) is not fully known from any arbitrary point within the
structure. For large networks, we need abstraction to enable scaling.
Also, those of us who work with MANET technologies are quick to point
out that topology is also a function of time in that topology (and
therefore its graph, if we could draw it) is also a partial function of
the 4 dimensional geographic system (x, y, z, time) in which it exists. 

I suspect that this is why arcs proved useful in the discussions which
Noel alluded to below -- arcs provide a mechanism to represent
abstraction.

-----Original Message-----
From: Noel Chiappa [mailto:[email-masked]] 

    > for the most part we seem to be using locators to name the edges
of the

All depends on how you model the network! Are the graph-nodes
interfaces, and the networks the arcs (this requires multi-drop arcs, of
course), or are the networks the nodes, and interfaces the arcs?

The latter is what it-whose-name-I-don't-like-to-utter originally did,
but that meant we had to have attributes on the arcs, which after some
thought I decided was excess hair. That's because it turned out that
when you started thinking about what data you needed, arcs started to
look a lot like nodes, at least in terms of the data structures. So that
led to the next step - make everything (networks, interfaces, etc) a
graph-node; you wound up with a graph with attribute-less arcs, which
only indicated connectivity. (I.e. the data structure for node X says "I
am connected to nodes A, B and C", etc - there are no actual arc
data-structures.)

<snip>