Odd request

[Bob Drzyzgula]

The "Spanning Tree Algorithm" has its roots (sorry) in
the branch (geez, I really didn't set out to do this) of
mathematics known as Graph Theory. It describes a mechanism
whereby a cycle-free subtree of a connected graph, reaching
every node of the graph, can be identified. As with most
of these things, there's more than one way to do it --
any given graph will potentially have several different
spanning subtrees, although some will be "better" or
"more optimal" than others according to some criteria
or another. In particular, depending on the problem
one is attempting to solve, one might be looking for a
spanning subtree which maximizes or minimizes the number
or aggregate length (or perhaps "cost") of the arcs
which connect the various nodes. In LANs, one usually
is interested in a shortest-path spanning tree. Any
decent book on graph theory should discuss this -- I just
refreshed my memory on this out of my copy of "Flows in
Networks", by Ford & Fulkerson, Princeton 1962 (out of
print, sadly).

When translated to a network, however, a spanning tree
algorithm is used as the basis of what is then called a
"Spanning Tree Protocol". The whole point here is to find
a set of point-to-point links in a network over which you
can reach any network attachment point, but within which
one cannot get caught in a circle without immediately
backtracking over the last link followed. Since MAC-layer
bridges (and hence switches, which are fancy bridges)
know only about "here" and "there" and not "over yonder" --
their view does not extend beyond the immediately-connected
segements -- the failure to limit the usable paths in this
way can result in packets spinning around in a cycle and
never being forwarded to their intended destination.

As with just about any protocol, this too has been subject
to revision, reuse and refinement over the years. The
protocol used by modern switches is specified by the
IEEE 802.1d document which, alas, is not available for
free download anywhere -- IEEE charges real money for
their standards documents.  I believe that the protocol
used in 802.1d is based on an earlier DEC protocol, but
incompatibly so.

Just about any reasonably detailed book on network technology
should contain an explaination of spanning tree. As
I was searching for some other references (no, I didn't
just write up all this detail from memory), one book that
kept coming up was "Interconnections", by Radia Pearlman.
At Amazon, sixteen reviewers give it all five stars, one
only gives it four stars because he found himself
underprepared :-) Thus, I assume that it's a decent reference:

http://www.amazon.com/exec/obidos/ASIN/0201634481/

Hope this helps,
--Bob

On Thu, Mar 29, 2001 at 06:04:25PM +0100, Grenyer, Richard wrote:
> Someone wrote:
> 
> >And your N networks had to be isolated from each other, 
> >so that their tree-spanning algorithm, etc. would not get confused 
> 
> What is this tree-spanning algorithm. Is it detailed anywhere? What would I
> need to search around under - keywords, acronyms, similar?
> 
> Many thanks,
> 
> Rich Grenyer
> 
> 
> _______________________________________________
> Beowulf mailing list, Beowulf at beowulf.org
> To change your subscription (digest mode or unsubscribe) visit http://www.beowulf.org/mailman/listinfo/beowulf