Fundamentals of L2 Switching - Part:2

3. Spanning Tree 

3.1 In a switched network with redundant paths (i.e. with loops), the following problems will occur:

_ Broadcast Storm - A broadcast or multicast frame will be forwarded by a switch out all its active ports except the source port. The resulted frames will then beforwarded by the other switches in the network similarly. Some of the frames will be forwarded around the network loop and back to the original switch. The process then repeats. Therefore, the frames will loop indefinitely in the network and eventually exhaust the processing power of the switches and the bandwidth of the network.

_ Receiving multiple copies of a frame - When a switch receives an unicast frame to a destination device that it does not have an entry in its bridge table, it will forward the frame out all its active ports except the source port. Therefore, the destination device may receive multiple copies of the frame through the redundant links.

_ Bridge Table Thrashing - A switch may receive frames from a source device at more than one ports if there are redundant links. It needs to update its bridge table whenever a frame from the source device arrives at a port differs from the last time. If the arrival frequency of such frames is high, the processing power of the switch will be exhausted.

Spanning Tree Protocol Basics

3.2 Spanning Tree Protocol or STP (IEEE 802.1d) is used to solve the looping problem. It runs on bridges and switches in a network. It implements a Spanning Tree Algorithm (STA), which calculates a loop-free topology for the network.

3.3 STP ensures that there is only one active path between any two network segments by blocking the redundant paths. A redundant path is used only when the corresponding active path failed. It is not used for load-balancing.

3.4 Because STP solves the looping problem by blocking one or more links in a network, the frames traveling between some source / destination devices may not be able to use the shortest physical path.

3.5 Bridges exchange STP information using messages called Bridge Protocol Data Units (BPDUs) through Layer 2 multicast.

3.6 A port of a bridge running STP can be in one of the following 5 states:

State	Handling of BPDUs	Learning MAC addresses	Handling of frames
Disabled (administratively down)	Does not receive BPDUs	Does not learn addresses	Discards frames received
Blocking (default state when a bridge is powered on)	Receives BPDUs	Does not learn addresses	Discards frames received
Listening (a blocking port goes through this state before entering the learning state)	Receives and forwards BPDUs	Does not learn addresses	Discards frames received
Learning (a listening port goes through this state before entering the forwarding state)	Receives and forwards BPDUs	Learns addresses	Discards frames received
Forwarding (all ports in the forwarding state belong to the current spanning tree)	Receives and forwards BPDUs	Learns addresses	Receives and forwards frames

By default, the transition from the blocking state to the listening state takes 20 seconds (MaxAge time), from the listening state to the learning state takes 15 seconds (FwdDlay time), and from the listening state to the forwarding state takes another 15 seconds (FwdDlay time). The whole process takes 50 seconds.

3.7 In a network without any network topology change, all bridge ports should be either in the forwarding state or the blocking state. When there is a change in the status of a port (e.g. a port is brought up), the spanning tree topology may change and some ports may transit from the blocking state to the forwarding state (through the listening state and the learning state) or vice versa.

3.8 Convergence refers to the condition that all bridge ports in a network have transitioned to either the forwarding state or the blocking state after a network topology change.

3.9 A spanning tree consists of a root bridge, which likes the root of a living tree. There is only one root bridge in the whole switched network. There is a single path from the root bridge (root) to each network segment (leaf). The paths form the spanning tree of the network. The bridges place the interfaces on the spanning tree in the forwarding state, and the interfaces not on the spanning tree in the blocking state.

3.10 Each bridge has an 8-byte Bridge ID, which is the concatenation of the priority (2-byte) and the MAC address (6 byte) of the bridge. The default priority of a device is 32,768.

3.11 The bridge with the lowest bridge ID is elected as the root bridge.

3.12 The root path cost of a bridge (i.e. cost of the path from the bridge to the root bridge) is the accumulated cost of the links along the root path. The cost of a link is determined by its bandwidth. The following default costs are used for different types of links:

Link Speed	New IEEE Cost	Original IEEE Cost
10Gpbs	2	1
1Gpbs	4	1
100 Mbps	19	10
10Mbps	100	100

3.13 In a spanning tree, the ports of a non-root bridge can be classified as follows:

_ Root port - The root port of a bridge is the port that is the closest to the root bridge in terms of path cost. The path cost can be calculated based on the information stored in the BPDUs sent by the root bridge (to be explained later in this Section).

_ Designated port - For each physical network segment, the bridge with the lowest cost to the root bridge is elected as the designated bridge of that segment. If two or more bridges have the same cost to the root bridge, the bridge with the lowest bridge ID is elected. The designated bridge puts the port connected to that segment in the forwarding state. This port is known as a designated port. For those segments that are directly connected to the root bridge, the root bridge is their designated bridge.

3.14 In determining which is the root port of a non-root bridge, if there are two or more ports with equal root path cost, the following factors are used as the tiebreaker in sequence:

_ Sender Bridge ID, i.e. the bridge ID of the next bridge in the path to the root bridge (the lowest one is preferred).

_ Sender Port ID (the lowest one is preferred).

3.15 The Port ID of a port is 2 bytes long, and is the concatenation of the port priority (1-byte) and the physical port number (1 byte).

3.16 Other than the ports of the root bridge, the root port of each non-root bridge, and the designated port of each LAN segment, all ports in the network are put in the blocking state.

In summary, STP works as follows:

Election of the root bridge

1. When a bridge is powered up, it claims to be the root bridge by sending Hello BPDUs with its bridge ID as the root bridge's ID and the cost to the root bridge equals 0.

2. The bridge with the lowest bridge ID is elected as the root bridge.

3. The root bridge puts all its ports in the forwarding state.

Selection of the root port for each non-root bridge

4. The root bridge continually sends Hello BPDUs out all its ports every Hello time interval.

5. When a non-root bridge receives a Hello BPDU, it modifies the packet by incrementing the cost field, and then forwards the packet out all its ports (except the port at which the packet is received).

6. Each non-root bridge compares the cost value of the BPDUs received from different ports. The port that receives the lowest-cost BPDU is the root port of the bridge. The bridge then puts the root port in the forwarding state.

Election of the designated bridge for each LAN segment

7. For each physical network segment, the bridge with the lowest cost to the root bridge is elected as the designated bridge of that segment. The designated bridge then puts the port connected to that segment in the forwarding state. This port is known as the designated port.

Blocking of redundant links for loops removal

8. Other than the ports on the spanning tree, i.e. ports of the root bridge, the root port of each non-root bridge, and the designated port of each LAN segment, all ports are put in the blocking state.

3.26 For example, in the following network, Switch X has the lowest bridge ID and is elected as the root bridge. Its ports are in the forwarding state. The root ports of Switch Y and Z are also in the forwarding state. Both Switch Y and Z have the same cost to the root bridge (Switch X), but Switch Y has a lower bridge ID. Therefore, Switch Y is elected as the designated bridge for the network segment between Switch Y and Z. The non-designated port of Switch Z is put in the blocking state.

                                                          Fig -1

3.27 Now, if the link between Switch X and Switch Z failed, the following changes will happen:

1. When Switch Z detects the link failure or it has not received any Hello BPDU from Switch X for a time period of MaxAge (worst case), it either advertises itself as the root for re-election of the root bridge, or selects another port as its root port. Since it still receives BPDUs from Switch Y and knows that the bridge ID of Switch X is lower than itself, it selects the port to Switch Y as its new root port.

2. Switch Z puts the port to Switch Y in the listening state (from the blocking state). It also sends a TCN BPDU out the port to Switch Y.

3. Switch Y forwards the TCN BPDU towards the root bridge, i.e. Switch X, and acknowledges the TCN BPDU (by setting the TCA bit of the next Configuration BPDU received from the root bridge and forwarding it to Switch Z).

4. Switch X sends a Configuration BPDU downstream to Switch Y, with the TC bit set. Switch Y forwards the BPDU to Switch Z. Both Switch Y and Z then change the aging time of their bridge table entries from 300 seconds to the forward delay time. Therefore an entry will be aged out if no frame is received from the host specified in the entry within the forward delay time.

5. When the forward delay timer expires, Switch Z puts the port to Switch Y in the learning state (from the listening state), and learns MAC addresses based on received frames.

6. When the forward delay timer expires again, Switch Z puts the port to Switch Y in the forwarding state (from the learning state), and starts forwarding frames through this interface.