STP生成树协议原理与算法简析

1、STP生成树协议原理与算法简析简介在实际的网络环境中，物理环路可以提高网络的可靠性，当一条线路断掉的时候，另一条链路仍然可以传输数据。但是，在交换网络中，当交换机接收到一个未知目的地址的数据帧时，交换机的操作是将这个数据帧广播出去，这样，在存在物理的交换网络中，就会产生一个双向的广播环，甚至产生广播风暴，导致交换机死机。这就产生一个矛盾，需要物理环路来提高网络可靠性，而环路又可能产生广播风暴，如何才能两全其美呢？本章将要讲述的STP，就是用来解决这个矛盾的。STP（Spanning Tree Protocol，生成树协议）是根据IEEE 802.1D 标准建立的，用于在局域网中消除数据链路层物

2、理环路的协议。运行该协议的设备通过彼此交互信息发现网络中的环路，并有选择的对某些端口进行阻塞，最终将环路网络结构修剪成无环路的树型网络结构，从而防止报文在环路网络中不断增生和无限循环，避免设备由于重复接收相同的报文所造成的报文处理能力下降的问题发生。STP采用的协议报文是BPDU（Bridge Protocol Data Unit，桥协议数据单元），也称为配置消息，BPDU中包含了足够的信息来保证设备完成生成树的计算过程。STP即是通过在设备之间传递BPDU来确定网络的拓扑结构。1 STP 生成树协议1.1 STP的主要作用消除环路：通过阻断冗余链路来消除网络中可能存在的路径回环。链路备份：当

3、前活动路径发生故障时，激活冗余备份链路，恢复网络连通性。1.2 STP的基本原理：通过在交换机之间传递一种特殊的协议报文BPDU（在IEEE 802.1D中这种协议报文被称为“配置消息”）来确定网络的拓扑结构。配置消息中包含了足够的信息来保证交换机完成生成树计算。（注：此BPDU被称为配置BPDU，另外STP还有TCN BPDU。）图1 BPDU的报文格式注意看BPDU数据报文的最后8个字段，分别是：根桥ID：由树根的优先级（0-65535，默认32768）和MAC地址组合而成；到树根的最短路径开销(实际由PortPathCost叠加而成)，有两个标准dot1d-1998，默认值为100和do

4、t1t，默认值为200000；指定桥的ID：由指定交换机的优先级和MAC地址组合而成；指定端口的ID：由指定端口的优先级（0-256，默认128）和端口编号组成；配置消息的生存期：MessageAge；配置消息的最大生存期：MaxAge；配置消息发送的周期：HelloTime；端口状态迁移的延时：ForwardDelay。启动了STP的交换机互相之间通过发送配置BPDU来完成根桥，指定桥的选举，各端口状态的选择和整个网络拓扑结构的确定。比较的关键部分在于这八个字段中的前四个字段，即：根桥ID、路径开销、指定桥ID和指定端口的ID。其实还有一个接收端口的ID，用于本地比较（当交换机的2个端口都收

5、到相同的BPDU时比如上连一个stp disable的交换机或hub）。比较的原则：从上到下、从左到右数值小者优先。STP协议使用的所有BPDU都是组播报文，目的MAC是01-80-c2-00-00-00。1.3 STP端口的角色和状态STP拓扑结构的建立微观上说是一个全网交换机互相交互的过程，各台交换机相互之间不停的发送配置BPDU，发送和接受BPDU的是各switch的Ports，BPDU不单在不同交换机的端口之间比较，也在交换机的内部作比较，如果发现比自己“优”的BPDU，就进行报文的更新，如果发现对方传来的BPDU不如自己的，则丢弃报文，直到再收不到比自己更优的BPDU为止。当网络中所

6、有的交换机都处于这种状态的时候我们可以认为拓扑结构已经建立，但根端口和指定端口还得经过2个Forward Delay Time才能进入转发状态。所以STP拓扑结构的建立实际上可以理解为端口角色的建立，所有端口都为指定端口的交换机被选为根桥，其余的为指定桥。这里要提到5个概念：根桥，指定桥，根端口，指定端口，Block端口。根桥就是“网桥ID”最优的桥，当STP的拓扑结构稳定之后由根桥负责每2秒（Hello Time）向树中所有的网桥发送配置BPDU报文，其他网桥接收并转发。根端口即去往根桥路径最近的端口，这个最近的衡量是靠Root Path Cost来判定的。有关Path Cost的计算，是每

7、当一个端口收到一个BPDU后，会在该BPDU所指示的Path Cost上加上该端口的Port Path Cost（这是可以人为配置的）。比较累计Root Path Cost最小的端口就是根端口，如果有两条开销相同的路径，那么就选择桥BID较小的。指定桥就是对下游来说向它转发BPDU报文的桥，一个LAN上除了根桥以外的所有网桥都是指定桥。为什么这么说呢？根据定义而来，指定桥上必定有指定端口（即使是网络边缘的网桥也有连接到主机的端口），而指定端口就是用来转发BPDU报文的。这里要注意的是拓扑稳定后Root Port是不发送BPDU报文的，虽然它的状态是Forwarding，它只接收BPDU。指定端

8、口：即在一个LAN里面负责转发BPDU的端口，根桥和指定桥上都有它，但根端口只在指定桥上有，同样block端口也只存在于指定桥上。Block端口：即被对方的指定端口抑制的端口，Block端口不转发任何报文，但他接收BPDU，监听网络变化。根端口、指定端口、Block端口即为STP网桥端口的三个角色。1.4 端口状态： 如图所示，一共有5种端口状态：Forwarding转发用户流量的状态，只有根端口或指定端口才有这种状态。Learning构建MAC地址表，这时接收到用户帧，网桥会填充自己MAC地址表。所以是学习“状态”。Listening根桥、根端口、指定端口的选择就是在该状态内完成。Block

9、ing仅仅接收Configuration BPDU。Disabled或Down，认为阻断或物理上断掉。表1 STP的五种端口状态前三个状态之间的转换各需要经过一个Forwarding Delay Time（15s），这也是可以人为配置的。关于几个计时器将在后面的内容加以介绍。1.5 STP工作原理生成树算法及验证（STP选举过程） .生成树算法 生成树协议运行生成树算法（STA）。生成树算法很复杂，但是其过程可以归纳为以下三个步骤。（） 选择根网桥（ROOT BRIDGE）（） 选择根端口（ROOT PORTS）（） 选择指定端口（DESIGNATED PORTS） *名词解释： 网桥的交换机

10、的前身，由于STP是在网桥基础上开发的，因此现在交换机的网络中仍然沿用网桥这一术语。* 下面以一个例子来讲解这几个步骤的选择过程，它采用如图.所示的网络拓扑。 图.STP收敛过程示例拓扑图 要将图所示的网络结构变成一个无环的拓扑，首先，STP要选择根网桥，前面讲过，STP是将一个环形的拓扑变成一个树状的拓扑结构，因此选择根网桥实现上就是为网络选出一个树根，那么选择根网桥的依据是什么呢？） 选择根网桥 选择根网桥的依据是网桥ID，网桥ID是一个八字节的字段，其组成结构如图4.6所示，前面两个字节的十进制数称为网桥优先级，后六个字节是网桥的MAC地址。 网桥优先级是用于衡量网桥在生成树算法中优生级

11、的十进制数，取值范围为65535,默认值是32768. 网桥ID中的MAC地址是交换机自身的MAC地址. 按照生成树算法的定义，当比较那个STP参数的两个取值时，值小的优先级高。因此，在选择根网桥的时候，比较的方法是看哪台交换机的网桥ID的值最小，优先级小的被选择为根网桥，在优先级相同的情况下，MAC地址小的为根网桥。 在如图.所示的拓扑中，SW2的优先级为4096,SW1与SW3的优先级为默认值32768,因此，SW2被选为根网桥，如图.所示。 图.收敛过程选择根网桥 如果SW2的优先级也是32768时，三台交换机的优先级相同。比较三台交换机的MAC地址，SW2的MAC地址最小，所以SW2被

12、选为根网桥。） 选择根端口选出了根网桥之后，网络中的每台交换机必须和根网桥建立关联，因此，STP将开始选择根端口的过程。根端口存在每个非根网桥上，需要在每个非根网桥上选择一个根端口。选择根端口的依据按照顺序依次如下:到根网桥最低的根路径成本。直连的网桥ID最小端口ID最小根路径成本是两个网桥间的路径上所有链路的成本之和，也就是一个网桥到达根网桥的中间所有链路的路径成本之和，如图4.8所示 图4.8根路径成本与路径成本路径成本用来代表一条链路带宽的大小，见表4-1，一条链路的带宽越大，它的传输数据的成本也就越低。4-1 带宽与路径成本的关系端口ID是一个二字节的STP参数，由一个字节的端口优先级

13、和一个字节的端口编号组成，如图4.9所示。 端口优先级是一个可配置的STP参数，在基于IOS的交换机上，端口优先级的十进制取值范围是0255，默认值是128。端口编号是catalyst用于列举各个端口的数字标识符。在STP选择根端口的时候，首先比较交换机端口的根路径成本，根路径成本低的为根端口，当根路径成本相同的时候，比较连接的交换机的网桥ID值，选择网桥ID值小的作为根端口；当网桥ID相同的时候，比较端口ID值，选择较小的作为根端口。 *注意啦：在比较端口ID时，比较的是接收到的对端的端口ID值*在如图4.10所示的拓扑中，已经选出了根网桥，那么下一步就需要在SW1和SW3上各选择一个根端口

14、，在本例中，所有的链路都是100MB/S的，那么下一步就需要在SW1和SW3上直接与SW2相连的接口的根路径成本是19，而SW1 与SW3之间连接的端口，其根路径成本应该是19+19=38;因此，在SW1与SW3上，直连SW2的端口被选为根端口，如图4.10 图4.10 STP收敛过程选择根端口） 选择指定端口 选择完根网桥和每台交换机的根端口后， 一个树形结构已初步形成，但是，所有链路仍连接在一起，并可以都处于活动状态，最后导致形成环路。 为了消除环路形成的可能，STP进行最后的计算，在每一个网段上选择一个指定端口，选择指定端口的依据有三个: 根路径成本较低 所在的交换机的网桥ID值较小 端

15、口ID较小 在STP选择指定端口的时候，首先比较同一网段上端口中根路径成本最低的，也就是将到达根网桥最近的端口作为指定端口；当根路径成本相同的时候，比较这个端口所在的交换机的网桥ID值，选择一个网桥ID值小的交换机上的端口作为指定端口；当网桥ID相同的时候，也就是说，有几个位于同一交换机上的端口时，比较端口ID值，选择较小的作为指定端口。另外，根网桥上的接口都是指定端口，因为根网桥上端口的根路径成本为0 如图4.11所示的拓朴中，首先，作为根网桥的SW2上的端口都是指定端口。那么在SW1 与SW3连接的网段上需要在两个端口之间选出一个指定端口来。 首先比较两个端口的根路径成本，这两个端口的根路

16、径成本的值都是38 （19+19），那么只能比较网桥的ID 了，现在SW1与SW3的网桥优先级相同，SW3的MAC地址小于SW1的MAC地址，因此，SW3的网桥ID小，所以SW3上的端口选作指定端口（如图4.11所示）。 STP的计算过程结束，这时，只有在SW1上连接到SW3的端口既不是根端口，也不是指定端口，那么这个端口被阻塞（BLOCK）。被阻塞的端口不能传输数据。 由于SW1上连接SW3的接口被阻塞，所以图4.11所示的拓朴可以等价为图4.12 SW1和SW3之间的链路成为备份链路。 1.6 STP算法现在重点讲一下STP算法的实现，纯理论的讲算法过于枯燥，这儿以三台全互连的交换机为例描

17、述一下实现过程。（注：关于状态机的标准实现可以参考IEEE.802.1D，这里只用容易理解的语言描述整个过程，可能有细节说法上不太规范，但更方便理解。）图2 STP算法拓扑图为了描述方便，这里指比较BPDU的前四项：根桥ID（以以太网交换机的优先级表示），根路径开销，指定交换机ID（以以太网交换机的优先级表示），指定端口ID（以端口号表示）。假设SWA,SWB,SWC的桥优先级分别为0，1，2。各链路开销为2，3，6。这里要特别说明一点：Root Path Cost不是一个可配置项，即它是由交换机根据Port Path Cost比较而累积得出的，Port Path Cost才是一个可配置的选项

18、。图中的链路开销可理解为2端端口的Port Path Cost，只不过它们恰好相同而已。（1）初始状态各台交换机的各个端口在初始时会生成以自己为根的配置消息，根路径开销为0，指定交换机ID为自身交换机ID，指定端口为本端口。Switch A：端口AP1配置消息：0，0，0，AP1端口AP2配置消息：0，0，0，AP2Switch B：端口BP1配置消息：1，0，1，BP1端口BP2配置消息：1，0，1，BP2Switch C：端口CP2配置消息：2，0，2，CP2端口CP1配置消息：2，0，2，CP1（2）选出最优配置消息各台交换机都向外发送自己的配置消息。当某个端口收到比自身的配置消息优先级

19、低的配置消息时，交换机会将接收到的配置消息丢弃，对该端口的配置消息不作任 何处理。当端口收到比本端口配置消息优先级高的配置消息的时候，交换机就用接收到的配置消息中的内容替换该端口的配置消息中的内容。然后以太网交换机将该 端口的配置消息和交换机上的其它端口的配置消息进行比较，选出最优的配置消息。配置消息的比较原则是：树根ID较小的配置消息优先级高；若树根ID相同，则比较根路径开销，比较方法为：用配置消息中的根路径开销加上本端口对应的路径开销之和（设为S），则S较小的配置消息优先级较高；若根路径开销也相同，则依次比较指定交换机ID、指定端口ID、接收该配置消息的端口ID等。为便于表述，本例中假设只

20、需比较树根ID就可以选出最优配置消息。（3） 确定根端口，并阻塞冗余链路，然后更新指定端口的配置消息。交换机接收最优配置消息的那个端口定为根端口，端口配置消息不作改变；其它端口中，如果某端口的配置消息在过程“选出最优配置消息”中更新过，则交换机将 此端口阻塞，端口配置消息不变，此端口将不再转发数据，并且只接收但不发送配置消息；如果某端口的配置消息在过程“选出最优配置消息”中没有更新过，则交换 机就将其定为指定端口，配置消息要作如下改变：树根ID替换为根端口的配置消息的树根ID；根路径开销替换为根端口的配置消息的根路径开销加上根端口对应 的路径开销；指定交换机ID替换为自身交换机的ID；指定端口

21、ID替换为自身端口ID。例子中各台交换机的比较过程如下：Switch A：端口AP1收到Switch B的配置消息，Switch A发现本端口的配置消息优先级优于接收到的配置消息的优先级，就把接收到的配置消息丢弃。端口AP2的配置消息处理过程与端口AP1类似。Switch A发现自己各个端口的配置消息中树根和指定交换机都是自己，则认为自己是树根，各个端口的配置消息都不作任何修改，以后周期性的向外发送配置消息。此时两个端口的配置消息如下：端口AP1配置消息：0，0，0，AP1。端口AP2配置消息：0，0，0，AP2。Switch B：端口BP1收到来自Switch A的配置消息，经过比较后Swi

22、tch B发现接收到的配置消息的优先级比端口BP1的配置消息的优先级优，于是更新端口BP1的配置消息。端口BP2收到来自Switch C的配置消息，Switch B发现该端口的配置消息优先级优于接收到的配置消息的优先级，就把接收到的配置消息丢弃。则此时各个端口的配置消息如下：端口BP1配置消息：0，0，0，AP1，端口BP2配置消息：1，0，1，BP2。Switch B对各个端口的配置消息进行比较，选出端口BP1的配置消息为最优配置消息，然后将端口BP1定为根端口，这个过程中端口BP2的配置消息没有更新过，则将端口BP2定位指定端口。整台交换机各个端口的配置消息都进行如下更新：根端口BP1配置

23、消息不作改变：0，0，0，AP1。端口BP2配置消息中，树根ID更新为最优配置消息中的树根ID，根路径开销更新为2，指定交换 机ID更新为本交换机ID，指定端口ID更新为本端口ID，配置消息变为：0，2，1，BP2。然后Switch B各个指定端口周期性向外发送自己的配置消息。Switch C：端口CP2先会收到来自Switch B端口BP2更新前的配置消息1，0，1，BP2，Switch C触发更新过程，更新后的配置消息如下：1，0，1，BP2。端口CP1收到来自Switch A的配置消息0，0，0，AP2后Switch C也触发更新过程，更新后的配置消息如下：0，0，0，AP2。经过比较，

24、端口CP1的配置消息被选为最优的配置消息，端口CP1就被定为根端口；而端口CP2就会被选为指定端口，并发送更新后的BPDU：0，6，2，CP2接着端口CP2会收到Switch B更新后的配置消息0，2，1，BP2，由于收到的配置消息比原配置消息优，则Switch C触发更新过程，更新后的配置消息为：0，2，1，BP2。同时端口CP1收到来自Switch A配置消息，比较后Switch C不会触发更新过程，配置消息仍然为：0，0，0，AP2。经过内部比较，( CP10，6，0，AP2,CP20，5，1，BP2 )端口CP2的配置消息被选为最优的配置消息，端口CP2就被选为根端口，端口CP1的配置消息因为更新过，所以端口CP1就被阻塞，状态稳定后，不接收从Switch A转发的数据，直到新的情况触发生成树的计算，比如从Switch A到Switch C的链