Handbook of Local Area Networks, 1998 Edition:LAN Basics Click Here! Search the site:   ITLibrary ITKnowledge EXPERT SEARCH Programming Languages Databases Security Web Services Network Services Middleware Components Operating Systems User Interfaces Groupware & Collaboration Content Management Productivity Applications Hardware Fun & Games EarthWeb sites Crossnodes Datamation Developer.com DICE EarthWeb.com EarthWeb Direct ERP Hub Gamelan GoCertify.com HTMLGoodies Intranet Journal IT Knowledge IT Library JavaGoodies JARS JavaScripts.com open source IT RoadCoders Y2K Info Previous Table of Contents Next Spanning Tree Bridge Algorithm The spanning tree bridge algorithm consists of three processes: bridge forwarding, bridge learning, and formation of the spanning tree. In the bridge forwarding mode, the bridge intercepts all transmissions. It compares the destination address found in the frame header with the records contained in the forwarding data base. This data base contains addresses of the individuals and groups, along with the addresses of the bridge ports. The bridge discards a frame if it finds that the port identifier kept with the address is the same as the identifier of the bridge port on which the frame is received. In the event of an address mismatch, the port number is collected from the data base and the frame is forwarded to the appropriate port. However, if the destination address is not found in the forwarding data base, the frame is transmitted to all ports. This situation is illustrated in Exhibit 1-1-32. Exibit 1-1-32.  Bridge Forwarding and Learning Algorithm The bridge updates the forwarding data base every time it receives an error-free frame whose address it does not find in the data base. The data base entry is made of the source address along with the received-port identification number. The timer value, usually a few minutes, is also reset to indicate that this is anew entry in the data base. If the bridge detects a frame with a known source address from a different port number, it notes this change, updates the data base, and resets the timer for this record. Data is removed from the forwarding data base when the timer for an entry indicates that the data is stale (i.e., the timer value has been exceeded). The timer can be set by network management. When the spanning tree algorithm detects a change in the topology, a shorter time is used to ensure that bridges quickly age out of potentially stale information. The forwarding and learning algorithms assume a topology of brides and LANs in which only one path exists between any two bridges in the entire constellation of LANs. However, fault tolerance parameters may dictate multiple paths between bridges. In such a case, the learning algorithm may break down if it confuses the direction in which end stations are found. As a result, a frame may circulate in a closed loop. The spanning tree algorithm is designed to prevent this by transforming any arbitrary mesh topology into a single spanning tree. The algorithm is based on the following assumptions: •  Each bridge must have a unique identifier. This identifier consists of two components, a priority field and a unique bridge station address, which is administered globally. •  A unique group address must be set aside for all bridges of the LAN. This is implemented in LAN architecture and therefore does not need to be assigned by the network manager. •  Each bridge port exists as a unique identity. The spanning tree is formed by selecting a unique root bridge that has the best priority. This priority could be the default assigned at the factory or set by the bridge administrator. Each bridge decides which bridge port lies in the direction of the root. This is the bridge port through which the least-cost path to the root is found and that is called the root port. A unique destination bridge is selected for each LAN. This is now the bridge that offers the least-cost path to the root from that LAN. Performance can be adjusted by tuning the parameters. For backbone topologies, it is advisable to assign higher root priorities to bridges that are directly connected to the backbone. Path cost can also be adjusted to accommodate variable link speeds. Lower-speed links can be assigned a higher cost in that they are placed into the spanning tree only in the absence of a higher-speed primary link. Source-Routing Transparent Bridge Algorithm The source-routing algorithm was recommended by the IEEE 802.5 standards committee to allow stations to communicate across multiple rings. The primary issue in this algorithm is how to discover the route to the destination. The originating station identifies the message route and the recovery process in each frame. The node launches a query packet, which is broadcast over the entire bridged LAN. The query packet travels along all possible paths between the originating and recipient stations and records the various path descriptions as it travels. The originator then selects the most appropriate path, inserts that information into the header, and sets the group address or multicast bit within a frame to indicate the presence of routing information for all packets transmitted to that destination. Because the routes are selected by the originator, the bridge can be simpler. On receiving a packet, a bridge scans the route information to determine whether an adjacent pair of LAN numbers matches any two of its attached LANs. The bridge forwards the packet if the result is found to be true; otherwise, it discards the packet. To avoid duplication, the algorithm divides the routing information into two logical parts, the route control field and the route descriptor field (see Exhibit 1-1-33). Exhibit 1-1-33.  Frame Format for Source Routing Each route descriptor is composed of a ring number and the bridge umber and is administered by the LAN manager. The current recommendation uses a 12-bit field as the ring number. Each bridge number is 4 bits long and must be unique throughout the bridge LAN. These numbers are assigned manually to ensure their uniqueness. The route control field allows for a maximum of 14 hops through the bridges. (The number of hops, however, can be extended to 28.) The route control field also includes information concerning the largest frame that could traverse the route. The receiving bridge continuously updates this field before forwarding it to the frame. The recommendation also calls for source routing that allows for single-route broadcasting. In source routing, the selected frame travels across a spanning tree made up of source-routing bridges, thus ensuring that the frame will visit each ring at least once. The cost of running this algorithm consists of the costs of route discovery, monitoring the routes, and carrying complete path information in every packet. Previous Table of Contents Next Use of this site is subject certain Terms & Conditions. Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.