3.4.1 生成树协议（Spanning Tree Protocol (STP)）
网桥可以单独运行，也可以与其他网桥结合使用
当使用两个以上的网桥时（或者当交换机端口交叉连接时），可能会形成一个级联的、循环的帧集
图 3-12
一个具有四个交换机和多个冗余链路的扩展以太网
如果在通过该网络转发帧时使用简单的泛洪，则会由于过多的倍增流量而发生灾难（所谓的广播风暴）
这种情况需要使用 STP
假设图 3-12 中的交换机刚刚打开，它们的过滤数据库为空
当站点 S 发送帧时，交换机 B 在端口 7、8 和 9 上复制该帧，此时，初始帧已被 “ 放大 ” 了 3 倍
这些帧被交换机 A、D 和 C 接收到，交换机 A 在端口 2 和 3 上复制该帧，交换机 D 和 C 分别在端口 20、22 和 13、14 上复制该帧
放大系数已增加到 6，帧的副本在交换机 A、C 和 D 之间双向传播
一旦这些帧到达，转发数据库开始摇摆不定，因为网桥试图找出哪个端口才是真正可以到达站点 S 的端口，显然，这种情况是不能容忍的
幸运的是，有一种协议可以用来避免这种情况，称为生成树协议（Spanning Tree Protocol (STP)）
我们将详细描述 STP，以解释为什么网桥和交换机需要一些重复抑制方法
在当前的 [802.1D-2004] 标准中，常规 STP 已经被快速生成树协议（Rapid Spanning Tree Protocol (RSTP)）所替代
STP 的工作原理是禁用网桥上的某些端口，从而避免拓扑环路（即：网桥之间不允许有重复路径），但拓扑没有分区，所有站都可以到达
从数学上来说，一棵生成树是一个由图的所有节点和部分边组成的集合
从任何一个节点都可以到达任何其它节点（跨越（spanning）图）但没有环（边的集合组成了一棵树（tree））
一个图可以有多个不同的生成树，STP 会为由网桥作为节点链路作为边的图找到其中一个生成树
图 3-13
使用 STP，B-A、A-C 和 C-D 链路作为生成树的边被激活
端口 6、7、1、2、13、14、20 处于转发状态，所有其它端口都被阻塞（即：不转发）
这可以防止帧循环并避免广播风暴
如果配置发生变更或交换机出现故障，则阻塞端口可以变为转发状态，网桥会重新计算新的生成树
在图 3-13 中，黑线代表网络中被 STP 选中的用于转发帧的链路，其它的链路不会被使用，端口 8、9、12、21、22 和 3 被阻塞（blocked）
使用 STP 后不会再出现之前遇到的各种问题，因为仅在另一个帧到达时才会创建帧，帧不会再被放大了
此外，由于任何两个站点之间只有一条路径，因此避免了循环
生成树是由一种运行在每个网桥中的分布式算法进行生成与维护的
与转发数据库一样，STP 必须处理网桥关闭和打开、接口卡更换或 MAC 地址更改的情况
显然，这样的变化可能会影响生成树的运行，因此 STP 会去适应这些变化
网桥通过交换称为桥接协议数据单元（Bridge Protocol Data Units (BPDUs)）的特殊帧来实现对环境变化的适应
这些帧被用来生成和维护生成树
这棵树是从一个由其它网桥选举出来的网桥（称为 “ 根网桥 ”）“ 生长 ” 出来的
如前所述，给定的一个网络存在许多可能的生成树
哪一个生成树最适合用于转发帧取决于一组与每条链路相关的成本（cost）和根网桥的位置
成本（cost）只是（建议）一些与链路速度成反比的整数
例如，10Mb/s 的链路的建议成本为 100，而 100Mb/s 和 1000Mb/s 链路的建议成本分别为 19 和 4
STP 通过使用这些成本来计算通向根网桥的最低成本路径
如果必须遍历多个链路，则相应的成本就是这些链接成本的总和
3.4.1.1 端口状态与角色
要理解 STP 的基本操作，得先理解表示每个网桥上每个端口状态的状态机的行为，以及 BPDU 的内容
每个网桥中的每个端口可能处于五种状态之一：阻塞（blocking）、监听（listening）、学习（learning）、转发（forwarding）、禁用（disabled）
图 3-14
在正常的 STP 操作中，端口在 4 种主要状态之间转换
在阻塞（blocking）状态下，帧不会被转发，拓扑变化或超时可能会导致转换为监听（listening）状态
转发（forwarding）状态是携带数据流量的活跃交换机端口的正常状态
括号中的状态名称表示 RSTP 的端口状态
图 3-14 中的实线箭头表示生成树上端口状态间的正常转换过程，虚线小箭头表示由管理配置引起的状态变化
初始化之后，端口进入阻塞（blocking）状态，在这个状态下，端口不学习地址，不转发帧也不传输 BPDU
但它会监听收到的 BPDU，将来需要被包含在通往根网桥的路径上时，会转换为监听（listening）状态
在监听（listening）状态下，端口可以发送和接收 BPDU，但不能学习地址或转发数据
在典型的 15 秒转发延迟超时后，端口将进入学习（learning）状态，学习状态下可以执行除转发数据以外的所有操作
端口在学习（learning）状态下等待一个转发延迟之后将进入转发（forwarding）状态并开始转发帧
与端口状态机相关的一件事是每个端口都拥有一个角色（role），该术语在 RSTP 中更加重要（见第 3.4.1.6 节）
一个端口可能拥有以下这些角色：
- 根端口（root port）
生成树是棵由网桥作为节点的树，因此每个网桥都有且仅有一个父网桥
在一个网桥上，连接其父网桥的那个端口就是根端口 - 指定端口（designated port）
指定端口是处于转发（forwarding）状态的端口，是从接入网段到根的成本最低路径上的端口 - 替换端口（alternate port）
替换端口是接入网段上的其它端口，它们也可以到达根节点，但成本更高，它们不处于转发（forwarding）状态 - 备份端口（backup port）
备份端口是与同一网桥上的指定端口（designated port）连接到同一网段的端口
因此，备份端口可以轻松地接管发生故障的指定端口（designated port）而不会破坏生成树拓扑结构的任何其余部分
但如果整个网桥发生故障，则无法通过备份端口提供通往根的备用路径（替换端口可以）
3.4.1.2 BPDU 结构
为了确定生成树中的链路，STP 使用符合图 3-15 所示格式的 BPDU
图 3-15
802 帧的有效载荷区域会携带 BPDU，并在网桥之间进行交换，以建立生成树
重要的字段包括：源、根节点、到根节点的成本和拓扑变化指示
对于 802.1w 和 [802.1D-2004]（包括 RSTP），还包括指示端口状态的额外字段
图 3-15 所示的格式既适用于原始 STP，也适用于新的 RSTP（见第 3.4.1.6 节）
BPDU 总是发送到组地址 01:80:C2:00:00:00（有关链路层组和 Internet 组播寻址的详细信息，见第 9 章），并且不会通过未经修改的网桥转发
DST、SRC 和 L/T（Length/Type）字段是常规以太网（802.3）标头的一部分
3 字节的 LLC/SNAP 报头（header）由 802.1 定义，对于 BPDU，该字段的值为常数 0x424203
并非所有 BPDU 都使用 LLC/SNAP 进行封装，但这是一种常见的选择
协议（Protocol）（Prot）字段表示协议 ID 号，设置为 0
Version（Vers）字段设置为 0 或 2，取决于使用的是 STP 还是 RSTP，类型（Type）字段的分配方式类似
Flags 字段包含由原始 802.1d 标准定义的拓扑变化（Topology Change (TC)）和拓扑变化确认（Topology Change Acknowledgment (TCA)）比特位
同时为以下这些字段定义了额外的比特位：
提议（Proposal）（P）
端口角色（Port Role）（00 未知、01 替换、10 根、11 指定）
学习（Learning）（L）
转发（Forwarding）（F）
协议（Agreement）（A）
这些将在第 3.4.1.6 节的 RSTP 上下文中讨论
Root ID 字段给出了帧发送者眼中的根网桥的标识符，Bridge ID 字段表示帧发送者的 MAC 地址
这两个 ID 字段都以特殊的方式编码，包括紧挨在 MAC 地址前面的 2 字节优先级（Priority）字段
管理软件可以操纵优先级（priority）的值，以强制生成树将特定的网桥作为根（如：思科在其 Catalyst 交换机中使用默认值 0x8000）
根路径成本是到达 Root ID 字段指定的网桥的成本
PID 字段表示端口标识符（port identifier），由 1 字节可配置优先级（Priority）字段（默认 0x80）和附加在其后的发送帧的端口号组成
消息 A（Message A (MsgA)）字段表示消息年龄
最大年龄（Maximum Age (MaxA)）字段给出超时前的最大年龄（默认 20 秒）
Hello Time 字段表示定期传输配置帧（configuration frame）的间隔时间
转发延迟（Forward Delay (Forw Delay)）字段表示学习（learning）和监听（listening）状态花费的时间
所有的年龄和时间字段都以 1/256 秒为单位
和其它时间相关字段不同，消息年龄（Message Age）字段不是固定值，当根网桥发送一个 BPDU 时，它会将这个值设为 0
任何接收到帧的网桥都会向其所有非根端口发出帧，并且消息年龄（Message Age）字段加 1
本质上，该字段充当跳数计数器，表示在接收到 BPDU 之前已处理过它的网桥的数量
当在端口上收到 BPDU 时，它包含的信息会被保存到内存中并参与 STP 算法，直到超时（MaxA – MsgA <= 0 时）
在一个根端口上，如果这个时间过期，并且没有收到其它的 BPDU，根网桥将被宣布 “ 死亡 ”，网桥会再次开始挑选新的根网桥
3.4.1.3 构建生成树
STP 的第一个工作就是要选择一个根网桥
根网桥作为网络（或 VLAN）中具有最小标识符（优先级（priority）与 MAC 地址相结合）的网桥被发现
当一个网桥初始化时，先假设自己是根网桥，并发送 “ 配置 BPDU ”，此时发送的帧中的 Root ID 字段的值与 Bridge ID 字段的值匹配
但如果它检测到了一个 ID 更小的网桥，则会停止发送自己的帧，然后把接收到的包含更小 ID 的帧作为之后发送的 BPDU 的基础
接收到这个拥有更小 ID 的根 BPDU 的端口将被标记为根端口（即：在通往根网桥的路径上的端口）
其余端口处于阻塞（blocked）或转发（forwarding）状态
3.4.1.4 拓扑变化
STP 的下一个重要工作就是处理拓扑变化
尽管可以使用前面描述的基本数据库老化机制来适应不断变化的拓扑
但这是一个糟糕的方法，因为老化计时器可能需要很长时间（5 分钟）才能删除错误的条目
STP 结合了一种检测拓扑变化的方法并快速通知网络
在 STP 中，当一个端口进入阻塞或转发状态时，就算作是拓扑发生了变化
当一个网桥检测到连接变化（如：一条链路断开了）时
会发送拓扑变化通知（topology change notification (TCN)）BPDU 通知其父网桥（父端口连接的朝根方向的相邻网桥）
父网桥会回复收到 TCN BPDU 的确认信号，同时继续向根方向发送 TCN BPDU
根网桥接收到拓扑变化的通知后，会在下一个定期发送的配置消息中设置 TC 比特位字段
这些配置消息被网络中的每个网桥转发，并由处于阻塞（blocking）或转发（forwarding）状态的端口接收
该比特位字段的设置允许网桥将它们的老化时间减少到转发延迟计时器的时间，从而将通常推荐的老化时间 5 分钟降低到了秒的级别
这让不正确的数据库条目被更快地清除和重新学习，但它也允许那些积极通信的站点不会错误地删除它们的条目
3.4.1.5 例子
在 Linux 中，网桥功能默认禁用了 STP，因为在大多数把普通计算机当做网桥的情况下，网络拓扑都比较简单
可以通过以下方式开启网桥的 STP：
Linux# brctl stp br0 on
这条命令的输出：
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
网桥设备 br0 保存了整个网桥的信息
这包括网桥 ID（8000.0007e914a9c1），源自图 3-11 中基于 PC 的网桥（端口 1）上的最小 MAC 地址
主要的配置参数（如：hello time、拓扑变化计时器等）以秒为单位
flags 值指出最近的拓扑变化
输出的其余部分描述了 eth0（网桥端口 1）和 eth1（网桥端口 2）的端口信息
如上所示，eth0 的路径成本大约是 eth1 成本的 10 倍
这与 eth0 是 10Mb/s 的以太网网络，eth1 是全双工 100Mb/s 的网络一致
我们可以使用 Wireshark 查看 BPDU，在图 3-16 中，我们看到了一个 52 字节的 BPDU 的内容
52 字节的长度（小于以太网的最小值 64 字节，因为 Linux 捕获工具删除了填充（padding）部分）
是从以太网报头的 Length/Type 字段中加 14 得出的
正如预期的那样，目标地址是组地址 01:80:C2:00:00:00
有效载荷长度为 38 字节，该值包含在 Length 字段中
SNAP/LLC 字段包含常量 0x424243，封装的帧是生成树（版本 0）帧
其它协议字段指出站点 00:07:e9:14:a9:c1 认为它是生成树的根，使用优先级 32768（低优先级），并且 BPDU 已经以优先级 0x80 从端口 2 发送
还可以看到：最大年龄（maximum age）为 20 秒，hello time 为 2 秒，转发延迟（forwarding delay）为 15 秒
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PWcGgns2-1656250424083)(image/Figure 3-16.png)]
图 3-16
Wireshark 展示的一个 BPDU，以太网目的地是一个网桥组地址（01:80:c2:00:00:00）
3.4.1.6 快速生成树协议（Rapid Spanning Tree Protocol (RSTP)）(以前的 802.1w)
常规 STP 的一个已知的问题是，拓扑变化只能通过在一定时间内未能接收到 BPDU 的方式来检测
如果超时时间很长，则收敛时间（沿生成树重新建立数据流的时间）可能比预期的要长
IEEE 802.1w 标准（现在是 [802.1D-2004] 的一部分）指定了对常规 STP 的增强，并采用了新名称快速生成树协议（Rapid Spanning Tree Protocol (RSTP)）
RSTP 对 STP 的主要改进是，RSTP 会监视每个端口的状态，并在出现故障指示时立即触发拓扑变化指示
此外，RSTP 使用 BPDU 格式的 Flag 字段中的所有 6 比特位来支持网桥之间的协议，这样一来在某些情况下就不再需要用计时器来启动协议操作
RSTP 将 STP 的 5 种端口状态减少为了 3 种（丢弃（discarding）、学习（learning）、转发（forwarding），如图 3-14 中括号中的状态名称所示）
RSTP 中的丢弃（discarding）状态取代了常规 STP 中的禁用（disabled）、阻塞（blocking）和监听（listening）状态
RSTP 还创建了一个新的端口角色，称为替换端口（alternate port），它在根端口停止运行时充当即时备份
RSTP 只采用了一种类型的 BPDU，例如，没有一种特殊的拓扑变化 BPDU
RSTP BPDU 使用版本和类型编号 2 而不是 0
在 RSTP 中，任何检测到拓扑变化的交换机都会发送指示拓扑变化的 BPDU，并且任何接收到它们的交换机都会立即清除过滤数据库
这个变化会显著地影响协议的收敛时间
RSTP 不再需要等待拓扑变化迁移到根网桥，以及之后的转发延迟等待时间，条目会被立即清除
在大多数情况下，收敛时间可以从几十秒减少到几分之一秒
RSTP 对边缘端口（edge port）（仅连接到终端站点的端口）和正常的生成树端口进行了区分，对点对点链路和共享链路也进行了区分
边缘端口（edge port）和点对点链路上的端口通常不会形成环路
因此可以跳过监听（listening）和学习（learning）状态，直接进入转发（forwarding）状态
当然，如果两个端口交叉连接，则可能违反作为边缘端口的假设
但可以通过将携带过任何形式的 BPDU 的端口重新分类为生成树端口的方式来解决这个问题（简单终端站点通常不会产生 BPDU）
点对点链路是从接口的工作模式推断出来的，如果接口运行在全双工模式下，则链路被归类为点对点链路
在常规 STP 中，BPDU 通常是从通知网桥或根网桥转发的
在 RSTP 中，所有网桥都会定期发送 BPDU 作为 “ keep-alive ” 信号，以确定与邻居的连接是否正常，高层路由协议通常也是这么做的
如果网桥在 3 倍的 hello 时间间隔内未能接收到更新过的 BPDU，则网桥会认为它已失去了与邻居的连接
与常规 STP 不同，在 RSTP 中，边缘端口的连接或断开不会导致拓扑变化
当检测到拓扑变化后，通知网桥（notifying bridge）会发送设置了 TC 比特位字段的 BPDU，不仅发送给根网桥，还会发送给所有其它网桥
这样做可以让整个网络得知拓扑变化的速度比常规 STP 快得多
当一个网桥接收到这些消息之后，它会刷新除边缘端口关联的条目以外的所有表条目，并重新启动学习过程
RSTP 的许多特性是由 Cisco Systems 公司和一些一段时间以来在其产品中为常规 STP 提供专有增强功能的公司开发的
IEEE 委员会将其中许多增强功能纳入了更新的 802.1d 标准中，该标准涵盖了两种类型的 STP
因此扩展局域网可以在某些网段上运行常规 STP，在其它网段上运行 RSTP（尽管会失去 RSTP 的优势）
RSTP 已扩展为包括虚拟局域网 [802.1Q-2005]，一种称为多生成树协议（Multiple Spanning Tree Protocol (MSTP)）的协议
这个协议保留了 RSTP（因此也就保留了 STP）的 BPDU 格式，因此可以向后兼容，但它还支持形成多棵生成树（每个虚拟局域网都对应一颗生成树）