Spanning Tree Algorithm
Brett Lee
=============================================================================


The Spanning Tree Altorithm (STA) can be thought of as a dynamic Layer 2 (MAC) 
routing protocol.  To clarify and expand, a quick detour is necessary.


Repeater:
-------------
A repeater is a simple hardware device used to connect two (2) Ethernet 
segments.  The repeater contains two ports, one for each segment.  The 
repeater listens on each port, then transmits data from one port to the other.


Hub:
-------------
A hub can be thought of a multiport repeater.  It typically has from five (5) 
to twenty (20) ports and may also contain an "uplink" port.  A hub listens
on all ports and, like a repeater (except remember it's a multiport repeater) 
it takes what it hears on one port and retransmits it on all the other ports.

As you can imagine, with devices that transmit quite often connected to the same
hub, this results in contention for the ability to send the electrical signal 
and frequent collisions.


Switch:
-------------
A switch is a multiport device that has more intelligence than a repeater.  For
starters a switch doesn't just listen and repeat the bits; instead it reads
the frame header (at the Data Link layer) and determines the source and 
destination MAC addresses.

Having read the source address, the switch learns which MAC address is attached
on each port.  This information goes into a lookup table, and the next time a 
frame arrives containing that MAC address as the destination, the frame is sent
out on that port only.

Aside from the core functionality of "OSI Layer 2 switching between MAC
addresses", some switches (Cisco, Nortel, Alteon, etc.) have evolved from purely
integrated circuit devices to hardware devices that contain a CPU, an operating
system and many additional networking functionalities such as VLAN tagging, the
spanning tree algorithm and intelligence to read higher level (OSI Layer 3-7)
protocols and "switch" traffic based on the packet data at the higher layers and
/or health monitoring initiated by the switch.  For more on this see the multi-
layer switch (MLS) section below.


Spanning Tree Algorithm:
---------------------------
Switches are frequently interconnected by stacking or cascading.  While stacking
switches makes them effectively one, cascading them creates a distributed
network as seen below:


       Figure 1

                             |-------------|
       ______________________|      A      |___________________
       |                     |-------------|                  |
|-------------|                                        |-------------|
|      B      |                                        |      C      |
|-------------|                                        |-------------|


In Figure 1, switches A, B and C are interconnected via Ethernet.  If each 
switch runs STA, then each switch will distribute their table of MAC
addresses and learn from other STA distributions.  This means that switch C
will have, in effect, a tree showing that the MAC addresses on switches A & B
can be reached via the port that connects to the MAC address of switch A.



       Figure 2

                             |-------------|
       ______________________|      A      |___________________
       |                     |-------------|                  |
|-------------|                                        |-------------|
|      B      |________________________________________|      C      |
|-------------|                                        |-------------|


While Figure 1 depicts a common scenario, a more robust solution contains
interconnectivity between all switches (Figure 2), such that if any one switch
fails the remaining network remains in tact.  This works well for redundancy,
however it introduces multiple routes to each remote MAC address.  

STA provides for this in that it eliminates multiple routes to the same MAC
address.  This is done by selecting a master switch via an election process.  
After the the other switches learn of the master switch, they parse their
learned routes and remove all the duplicate routes that are not thru the master
switch.  This leaves one and only one route to each MAC address.  For example,
if an election were held on the switches in Figure 2, and C was configured 
with the highest priority, then the network wouild look like Figure 3:



       Figure 3

                             |-------------|
       __   <hot standby>  __|      A      |___________________
       |                     |-------------|                  |
|-------------|                                        |-------------|
|      B      |________________________________________|      C      |
|-------------|                                        |-------------|


STA switches have the option to be configured with a priority value that will 
be used in the election process.  Barring configured values, the MAC address of
the switches are used.


Multi-Layer Switching (MLS)
------------------------------

As mention earlier, switches have become more sophisticated and now perform
more than merely switching between MAC addresses at the integrated circuit (IC)
level.  Typically, layer 2 switches forward traffic to layer 3 routers for
packet routing decisions.  The downside to this has been the overhead involved
with sending packets to and from a router, getting the packets into a single
threaded router CPU, and having the packets analyzed in software as opposed to
the faster IC's.

The designers of the Layer 3 (L3) switches have incorporated the ability to
read network level (OSI Layer 3) headers and make routing decisions based on
the destination address at the network layer.  L3 switches also run routing
protocols (RIP, OSPF, BGP, etc.) which feed into the routing decision.

So what's the difference between L3 switches and traditional routers?  One thing
for sure is that the routing is done in IC's instead of the CPU.  This increases
the speed ten-fold brings down the per-port cost dramatically.  Another apparent
difference is that L3 switches (currently) do not offer as much WAN support as
do traditional routers.


-Brett