12.1.4 生成树技术
生成树协议（Spanning-Tree Protocol，STP）是一个用于在局域网中消除环路的协议。运行该协议的交换机通过彼此交互信息而发现网络中的环路，并适当对某些端口进行阻塞以消除环路。由于局域网规模的不断增长，STP已经成为了当前最重要的局域网协议之一。
1．STP出现的背景
图12-12展示了现在普遍采用的多交换机来实现冗余的局域网结构。
在图12-12所示的网络中，可能产生如下两种情况。
·广播环路（Broadcast Loop）。显然，当PCA发出一个DMAC为广播地址的数据帧时，该广播会被无休止地转发。
·MAC地址表震荡（Bridge Table Flapping）。在图12-12中，即使是单播，也有可能导致异常。交换机SW1可以在端口B上学习到PCB的MAC地址，但是由于SW2会将PCB发出的数据帧向自己其他的端口转发，所以SW1也可能在端口A上学习到PCB的MAC地址。如此SW1会不停地修改自己的MAC地址表。这样就引起了MAC地址表的抖动（Flapping）。
2．STP的基本概述
STP可以消除网络中的环路。其基本理论依据是根据网络拓扑构建（生成）无回路的连通图（就是树），从而保证数据传输路径的唯一性，避免出现环路报文流量增生和循环。STP是工作在OSI第二层（Data Link Layer）的协议。
STP协议通过在交换机之间传递特殊的消息并进行分布式的计算，来决定一个有环路的网络中，哪台交换机的哪个端口应该被阻塞（Blocking），用这种方法来剪切掉环路，如图12-13所示。
图12-12 冗余交换网络示意图
图12-13 STP原理示意图
（1）一个根桥
树形的网络结构，必须要有根，于是STP引入了根桥（Root Bridge）的概念。
对于一个STP网络，根桥有且只有一个。它是整个网络的逻辑中心，但不一定是物理中心。但是根据网络拓扑的变化，根桥可能改变。而且一旦网络收敛之后，只有根桥按照一定的时间间隔产生并且向外发送一种称为“配置消息”的协议报文，其他的交换机仅对该种报文进行“接力”，这样来保证拓扑的稳定。
（2）二种度量
生成树的生成计算有ID和路径开销（PC，Path Cost）两大基本度量依据。
1）ID
又分为BID和PID。
·BID即Bridge ID，或称为桥ID。IEEE802.1D标准对这个值的规定是由16位的桥优先级（Bridge Priority）与桥MAC地址构成。BID桥优先级占据高16位，其余的低48位是MAC地址。在STP网络中，桥ID最小的交换机会被选举为根桥。
·PID即Port ID，或称为端口ID。也是由两部分构成的，高8位是端口优先级，低位是端口号。PID只在某些情况下对选择指定端口有作用。
2）路径开销
路径开销（Path Cost）是一个端口量，反映了本端口所连接网络的开销。该值越低，表示这个端口连接的网络越好。在一个STP网络中，某端口到根桥累计的路径开销就是通过所经过的各个桥上的各端口的路径开销累加而成，这个值叫做根路径开销（Root Path Cost）。
IEEE 802.1t中规定的路径开销如表12-2所示，而各厂商采用的路径开销标准不尽相同。
表12-2 IEEE802.1t路径开销列表
（3）三要素选举
从一个初始的有环拓扑生成树状拓扑，总体来说有根桥、根端口和指定端口3个要素。
·根桥是全网意义上的。通过交换特殊的协议报文，网络中很快就会对最小的BID达成一致。
·所谓根端口，是指一个非根桥的STP交换机上离根桥最近的端口，这个端口的选择标准就是上面提过的根路径开销。在本交换机上所有使能STP的端口中，根路径开销最小者，就是根端口。很显然，在一个STP交换机上根端口有且只有一个。
·指定端口的概念是针对于某网段的，是流量从根桥方向来而从这个端口转发“出去”。从一个连接到STP交换机的网段来说，该网段通过指定端口接收到根桥方向过来数据。根桥上的所有端口都是指定端口。在每一个网段上，指定端口有且只有一个。
在拓扑稳定状态，只有根端口和指定端口转发流量，其他的非根非指定端口都处于阻塞（Blocking）状态，它们只接收STP协议报文而不转发用户流量。
一旦根桥、根端口、指定端口选举成功，则整个树形拓扑就建立完毕了。
（4）四个比较原则
BPDU分为配置BPDU（配置BPDU）和TCNBPDU（Topology Change Notification BPDU）两类。配置BPDU用来生成树拓扑的配置BPDU，维护网络拓扑；TCNBPDU则只在拓扑发生变化的时候发出，用来通知相关的交换机网络发生变化。
配置BPDU主要携带根桥BID、累计根路径开销、发送交换机BID和发送端口PID几个重要信息。
STP交换机接收配置BPDU，并处理上述字段，如图12-14所示。
·最低BID。用来选根桥。STP交换机之间根据上页表中所示根桥BID字段选择最低的BID。
·最小的累计根路径开销。用来在非根桥上选择根端口。在根桥上，每个端口到根桥的根路径开销都是0。在接收到BPDU后，端口会根据BPDU中携带的根路径成本加上自己的路径成本，计算出自己到根的累计根路径开销。
·最小发送者BID。如图12-14，假设SW2的BID小于SW3的BID，如果在SW4的A、B两个接收到的BPDU里面的根路径开销相等，那么端口B将成为根端口。
·最小PID。只有在图12-15所示的情况下，PID才起到了作用。SW1的端口A的PID小于端口B的PID。由于两个端口上收到的BPDU中，根路径开销、发送交换机BID都相同，所以消除环路的依据就剩下PID了。
在STP的所有的比较量中，都遵循“数值越低就越好”的原则，如BID、PID和路径开销等等都是这样的。
图12-14 STP选举示意图
图12-15 通过PID选举根端口示意图
（5）五种端口状态
STP端口有5种状态，如表12-3所示。
表12-3 STP端口的5种状态
端口处于Listening和Learning状态的时间是由Forward Delay Timer来统一控制的，这两个时间总是一样长的。这5种状态在相应条件下的相互转化。
3．STP技术细节
本节将介绍STP协议相关的技术细节。
（1）初始化生成树的过程
此时通过交换BPDU，进行选举的工作：即选根桥，选根端口，选指定端口。
由于每个桥都认为自己是根桥，所以在每个端口所发出的BPDU中，根桥字段都是用各自的BID，Root Path Cost字段是累计的到根桥的开销，发送者BID是自己的BID，端口PID是发送该BPDU端口的端口ID。BPDU会按照Hello Time指定的时间间隔来发送，默认的时间为2秒。
一旦在某端口上收听到比自己发的还要“好”的BPDU，那么这个端口就提取该BPDU中的某些信息，更新自己的信息。再次强调，比较BPDU的“好坏”的方式（自己的或其他交换机的），都是根据四元组来完成的，即最低桥ID、最低到累计根路径开销，最低发送者BID（有时还需要最低端口PID）。该端口缓存他人BPDU后，自己则立即停止发送BPDU。
当发送BPDU的时候，交换机填充Sender BID字段的总是自己的BID，而填充Root BID字段的是“当前我所认为是根桥的”BID。此过程不断交互进行，直到所有交换机的所有端口都认为根桥是相同的，就说明根桥已经选择完毕了。
每个非根桥STP交换机都要选择一个根端口，根端口对于一个交换机来说有且只有一个。其本质是“距离根桥最近的端口”，这个最近的衡量是靠累计根路径开销来判定的，即累计根路径开销最小的端口就应该是根端口。累计根路径开销的计算方法如下：端口收到一个BPDU后，抽取该BPDU中累计根路径开销字段的值，加上该端口本身的路径开销。所谓该端口本身的路径开销只体现直连链路的开销，这个值是端口量，可以人为配置的。如果有两个以上的端口计算得到的累计根路径开销相同，那么选择收到发送者BID最小的那个端口作为根端口。
在网段上抑制其他端口（无论是自己的还是其他交换机的）发送BPDU的端口，就是该网段的指定端口。根桥的所有端口都是指定端口（根桥物理上环路这种情况除外）。在收敛后，只有指定端口和根端口可以处于转发状态。其他端口都是Blocking状态，即收听BPDU而不转发用户流量。
（2）拓扑稳定之后
在拓扑稳定之后，根桥仍然按照Hello Time间隔发出配置BPDU，其他非根桥交换机仅仅在收到上一级过来的BPDU，才会触发发出BPDU。如果有必要，则根据BPDU里面的信息更新自己相应端口。
配置BPDU是一种“心跳”报文，只要端口上使能了STP，则配置BPDU就会按照HelloTimer所规定的时间间隔发出。在初始化过程中，每个桥都主动发出配置BPDU；但在网络拓扑稳定以后，只有根桥主动发送配置BPDU，其他桥在收到上游传来的配置BPDU后，才触发发送自己的配置BPDU。配置BPDU的长度至少要35个字节，而且如果当且仅当发送者BID或发送端口PID两个字段中至少有一个和本桥本接收端口不同，才会被处理，否则丢弃，这样避免了处理和本端口信息一致的BPDU。
（3）3个计时器
对于STP，一共有3个计时器影响着端口状态以及网络的收敛，如下所述。
·Hello Timer：STP交换机发送BPDU的时间间隔。当网络拓扑稳定之后，该计时器的修改只有在根桥修改才有效。根桥会在之后发出的BPDU中填充适当的字段以向其他非根桥传递该计时器修改信息。但当拓扑变化之后，TCNBPDU的发送不受这个计时器的管理。
·Forwarding Delay Timer：指一个端口Listening和Learning的各自时间，默认为15s，即Listening状态持续15s，随后Learning状态再持续15s。这两个状态下的端口会处于Blocking状态，这是STP用于避免临时环路的关键。
·Max Age：端口会根据接收到的BPDU存储所接收到的最好的四个信息（根桥BID、累计根路径开销、发送者BID和发送端口PID）。每次接收到合适的BPDU，端口都会启动这个MaxAge计时器。超过这个MaxAge时间端口接收不到合适BPDU，就会认为网络直径过大。这个时间默认为20s。
4．RSTP技术
RSTP快速生成树协议（rapid spanning Tree Protocol）是从stp发展过来的，其实现基本思想一致，但它进一步处理了网络临时失去连通性的问题。RSTP规定在某些情况下，处于Blocking状态的端口不必经历2倍的Forward Delay时延而可以直接进入转发状态。如网络边缘端口（即直接与终端相连的端口），可以直接进入转发状态，不需要任何时延。或者是网桥旧的根端口已经进入Blocking状态，并且新的根端口所连接的对端网桥的指定端口仍处于Forwarding状态，那么新的根端口可以立即进入Forwarding状态。即使是非边缘的指定端口，也可以通过与相连的网桥进行一次握手，等待对端网桥的赞同报文而快速进入Forwarding状态。
在RSTP中只有3种端口状态，分别为Discarding、Learning和Forwarding。802.1D中的禁止端口、监听端口、阻塞端口在802.1W中统一合并为禁止端口。
RSTP有5种端口类型。根端口和指定端口这两个角色在RSTP中被保留，阻断端口分成备份和替换端口角色。生成树算法（STA）使用BPDU来决定端口的角色，端口类型也是通过比较端口中保存的BPDU来确定哪个比其他的更优先。
RSTP与STP的比较如下。
·STP没有明确区分端口状态与端口角色，收敛时主要依赖于端口状态的切换。RSTP比较明确的区分了端口状态与端口角色，且其收敛时更多的是依赖于端口角色的切换。
·STP端口状态的切换必须被动的等待时间的超时。而RSTP端口状态的切换却是一种主动的协商。
·STP中的非根网桥只能被动的中继BPDU。而RSTP中的非根网桥对BPDU的中继具有一定的主动性。
5．PVST和PVST+技术
在IEEE 802.1D中，并没有说明STP和VLAN配合的情况（在设计STP协议的时候，VLAN的IEEE802.1Q还没有出现）。所以STP就变成了VLAN无关的协议了，这样就有可能出现一棵公共生成树可能包括两个以上的VLAN的情况。这就是所谓的CST（Common SpanningTree，公共生成树）。
由对于不同的VLAN，STP都进行同样的阻塞算法，则有可能导致某些链路不通。针对这种情况，Cisco提出了PVST（per-VLAN Spanning Tree，每VLAN生成树）来实现STP协议。PVST，即每个VLAN对应一个生成树。但是PVST也有缺点，那就是在Trunk链路上要对各个VLAN中的BPDU提供传输服务。而且对于每个VLAN的BPDU，交换机都要分别处理，开销很大。
PVST+是对PVST的补充和改进，通过PVST+，PVST设备可以通过PVST+设备实现和标准STP的互通。
6．MST多生树技术
MST（Multiple Spanning Tree，多生成树）是把IEEE 802.1w的快速生成树（RST）算法扩展而得到的。
采用多生成树（MST），能够通过干道（Trunks）建立多个生成树，关联VLANs到相关的生成树进程，每个生成树进程具备单独于其他进程的拓扑结构；MST提供了多个数据转发路径和负载均衡，提高了网络容错能力，因为一个进程（转发路径）的故障不会影响其他进程（转发路径）。
MSTP的特点如下。
·MSTP设置VLAN映射表（即VLAN和生成树的对应关系表），把VLAN和生成树联系起来；通过增加“实例”（将多个VLAN整合到一个集合中）这个概念，将多个VLAN捆绑到一个实例中，以节省通信开销和资源占用率。
·MSTP把一个交换网络划分成多个域，每个域内形成多棵生成树，生成树之间彼此独立。
·MSTP将环路网络修剪成为一个无环的树形网络，避免报文在环路网络中的增生和无限循环，同时还提供了数据转发的多个冗余路径，在数据转发过程中实现VLAN数据的负载分担。
·MSTP兼容STP和RSTP。