Lecture 03 – Spanning Tree
Protocol (IEEE 802.1d)
LECTURE 2: DEVICES AND SWITCHING
CONCEPTS
Layer 2 Redundant Links & Loop Problem
Redundant Links are required in a network especially
for Uplinks
When on link fails, the other one will work, but what
happens in a switched network when both links are
up and working?
5/10/2023 2
LECTURE 2: DEVICES AND SWITCHING
CONCEPTS
Layer 2 Redundant Links & Loop Problem
Switches learn the MAC addresses of devices on their ports so that
data can be properly forwarded to the destination.
Switches will flood frames for unknown destinations until they
learn the MAC addresses of the devices.
Broadcasts and multicasts are also flooded.
5/10/2023 3
LECTURE 2: DEVICES AND SWITCHING
CONCEPTS
Layer 2 Redundant Links &
Loop Problem
• Broadcasts and multicasts can cause problems in a switched network.
• If Host X sends a broadcast, like an ARP request for the Layer 2
address of the router, then Switch A will forward the broadcast out all
ports.
• Switch B, being on the same segment, also forwards all broadcasts.
• Switch B sees all the broadcasts that Switch A forwarded and Switch
A sees all the broadcasts that Switch B forwarded.
• Switch A sees the broadcasts and forwards them.
• Switch B sees the broadcasts and forwards them.
• The switches continue to propagate broadcast traffic over and over.
• This is called a broadcast storm (Caused by Switching Loop)
5/10/2023 4
LECTURE 2: DEVICES AND SWITCHING
CONCEPTS
Layer 2 Redundant Links & Loop Problem
Qn: How Can we Use Redundancy and Avoid
Loops?
5/10/2023 5
Spanning Tree Protocol (STP)
• What is STP?
• Why do we need it?
• How to configure STP
6
Loop Resolution with Spanning Tree
Protocol
• IEEE.802.1D standard
7
Spanning Tree Protocol (IEEE
802.1d)
• The Spanning-Tree Protocol constructs a topology that has one path for
reaching every network node
• Shortest path is based on cumulative link costs.
• Link costs are based on the speed of the link.
• The Spanning-Tree Protocol establishes a root node, called the Root
Bridge.
• The resulting tree originates from the Root Bridge.
• Redundant links that are not part of the shortest path tree are blocked.
Spanning-Tree Protocol (STP)
We will see how this
works in a moment.
9
Spanning-Tree Protocol (STP)
BPDU
• It is because certain paths are blocked that a loop free topology is possible.
• Data frames received on blocked links are dropped.
• The Spanning-Tree Protocol requires network devices to exchange messages
to detect bridging loops. , they are called a Bridge Protocol Data Unit
(BPDU).
• Links that will cause a loop are put into a blocking state.
• BPDUs continue to be received on blocked ports, this ensures that if an active
path or device fails, a new spanning tree can be calculated.
10
Spanning-Tree Protocol (STP)
BPDUs contain enough information so that all switches can do the
following:
• Select a single switch that will act as the root of the spanning tree
• Calculate the shortest path from itself to the root switch
• Designate one of the switches as the closest one to the root, for
each LAN segment. This bridge is called the “designated switch”.
– The designated switch handles all communication from that LAN
towards the root bridge.
• Choose one of its ports as its root port, for each non-root switch.
– This is the interface that gives the best path to the root switch.
• Select ports that are part of the spanning tree, the designated ports.
Non-designated ports are blocked.
11
Two Key Concepts: BID and Path Cost
• STP executes an algorithm called Spanning Tree Algorithm (STA).
• STA chooses a reference point, called a root bridge, and then
determines the available paths to that reference point.
– If more than two paths exists, STA picks the best path and blocks
the rest
• STP calculations make extensive use of two key concepts in creating a
loop-free topology:
– Bridge ID
– Path Cost
12
Bridge ID (BID)
• Bridge ID (BID) is used to identify each bridge/switch.
• The BID is used in determining the center of the network, in respect to
STP, known as the root bridge.
• Consists of two components:
– A 2-byte Bridge Priority: Cisco switch defaults to 32,768 or
0x8000.
– A 6-byte MAC address
13
Bridge ID (BID)
• Bridge Priority is usually expressed in decimal format and the MAC
address in the BID is usually expressed in hexadecimal format.
• BID is used to elect a root bridge
• Lowest Bridge ID is the root.
• If all devices have the same priority, the bridge with the lowest MAC
address becomes the root bridge.
14
Path Cost
• Bridges use the concept of cost to evaluate how close they are to other
bridges.
• This will be used in the STP development of a loop-free topology .
• Originally, 802.1d defined cost as 1000/bandwidth of the link in Mbps.
– Cost of 10Mbps link = 100 or 1000/10
– Cost of 100Mbps link = 10 or 1000/100
– Cost of 1Gbps link = 1 or 1000/1000
15
Path Cost
• IEEE modified the most to use a non-linear scale with the new values of:
– 4 Mbps 250 (cost)
– 10 Mbps 100 (cost)
– 16 Mbps 62 (cost)
– 45 Mbps 39 (cost)
– 100 Mbps 19 (cost)
– 155 Mbps 14 (cost)
– 622 Mbps 6 (cost)
– 1 Gbps 4 (cost)
– 10 Gbps 2 (cost)
16
Path Cost
• You can modify the path cost by modifying the cost of a port.
– Exercise caution when you do this!
• BID and Path Cost are used to develop a loop-free topology .
• But first the Four-Step STP Decision Sequence
17
Four-Step STP Decision Sequence
• When creating a loop-free topology, STP always
uses the same four-step decision sequence:
Four-Step decision Sequence
Step 1 - Lowest BID
Step 2 - Lowest Path Cost to Root Bridge
Step 3 - Lowest Sender BID
Step 4 - Lowest Port ID
• Bridges use Configuration BPDUs during this four-
step process.
18
Four-Step STP Decision Sequence
BPDU key concepts:
• Bridges save a copy of only the best BPDU seen on every port.
• When making this evaluation, it considers all of the BPDUs
received on the port, as well as the BPDU that would be sent on
that port.
• As every BPDU arrives, it is checked against this four-step
sequence to see if it is more attractive (lower in value) than the
existing BPDU saved for that port.
• Only the lowest value BPDU is saved.
• Bridges send configuration BPDUs until a more attractive BPDU
is received.
19
Three Steps of Initial STP Convergence
• The STP algorithm uses three simple steps to converge on a loop-
free topology.
• Switches go through three steps for their initial convergence:
STP Convergence
Step 1 Elect one Root Bridge
Step 2 Elect Root Ports
Step 3 Elect Designated Ports
• All STP decisions are based on a the following predetermined
sequence:
Four-Step decision Sequence
Step 1 - Lowest BID
Step 2 - Lowest Path Cost to Root Bridge
Step 3 - Lowest Sender BID
Step 4 - Lowest Port ID
20
Three Steps of Initial STP Convergence
STP Convergence
Step 1 Elect one Root Bridge
Step 2 Elect Root Ports
Step 3 Elect Designated Ports
21
Step 1 Elect one Root Bridge
Root
Bridge
Cost=19 1/1 1/2 Cost=19
Cat-A
1/1 1/1
Cat-B Cat-C
1/2 1/2
Cost=19
22
Step 1 Elect one
Root Bridge
• When the network first starts, all bridges are announcing a chaotic
mix of BPDUs.
• All bridges immediately begin applying the four-step sequence
decision process.
• Switches need to elect a single Root Bridge.
• Switch with the lowest BID wins!
• Note: Many texts refer to the term “highest priority” which is the
“lowest” BID value.
• This is known as the “Root War.”
23
Step 1 Elect one Root Bridge
Cat-A has the lowest Bridge MAC Address, so it wins the Root War!
All 3 switches have the same default Bridge Priority value of 32,768
24
Step 1 Elect one Root Bridge
BPDU Its all done with BPDUs!
802.3 Header
Destination: 01:80:C2:00:00:00 Mcast 802.1d Bridge group
Source: 00:D0:C0:F5:18:D1
LLC Length: 38
802.2 Logical Link Control (LLC) Header
Dest. SAP: 0x42 802.1 Bridge Spanning Tree
Source SAP: 0x42 802.1 Bridge Spanning Tree
Command: 0x03 Unnumbered Information
802.1 - Bridge Spanning Tree
Protocol Identifier: 0
Protocol Version ID: 0
Message Type: 0 Configuration Message
Flags: %00000000
Root Priority/ID: 0x8000/ 00:D0:C0:F5:18:C0
Cost Of Path To Root: 0x00000000 (0)
Bridge Priority/ID: 0x8000/ 00:D0:C0:F5:18:C0
Port Priority/ID: 0x80/ 0x1D
Message Age: 0/256 seconds (exactly 0 seconds)
Maximum Age: 5120/256 seconds (exactly 20 seconds)
Hello Time: 512/256 seconds (exactly 2 seconds)
Forward Delay: 3840/256 seconds (exactly 15 seconds)
Configuration BPDUs are sent every 2 seconds by default.
25
Step 1 Elect one Root Bridge
• At the beginning, all bridges assume they are the center of the
universe and declare themselves as the Root Bridge, by placing its
own BID in the Root BID field of the BPDU.
• Once all of the switches see that Cat-A has the lowest BID, they are all
in agreement that Cat-A is the Root Bridge.
26
Three Steps of Initial STP Convergence
STP Convergence
Step 1 Elect one Root Bridge
Step 2 Elect Root Ports
Step 3 Elect Designated Ports
27
Step 2 Elect Root Ports
Root
Bridge
Cost=19 1/1 1/2 Cost=19
Cat-A
1/1 1/1
Cat-B Cat-C
1/2 1/2
Cost=19
• Now that the Root War has been won, switches move on to selecting
Root Ports.
• A bridge’s Root Port is the port closest to the Root Bridge.
• Bridges use the cost to determine closeness.
• Every non-Root Bridge will select one Root Port!
• Specifically, bridges track the Root Path Cost, the cumulative cost of
all links to the Root Bridge.
28
Root
Bridge
Cost=19 1/1 1/2 Cost=19
Cat-A
1/1 1/1
Cat-B Cat-C
1/2 1/2
Cost=19
29
Step 2 Root
Bridge
Elect Root
Cost=19 1/1 1/2 Cost=19
BPDU Cat-A BPDU
Ports Cost=0 Cost=0
BPDU BPDU
1/1 Cost=0+19=19 Cost=0+19=19 1/1
Cat-B Cat-C
1/2 1/2
Cost=19
Step 1
• Cat-A sends out BPDUs, containing a Root Path Cost of 0.
• Cat-B receives these BPDUs and adds the Path Cost of Port 1/1 to the
Root Path Cost contained in the BPDU.
Step 2
• Cat-B adds Root Path Cost 0 PLUS its Port 1/1 cost of 19 = 19
30
Root
Bridge
Step 2 Cost=19 1/1 1/2 Cost=19
Elect Root Cat-A
BPDU BPDU
Ports Cost=0 Cost=0
BPDU BPDU
1/1
Cost=19 Cost=19 1/1
Cat-B Cat-C
1/2 BPDU BPDU 1/2
BPDU Cost=19 Cost=19 BPDU
Cost=38 (19=19) Cost=38 (19=19)
Cost=19
Step 3
• Cat-B uses this value of 19 internally and sends BPDUs with a Root
Path Cost of 19 out Port 1/2.
Step 4
• Cat-C receives the BPDU from Cat-B, and increased the Root Path
Cost to 38 (19+19). (Same with Cat-C sending to Cat-B.)
31
Root
Bridge
Step 2 Cost=19 1/1 1/2 Cost=19
Elect Root Cat-A
BPDU BPDU
Ports Cost=0 Cost=0
BPDU BPDU
Cost=19 Cost=19
1/1 1/1 Root
Root Port
Port
Cat-B Cat-C
1/2 1/2
BPDU BPDU
Cost=38 (19=19) Cost=38 (19=19)
Cost=19
Step 5
• Cat-B calculates that it can reach the Root Bridge at a cost of 19 via Port
1/1 as opposed to a cost of 38 via Port 1/2.
• Port 1/1 becomes the Root Port for Cat-B, the port closest to the Root
Bridge.
• Cat-C goes through a similar calculation. Note: Both Cat-B:1/2 and Cat-
C:1/2 save the best BPDU of 19 (its own). 32
Three Steps of Initial STP Convergence
STP Convergence
Step 1 Elect one Root Bridge
Step 2 Elect Root Ports
Step 3 Elect Designated Ports
33
Step 3 Elect
Designated
Ports
• The loop prevention part of STP becomes evident during this step, electing
designated ports.
• A Designated Port functions as the single bridge port that both sends
and receives traffic to and from that segment and the Root Bridge.
• Each segment in a bridged network has one Designated Port, chosen
based on cumulative Root Path Cost to the Root Bridge.
• The switch containing the Designated Port is referred to as the Designated
Bridge for that segment.
• To locate Designated Ports, lets take a look at each segment.
• Root Path Cost, the cumulative cost of all links to the Root Bridge.
34
Root
Root Path Cost = 0 Bridge Root Path Cost = 0
Cost=19 1/1 1/2 Cost=19
Segment 1 Segment 2
Cat-A
Step 3 Elect
Designated Ports
Root Path Cost = 19 Root Path Cost = 19
1/1 1/1
Root Port Root Port
Cat-B Cat-C
1/2 1/2
Root Path Cost = 19 Root Path Cost = 19
Segment 3
Cost=19
• Segment 1: Cat-A:1/1 has a Root Path Cost = 0 (after all it has the Root
Bridge) and Cat-B:1/1 has a Root Path Cost = 19.
• Segment 2: Cat-A:1/2 has a Root Path Cost = 0 (after all it has the Root
Bridge) and Cat-C:1/1 has a Root Path Cost = 19.
• Segment 3: Cat-B:1/2 has a Root Path Cost = 19 and Cat-C:1/2 has a Root
Path Cost = 19. It’s a tie!
35
Root
Root Path Cost = 0 Bridge Root Path Cost = 0
Cost=19 1/1 1/2 Cost=19
Segment 1 Segment 2
Cat-A
Step 3 Elect Designated Port Designated Port
Designated Ports
Root Path Cost = 19 Root Path Cost = 19
1/1 1/1
Root Port Root Port
Cat-B Cat-C
1/2 1/2
Root Path Cost = 19 Root Path Cost = 19
Segment 3
Cost=19
Segment 1
• Because Cat-A:1/1 has the lower Root Path Cost it becomes the
Designate Port for Segment 1.
Segment 2
• Because Cat-A:1/2 has the lower Root Path Cost it becomes the
Designate Port for Segment 2.
36
Root
Root Path Cost = 0 Bridge Root Path Cost = 0
Cost=19 1/1 1/2 Cost=19
Segment 1 Segment 2
Cat-A
Designated Port Designated Port
Root Path Cost = 19 Root Path Cost = 19
1/1 1/1
Root Port Root Port
Cat-B Cat-C
1/2 1/2
Root Path Cost = 19 Root Path Cost = 19
Segment 3
Cost=19
Segment 3
• Both Cat-B and Cat-C have a Root Path Cost of 19, a tie!
• When faced with a tie (or any other determination) STP always uses the four-
step decision process:
1. Lowest Root BID; 2. Lowest Path Cost to Root Bridge;
3. Lowest Sender BID; 4. Lowest Port ID
37
Root
Root Path Cost = 0 Bridge Root Path Cost = 0
Cost=19 1/1 1/2 Cost=19
Segment 1 Segment 2
Cat-A
Designated Port Designated Port
Root Path Cost = 19 Root Path Cost = 19
1/1 1/1
Root Port Root Port
Cat-B 32,768.CC-CC-CC-CC-CC-CC Cat-C
1/2 32,768.BB-BB-BB-BB-BB-BB 1/2
Root Path Cost = 19 Root Path Cost = 19
Designated Port Segment 3 Non-Designated Port
Cost=19
Segment 3 (continued)
• 1) All three switches agree that Cat-A is the Root Bridge, so this is a tie.
• 2) Root Path Cost for both is 19, also a tie.
• 3) The sender’s BID is lower on Cat-B, than Cat-C, so Cat-B:1/2 becomes the
Designated Port for Segment 3.
• Cat-C:1/2 therefore becomes the non-Designated Port for Segment 3.
38
STP Port States
• Time is required for (BPDU) protocol information to propagate
throughout a switched network.
• Topology changes in one part of a network are not instantly known in
other parts of the network.
• There is propagation delay.
• A switch should not change a port state from inactive (Blocking) to
active (Forwarding) immediately, as this may cause data loops.
• Each port on a switch that is using the Spanning-Tree Protocol has one
of five states, 39
40
STP Port States
• In the blocking state, ports can only receive BPDUs.
– Data frames are discarded and no addresses can be learned.
– It may take up to 20 seconds to change from this state.
• Ports go from the blocked state to the listening state.
– Switch determines if there are any other paths to the root bridge.
– The path that is not the least cost path to the root bridge goes back to
the blocked state.
– The listening period is called the forward delay and lasts for 15 seconds.
– In the listening state, user data is not being forwarded and MAC addresses
are not being learned.
– BPDUs are still processed.
41
STP Port States
• Ports transition from the listening to the learning state.
– In this state user data is not forwarded, but MAC addresses are
learned from any traffic that is seen.
– The learning state lasts for 15 seconds and is also called the forward
delay.
– BPDUs are still processed.
• A port goes from the learning state to the forwarding state.
– In this state user data is forwarded and MAC addresses continue to be
learned.
– BPDUs are still processed.
42
X Fails Not seeing BPDU from Cat-B
Ages out BPDU and goes into Listening mode
Hub
• Cat-B:1/2 fails.
• Cat-C has no immediate notification because it’s still receiving a link
from the hub.
• Cat-C notices it is not receiving BPDUs from Cat-B.
• 20 seconds (max age) after the failure, Cat-C ages out the BPDU that
lists Cat-B as having the DP for segment 3.
• Hub into the Listing state (15
This causes Cat-C:1/2 to transition
seconds) in an effort to become the DP.
43
X Fails
Forwarding
ListeningMode
Mode
Hub
• Because Cat-C:1/2 now offers the most attractive access from the Root
Bridge to this link, it eventually transitions to Learning State (15
seconds), then all the way into Forwarding mode.
• In practice this will take 50 seconds (20 max age + 15 Listening + 15
Learning) for Cat-C:1/2 to take over after the failure of Cat-B:1/2.
Hub
44
Port Cost/Port ID
Blocking
0/2 X
0/1
Forwarding
Assume path cost and port priorities are
default (32). Port ID used in this case.
Port 0/1 would forward because it’s the
lower than Port 0/2.
• If the path cost and bridge IDs are equal (as in the case of parallel
links), the switch goes to the port priority as a tiebreaker.
• Lowest port priority wins (all ports set to 32).
• You can set the priority from 0 – 63.
• If all ports have the same priority, the port with the lowest port number
forwards frames.
45
Port Cost/Port ID
• If all ports have the same priority, the port with the lowest port number
forwards frames.
46
