This chapter describes the operation of a transparent bridge, including how a transparent bridge:

• Learns addresses

• Ages addresses

• Forwards packets

• Prevents loops in a network

A transparent bridge allows two or more LANs to be interconnected and to communicate as if they were one LAN. The bridge listens promiscuously to packets on another LAN. A packet is never retransmitted onto the LAN from which it was sourced.

Transparent bridging has been adopted for standardization by the IEEE and is defined in the IEEE 802.1d specification.

What Makes a Bridge 802.1d Compliant?

The IEEE 802.1d bridging standard specifies many requirements with
which a transparent bridge must comply. An 802.1d bridge must:

• Learn source addresses from packets transmitted by stations on attached LANs

• Age addresses of stations on attached LANs that have not transmitted a packet for a prolonged period of time

• Store and forward packets from one LAN to another

• Use the Spanning Tree Protocol for loop detection

The Switch 2200 system complies with all IEEE 802.1d bridging requirements.

How a Bridge Learns Addresses

Bridges learn addresses so that they can make intelligent decisions about which packets to forward from one bridge port to another. A bridge automatically learns addresses by listening on the network. For a bridge to learn the address of a station on the network, that station must transmit a packet. Each bridge maintains a dynamic table, called the address table, which contains all learned source addresses.

When a bridge receives a packet, it looks up the packet's source address in the address table, and does one of the following:

• If the source address is known to the bridge, then the bridge updates the source address entry in the address table and verifies the port on which the packet was received.

• If the source address is not known to the bridge, then the bridge stores the packet's source address in the address table, along with the port on which the packet was received. See Figure 5-1.

Figure 5-1 Learning Source Addresses

How a Bridge Ages Addresses

A source address remains in the address table as long as the station to which it relates regularly transmits through the bridge. If the station does not regularly transmit, the source address is "aged out" of the bridge's table. Address aging is primarily implemented to ensure that if a station moves to a different segment on the network, its address will be forgotten at the old location and packets will no longer be forwarded to that location. Address aging is also necessary because a bridge can learn only a finite number of addresses. The Switch 2200 system, when configured as an IEEE 802.1d bridge, can learn up to 8K addresses in its address table.

Address aging, although typically an efficient means of maintaining a current address table, can create problems when regularly used stations on the network do not transmit periodically. For instance, printers only transmit when they are powered on, yet printing is a function performed frequently on a network. In this case, the printer's address is aged out of the address table and the bridge no longer has the information it needs to send packets directly to that station.

To handle this situation, the Switch 2200 system allows you to statically configure the addresses of these stations. Because a statically configured address is not aged out of memory, it must be manually flushed when the station is removed from the network. Static configuration of Ethernet addresses and flushing static Ethernet addresses are described in the SuperStack II Switch 2200 Administration Console User Guide.

Packet Forwarding

A bridge either filters, floods, or forwards packets by comparing the packet's destination address to the addresses in the bridge's address table, and by comparing the destination bridge port (if known) to the port on which
the packet was received. This process is described and shown in
Figure 5-2.

The bridge compares the destination address to the addresses in the address table and does one of the following:

• If the destination address is known to the bridge, then the bridge identifies the port on which the destination address is located.

  • If the destination bridge port is different from the bridge port on which the packet was received, then the packet is forwarded to the destination bridge port.

  • If the destination bridge port is the same as the port on which the packet was received, then the packet is filtered (discarded) by the bridge.

• If the destination address is not known to the bridge, the packet is forwarded to all active bridge ports other than the bridge port on which the packet was received. This process is called flooding. For a port to be active, it must be enabled and in the forwarding state. See the section "Spanning Tree Port States" on page 5-16 for more information about states.

Figure 5-2 Forwarding, Filtering, and Flooding Packets

Spanning Tree and the Bridged Network

When transparent bridges are used to attach networks with redundant links, packets can loop and rapidly multiply on the attached LANs. These additional packets create traffic that might unnecessarily clog the LAN.

A loop exists if more than one path can be used to forward a packet from one station to another. To solve this problem, IEEE 802.1d bridging includes Spanning Tree Protocol, an algorithm that dynamically maps out a loopless network topology (a subset of the entire topology), ensuring that only one active path exists between every pair of LANs.

Packet Looping in a Bridged Network

Loops can occur on a bridged network for various reasons. In a network where reliability is key, network administrators often implement redundant links so that, although individual bridges might fail, the "networks" (data pathways) between stations remain active. Loops can also occur by accident. For instance, when more than one bridge is used to connect various LANs, the network manager might inadvertently configure the extended network with loops, causing packets to be circulated indefinitely.

A potential example of packet looping is shown in Figure 5-3. In this example:

1 . Packet 1 is transmitted on LAN 1.

2 . Bridges A, B, and C (connected to both LAN 1 and LAN 2) receive Packet 1 and forward it onto LAN 2, creating packets 1a, 1b, and 1c, respectively.

3 . Bridge A receives Packets 1b and 1c on LAN 2 and forwards them onto LAN 1; at the same time, Bridge B receives Packets 1a and 1c on LAN 2 and forwards them onto LAN 1. Bridge C follows this same pattern.

When multiple bridges receive the same packet, they each transmit a new copy of the packet onto the attached LANs. Consequently, the packets will loop and multiply indefinitely as they traverse the bridges.

Figure 5-3 Packets Looping and Multiplying without Spanning Tree

The Spanning Tree Algorithm

The Spanning Tree algorithm detects loops and logically blocks (eliminates) redundant paths by putting some bridge ports in the blocking state so that only one path exists between any two LANs and, therefore, between any two stations. See Figure 5-4. A port in the blocking state neither forwards nor receives data packets.

After the algorithm eliminates extra paths, the network configuration
stabilizes. When one or more of the bridges or communication paths in the stable topology fail, the protocol automatically recognizes the changed configuration and activates redundant links. This ensures that all stations remain connected.

Figure 5-4 Spanning Tree Implemented to Block Redundant Links

How the Spanning Tree Algorithm Works

The Spanning Tree algorithm is based on the idea that bridges transmit messages to each other that allow them to calculate the Spanning Tree topology. These messages are special packets called Configuration Bridge Protocol Data Units (CBPDUs), or configuration messages. CBPDUs are not propagated through the bridge like regular data packets. Instead, each bridge behaves as an end-station for these packets - receiving and interpreting them.

CBPDUs at work

The CBPDUs help the bridges establish a hierarchy among themselves (or a calling order) for the purposes of creating a loopless network. Based on the information in the CBPDUs, the bridges elect a root bridge, which is at the top level of the hierarchy. The bridges then choose the best path on which to transmit information to the root bridge.

The bridges chosen as the best path, called designated bridges, are the second level of the hierarchy. A designated bridge "relays" the network transmissions to the root bridge through its root port. Any port that transmits to the root bridge is a root port. The designated bridges also have
designated ports - the ports attached to the LANs from which the bridge is receiving information. Figure 5-5 shows the hierarchy of the Spanning Tree bridges and their ports.

Figure 5-5 Hierarchy of the Root Bridge and the Designated Bridge

From the information that the CBPDUs provide, the bridges:

• Elect a single bridge to be the root bridge. The root bridge has the lowest bridge ID among all the bridges on the extended network.

• Calculate the best path between themselves and the root bridge.

• Elect a designated bridge on each LAN from among the bridges residing
  on that LAN. This is the bridge with the least cost path to the root bridge.
  Its function is to forward packets between that LAN and the path to the
  root bridge. For this reason, the root bridge is always the designated bridge for its attached LANs. The port through which the designated bridge is attached to the LAN is elected the designated port.

• Choose a root port that gives the best path from themselves to the root bridge.

• Select ports to be included in the Spanning Tree topology. The ports selected include the root port plus any designated ports. Data traffic is forwarded to and from ports selected for inclusion in the Spanning Tree topology. Data traffic is never forwarded to or received on ports that are not selected for inclusion in the Spanning Tree topology.

Figure 5-6 shows a bridged network with its Spanning Tree elements.

Figure 5-6 Root and Designated Bridges and Ports in a Spanning Tree Topology

CBPDU's contents

The specific information that bridges receive from the CBPDU allows them to calculate a Spanning Tree topology:

• Root ID - The identification of the bridge assumed to be the root

• Cost - The cost of the least-cost path to the root from the transmitting bridge. One of the determining factors in cost is the speed of the bridge's network interface. In this case, the faster the speed, the lower the cost.

• Transmitting bridge ID - The identification of the bridge transmitting this CBPDU. The bridge ID consists of the bridge address and the bridge priority

• Port identifier - The port priority plus the number of the port from which the transmitting bridge sent a CBPDU. It is only used in the Spanning Tree calculation if the root IDs, transmitting bridge IDs, and costs (when compared) are equal. In other words, the port identifier is a tie breaker in which the lowest port identifier takes priority. This field is primarily useful for selecting the preferred port when two ports of a bridge are attached to the same LAN or when two routes are available from the bridge to the root bridge.

Comparing CBPDUs

Here are some examples showing how the best CBPDU is determined by the bridge. The root ID is the most important determining factor. If the root ID fields are equal, then the cost is compared. The last determining factor is the transmitting bridge ID. If the CBPDUs all have the same root ID, cost, and transmitting bridge ID, then the port identifier is used as a tiebreaker.

Example 1.

Message 1 has a lower root ID, so it is saved by the bridge.

Message 1			Message 2
root ID	cost	transmitter	root ID	cost	transmitter
12	15	35	31	12	32

Example 2.

Root ID is the same for both messages, but cost is lower in Message 1. Message 1 is saved.

Message 1			Message 2
root ID	cost	transmitter	root ID	cost	transmitter
29	15	80	29	18	38

Example 3

Root ID and cost are the same for both messages, but the transmitting bridge ID is lower in Message 1. Message 1 is saved.

Message 1			Message 2
root ID	cost	transmitter	root ID	cost	transmitter
35	80	39	35	80	40

How a bridge
handles CBPDUs

The following case describes how one bridge interprets CBPDUs, thus contributing to the Spanning Tree configuration. For purposes of this case, the following convention is used to depict a CBPDU:
root ID.cost.transmitter ID.

1 . When Spanning Tree is first started on a network, the bridge thinks that it is the root bridge and transmits a CBPDU from each of its ports with the following information:

• Its own bridge ID as the root ID (for example, 85)

• Zero (0) as the cost (because it thinks it is the root bridge)

• Its own bridge ID as the transmitting ID (for example, 85)

This CBPDU looks like: 85.0.85.

2 . The bridge receives CBPDUs on each of its ports from all other bridges.
It saves the "best" CBPDU from each port. The best one is determined by comparing the information in each message arriving at a particular port to the message the bridge currently has stored at that port. In general, the lower the values of the CBPDU, the "better" it is. When the bridge comes across a better CBPDU than it has stored, it replaces the old message with the new one.

3 . From the messages received, the bridge determines which bridge is the root bridge. For example, if the bridge receives a CPBDU with the contents 52.0.52, then it would assume that the bridge with the ID 52 is the root (because its root ID is smaller).

4 . Because the bridge now knows the root bridge, it can determine its distance to root and elect a root port. It examines CBPDUs from all ports to see which port has received a CBPDU with the smallest cost to the root. This port becomes the root port.

5 . Now that the bridge knows what its own CBPDU contains, it can compare this updated CBPDU with the ones received on its other ports. If the bridge's message is better than the ones received on any of its ports, then the bridge assumes that it is the designated bridge for the attached LANs.

If the bridge receives a better CBPDU on a port than the message it would transmit, it no longer transmits CBPDUs on that LAN. When the algorithm stabilizes, only the designated bridge transmits CBPDUs on that LAN.

How Spanning Tree Is Calculated for the Network

The following example illustrates how the Spanning Tree algorithm determines the Spanning Tree configuration on an entire network.

Determining the root bridge and root ports

In Figure 5-7, the network topology consists of six bridges connecting six LANs. The topology is designed with redundant links for backup purposes, which creates four loops in the extended network. When the Spanning Tree algorithm first runs, each bridge transmits a CBPDU that contains its bridge ID as both the root ID and the transmitting bridge ID, and zero as the cost.

Figure 5-7 Starting the Spanning Tree Calculation

The root ID portion of the CBPDU determines which bridge will be the root bridge. The bridges transmit their CBPDUs, receive each other's CBPDUs, and compare the CBPDUs to each other. Because Bridge B has the lowest root ID of all the bridges, it becomes the root. See Figure 5-8.

Figure 5-8 Spanning Tree Topology Calculated

Each bridge, except for the root bridge, must select a root port. To do this, each bridge determines the most cost-effective path for packets to travel from each of its ports to the root bridge. The cost depends on 1) the port's path cost, and 2) the root path cost of the designated bridge for the LAN to which this port is attached.

If the bridge has more than one port attachment, the port with the lowest cost becomes the root port, and the other ports become either designated or backup ports. If bridges have redundant links to the same LAN, then the port with the lowest port identifier becomes the root port. In Figure 5-8, Bridge F has two links to LAN 3 (through port 1 and port 2). Because the lowest port identifier for Bridge F is port 1, it becomes the root port, and port 2 becomes a backup port to LAN 3.

Determining the designated bridge and designated ports

If a LAN is attached to a single bridge, that bridge is the LAN's designated bridge. For a LAN that is attached to more than one bridge, a designated bridge must be selected from among the attached bridges. The root bridge is automatically the designated bridge for all the attached LANs.

For example, Bridge B, the root bridge in Figure 5-8, is also the designated bridge for LANs 1, 2, and 5. A designated bridge must still be determined for LANs 3, 4, and 6. Because Bridges C, D, and F are all attached to LAN 3, one of them must be the designated bridge for that LAN. The algorithm first compares the root ID of these bridges, which is the same for all. The cost is then compared. Bridge C and Bridge D both have a cost of 11. Bridge F, with a cost of 12 is eliminated as the designated bridge. Finally, the transmitting bridge ID is compared between Bridge C and Bridge D. Because Bridge C's ID (20) is smaller than Bridge D's (29), Bridge C becomes the designated bridge for LAN 3.

The designated bridge for LAN 6 is either Bridge D or Bridge E. Because Bridge D's transmitting bridge ID (29) is lower than Bridge E's (35), Bridge D becomes the designated bridge for that LAN. Finally, the designated bridge for LAN 4 is the only bridge attached to that LAN, Bridge F.

The designated port is determined by the port that attaches the designated bridge to the LAN. If there is more than one port attached to the LAN, then the port identifier determines which port is the designated port.

Spanning Tree
Port States

As the Spanning Tree algorithm determines the Spanning Tree configuration, it places ports in the following states: listening, learning, forwarding, blocking, or disabled. As changes occur in the network, the port may transition in and out of these states to maintain a loopless network. These states are described in Table 5-1.

Table 5-1 Spanning Tree Port States

Port State	Description
Listening	When Spanning Tree is configuring, all ports are placed in the listening state. Each port remains in this state until the root bridge is elected. While in the listening state, the bridge continues running the Spanning Tree algorithm and transmitting CBPDUs on the port; however, it discards data packets received on that port and does not transmit data packets from that port. The listening state should be long enough for a bridge to hear from all other bridges on the network (this time can be adjusted if necessary). After the time of the listening state, the bridge ports that are to proceed to the forwarding state go into the learning state. All other bridge ports go into the blocking state.
Learning	The learning state is similar to the listening state except that data packets are received on that port for the purpose of learning stations attached to that port. After spending the specified time in this state, if the bridge has still not heard any information that would make it transition the port back to the blocking state, then the bridge transitions the port to the forwarding state. The time the port spends in both the listening and learning states is determined by the value of the forward delay parameter. Forward delay is a timer that temporarily prevents a bridge from starting to forward data packets to and from a link until news of a topology change has spread to all parts of the network. This delay gives all links that need to be turned off in the new topology time to do so before new links are turned on.
Forwarding	Once in the forwarding state, the bridge performs standard bridging functions. It receives packets and either forwards or does not forward them, depending on address comparisons between the packet's destination address and the addresses in the bridge's address table.
Blocking	When a port is put in a blocking state, the bridge continues to receive CBPDUs on that port (monitoring for network reconfigurations), but it does not transmit them. Additionally, the bridge does not receive data packets from the port, learn locations of station addresses from it, or forward packets onto it.
(continued)
Disabled	A port is disabled when Spanning Tree has been turned off for that specific port or when the port has failed. In the disabled state, the port does not participate in the Spanning Tree algorithm. If Spanning Tree has been turned off for a specific port, that port will continue to forward frames only if Spanning Tree is disabled for the entire bridge.

Figure 5-9 illustrates the factors that cause a port to transition from one state to another. The arrows indicate the direction of movement between states. The numbers correspond to the factors that affect the transition.

For example, for a port in the blocking state to transition to the listening state, the Spanning Tree algorithm must select that port as a designated or root port. Once in the listening state, forward delay must expire before the port can transition to the learning state. When in listening, learning, and forwarding states, if a port is disabled by the network administrator or by a failure or initialization, then that port becomes disabled.

Figure 5-9 Factors Involved in Spanning Tree Port State Transitions

Reconfiguring the Bridged Network Topology

The Spanning Tree algorithm reconfigures the bridged network topology when 1) bridges are added or removed, 2) the root bridge fails, or 3) the network administrator changes the bridging parameters that determine the topology.

Whenever a designated bridge detects a topology change, it sends out a Topology Change Notification Bridge Protocol Data Unit (BPDU) through its root port. This information is eventually relayed to the root bridge. The root bridge then sets the Topology Change Flag in its CBPDU so that the information is broadcast to all the bridges. It transmits this CBPDU for a fixed amount of time to ensure that all bridges are informed of the topology change.

If a port transitions from the blocking state to the forwarding state as a result of the topology change, the algorithm ensures that it sends the topology information to all of the ports before that port starts forwarding data. This delay prevents temporary data loops.

As a result of a network reconfiguration, the bridge flushes all addresses from the address table. This action ensures that each active port still forwards packets to the right network after a topology change.

Bridging References

IEEE 802.1d MAC Bridges. D9, July 14, 1989.

Perlman, Radia. Interconnections: Bridges and Routers. Reading, Massachusetts: Addison-Wesley Publishing Company, Inc., 1992.