Learning Bridges &
Spanning Tree Algorithm
Unit -2
Learning Bridges & Spanning Tree Algorithm
Just Above the Data Link Layer
Application
• Bridging
Presentation • How do we connect LANs?
Session • Function:
Transport • Route packets between LANs
Network • Key challenges:
• Plug-and-play, self configuration
Data Link • How to resolve loops
Physical
2
Learning Bridges & Spanning Tree Algorithm
Background
• Originally, Ethernet was a broadcast technology
Terminator
Repeater
Tee Connector
Pros: Simplicity Hub
Hardware is stupid and cheap
Cons: No scalability
More hosts = more collisions = pandemonium
3
Learning Bridges & Spanning Tree Algorithm
The Case for Bridging
• Need a device that can bridge different LANs
• Only forward packets to intended recipients
• No broadcast!
Send Packet A Send Packet A
BC BC
Bridge
B Hub B
4
C C
Learning Bridges & Spanning Tree Algorithm
Bridging the LANs
Hub
Hub
• Bridging limits the size of collision domains
• Vastly improves scalability
• Question: could the whole Internet be one bridging domain?
• Tradeoff: bridges are more complex than hubs
• Physical layer device vs. data link layer device 5
• Need memory buffers, packet processing hardware, routing tables
Learning Bridges & Spanning Tree Algorithm
Bridge Internals
Bridge Hub
Inputs Outputs
Switch
Fabric
Makes
Memory routing
buffer
•decisions
Bridges have memory buffers to queue packets
• Bridge is intelligent, only forwards packets to the correct
output 6
• Bridges are high performance, full N x line rate is possible
Learning Bridges & Spanning Tree Algorithm
Bridges
• Original form of Ethernet switch
• Connect multiple IEEE 802 LANs at layer 2
1.• Goals
Forwarding of frames
2. Learning
• Reduce theof (MAC)
collision Addresses
domain
3. • Complete transparency
Spanning Tree Algorithm (to handle loops)
• “Plug-and-play,” self-configuring
• No hardware of software changes on hosts/hubs
• Should not impact existing LAN operations
Hub
7
Learning Bridges & Spanning Tree Algorithm
Frame Forwarding Tables
MAC Address Port Age
00:00:00:00:00:AA 1 1 minute
00:00:00:00:00:BB 2 7 minutes
00:00:00:00:00:CC 3 2 seconds
00:00:00:00:00:DD 1 3 minutes
• Each bridge maintains a forwarding table
8
Learning Bridges & Spanning Tree Algorithm
Frame Forwarding in Action
Port 1
Port 4 Port 2
Port 3
• Assume a frame arrives on port 1
• If the destination MAC address is in the forwarding table,
send the frame on the correct output port
• If the destination MAC isn’t in the forwarding table, 9
broadcast the frame on all ports except 1
Learning Bridges & Spanning Tree Algorithm
Learning Addresses
• Manual configuration is possible, but…
• Time consuming
• Error Prone
• Not adaptable (hosts may get added or removed)
• Instead, learn addresses using a simpleDelete
heuristic
old entries
• afterport
Look at the source of frames that arrive on each a timeout
MAC Address Port Age
00:00:00:00:00:AA 1 0 minutes
00:00:00:00:00:AA
00:00:00:00:00:BB 2 0 minutes
Port 1 Port 2
10
Hub 00:00:00:00:00:BB
Learning Bridges & Spanning Tree Algorithm
Complicated Learning Example
Bridge 1 Bridge 2
AA 1 AA 1
CC 2 CC 1
EE 2 EE 2
• <Src=AA, Dest=FF>
• <Src=CC, Dest=AA> Port 1 Port 2 Port 1 Port 2
• <Src=EE, Dest=CC>
Hub Hub Hub
11
AA BB CC DD EE FF
Learning Bridges & Spanning Tree Algorithm
The Danger of Loops
• <Src=AA, Dest=DD> CC DD
• This continues to infinity
• How do we stop this?
• Remove loops from the Hub
topology
• Without physically unplugging Port 2 Port 2
cables AA 12 AA 12
• 802.1 uses an algorithm to Port 1 Port 1
build and maintain a spanning
tree for routing Hub
12
AA BB
Learning Bridges & Spanning Tree Algorithm
Spanning Tree Definition
• A subset of edges in a graph that:
• Span all nodes
• Do not create any cycles
• This structure is a tree
5
1 2 3 4 6 2
5 3
4 1
6 7 13 7
Learning Bridges & Spanning Tree Algorithm
802.1 Spanning Tree Approach
1. Elect a bridge to be the root of the tree
2. Every bridge finds shortest path to the root
3. Union of these paths becomes the spanning tree
• Bridges exchange Configuration Bridge Protocol Data
Units (BPDUs) to build the tree
• Used to elect the root bridge
• Calculate shortest paths
• Locate the next hop closest to the root, and its port
• Select ports to be included in the spanning trees
14
Learning Bridges & Spanning Tree Algorithm
Definitions
• Bridge ID (BID) = <Random Number>
• Root Bridge: bridge with the lowest BID in the tree
• Path Cost: cost (in hops) from a transmitting bridge to the
root
• Each port on a bridge has a unique Port ID
• Root Port: port that forwards to the root on each bridge
• Designated Bridge: the bridge on a LAN that provides the
minimal cost path to the root
• The designated bridge on each LAN is unique
15
Learning Bridges & Spanning Tree Algorithm
Determining the Root
• Initially, all hosts assume they are the root
• Bridges broadcast BPDUs:
Root ID Path Cost to Root Bridge ID
• Based on received BPDUs, each switch chooses:
• A new root (smallest known Root ID)
• A new root port (what interface goes towards the root)
• A new designated bridge (who is the next hop to root)
16
Learning Bridges & Spanning Tree Algorithm
Comparing BPDUs
BPDU1 BPDU2
R1 Cost1 B1 R2 Cost2 B2
if R1 < R2: use BPDU1
else if R1 == R2 and Cost1 < Cost2: use BPDU1
else if R1 == R2 and Cost1 == Cost 2 and B1 < B2: use BPDU1
else: use BPDU2
17
Learning Bridges & Spanning Tree Algorithm
Spanning Tree Construction
0: 0/0 12:
12:12/0
0/1 3: 0/2
3/0
27: 27/0
27: 0/1 41: 3/1
41:41/0
0/2
3/2
9: 0/3
9/0 68: 3/2
9/1
68:68/0
0/3
18
Learning Bridges & Spanning Tree Algorithm
Bridges vs. Switches
• Bridges make it possible to increase LAN capacity
• Reduces the amount of broadcast packets
• No loops
• Switch is a special case of a bridge
• Each port is connected to a single host
• Either a client machine
• Or another switch
• Links are full duplex
• Simplified hardware: no need for CSMA/CD!
• Can have different speeds on each port
19
Learning Bridges & Spanning Tree Algorithm
Switching the Internet
• Capabilities of switches:
• Network-wide routing based on MAC addresses
• Learn routes to new hosts automatically
• Resolve loops
• Could the whole Internet be one switching domain?
NO
20
Learning Bridges & Spanning Tree Algorithm
Limitations of MAC Routing
• Inefficient
• Flooding packets to locate unknown hosts
• Poor Performance
• Spanning tree does not balance load
• Hot spots
• Extremely Poor Scalability
• Every switch needs every MAC address on the Internet in its
routing table!
21
