Tcp/ip explanation (version 2) notes / 3 link layer / 3.4 bridge and switch / 3.4.1 spanning tree protocol (STP)

Catalog 、 reference

---

3.4.1 Spanning tree protocol （Spanning Tree Protocol (STP)）

The bridge can operate independently , It can also be used in combination with other bridges
When using more than two bridges （ Or when the switch ports are cross connected ）, May form a cascade 、 Cyclic frame set

chart 3-12
An extended Ethernet with four switches and multiple redundant links
If you use simple flooding when forwarding frames through the network , There will be disaster due to too much doubled traffic （ The so-called broadcast storm ）
This situation requires the use of STP

Suppose the graph 3-12 The switch in has just been turned on , Their filter database is empty
When the site S When sending a frame , Switch B In the port 7、8 and 9 Copy the frame on , here , The initial frame has been “ Zoom in ” 了 3 times
These frames are switched A、D and C Received , Switch A In the port 2 and 3 Copy the frame on , Switch D and C Respectively on port 20、22 and 13、14 Copy the frame on
The magnification factor has been increased to 6, A copy of the frame is on the switch A、C and D Two way communication between
Once these frames arrive , The forwarding database starts to wobble , Because the bridge is trying to find out which port can really reach the site S The port of , obviously , This situation is intolerable
Fortunately, , There is a protocol that can be used to avoid this situation , be called Spanning tree protocol （Spanning Tree Protocol (STP)）
We will describe in detail STP, To explain why bridges and switches need some repetition suppression methods
In the current [802.1D-2004] In the standard , routine STP Has been Fast spanning tree protocol （Rapid Spanning Tree Protocol (RSTP)） Replace

STP It works by disabling some ports on the bridge , This avoids topology loops （ namely ： Duplicate paths are not allowed between bridges ）, But the topology has no partitions , All stations are accessible
Mathematically , A spanning tree is a set of all nodes and some edges of a graph
From any node to any other node （ stride across （spanning） chart ） But there is no ring （ The set of edges forms a tree Trees （tree））
A graph can have multiple different spanning trees ,STP One of the spanning trees will be found for the graph with bridges as nodes and links as edges

chart 3-13
Use STP,B-A、A-C and C-D The link is activated as an edge of the spanning tree
port 6、7、1、2、13、14、20 In forwarding state , All other ports are blocked （ namely ： Do not forward ）
This prevents frame cycling and avoids broadcast storms
If the configuration changes or the switch fails , Then the blocking port can change to the forwarding state , The bridge recalculates the new spanning tree

In the figure 3-13 in , The black line represents the network STP The selected link for forwarding frames , Other links will not be used , port 8、9、12、21、22 and 3 By Blocking （blocked）
Use STP There will be no problems encountered before , Because a frame is created only when another frame arrives , The frame is no longer magnified
Besides , Since there is only one path between any two sites , Therefore, the circulation is avoided
The spanning tree is generated and maintained by a distributed algorithm running in each bridge

Same as forwarding database ,STP Bridge shutdown and opening must be handled 、 Interface card replacement or MAC Address change
obviously , Such changes may affect the operation of the spanning tree , therefore STP Will adapt to these changes
The bridge is called by switching Bridge protocol data unit （Bridge Protocol Data Units (BPDUs)） To adapt to environmental changes
These frames are used to generate and maintain spanning trees
This tree is a bridge elected by other bridges （ be called “ Root bridge ”）“ growth ” Coming out

As mentioned earlier , There are many possible spanning trees for a given network
Which spanning tree is most suitable for forwarding frames depends on a set of... Associated with each link cost （cost） And the location of the root bridge
cost （cost） It's just （ Suggest ） Some integers inversely proportional to the link speed
for example ,10Mb/s The recommended cost of the link is 100, and 100Mb/s and 1000Mb/s The recommended costs of the links are 19 and 4
STP Use these costs to calculate the lowest cost path to the root bridge
If you have to traverse multiple links , The corresponding cost is the sum of these link costs

3.4.1.1 Port status and role

To understand STP Basic operation , First understand the behavior of the state machine that represents the state of each port on each bridge , as well as BPDU The content of
Each port in each bridge may be in one of five states ： Blocking （blocking）、 monitor （listening）、 Study （learning）、 forward （forwarding）、 Ban （disabled）

chart 3-14
In the normal STP In operation , Port in 4 Transition between main states
Blocking （blocking） State, , Frames will not be forwarded , Topology changes or timeouts may result in switching to listening （listening） state
forward （forwarding） Status is the normal status of the active switch port carrying data traffic
The status name in parentheses indicates RSTP Port status of

chart 3-14 The solid arrows in represent the normal transition between port States on the spanning tree , The dashed small arrows indicate the state changes caused by the management configuration
After initialization , Port entry blocked （blocking） state , In this state , Ports do not learn addresses , Neither forwarding nor transmitting frames BPDU
But it listens to what it receives BPDU, When it needs to be included in the path to the root bridge in the future , Will be converted to listening （listening） state
Monitoring （listening） State, , Ports can send and receive BPDU, But you can't learn addresses or forward data
In a typical 15 Seconds after forwarding delay timeout , The port will enter learning （learning） state , In the learning state, you can perform all operations except forwarding data
Port is learning （learning） After waiting for a forwarding delay in the state, forwarding will be entered （forwarding） Status and start forwarding frames

One thing related to the port state machine is that each port has a role （role）, This term is used in RSTP More important （ See the first 3.4.1.6 section ）
A port may have the following roles ：

1. Root port （root port）
   A spanning tree is a tree with a bridge as the node , Therefore, each bridge has only one parent bridge
   On a bridge , The port connecting the parent bridge is the root port
2. Designated port （designated port）
   The specified port is in forwarding （forwarding） Port of status , Is the port on the lowest cost path from the access network segment to the root
3. Replace port （alternate port）
   The replacement port is another port on the access network segment , They can also reach the root node , But the cost is higher , They are not in forwarding （forwarding） state
4. Backup port （backup port）
   The backup port is on the same bridge Designated port （designated port） Ports connected to the same network segment
   therefore , The backup port can easily take over the failed Designated port （designated port） Without destroying any of the rest of the spanning tree topology
   But if the entire bridge fails , You cannot provide an alternate path to the root through the backup port （ The replacement port can ）

3.4.1.2 BPDU structure

To determine the links in the spanning tree ,STP Use the compliance chart 3-15 In the format shown BPDU

chart 3-15
802 The payload area of the frame will carry BPDU, And exchange between bridges , To build a spanning tree
Important fields include ： Source 、 The root node 、 The cost to the root node and the indication of topology changes
about 802.1w and [802.1D-2004]（ Include RSTP）, Additional fields indicating port status are also included

chart 3-15 The format shown applies to both the original STP, It also applies to new RSTP（ See the first 3.4.1.6 section ）
BPDU Always send to group address 01:80:C2:00:00:00（ About link layer groups and Internet Details of multicast addressing , See the first 9 Chapter ）, And it will not be forwarded through the unmodified bridge
DST、SRC and L/T（Length/Type） The field is conventional Ethernet （802.3） Part of the header
3 Bytes of LLC/SNAP Headlines （header） from 802.1 Definition , about BPDU, The value of this field is constant 0x424203
Not all BPDU All use LLC/SNAP encapsulate , But this is a common choice

agreement （Protocol）（Prot） The field represents the Protocol ID Number , Set to 0
Version（Vers） Field set to 0 or 2, Depending on what is used STP still RSTP, type （Type） Fields are assigned in a similar way
Flags The field contains the original 802.1d Standard definition of Topology changes （Topology Change (TC)） and Topology change confirmation （Topology Change Acknowledgment (TCA)） bits
Additional bits are also defined for these fields ：

proposal （Proposal）（P）
Port role （Port Role）（00 Unknown 、01 Replace 、10 root 、11 Appoint ）
Study （Learning）（L）
forward （Forwarding）（F）
agreement （Agreement）（A）

These will be in the 3.4.1.6 Chaste RSTP Discuss in context
Root ID Field gives the identifier of the root bridge in the eyes of the frame sender ,Bridge ID The field represents the... Of the frame sender MAC Address
these two items. ID Fields are encoded in a special way , Including next to MAC In front of the address 2 byte priority （Priority） Field
Management software can manipulate priorities （priority） Value , To force the spanning tree to take a specific bridge as the root （ Such as ： Cisco in its Catalyst Default values are used in the switch 0x8000）

The root path cost is arrival Root ID Field specifies the cost of the bridge
PID Field representation Port identifier （port identifier）, from 1 Bytes configurable priority （Priority） Field （ Default 0x80） And the port number of the subsequent transmission frame
news A（Message A (MsgA)） The field indicates the age of the message
Maximum age （Maximum Age (MaxA)） The field gives the maximum age before the timeout （ Default 20 second ）
Hello Time Field indicates periodic transmission Configure frame （configuration frame） Interval of
Forwarding delay （Forward Delay (Forw Delay)） Field representation Study （learning） and monitor （listening） Time spent in the State
All age and time fields are marked with 1/256 Seconds per unit

Different from other time related fields , Message age （Message Age） Field is not a fixed value , When the root bridge sends a BPDU when , It will set this value to 0
Any bridge that receives a frame sends a frame to all its non root ports , also Message age （Message Age） Field plus 1
Essentially , This field acts as a hop counter , Indicates that... Is received BPDU The number of bridges that have processed it before
When received on port BPDU when , The information it contains will be stored in memory and participate in STP Algorithm , Until timeout （MaxA – MsgA <= 0 when ）
On a root port , If this time expires , And no other BPDU, The root bridge will be announced “ Death ”, The bridge will start picking new root bridges again

3.4.1.3 Build a spanning tree

STP The first task of is to select a root bridge
The root bridge acts as a network （ or VLAN） Has the smallest identifier in （ priority （priority） And MAC Address combination ） The bridge was found
When a bridge is initialized , First assume that you are the root bridge , And send the “ To configure BPDU ”, In the frame sent at this time Root ID The value of the field is the same as Bridge ID The value of the field matches
But if it detects one ID Smaller bridges , Will stop sending your own frames , Then the received content is smaller ID As a frame sent later BPDU The basis of
Receive this with smaller ID The root of the BPDU The port of will be marked as the root port （ namely ： Port on the path to the root bridge ）
The remaining ports are in Blocking （blocked） or forward （forwarding） state

3.4.1.4 Topology changes

STP The next important task of is to deal with topology changes
Although the basic database aging mechanism described earlier can be used to adapt to changing topologies
But this is a bad way , Because aging timers can take a long time （5 minute ） To delete the wrong entry
STP It combines a method to detect topology changes and quickly notify the network
stay STP in , When a port enters a blocking or forwarding state , Even if the topology changes
When a bridge detects a connection change （ Such as ： A link is down ） when
Will send Topology change notification （topology change notification (TCN)）BPDU Notify its parent bridge （ The adjacent bridge in the root direction connected by the parent port ）
The parent bridge will reply to receive TCN BPDU Confirmation signal of , At the same time, continue to send to the root TCN BPDU
After the root bridge receives the notification of topology change , It will be set in the next regularly sent configuration message TC Bit field
These configuration messages are forwarded by each bridge in the network , And by being in Blocking （blocking） or forward （forwarding） Status of the port receiving
The setting of this bit field allows the bridge to reduce their aging time to the time of the forwarding delay timer , Thus, the generally recommended aging time 5 Minutes have been reduced to the level of seconds
This allows incorrect database entries to be purged and relearned faster , But it also allows sites that communicate actively not to delete their entries by mistake

3.4.1.5 Example

stay Linux in , The bridge function is disabled by default STP, Because in most cases, ordinary computers are used as bridges , The network topology is relatively simple
You can open the network bridge in the following ways STP：

Linux# brctl stp br0 on

The output of this command ：

Linux# brctl showstp br0 
br0 
    bridge id               8000.0007e914a9c1
    designated root         8000.0007e914a9c1
    root port               0                   path cost               0
    max age                 19.99               bridge max age          19.99
    hello time              1.99                bridge hello time       1.99
    forward delay           14.99               bridge forward delay    14.99
    ageing time             0.99 
    hello timer             1.26                tcn timer               0.00
    topology change timer   3.37                gc timer                3.26
    
    flags                   TOPOLOGY_CHANGE TOPOLOGY_CHANGE_DETECTED

eth0 (0) 
    port id                 0000                state                   forwarding 
    designated root         8000.0007e914a9c1   path cost               100 
    designated bridge       8000.0007e914a9c1   message age timer       0.00 
    designated port         8001                forward delay timer     0.00

    designated cost         0                   hold timer              0.26
    
    flags

eth1 (0) 
    port id                 0000                state                   forwarding 
    designated root         8000.0007e914a9c1   path cost               19 
    designated bridge       8000.0007e914a9c1   message age timer       0.00 
    designated port         8002                forward delay timer     0.00 
    designated cost         0                   hold timer              0.26
    
    flags

Bridge equipment br0 Save the information of the whole bridge
This includes bridges ID（8000.0007e914a9c1）, From figure 3-11 Based on PC The bridge （ port 1） The smallest on MAC Address
Main configuration parameters （ Such as ：hello time、 Topology change timer, etc ） In seconds
flags Value indicates the recent topology change
The rest of the output describes eth0（ Bridge port 1） and eth1（ Bridge port 2） Port information
As shown above ,eth0 The cost of the path is about eth1 Cost 10 times
This is related to eth0 yes 10Mb/s Ethernet network ,eth1 It's full duplex 100Mb/s Network consistency

We can use Wireshark see BPDU, In the figure 3-16 in , We see one 52 Bytes of BPDU The content of
52 The length of bytes （ Less than the minimum value of Ethernet 64 byte , because Linux The capture tool removed the padding （padding） part ）
From the Ethernet header Length/Type Add... To the field 14 It is concluded that the
As expected , The destination address is the group address 01:80:C2:00:00:00
The payload length is 38 byte , The value is contained in Length Field
SNAP/LLC Fields contain constants 0x424243, The encapsulated frame is a spanning tree （ edition 0） frame
Other protocol fields indicate sites 00:07:e9:14:a9:c1 Think of it as the root of the spanning tree , Use priority 32768（ Low priority ）, also BPDU Has been prioritized 0x80 From port 2 send out
You can also see that ： Maximum age （maximum age） by 20 second ,hello time by 2 second , Forwarding delay （forwarding delay） by 15 second

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-PWcGgns2-1656250424083)(image/Figure 3-16.png)]
chart 3-16
Wireshark One on display BPDU, The Ethernet destination is a bridge group address （01:80:c2:00:00:00）

3.4.1.6 Fast spanning tree protocol （Rapid Spanning Tree Protocol (RSTP)）( Former 802.1w)

routine STP A known problem with is , Topology changes can only be received after a certain period of time BPDU To detect
If the timeout is long , Then the convergence time （ Time to reestablish the data flow along the spanning tree ） It may be longer than expected
IEEE 802.1w standard （ Now it is [802.1D-2004] Part of ） Specifies the general STP The enhancement of , And adopted a new name Fast spanning tree protocol （Rapid Spanning Tree Protocol (RSTP)）
RSTP Yes STP The main improvement of the system is ,RSTP Will monitor the status of each port , In case of fault indication, the topology change indication will be triggered immediately
Besides ,RSTP Use BPDU Format Flag All in the field 6 Bit to support the protocol between bridges , This eliminates the need for timers to start protocol operations in some cases
RSTP take STP Of 5 The port states are reduced to 3 Kind of （ discarded （discarding）、 Study （learning）、 forward （forwarding）, Pictured 3-14 The status name in brackets is shown as ）
RSTP Medium discarded （discarding） Status replaces routine STP Medium Ban （disabled）、 Blocking （blocking） and monitor （listening） state
RSTP A new port role has also been created , be called Replace port （alternate port）, It acts as an instant backup when the root port is down

RSTP Only one type of BPDU, for example , There is no particular topology change BPDU
RSTP BPDU Use version and type numbers 2 instead of 0
stay RSTP in , Any switch that detects a topology change will send a message indicating the topology change BPDU, And any switch that receives them will immediately clear the filter database
This change will significantly affect the convergence time of the protocol
RSTP No longer need to wait for topology changes to migrate to the root bridge , And the subsequent forwarding delay waiting time , The entry will be cleared immediately
in the majority of cases , The convergence time can be reduced from tens of seconds to a fraction of a second

RSTP Yes Edge port （edge port）（ Only connect to the port of the terminal site ） And normal spanning tree ports , Point to point links and shared links are also distinguished
Edge port （edge port） And ports on a point-to-point link do not usually form a loop
So you can skip monitor （listening） and Study （learning） state , Go straight into forward （forwarding） state
Of course , If two ports are cross connected , It may violate the assumption of being an edge port
But it can be carried through any form of BPDU To solve this problem, the ports of are reclassified into spanning tree ports （ Simple terminal sites usually do not generate BPDU）
The point-to-point link is inferred from the operating mode of the interface , If the interface is running in full duplex mode , The link is classified as a point-to-point link

In the routine STP in ,BPDU It is usually forwarded from the notification bridge or the root bridge
stay RSTP in , All bridges send messages regularly BPDU As “ keep-alive ” The signal , To determine whether the connection with the neighbor is normal , High level routing protocols usually do the same
If the bridge is 3 Times hello Failed to receive updated within the time interval BPDU, Then the bridge will think that it has lost its connection with its neighbors
And Convention STP Different , stay RSTP in , The connection or disconnection of edge ports will not cause topology changes
When a topology change is detected , Notify the bridge （notifying bridge） Will send the settings TC Of the bit field BPDU, Not only to the root bridge , It will also be sent to all other bridges
In this way, the whole network can know that the topology changes faster than the conventional STP Much faster
When a bridge receives these messages , It will refresh all table entries except those associated with the edge port , And restart the learning process

RSTP Many of the features of Cisco Systems The company and some have been routine in their products for some time STP Developed by companies that provide proprietary enhancements
IEEE The Committee has incorporated many of these enhancements into the updated 802.1d In the standard , The standard covers two types of STP
Therefore, the extended LAN can run on some network segments STP, Run on other network segments RSTP（ Although it will lose RSTP The advantages of ）
RSTP Has been expanded to include virtual LANs [802.1Q-2005], One is called Multiple spanning tree protocol （Multiple Spanning Tree Protocol (MSTP)） The agreement
This agreement preserves RSTP（ Therefore, it is reserved STP） Of BPDU Format , So it can be backward compatible , But it also supports the formation of multiple spanning trees （ Each VLAN corresponds to a spanning tree ）

---

Catalog 、 reference