\documentstyle[11pt,fancyheadings]{article}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0.5in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8.5in}
\setlength{\parindent}{0in}
\setlength{\parskip}{0.05in}

\begin{document}

\pagestyle{fancy}
\cfoot{Spanning Trees: \thepage}    

\title{Use of Spanning Trees for Bridged Internets}

\author{Norman Matloff \\
University of California at Davis}                      

\date{November 24, 1997}

\maketitle

\section{Overview}

In a large LAN with consistently heavy traffic, it may make sense to
break up the LAN into {\it segments}, i.e. smaller LANs, and connect
them with a {\it bridge}, with the goal of improving performance.
(Or the connecting may be done via {\it switches} instead of bridges;
switches work like bridges but have somewhat more functionality.)
The idea is to put nodes which communicate often with each other on
the same segment.  A node can still communicate with nodes on other
segments, via the bridge, albeit somewhat more slowly.

The segmented Ethernet is called an {\it extended LAN}.  Nodes on the
LANs then in essence see the extended LAN as one large LAN, with the
bridges hiding the fact that there are actually many individual LANs;
in other words, the nodes do not ``know'' that the LAN is segmented.

A bridge operates at the data-link level, in contrast to the network
level used by {\it routers}.  A bridge will be more efficient; a message
will go through fewer layers (in the seven-layer model sense) when
routed by a bridge than it would with a router, and other efficiencies
(especially in the case of a switch) may be attained.  On the other
hand, bridges could not handle really large numbers of nodes, where
the hierarchical routing of routers would provide superior efficiency.
Also, routers can connect two very different kinds of LANs, whereas
bridges need the two LANs to at least have the same address structure
(e.g. the 48-bit addresses of Ethernet and FDDI).



Suppose LANs A and B are, say Ethernets, connected by a bridge.  Whenever
a bridge sees a frame on LAN A whose destination address\footnote{Again,
this will be an Ethernet address, consisting of a 48-bit serial number
on the node's Ethernet board, not an Internet IP address.} corresponds
to a node on LAN B, the bridge will simply copy the frame to LAN B.
If the destination is also on LAN A, the bridge will ignore the frame.
A similar situation holds of frames the bridge sees on LAN B, some of
which may have destinations on LAN A.

Each bridge is connected to two or more LANs, with a {\it port} for
each one.  Each bridge will maintain a table, with each entry 
consisting of two items, a node address and a port number.  If the 
bridge sees a frame come by on port x, the bridge will check the
table.  If the frame's destination has an entry in the table, the
bridge will copy the frame to the indicated port (unless the port
is x, so that no action is needed).  Note that the destination node 
may be several {\it hops} away, in which case the indicated port will 
be the site of the first of the hops.  If the destination node is not 
in the table, then the bridge simply copies the frame to all of its 
ports (again except for x), i.e. {\it flooding} is used.

When the network first is brought up, the tables are empty.  They
are then expanded (though typically never completed) graduallly via 
{\it address learning}:  In the scenario described in the last 
paragraph, let s be the source node number.  If there is no entry for 
s in the table, the bridge will add one, specifically the pair (s,x), 
meaning ``If I ever see a frame addressed to s in the future, I know 
now that I must copy the frame to port x.''

\section{Spanning Trees}

It may be the case that the internet includes loops, in the
graph-theoretic sense.  This would cause obvious problems, in that
a frame may circulate endlessly, never reaching its destination.
The goal of a {\it spanning tree} is to eliminate these loops,
as well to set up paths which are in some sense of minimum 
lengths.\footnote{More generally, one can define costs at the various 
bridge ports, and then find minimum-cost paths.  We will not do
so here; our only definition of cost of a path will be the number
of hops in the path.}

\subsection{Terminology}

Each bridge will be assigned an i.d. number (arbitrarily).
The spanning tree will elect a {\it root bridge}, defined to be
that bridge which has the smallest i.d. number.

Among all bridges on a given LAN, one will be elected the
{\it designated bridge}, defined to be the bridge which is
closest to the root.  In the case of a tie, the bridge with
smallest i.d. number will be chosen.  All traffice forwarded to
and from the root for a given LAN will go through this bridge.
This property guarantees that there will be no loops in the
associated graph.

\subsection{Bridge Protocol Data Units}

Certain nodes will send out Bridge Protocol Data Units (BPDUs)
periodically, typically every 1 to 4 seconds.  When the network
first comes up, all nodes will be both originating BPDUs and
relaying the BPDUs originated by other nodes.  

The format of a BPDU is:

\begin{verbatim}
    sender i.d.     claimed root      distance to root
\end{verbatim}

\subsection{Election of the Root}

At first, all bridges are sending out BPDUs claiming to be the root
(with distance of 0).  When a bridge A receives a BPDU sent (originated
or relayed) by bridge B, A does the following:

\begin{verbatim}
if (B's claimed root < A's claimed root or
    B's claimed root = A's claimed root and B's distance < A's distance or
    B's root and distance = A's and B's i.d. < A's i.d.) then
        A updates its claimed root record to B's
        A adds 1 to B's distance, to produce A's distance
        A relays B's BPDU (with updated distance) to all ports except
           the one B's BPDU came in on
        A stops originating BPDUs
else
    A ignores the BPDU
\end{verbatim}

In the first iteration, where A and B above will be claim to be the
root with distance 0, but whichever one has the smaller i.d. will
``win.''

As time passes, fewer and fewer bridges will be originating BPDUs,
until only one bridge is doing so.  That bridge then becomes the
root.

\subsection{Election of the Designated Bridges}

All of the bridges on each LAN will now again exchange BPDUs.  They
will all have the same claimed (and now actual) root, but their
distances to the root may vary.  If a bridge receives a BPDU with
a distance value less than its own,\footnote{Or of equal distance
but smaller i.d..} that bridge will give up.  Eventually only one 
bridge will be left, and it becomes the designated bridge.

\subsection{Subsequent Operation of the Network}

After the root and all the designated bridges are determined, the
root will continue to originate BPDUs, and each designated bridge
will continue to relay them.  

Each table entry at each bridge has a timer associated with it.
It during stable operation the entry times-out before a root BPDU
arrives, usually due to some bridge in the network having gone
down, the observing bridge will start originating its own BPDUs, so
that the network can reconfigure itself.

\end{document}