\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{June 4, 1996}

\maketitle

\section{Overview}

A {\it bridge} connects two or more LANs of the same structure, say two 
Ethernets, into one larger network called an {\it internet}.\footnote{Note 
the use of the lower-case `i', as opposed to the Internet.}  A bridge
operates at the data-link level, in contrast to the network level
used by {\it routers}.  A typical usage may be in a large company
which has many LANs, in which case many bridges would be used to
connect them.  Nodes on the LANs then in essence see the internet as 
one large LAN, with the bridges hiding the fact that there are actually
many individual LANs.

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}

The spanning tree will elect a {\it root bridge}, defined to be
that bridge which has the smallest address.

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 address will be chosen.  All traffice forwarded to
and from the root for a given LAN will go through this bridge.

\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 address     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 address < A's address) 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}

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 address.} 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}