Everything Penguin

Focusing on Linux-based Operating Systems
htDig Search:

Operating Systems
  • /pub/OS/Linux

  • Storage
  • File Systems
  • HPC
  • /pub/Storage

  • Networking
  • /pub/Networking

  • Network Services
  • /pub/NetworkServices

  • Security
  • /pub/Security
  • Keytool/OpenSSL

  • Clustering
  • HA
  • DRM

  • Development
  • Design
  • C/C++
  • Java
  • Perl
  • Python
  • Shell
  • Web / J2EE

  • Not Linux ?
  • BSD
  • HP-UX
  • Mac
  • Solaris
  • VM
  • Windows
  • /pub/OS

  • Other
  • /pub
  • /pub/3rdParty
  •  Parent Directory

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

    Other Sites

  • FAQ's
  • IETF
  • RFC Sourcebook

  • Linux
  • Linux - Intro
  • Linux Kernel
  • Linux Kernel (LKML)
  • Bash - Intro
  • Bash - Advanced
  • Command Line
  • System Administration
  • Network Administration
  • Man Pages (& more)
  • More Guides
  • Red Hat Manuals
  • HOWTO's

  • Reference/Tutorials
  • C++ @ cppreference
  • C++ @ cplusplus
  • CSS @ echoecho
  • DNS @ Zytrax
  • HTML @ W3 Schools
  • Java @ Sun
  • LDAP @ Zytrax
  • Linux @ YoLinux
  • MySQL
  • NetFilter
  • Network Protocols
  • OpenLDAP
  • Quagga
  • Samba
  • Unix Programming

  • This site contains many of my notes from research into different aspects of the Linux kernel as well as some of the software provided by GNU and others. Thouugh these notes are not fully comprehensive or even completetly accurate, they are part of my on-going attempt to better understand this complex field. And, they are your to use.

    Should you wish to report any errors or suggestions, please let me know.

    Should you wish to make a donation for anything you may have learned here, please direct that donation to the ASPCA, with my sincere thanks.

    Brett Lee
    Everything Penguin

    The code for this site, which is just a few CGI scripts, may be found on GitHub (https://github.com/userbrett/cgindex).

    For both data encryption and password protection, try Personal Data Security (https://www.trustpds.com).

    "We left all that stuff out. If there's an error, we have this routine called 'panic', and when its called, the machine crashes, and you holler down the hall, 'Hey, reboot it.'"

        - Dennis Ritchie on Unix (vs Multics)

    [ Powered by Red Hat Linux ] [ Powered by Apache Server] [ Powered by MySQL ]

    [ Statistics by AWStats ]