A PAPER ON TRANSPARENT BRIDGES AND SPANNING TREE ALGORITHM BASED ON IEEE 802.1D

-SANDEEP GUPTA

M.Tech (WCC)-1^st Yr.

Summary

This paper talks about Transparent Bridges and Spanning Tree Algorithm as described in ANSI/IEEE standard 802.1D, 1998 Ed. All the IEEE 802 LANs can be connected together using MAC Bridges. Transparent Bridges operate transparently to the hosts in the sense that the hosts do not know about presence of such devices. These bridges listen to the traffic and learn about the topology of the network. Some of the interfaces of a bridge should be blocked lest they may create loops in the topology which can be disastrous. An algorithm called Spanning Tree Algorithm is used for this purpose.

Transparent Bridges

Transparent Bridges were originally developed by Digital Equipment Corporation (DEC) and were adopted by 802.1 committee. These bridges are very popular to connect multiple 802.x networks. Transparent bridges are named so because their working and presence are transparent to the hosts connected to the networks. They must have the following features:

Ø Promiscuous listen and the store and forward capability

Ø Learning ability

Ø Spanning tree algorithm

Listen and store & forward Bridge

FIG 1

The bridges having Listen and Store & Forward capabilities are called “No-frills” bridges. As shown in Fig. 1, bridge B listens to all the traffic coming from LAN 1 or 2 until a packet is completely stored and then forward it to the other LAN ( LAN 2 in case the traffic originated from LAN 1).

Learning

When a transparent bridge is powered on, it learns the workstations’ locations by analyzing the source of the traffic that it handles. Initially, it works in promiscuous mode, just like a “No-frills” bridge. It listens to every packet being transmitted and notes down the source and the port number of the packet in its “station cache”, if it is already not present or has changed since last time. It then checks if it has destination address listed in its station cache. If the address is not found then packet is forwarded onto all ports except the one on which it was received. If the address is found and the port specified for the destination is different from the port from which the packet was received, the packet is forwarded on the designated port. Otherwise, the packet is dropped (or filtered). If traffic is not received from a station for a certain time then its address is aged out of the station cache and the bridge follows the complete procedure again whenever there is a packet for that station. This is done to ensure that if a station is unplugged from a network and moved somewhere else, even then the bridge is able to deliver the traffic to it.

Fig 2 shows station cache of bridge B on ports 1 and 2 after it has learned the locations of all the connected stations.

FIG 2

Spanning Tree Algorithm

When a few networks are connected with some bridges, it is quite possible that loops exist i.e. there may be more than one way to reach a station. In this case a station will start receiving duplicate messages. In some cases, the packets not only loop but also proliferate. But a word of caution should be put here – loop-free topology is not the solution. On the contrary, loops are extremely useful. If a connection breaks then these redundant paths can be used to restore connections. An algorithm called Spanning Tree Algorithm developed by Radia Perlman is used by transparent bridges to maintain a loop-free subset (or a spanning tree). It dynamically discovers a subset of topology that is loop-free and spans every LAN in the topology. Also, it provides fault tolerance by automatic reconfiguration of spanning tree in case of breaks in topology.

Requirements

The following are required for working of the algorithm:

A unique MAC group address
A unique identifier for each bridge
A port number for each Bridge port distinct for each bridge.
Relative priority for each bridge within the bridged LAN.
Relative priority for each port within ports of a bridge.
Path cost for each port.

Strategy

Bridges transmit a configuration bridge protocol data unit (BPDU) (or configuration message) to each other for constructing a spanning tree. Each BPDU contains:

-&nbbsp; the unique identifier of the Bridge that the transmitting Bridge believes to be the Root

-&nbbsp; the cost of the path to the Root from the transmitting Port

-&nbbsp; the identifier of transmitting bridge

-&nbbsp; the identifier of transmitting port

Bridges follow the following steps:

a. All Bridges believe themselves to be the Root and originate Configuration Messages on all the LANs to which it is attached, at regular intervals with 0 as cost.

b. A Bridge that receives a Configuration BPDU on what it decides is its Root Port conveying better information (i.e., highest priority Root Identifier, lowest Root Path Cost, highest priority transmitting Bridge and Port), passes that information on to all the LANs for which it believes itself to be the Designated Bridge.

c. A Bridge that receives inferior information, on a Port it considers to be the Designated Port on the LAN to which it is attached, transmits its own information in reply, for all other Bridges attached to that LAN to hear.

The ports selected in the spanning tree are placed in the ‘forwarding’ state and other ports are placed in the ‘blocking’ state.

Configuration Message Format

The algorithm uses many parameters stored in configuration message to provide robustness and make it failure and change tolerant.

Fig 3 shows the configuration message format

FIG 3

The various fields are explained below:

Protocol Identifier: Contains 0

Version: Contains 0

Message Type: Contains 0

Flags:

TC – is set if the receiving bridge should use forward delay (explained later) for aging out station cache entries.

TCA – is set when the parent of the receiving bridge acknowledges the message that topology has been changed. After this, it is the responsibility of the parent bridge for advising the root of the topology change.

Root ID: This 8-octet ID contains 2-octet priority and 6-octet ID of the root bridge.

Root Path Cost: It is the cost from the transmitting bridge to the root bridge. (4-octets)

Bridge ID: The ID of the transmitting bridge. (2-octet priority plus 6-octet ID)

Port ID: It consists of 1-octet (local) priority and 1-octet ID. Port ID is unique for each port in a bridge.

Message Age: Time, in 256^th of a second, since the root originally transmitted its configuration message.

Max Age: Time, in 256^th of a second, at which the configuration message should be deleted.

Hello Time: Time, in 256^th of a second, between generation of subsequent configuration message by the root bridge.

Forward Delay: Time, in 256^th of a second, that bridges should stay in listening and learning states before transmitting a port from blocking to forwarding.

Bibliography

Radia Perlman, “Interconnections”, Second Edition, Pearson Education
ANSI/IEEE Std. 802.1D, 1998 Edition