① STP生成树协议
为了提高网络可靠性，交换机网络中通常会使用冗余链路，冗余链路会给交换机带来环路风险，并导致 广播风暴 以及 MAC地址表不稳定 等问题，生成树协议STP（Spanning Tree Protocol）可以在提高可靠性的同时又避免环路带来的各种问题。
根据交换机的转发原则， 如果交换机从一个端口上接收到的是一个广播帧， 或者是一个目的MAC地址未知的单播帧，则会将这个帧向除源端口之外的所有其他端口转发。如果交换网络中有环路，则这个帧会被无限转发，此时便会形成广播风暴，网络中也会充斥着重复的数据帧。
STP的主要作用： 利用生成树算法、在以太网络中，创建一个以某台交换机的某个端口为根的生成树，自动地在逻辑上阻塞一个或多个冗余端口，避免环路。
STP的基本工作原理为：通过 BPDU (Bridge Protocol Data Unit,桥接协议数据单元)的交互来传递STP计算所需要的条件，随后根据特定的算法，阻塞特定端口，从而得到无环的树形拓扑。
为了计算生成树， 交换机之间需要交换相关的信息和参数， 这些信息和参数被封装在BPDU（Bridge Protocol Data Unit） 中。
BPDU有两种类型：配置BPDU和TCN BPDU（拓扑变更BPDU）。
STP中根桥的选举依据的是桥ID， STP中的每个交换机都会有一个桥ID(Bridge ID) 。 桥ID由16位的桥优先级（Bridge Priority） 和48位的MAC地址构成。 在STP网络中， 桥优先级是可以配置的， 取值范围是0～65535， 默认值为32768。 优先级最高的设备（数值越小越优先） 会被选举为根桥。 如果优先级相同， 则会比较MAC地址， MAC地址越小则越优先 。
非根交换机在选举根端口时分别依据该端口的 根路径开销、 对端BID（Bridge ID） 、 对端PID（Port ID） 和本端PID。
交换机的每个端口都有一个 端口开销 （Port Cost） 参数， 此参数表示该端口在STP中的开销值。 默认情况下端口的开销和端口的带宽有关，带宽越高，开销越小。从一个非根桥到达根桥的路径可能有多条，每一条路径都有一个总的开销值，此开销值是该路径上所有接收BPDU端口的端口开销总和（即BPDU的入方向端口），称为路径开销。非根桥通过对比多条路径的路径开销，选出到达根桥的最短路径，这条最短路径的路径开销被称为 RPC （Root Path Cost， 根路径开销），并生成无环树状网络。 根桥的根路径开销是0。
如果有两个或两个以上的端口计算得到的累计路径开销相同，那么选择收到发送者BID最小的那个端口作为根端口。
运行STP交换机的每个端口都有一个端口ID，端口ID由端口优先级和端口号构成。端口优先级取值范围是0到240，步长为16，即取值必须为16的整数倍。缺省情况下，端口优先级是128。端口ID（Port ID)可以用来确定端口角色，值小者优先。
在网段上抑制其他端口（无论是自己的还是其他设备的）发送BPDU报文的端口，就是该网段的指定端口。
根桥的每个端口总是指定端口。
根端口相对应的端口（即与根端口直连的端口）皆为指定端口。
指定端口的选举也是首先比较累计路径开销，累计路径开销最小的端口就是指定端口。如果累计路径开销相同，则比较端口所在交换机的桥ID，所在桥ID最小的端口被选举为指定端口。如果通过累计路径开销和所在桥ID选举不出来，则比较端口ID，端口ID最小的被选举为指定端口。(同根端口选举)
网络收敛后，只有指定端口和根端口可以转发数据。其他端口为预备端口，被阻塞，不能转发数据，只能够从所连网段的指定交换机接收到BPDU报文，并以此来监视链路的状态。
1、 Forwarding：转发状态。 端口既可转发用户流量也可转发BPDU报文， 只有根端口或指定端口才能进入Forwarding状态。
2、 Learning：学习状态。 端口可根据收到的用户流量构建MAC地址表，但不转发用户流量。 增加Learning状态是为了防止临时环路。
3、 Listening：侦听状态。 端口可以转发BPDU报文， 但不能转发用户流量。
4、 Blocking：阻塞状态。 端口仅仅能接收并处理BPDU， 不能转发BPDU， 也不能转发用户流量。 此状态是预备端口的最终状态。
5、 Disabled：禁用状态。 端口既不处理和转发BPDU报文， 也不转发用户流量。
在稳定的STP拓扑里， 非根桥会定期收到来自根桥的BPDU报文。如果根桥发生了故障，停止发送BPDU报文，下游交换机就无法收到来自根桥的BPDU报文。如果下游交换机一直收不到BPDU报文，Max Age定时器就会超时（Max Age的默认值为20秒），从而导致已经收到的BPDU报文失效，此时，非根交换机会互相发送配置BPDU报文，重新选举新的根桥。根桥故障会导致50秒左右的恢复时间，恢复时间约等于Max Age加上两倍的Forward Delay收敛时间。
1、SWA和SWB使用了两条链路互连，其中一条是主用链路，另外一条是备份链路。生成树正常收敛之后，如果SWB检测到根端口的链路发生物理故障，则其Alternate端口会迁移到Listening、Learning、Forwarding状态，经过两倍的Forward Delay后恢复到转发状态。
2、SWB经过集线器与SWA通过两条链路互连，当主用链路故障时，SWB尚未检测到信号丢失，因此保持原状态不变，但是，根端口已经无法收到来至根桥的BPDU报文，经过T=Max_Age-Message_Age 时间后，原BPDU报文过期，SWB的Alternate端口会迁移到Listening、Learning、Forwarding状态， 经过两倍的Forward Delay后恢复到转发状态。因此，链路经过2xForward_Time + (Max_Age-Message_Age)时间后恢复。
SWB与SWA之间的链路发生了某种故障（非物理层故障），SWB因此一直收不到来自SWA的BPDU报文。 等待Max Age定时器超时后，SWB会认为根桥SWA不再有效，并认为自己是根桥，于是开始发送自己的BPDU报文给SWC，通知SWC自己作为新的根桥。在此期间，由于SWC的Alternate端口再也不能收到包含原根桥ID的BPDU报文。其Max Age定时器超时后，SWC会切换Alternate端口为指定端口并且转发来自其根端口的BPDU报文给SWB。所以，Max Age定时器超时后，SWB、SWC几乎同时会收到对方发来的BPDU。 经过STP重新计算后，SWB放弃宣称自己是根桥并重新确定端口角色。非直连链路故障后，由于需要等待Max Age加上两倍的Forward Delay时间，端口需要大约50秒才能恢复到转发状态。
实验拓扑如上图所示，PCA的IP地址为2.2.2.1/24，PCB的IP地址配置为2.2.2.2/24。
由于网络中存在环路，此时可以看到交换机的所有互联端口以及连接主机的端口的指示灯均快速闪动，表示形成了广播风暴。此时PCA 无法ping通PCB。
在SW1上通过命令stp mode配置生成树协议的模式为RSTP，通过命令stp enable在交换机上使能生成树协议。
SW2、SW3、SW4的配置和SW1相同。启用生成树协议后可以看到交换机各端口指示灯停止快速闪动，网络恢复正常。此时PCA可以ping通PCB。
通过命令display stp brief可以查看交换机各端口的STP状态以及端口角色:
由上可以看出各交换机的根端口为连接SW3的端口，SW3不存在根端口，说明SW3即为网络中的根桥。
2中已知SW3为现根桥，我们可以通过以下命令指定根桥：
该配置将SW1设置为根桥，将SW2设置为备份根桥，我们也可以通过更改桥优先级控制根桥的选举，将SW3的优先级修改为8192，SW2的优先级修改为4096。
查看STP信息：
可以看到，SW2已成为新的根桥。
步骤3后，SW3的GigabitEthernet0/0/3端口为根端口，与根桥SW2互联，端口优先级默认为128，数值越大优先级越小。
将SW2的端口GigabitEthernet0/0/3端口优先级设置为32，GigabitEthernet0/0/6端口优先级设置为16：
注意：此处是修改SW2的端口优先级，而不是修改SW3的端口优先级。
在SW3上查看端口角色：
SW3的GigabitEthernet0/0/6端口成为了根端口。
SW4的GigabitEthernet0/0/3为替代端口，SW1的GigabitEthernet0/0/3为指定端口，修改SW1端口GigabitEthernet0/0/2路径开销为2000000。
查看当前端口角色信息。
STP能够提供无环网络，但是收敛速度较慢。如果STP网络的拓扑结构频繁变化，网络也会随之频繁失去连通性，从而导致用户通信频繁中断。快速生成树协议RSTP使用了Proposal/Agreement机制保证链路及时协商，从而有效避免收敛计时器在生成树收敛前超时。
RSTP的端口角色共有4种： 根端口、指定端口、Alternate端口和Backup端口。
Alternate端口：由于学习到其它网桥发送的更优配置BPDU报文而阻塞的端口；作为根端口的备份端口。
Backup端口：由于学习到自己发送的更优配置BPDU报文而阻塞的端口；作为指定端口的备份端口。
Discarding状态 ， 端口既不转发用户流量也不学习MAC地址。
Learning状态 ， 端口不转发用户流量但是学习MAC地址。
Forwarding状态 ， 端口既转发用户流量又学习MAC地址。
RSTP收敛遵循STP基本原理。网络初始化时，网络中所有的RSTP交换机都认为自己时“根桥”，并设置每个端口为指定端口，此时，端口为Discarding状态。
每个认为自己是“根桥” 的交换机生成一个RST BPDU报文来协商指定网段的端口状态，此RST BPDU报文的Flags字段里面的Proposal位需要置位。当一个端口收到RST BPDU报文时，此端口会比较收到的RST BPDU报文和本地的RST BPDU报文。如果本地的RST BPDU报文优于接收的RST BPDU报文，则端口会丢弃接收的RST BPDU报文，并发送Proposal置位的本地RST BPDU报文来回复对端设备。
当确认下游指定端口迁移到Discarding状态后，设备发送RST BPDU报文回复上游交换机发送的Proposal消息。在此过程中，端口已经确认为根端口，因此RST BPDU报文Flags字段里面设置了Agreement标记位和根端口角色。
在P/A进程的最后阶段，上游交换机收到Agreement置位的RST BPDU报文后，指定端口立即从Discarding状态迁移为Forwarding状态，然后，下游网段开始使用同样的P/A进程协商端口角色。
首先，RSTP将网络拓扑的变化定义为端口角色的变化，因为网络拓扑的变化可以描述为某些网络端口在转发/阻塞态之间的转换，而RSTP将端口角色和端口状态进行了明确的定义（这是RSTP比STP优胜的地方）。
其次，RSTP端口角色的变化直接影响端口状态的变化。R-Port、D-Port、Edge Port处于Forwarding状态；Alternated Port（以下简称A-Port）和Backup Port处于Discarding状态。
若某条链路失效，即链路两端的端口从转发态变为阻塞态。从生成树协议的目的来看，并不会使得网络形成环路。RSTP仅需要找到处于合适的阻塞态端口，并将其转为转发态，使拓扑重新连通起来。由于RSTP在计算时已经分配好R-Port的备份端口A-Port，因此若从转发态变为阻塞态的是R-Port，则把对应的A-Port改为转发态；同理，D-Port的则色也可置相应的Backup Port为转发来实现。而Edge Port并不影响生成树的计算，故忽略。这样，当某个（些）端口状态从转发到阻塞，对于RSTP而言，无需重新计算（是不是有点熟悉，好像哪儿见过不用计算直接使用备用路径的算法。聪明的你一定想到了：DUAL）。
由于某条链路的连通有可能导致生成树域成环。在RSTP里，该行为定义为D-Port从阻塞态转化为转发态，相对的检查机制应的就是P/A机制，即从需要进入转发态的D-Port，建议对端进行同步，待收到确认后进入转发态。
对端Bridge在接收到“建议”消息后，一方面阻塞自身所有D-Port，并返回“同意”消息给“建议”消息发送方；另一方面，对自身端口进行同步。同步分两种类型：若端口为E-Port，或者原来就是非转发态，则为“已同步”；若端口原来为转发态，为重新进入转发态，将对对端进行“建议”并等待确认。
下面将结合图例，演示P/A机制的流程：
1、B、E之间建立一条新链路，首先进行端口角色选择；
2、B、E通过该链路交换BPDU，由于B端口发送的BPDU较优（superior），因此B端口角色为D-Port；与此同时，E从B收到的BPDU比从C收到的较优，因此E把连接B的端口转换为Root Port，同时，连接C的端口转换为A-Port。要注意的是，RSTP相对STP进行了根端口转发的改进，一旦确定了旧的R-Port非转发态，且新的R-Port已确定，则新的R-Port立即进入转发态；
3、此刻B端口仍为Discarding状态，并期望进入Forwarding状态，因此它将从该D-Port发送“Proposal“置位的配置BPDU给E；E接收到该BPDU后，进入同步状态：即将所有转发态端口转为丢弃，并检查端口同步情况；
4、从同步原理可知，E中只有连接D的端口为转发态，因此E继续阻塞该端口，并向B返回”同意“置位的BPDU。自此，B-E链路进入已完成同步，立即进行流量转发；而由于D连接E的端口为A-Port，不转发BPDU，因此E发出的”Proposal“置位BPDU将不会被”Agreement“置位的BPDU回应。该端口将一直保持阻塞态。
实验拓扑如上图所示，交换机各端口均属于VLAN1，PCA的IP地址为2.2.2.1/24，PCB的IP地址配置为2.2.2.2/24。
测试SW2和SW3的连通性：
查看SW2的端口角色
SW2的GigabitEthernet0/0/3为根端口，用ping测试S1到S2的连通性20次。
提示：SW2执行ping操作之后立刻关闭SW3的GigabitEthernet0/0/3接口。
查看SW2的端口角色
SW2的GigabitEthernet0/0/6 成为根端口，端口进入FORWARDING状态，1个包超时。
在SW1上通过命令stp mode配置生成树协议的模式为RSTP，通过命令stp enable在交换机上使能生成树协议。
SW2、SW3、SW4的配置和SW1相同。
配置SW2为STP生成树，其他配置保持不变。
查看SW2端口角色信息
SW2的GigabitEthernet0/0/3为根端口，用ping测试S1到S2的连通性30次。
提示：SW2执行ping操作之后立刻关闭SW3的GigabitEthernet0/0/3接口。
查看SW2端口信息
SW2的GigabitEthernet0/0/6 成为根端口，端口进入FORWARDING状态，16个包超时。
RSTP兼容STP，但收敛方式以STP模式运行。
不管是STP还是RSTP，在网络中进行生成树计算的时候都没有考虑到VLAN的情况。它们都是对单一生成树实例进行应用的。也就是说，在STP和RSTP中所有的VLAN都共享相同的生成树。
为了解决这一个问题，思科提出了第二代生成树 - PVST、PVST+。按照PVST协议规定，每一个VLAN都有一个生成树，而且是每隔2秒就会发送一个BPDU，这对于一个有着上千万个VLAN网络来说，一方面这么多生成树维护起来比较困难，另一方面，为每个VLAN每隔2秒就发送一个BPDU，交换机也是难以承受的。
为了解决PVST带来的困难，思科又提出了第三代生成树 - MST（MSTP）多生成树协议。MSTP可以对网络中众多的VLAN进行分组，把VLAN分到组里。这里的组就是后面讲的MST实例（Instance）。每个实例一个生成树，BPDU只对实例进行发送。这样就达到了负载均衡。
多生成树协议MSTP（Multiple Spanning Tree Protocol）是IEEE 802.1s中定义的一种新型生成树协议。简单说来，STP/RSTP是基于端口的，PVST＋是基于VLAN的，而MSTP是基于实例的。与STP/RSTP和PVST+相比，MSTP中引入了“实例”（Instance）和“域”(Region) “的概念。
所谓“实例”就是多个VLAN的一个集合，这种通过多个VLAN捆绑到一个实例中去的方法可以节省通信开销和资源占用率。MSTP各个实例拓扑的计算是独立的，在这些实例上就可以实现负载均衡。使用的时候，可以把多个相同拓扑结构的VLAN映射到某一个实例中，这些VLAN在端口上的转发状态将取决于对应实例在MSTP里的转发状态。
所谓“域”，即MST域（MST Region），由域名(Configuration Name)、修订级别(Revision Level)、格式选择器(Configuration Identifier Format Selector)、VLAN与实例的映射关系(mapping of VIDs to spanning trees)，其中域名、格式选择器和修订级别在BPDU报文中都有相关字段，而VLAN与实例的映射关系在BPDU报文中表现摘要信息(Configuration Digest)，该摘要是根据映射关系计算得到的一个16字节签名。只有上述四者都一样且相互连接的交换机才认为在同一个域内。如上图所示，每个域内所有交换机都有相同的MST域配置（具有相同的域名；具有相同的VLAN到生成树实例映射配置；具有相同的MSTP修订级别配置）。缺省时，域名就是交换机的桥MAC地址，修订级别等于0，格式选择器等于0，所有的VLAN都映射到实例0上。
MSTP的实例0具有特殊的作用，称为CIST（Common Internal Spanning Tree），即公共与内部生成树，其他的实例称为MSTI（Multiple Spanning Tree Instance），即多生成树实例。CIST由通过STP/RSTP计算得到的单生成树和MSTP计算得到的域组成，是为了保证在所有桥接的局域网是简单的和全连接的。CST（Common Spanning Tree）是STP/RSTP也是MSTP计算出的用于连接MST域的单生成树。IST（Internal Spanning Tree）是在一个给定的MST域内由CIST提供的连通性。如上图所示，如果把每个MST域看作是一个“交换机”，CST就是这些“交换机”通过STP/RSTP或者MSTP协议计算生成的一棵生成树。IST是CIST在MST域内的片段，是一个特殊的多生成树实例。
与STP和RSTP相比，MSTP中引入了总根和域根的概念。总根是一个全局概念，对于所有互连的运行STP/RSTP/MSTP的交换机只能有一个总根，也即是CIST的根；而域根是一个局部概念，是相对于某个域的某个实例而言的。上图所示，所有相连的设备，总根只有一个，而每个域所包含的域根数目与实例个数相关。
与STP和RSTP相比，MSTP中引入了外部路径开销和内部路径开销的概念。外部路径开销是相对于CIST而言的，同一个域内外部路径开销是相同的；内部路径开销是域内相对于某个实例而言的，同一端口对于不同实例对应不同的内部路径开销。
与STP和RSTP相比，MSTP中引入了域边缘端口和Master端口的概念。域边缘端口是连接不同MST域、MST域和运行STP的区域、MST域和运行RSTP的区域的端口，位于MST域的边缘；在某个不包含总根的域中，Master端口是所有边界端口中，到达总根具有最小开销的端口，也就是连接MST域到总根的端口，位于整个域到总根的最短路径上；Alternate端口是Master端口的备份端口，如果Master端口被阻塞后，Alternate端口将成为新的Master端口。
MSTP协议在计算生成树时使用的算法和原理与STP/RSTP大同小异，只是因为在MSTP中引入了域和内部路径开销等参数，故MSTP中的优先级向量是7维，而STP/RSTP是5维。
STP/RSTP中的优先级向量是：
{根桥标识符,根路径开销,桥标识符, 发送BPDU报文端口标识符, 接收BPDU报文端口标识符}
MSTP中的优先级向量是：
{CIST根桥标识符，CIST外部根路径开销，CIST域根标识符，CIST内部根路径开销，CIST指定桥标识符，CIST指定端口标识符，CIST接收端口标识符}
其中STP/RSTP中的桥标识符实际上是发送BPDU的设备的标识符，与MSTP中的CIST指定桥标识符对应。MSTP中的CIST域根标识符有两种情况，一种是总根所在域内，BPDU报文中该字段是参考总根的标识符，另一种情况是不包含总根的域中，BPDU报文该字段是参考主设备的标识符。运行MSTP的实体初始化时认为自己是总根、域根，通过交互配置消息，按照上面介绍的7维向量计算CIST生成树和MSTI。
网络中的设备发送接受BPDU报文，在经过比较配置消息后，在整个网络中选择一个优先级最高的交换机作为CIST的树根。在每个MST域内MSTP通过计算生成IST；同时MSTP将每个MST域作为单台交换机对待，通过计算在MST域间生成CST。如前所述，CST和IST构成了整个交换机网络的CIST。
在MST域内，MSTP根据VLAN和生成树实例的映射关系，针对不同的VLAN生成不同的生成树实例。每棵生成树独立进行计算，计算过程与STP/RSTP计算生成树的过程类似。
MSTI的特点：
MSTP拓扑变化处理与RSTP拓扑变化处理过程类似。
在RSTP中检测拓扑是否发生变化只有一个标准：一个非边缘端口迁移到Forwarding状态。
如此，网络中就会产生RST BPDU的泛洪。
定义VLAN1-10属于INSTANCE 1，VLAN11-20属于INSTANCE 2。
配置SW2在实例1中的优先级为4096, 在实例2中的优先级为8192。
配置SW3在实例2中的优先级为4096，在实例1中的优先级为8192。
查看实例1和实例2的状态
SW2为实例1的根桥，SW3为实例2的根桥。
查看MSTP实例1的端口角色
实例1中SW2为根网桥，SW1的VLAN 1到VLAN10的用户经过GigabitEthernet0/0/1 接口和SW2、 SW3、 SW4的VLAN 1到VLAN10的用户通讯。