在网络设计中，为了增强通信链路的可靠性，一般会在交换机之间设计一条或多条冗余链路。虽然冗余链路的添加可以保证链路的正常通信，但也可能会导致环路的产生。
在广播密集型的网络中，环路会形成广播风暴，从而导致网络网络全部堵塞。
对于二层以太网来说，连个局域网之间只能有一条活动着的链路，否则就会产生环路，形成广播风暴。但是为了加强一个局域网的可靠性，建立冗余链路又是十分必要的，因此，其中的一些通路必须处于备份状态，若网络发生故障，活动链路失效时，冗余链路就必须被提升为活动状态。
手工控制这样的过程是一项非常麻烦的工作，生成树协议(Spanning-Tree Protocol,STP)就能帮我们自动完成这项工作。
常见的生成树协议
| 协议 | 标准 |
|---|---|
| STP | IEEE802.1d |
| RSTP(Rapid Spanning-Tree Protocol,快速生成树协议) | IEEE802.1w |
| MSTP(Multiple Spanning-Tree Protocol ,多生成树协议) | IEEE802.1s |
STA(Spanning-Tree Algorithm,生成树算法)
STP协议
STP是一个数据链路层的管理协议，通过有选择性地阻塞网络冗余链路来达到消除网络环路的目的，同时具备链路冗余备份的功能。
STP的基本思想就是要生成一个稳定的树形拓扑网(我们的网络就是一个由交换机级联所组成的拓扑网络，在数据结构中表现为图,Graph,我们就是要建立一个特殊的图-树)。
树的根是一台称为根桥的交换机(Root Bridge,简称为根交换机).
从根交换机开始，逐级形成一棵树，交换机为树的节点，链路为树枝。
根交换机定时发送配置报文，非根交换机接收配置报文并转发给下一级。
树形结构中的每一个节点，都只有一个父节点。我们规定每一条活动链接连接的父节点都不相同。
当一台交换机从两个以上的端口接收到配置报文时，则说明该交换机的父节点不只一个。此时交换机需要根据端口的配置选出一个端口设置为转发状态,并将其它的端口设置为阻塞状态，从而确保当前的父节点只有一个。处于阻塞状态的端口所对应的链路称为备份链路.
当某个端口长时间不能接受到配置报文时，交换机会认为该父节点已经失效，网络拓扑结构可能改变，此时生成树就会重新计算，激活其它的备份链路，生成新的树形拓扑，并强制原来的故障链路变为备份链路,这时端口状态也会随之改变，以保证数据的传输路径是唯一的。
STP协议中定义根交换(Root Bridget)、根端口(Root Port)、指定端口(Designed Port)和路径开销(Path Cost)等概念，目的就在于通过构造一颗自然树的方法达到阻塞冗余环路的目的，同时实现链路备份和路径最优化。用于构造这棵树的算法称为生成树算法(Spanning Tree Algorithm)。
生成树协议的端口协议
在STP中，正常的端口具有四种状态:
-
阻塞(Blocking)
初始启用端口之后的状态。
端口不能接收或者传输数据，不能把MAC地址加入地址表，只能接收BPDU。
如果检测到有一个交换环路，或者端口失去了它的根端口或者指定端口的状态，那么就会返回到Blocking状态. -
监听(Listening)
如果一个端口可以成为一个根端口或者指定端口，那么它就转入监听状态，不能接收或者传输数据，也不能把MAC地址加入地址表，但可以接收和发送BPDU。
此时，该端口参与根端口或指定端口的选举，因此这个端口最终可能被允许称为一个根端口或指定端口。如果该端口最后失去根端口或指定端口的地位，那么就会返回到Blocking。 -
学习(Learning)
在转发延迟计时时间超时(默认15秒)后，端口进入学习状态，此时端口不能传输传输，但可以发送和接收BPDU,也可以学习MAC地址,并加入地址表。正因为如此，才使得交换机可以沉默一定的时间，处理有关地址表的信息。 -
转发(Forwarding)
在下一次转化延迟计时时间后，端口进入转发状态，此时端口能够发送和接收数据、学习MAC地址、发送和接收BPDU。
在生成树拓扑中，该端口至此才能成为一个全功能的交换机端口。
除此之外，STP中端口还有一个Disabled(禁用)状态，由网络管理员设定或因网络故障使系统的端口处于Disabled状态。这个状态是比较特殊的状态，它并不是正常的STP状态。
当交换机加电启动后，所有的端口从初始化状态进入阻塞状态，它们从这个状态开始监听BPDU。当交换机第一次启动时，它会认为自己是根交换机，所以会转换为监听状态。如果一个端口处于阻塞状态，并在一个最大老化时间(20秒)内没有接收到新的BPDU，端口也会从阻塞状态转换为监听状态。
在监听状态，所有交换机选举根交换机，在非根交换机上选举根端口，并且在每一个网段中选举指定端口.经过一个转发延迟(15)秒后，端口进入学习状态。
如果一个端口在学习状态结束之后(在经过一个转发延迟15秒)，还是一个根端口或者指定端口。这个端口就进入了转发状态，可以正常接收和发送用户数据，否者就转回阻塞状态。
最后，生成树经过一段时间(默认值是50秒)稳定之后，所有端口要么进入转发状态，要么进入阻塞状态。STP BPDU仍然会定时(默认每隔2秒)从各个交换机的指定端口发出，以维护链路的状态。如果网络拓扑发生变化，生成树就会重新计算，端口状态也会随之改变。
生成树拓扑变更
如果一个交换网络中的所有交换机和网桥端口都处于阻塞状态或者转发状态时，这个交换网络就达到了收敛。
转发端口发送并且接收数据通信和BPDU，阻塞状态仅接收BPDU。
当网络拓扑变更时，交换机必须重新计算STP，端口的状态会发生改变，这样会中断用户通信，直到计算出一个重新收敛的STP拓扑。
发生变化的交换机会在它的根端口上每隔hello time时间就发送TCN BPDU(拓扑变化通知BPDU)，直到生成树上游的指定网桥确认了该TCN BPDU为止。
当根网桥收到TCN BPDU后，会发送设置TC(Topology Change,拓扑改变)位的BPDU，通知整个生成树拓扑结构发生了变化。
如图所示
下游交换机发现了拓扑结构改变后，会逐级向上回报直至根网桥收到这个消息，然后根网桥再向全网内所有交换机通知拓扑的变更。
所有的下游交换机得到拓扑改变的通知后，会把他们的Address Table Aging(地址表老化)计时器从默认值(300秒)降为转发延迟(Fordward Delay,默认15秒)，从而让不活动的MAC地址比正常情况下更快地从地址表更新掉。
当拓扑发生变化时，新的配置消息要经过一定的时延才能传播到整个网络，这个时延就是15秒的转发延迟。在所有网桥收到这个变化的消息之前，若旧拓扑结构处于转发的端口还没有发现自己应该在新的拓扑中停止转发，则可能存在临时环路。
为了解决临时环路的问题，生成树采用的是定时器车略，及在端口从阻塞状态到转发状态中间加上一个只学习MAC地址但不参与转发的中间状态——学习状态，两次状态切换的时间长度都是一个转发时延。这样就可以保证在拓扑发生变化的时候不会产生临时环路。
但是这个看似良好的解决方案实际上带来的却是至少两倍转发时延的收敛时间。
STP的扩展协议-RSTP
为了解决STP协议的重新收敛时间过大的问题，在本世纪初，IEEE推出了802.1w标准，作为对802.1D标准的扩充。在IEE802.1w标准中定义了RSTP(Rapid Spanning Tree Protocol,快速生成树协议)协议。
RSTP在物理拓扑结构变化或配置参数发生变化时，显著地减少了网络拓扑的重新收敛时间。除了根端口和指定端口外，快速生成树协议新增了两种端口角色——替代端口(Alternate Port)和备份端口(Backup Port)，这两种新的端口用于取代阻塞端口。
- 替代端口
替代端口为当前的根端口到根交换机的连接提供了替代路径,也就是说替代端口是根端口的替补。 - 备份端口
备份端口提供了到达同段望断的备份路径，是对一个网段的冗余连接,也就是说备份端口是一个指定端口的替补。
此外，RSTP只有三种端口状态——丢弃(Discarding)、学习(Learning)和转发(Forwarding)。STP中的禁用、阻塞和监听状态对应了RSTP的丢弃状态。
根端口或指定端口在拓扑结构中具有非常重要的作用，而替代端口或备份端口则不然。在稳定的网络中，根端口和指定端口处于转发状态，而替代端口及备份端口处于丢弃状态。
RSTP可以主动地将端口立即转变为转发状态，而无须通过调整计时器的方式去缩短收敛时间。为了能够达到这种目的，就出了两个新的变量:边缘端口(Edge Port)和链路类型(Link Type)。
边缘端口是指连接终端的端口。由于连接端工作站(而不是另一台交换机)是不可鞥导致交换环路的，因此这类端口久没有必要经过监听和学习状态，从而可以直接转变为转发状态。一端边缘端口收到了BPDU，它将立即转变为普通的RSTP端口。
在RSTP中，仅当非边缘端口转变为转发状态时，拓扑结构彩绘发生变化。
链路类型是根据端口的双工模式来确定的。RSTP快速转变为转发状态的这一特点同样可以在点到点链路上实现。由于全双工操作的端口被认为是点到点型的链路，半双工端口被认为是共享型链路，因此，RSTP会将全双工操作的端口当成是点到点链路，从而达到快速收敛。
RSTP是STP的扩展，其主要特点是增加了端口状态快速切换机制,能够实现网络拓扑结构的快速转换。
如果一个局域网内的交换机都支持RSTP协议且管理员配置得当，一旦网络拓扑结构改变而需重新生成拓扑树时，只需要不超过1s的时间。
RSTP的优点
RSTP协议在STP协议基础上做了三点重要改进，使得收敛速度更快(最快1s以内)
为根端口和指派端口设置了快速切换用的替换端口(Alternate Port)和备份端口(Backup Port)两种角色。
当根端口/指派端口失效时，替换端口/备份端口就会无时延地进入转发状态。把直接与终端相连而不是把与其它网桥(或交换机)的端口定义为边缘端口(Edge Port)
边缘端口可以直接进入转发状态，不需要任何延时。
但是，由于网桥(或交换机)无法知道端口是否直接与终端相连，所以需要人工配置在只连接了两个交换端口的点对点链路中，指派端口只需要与下游网桥(或交换机)进行一次握手就可以无时延地进入转发终端。
如果是连接了三个以上网桥(或交换机)的共享链路，下游网桥(或交换机)是不会响应上游指派端口发出的握手请求的，只能等待两被的转发时延之后进入转发状态。
对VLAN的支持-MSTP
STP/RSTP协议不支持VLAN，局域网内的所有交换机共享一颗生成树。
为了解决上述问题，产生了MSTP。MSTP协议是在STP/RSTP协议的基础上发展而来的新的生成树协议，解决了RSTP中不同VLAN必须运行在同一颗生成树上的问题，并且还能够通过形成多棵生成树实现负载均衡。
MSTP的基本原理
MSTP的基本原理与STP/RSTP大同小异，可简单概述如下:MSTP协议将整个交换网络划分为多个区域(称为MST域)，经过比较配置消息后，在整个交换网络中选择一个优先级最高的交换机作为整个交换网络的树根(我们称整个交换网络的生成树为CIST,公共生成树)。在每个MST域内通过计算生成一个在CIST中代表该区域的生成树(称为IST,内部生成树)
MSTP的基本概念
在STP/RSTP中，我们称一台交换机为一棵生成树
我们称MSTP中的生成树为多生成树(这里的"多"只是翻译，并不是强调生成树的数量)
- 多生成树实例(MST Instance,MSTI)
一台交换机中的一个VLAN或多个VLAN的集合- 在一台交换机中，最多可以创建64个多生成树实例。多生成树实例的ID从1~64,其中ID为0是默认存在的。
- 在交换机上可以通过配置命令将1~4094个VLAN分配给不同的多生成树实例，每个VLAN有且只能分配给一个多生成树实例。默认情况下，VLAN是分配给实例ID为0的多生成树
- 多生成树域(MST Region)
网络中，有着相同实例映射规则和配置的交换机以及它们之间的网段共同构成一个多生成树域。
域内所有交换机都具有如下相同的MST域配置信息:- MST域名: 最长可用32字节长度的字符串来标识
- MST修订级别(MST Revision Number):用16位来标识，范围为0~65535
- 多生成树实例与VLAN的映射对应表
内部生成树(Internal Spanning-Tree,IST)
由多生成树域内的所有交换机组成的一棵生成树，保证了每个域的连通性。IST使用编号0公共生成树(Common Spanning-Tree,CST)
连接着网络内部所有的多生成树域的单生成树。
每个域在CST中只是一个节点。如果把每个多生成树域看成一台大的"交换机"，那么公共生成树就是这些"交换机"通过STP/RSTP协议计算生成的一棵生成树公共和内部生成树(Common and Internal Spanning-Tree ,CIST)
IST和CST共同构成了整个网络的CIST.CIST是连接一个交换网络中所有交换机的单生成树域根
指的是多生成树域内的内部生成树和多生成树实例的树根
多生成树域内各生成树的拓扑结构不同，域根也可能不同总根(Common Root Bridge)
公共生成树的树根，即一个交换网络的根
在MSTP协议中，每台交换机的端口具有各种不同的角色:
- Master端口 : 连接MST域到总根的端口，位于整个生成树域到总根的最短路径上
- 域边缘端口 : 连接不同的MST域、MST域和运行STP的区域、MST域和运行RSTP的区域的端口，位于MST域的边缘