INTERNET TEACHING LAB: SPANNING TREE PROTOCOL
INSTRUCTOR VERSION
Overview
The Spanning Tree Protocol, also known as the Djistrja’s Algorithm, is documented in the IEEE 802.1D standard. It is implemented in many current routers, bridges, and switches to provide a loop-free network topology. It is popular to build layer2 networks with redundant network connections to improve reliability, but the redundancy can lead to broadcast storms. Spanning Tree Protocol provides a mechanism for network devices to learn the network topology, elect a root bridge, and selectively block ports to form a loop-free spanning tree. We will explore some of the capabilities of this protocol, advantages, and limitations. The IEEE spanning tree protocol was first implemented in the DEC LAN Bridge 100 in the mid 1980s by Dr. Radia Perlman whose text book, Interconnections, now in the second edition, is the definitive reference.
Configuration
We will explore the Cisco Router implementation of 802.1D. Set up the physical cabling as specified in diagram above. The initial configuration for all five routers is listed at the end of this document also also on text file span-config.txt. Log into each of the five routers R1, R2, R3, R4, and R5, go into router configuration mode, and paste the appropriate configuration commands. Verify that all appropriate interfaces are up and that everything is cabled to the correct routers and ports. Use the commands “show ip interface”, “show ip interface brief”, and “show cdp neighbors” for verification.
(Sample “show cdp neighbors”)
r1#show cdp neighbors
Capability Codes: R - Router, T - Trans Bridge, B - Source Route Bridge
S - Switch, H - Host, I - IGMP, r - Repeater
Device ID Local Intrfce Holdtme Capability Platform Port ID
r2 Fddi0/0 137 R T RP1 Fddi0/0
r2 Ser 1/2 137 R T RP1 Ser 1/1
r3 Ser 1/3 176 R T RP1 Ser 1/1
r3 Fddi0/0 176 R T RP1 Fddi0/0
r4 Fddi0/0 173 R T RP1 Fddi0/0
r5 Fddi0/0 127 R T 4500 Fddi0
r5 Eth 2/1 127 R T 4500 Eth 1
r1#
(Sample “show ip interface brief”)
r2#show ip int brief
Interface IP-Address OK? Method Status Protocol
Fddi0/0 unassigned YES unset up up
Serial1/0 unassigned YES unset administratively down down
Serial1/1 unassigned YES unset up up
Serial1/2 unassigned YES unset administratively down down
Serial1/3 unassigned YES unset up up
Serial1/4 unassigned YES unset up up
Serial1/5 unassigned YES unset administratively down down
Serial1/6 unassigned YES unset administratively down down
Serial1/7 unassigned YES unset administratively down down
Setup PCs
Configure PCs S1 and S2 with IP addresses in the same IP network. Verify that you can PING between the two PCs. (Hint: If this does not work you can test the PCs by temporarily connecting them to the same physical Ethernet segment or by using a 10baseT Ethernet crossover cable. You may have difficulty if your router interface accidently has an IP address on one of the bridge interface in which case it may be routing IP protocol and bridging non-IP traffic. You can verify that the router is bridging IP traffic on the appropriate interfaces with the command “show interface crb”)
Try sending a series of PINGs from S1 à S2 using both small 64-byte packets and large 1500-byte packets and note the average round-trip time. Repeat this test while S1 and S2 are temporarily directly connected. Compare the numbers and if substancially different, explain why.
There are redundant connections in your network and we want to determine the physical path between S1 and S2 used by the PING packets. First, determine the Ethernet MAC addresses for the NIC cards in S1 and S2. (Hint: If two devices on the same IP network have recently communicated, you will find each other’s Ethernet MAC address inside their respective ARP caches which can be displayed with the command “arp –a”)
Use the command “show bridge 1” on each router to display the bridge forwarding table and find the S1 and S2 entries. Record the forwarding path on your network diagram.
r2#show bridge 1
Total of 300 station blocks, 298 free
Codes: P - permanent, S - self
Bridge Group 1:
Address Action Interface Age RX count TX count
0000.0c11.2233 forward Serial1/4 4 1 0
0000.0c44.5566 forward Serial1/1 4 1 0
Bridge IDs and Port Path Cost
Using the command “show span 1”, determine which router is the root bridge and indicate it on your network diagram. This implementation of 802.1D computes the port path cost by dividing 1,000,000,000 by the bandwidth of the port in bits/second. This gives us the following port costs for the connections in your network:
|
INTERFACE
TYPE |
BANDWIDTH |
PORT
PATH COST |
|
56K
SERIAL |
56,000
bits/sec |
17857 |
|
10M
ETHERNET |
10,000,000
bits/sec |
100 |
|
FDDI |
100,000,000
bits/sec |
10 |
Given your diagram, knowledge of the root bridge, and above table, manually compute the spanning tree algorithm. For each bridge port, indicate the port state (F=forwarding, B=blocking) as well as the port type (RP=root port, DP=designated port, NDP=non-designated port).
Verify your calculations by comparing them with the output of the command “show spanning-tree 1” on each router.
r2#show spanning-tree 1
Bridge Group 1 is executing the IEEE compatible Spanning Tree protocol
Bridge Identifier has priority 100, address 0000.0c00.22d9
Configured hello time 2, max age 20, forward delay 15
Current root has
priority 50, address 0000.0c36.f9b0
Root port is 87 (Serial1/4), cost of root path is 17867
Topology change flag not set, detected flag not set
Times: hold 1, topology change 30, notification 30
hello 2, max age 20, forward delay 15, aging 300
Timers: hello 0, topology change 0, notification 0
Port 84 (Serial1/1) of bridge group 1 is blocking
Port path cost 17857, Port priority 128
Designated root has priority 50, address 0000.0c36.f9b0
Designated bridge has priority 32768, address 0000.0c39.dfc4
Designated port is 85, path cost 100
Timers: message age 2, forward delay 0, hold 0
Port 86 (Serial1/3) of bridge group 1 is forwarding
Port path cost 17857, Port priority 128
Designated root has priority 50, address 0000.0c36.f9b0
Designated bridge has priority 100, address 0000.0c00.22d9
Designated port is 86, path cost 17867
Timers: message age 0, forward delay 0, hold 0
Port 87 (Serial1/4) of bridge group 1 is forwarding
Port path cost 17857, Port priority 128
Designated root has priority 50, address 0000.0c36.f9b0
Designated bridge has priority 32768, address 0000.0c50.3d70
Designated port is 85, path cost 10
Timers: message age 3, forward delay 0, hold 0
Bridge Protocol Data Units
On one of your routers with a blocked bridge port, issue the command “show interface xxx” where xxx is the name of the blocked interface/port. Note the input and output packet counters. Are they incrementing? If so, why are they incrementing? Instead of doing the arithmetic, you may find it easier to “clear counters” to zero the counters before you start.
The Cisco router has a number of debug modes used to diagnose network problems. Although sometimes dangerous to use on a production network, they are very good tools in a lab environment. The command “term monitor” will enable debug messages to be displayed on your router session and disabled with “term no monitor”. Try turning on the spanning tree topology change debug with “debug spanning tree” until you collect a few messages, then turn it off with “undebug all”. You should see some bridge protocol data unit packets represented in hexadecimal. You should be able to spot the MAC address of your root bridge embedded in the packet. Using the following table, decode the root bridge ID (priority and MAC address), sending bridge ID (priority and MAC address), root path cost, and timers.
|
FIELD |
OCTETS |
FUNCTION |
|
Protocol
ID |
2 |
future
(always zero) |
|
Version |
1 |
future
(always zero) |
|
Type |
1 |
BPDU Type
(0=config BPDU) |
|
Flags |
1 |
LSB
(topolgy chg flash), MSB (Topology chg ACK) |
|
Root BID |
8 |
Bridge ID
of root (16bit priority + 48bit MAC) |
|
Root Path
Cost |
4 |
Cumulative
cost to root bridge |
|
Sending
BID |
8 |
Bridge ID
of sender (16bit priority + 48bit MAC) |
|
Port ID |
2 |
Port ID
that sent this BPDU |
|
Message
Age |
2 |
Age of
root BPDU |
|
Max Age |
2 |
Max age
to save BPDU info (default = 20s) |
|
Hello
Time |
2 |
Time
between sending consecutive BPDUs (default = 2s) |
|
Forward
Delay |
2 |
Time
spent in listening and learning states in FSM (default = 15s) |
Output from "debug spanning tree":
ST: Ethernet2/1
0000000000006400000C503D700000000A800000000C36F9B080030100140002000F00
ST: Serial1/0
0000000000006400000C503D7000000000006400000C503D7080540000140002000F00
ST: Ethernet2/1
0000000000006400000C503D700000000A800000000C36F9B080030100140002000F00
This is a hexadecimal representation of the BPDU. Here is a manual
decode for the above BPDU:
0000 Protocol ID (always zero)
00 Version (always zero)
00 BPDU Type (0=Configuration BPDU)
00 Flags (LSB=Topology Change flag, MSB=Topology Change Ack)
0064 00000C503D70 Root BID [priority (100) + MAC address]
0000000A Root Path Cost (10) (Cumulative Cost to Root Bridge)
8000 00000C36F9B0 Sender BID [priority (32768) + MAC address]
8003 Port ID
01 Message Age
0014 Max Age (20 seconds)
0002 Hello Time (2 seconds)
000F Forward Delay (15 seconds)
00
Finite State Machine
Bridge ports can be in one of five states: disabled, blocking, listening, learning, and forwarding. See the diagram span-fsm.pdf to see what events cause transitions between different states. Log into one of your routers and identify a bridge interface in the forwarding state. Turn on spanning tree topology events debugging with “debug spanning events” and shut down the interface with “interface xyz” and “shutdown”. Wait a minute, then turn it back on with “no shutdown”. Note the state changes as it transitions from the disabled to the forwarding state including intermediate states. Record how much time was spent in each state. Turn off debugging with “undebug all”.
TEST TCP
Locate the program TTCP by searching the Internet. At the time of this writing, it was available for anonymous/ftp download at ftp://FTP.ARL.MIL/pub/ttcp. It is a TCP/IP benchmarking program. There are both C-language versions, usually named ttcp.c, and java implementations that work on Windows systems. You basically start this program on one system in receive mode, then start the other copy in transmit mode and supply the IP address of the receiver. The utility sends several blocks of data (you specify how many blocks and how many bytes per block) then displays statistics in Bytes/Second and Bits/Second on speed of the transfer. Use this tool to measure the network performance from S1 à S2 traversing your network. How many bits per second did you achieve? Study your network diagram paying particular attention to your router link speeds and which interfaces are blocked. As packets traverse your network, your throughput is affected factors such as the speed of the links traversed, congestion, router CPU load and switching method, errors, etc. If you focus on the link speeds, is there a better (faster) path through your network that is not used? Determine which bridge should be made the root bridge in order to maximize the S1 à S2 throughput and change your configuration to make it so. Is there an optimal solution or more than one equally good solution? Repeat your S1 à S2 test and compare results with the first time. (Hint: The bridge with lowest bridge ID is elected the root. BIDs are 64-bit numbers by concatenating the bridge priority with the bridge MAC address. Although you normally cannot change the MAC address, you can change the bridge priority.) What is the slowest link traversed in the new network configuration? Was your throughput significantly less than your slowest link speed? Why? (Hint: read up on CSMA/CD)
(The original configurations set the bridge priority of R2 to 100, while all other routers are set to the default of 32768. This will cause R5 to block its Ethernet port E1. Traffic from S1 à S2 will therefore traverse the slow 56Kbps serial links. Selecting R1, R4, or R5 as the root bridge should work equally well by unblocking the 10Mbps Ethernet ports connecting R1 and R5. This can be accomplished by adding the “bridge 1 priority xxx” command on any of R1, R4, or R5 where xxx is less than 100. The slowest link in the path traversed is now a half-duplex 10Mbps Ethernet. Although the bit rate is actually 10Mbps, the throughput will be much lower typically in the 3Mbps to 5Mbps range due to CSMA/CD (Carrier Sense Multiple Access with Collision Detection), the protocol Ethernets use to retransmit when collisions occur on an Ethernet bus.)
(Sample TTCP
run on a Cisco Router)
bfs-standby#ttcp
transmit or
receive [receive]: transmit
Target IP
address: 128.186.6.254
perform tcp
half close [n]:
send buflen
[8192]:
send nbuf
[2048]:
bufalign
[16384]:
bufoffset [0]:
port [5001]:
sinkmode [y]:
buffering on
writes [y]:
show tcp
information at end [n]:
ttcp-t:
buflen=8192, nbuf=2048, align=16384/0, port=5001 tcp
-> 128.186.6.254
ttcp-t:
connect (mss 1460, sndwnd 4128, rcvwnd 4128)
ttcp-t:
16777216 bytes in 23508 ms (23.508 real seconds) (~696 kB/s) +++
ttcp-t: 2048
I/O calls
ttcp-t: 0
sleeps (0 ms total) (0 ms average)
bfs-standby#
INITIAL ROUTER
CONFIGURATION: