STP生成树协议原理与算法简析.docx
《STP生成树协议原理与算法简析.docx》由会员分享，可在线阅读，更多相关《STP生成树协议原理与算法简析.docx（16页珍藏版）》请在冰点文库上搜索。
STP生成树协议原理与算法简析
STP生成树协议原理与算法简析
简介
在实际的网络环境中，物理环路可以提高网络的可靠性，当一条线路断掉的时候，另一
条链路仍然可以传输数据。
但是，在交换网络中，当交换机接收到一个未知目的地址的数据
帧时，交换机的操作是将这个数据帧广播出去，这样，在存在物理的交换网络中，就会产生
一个双向的广播环，甚至产生广播风暴，导致交换机死机。
这就产生一个矛盾，需要物理环路来提高网络可靠性，而环路又可能产生广播风暴，如何才能两全其美呢？
本章将要讲述的STP,就是用来解决这个矛盾的。
STP（SpanningTreeProtocol，生
成树协议）是根据IEEE802.1D标准建立的，用于在局域网中消除数据链路层物理环路的协议。
运行该协议的设备通过彼此交互信息发现网络中的环路，并有选择的对某些端口进行
阻塞，最终将环路网络结构修剪成无环路的树型网络结构，从而防止报文在环路网络中不断
增生和无限循环，避免设备由于重复接收相同的报文所造成的报文处理能力下降的问题发生。
STP采用的协议报文是BPDU（BridgeProtocolDataUnit，桥协议数据单元），也称为配置消息，BPDU中包含了足够的信息来保证设备完成生成树的计算过程。
STP即是通过在设
备之间传递BPDU来确定网络的拓扑结构。
1STP生成树协议
1.1STP的主要作用
消除环路：
通过阻断冗余链路来消除网络中可能存在的路径回环。
链路备份：
当前活动路径发生故障时，激活冗余备份链路，恢复网络连通性。
1.2STP的基本原理：
通过在交换机之间传递一种特殊的协议报文一一BPD（在IEEE802.1D中这种协议报文被称
为“配置消息”）来确定网络的拓扑结构。
配置消息中包含了足够的信息来保证交换机完成生成树计算。
（注：
此BPDU被称为配置BPDU另外STP还有TCNBPDU）
图1BPDU勺报文格式
注意看BPDL数据报文的最后8个字段，分别是：
根桥ID:
由树根的优先级（0-65535，默认32768）和MAC地址组合而成；
到树根的最短路径开销（实际由PortPathCost叠加而成），有两个标准一一dotld-1998，默
认值为100和dot1t，默认值为200000；
指定桥的ID:
由指定交换机的优先级和MAC地址组合而成；
指定端口的ID:
由指定端口的优先级（0-256，默认128）和端口编号组成；
配置消息的生存期：
MessageAge;
配置消息的最大生存期：
MaxAge
配置消息发送的周期：
HelloTime；
端口状态迁移的延时：
ForwardDelay。
启动了STP的交换机互相之间通过发送配置BPDU来完成根桥，指定桥的选举，各端口状态
的选择和整个网络拓扑结构的确定。
比较的关键部分在于这八个字段中的前四个字段，即：
根桥ID、路径开销、指定桥ID和指定端口的ID。
其实还有一个接收端口的ID，用于本地比较（当交换机的2个端口都收到相同的BPDU寸——比如上连一个stpdisable的交换机或hub）。
比较的原则：
从上到下、从左到右数值小者优先。
STP协议使用的所有BPDU都是组播报文，目的MAC是01-80-C2-00-00-00。
1.3STP端口的角色和状态
STP拓扑结构的建立微观上说是一个全网交换机互相交互的过程，各台交换机相互之间不停
的发送配置BPDU发送和接受BPDU的是各switch的Ports,BPDU不单在不同交换机的端口之间比较，也在交换机的内部作比较，如果发现比自己“优”的BPDU就进行报文的更
新，如果发现对方传来的BPDU不如自己的，则丢弃报文，直到再收不到比自己更优的BPDU
为止。
当网络中所有的交换机都处于这种状态的时候我们可以认为拓扑结构已经建立，但根
端口和指定端口还得经过2个ForwardDelayTime才能进入转发状态。
所以STP拓扑结构
的建立实际上可以理解为端口角色的建立，所有端口都为指定端口的交换机被选为根桥，其
余的为指定桥。
这里要提到5个概念：
根桥，指定桥，根端口，指定端口，Block端口。
根桥就是“网桥ID”最优的桥，当STP的拓扑结构稳定之后由根桥负责每2秒（HelloTime）
向树中所有的网桥发送配置BPDC报文，其他网桥接收并转发。
根端口即去往根桥路径最近的端口，这个最近的衡量是靠RootPathCost来判定的。
有关
PathCost的计算，是每当一个端口收到一个BPDU后，会在该BPDU所指示的PathCost上
加上该端口的PortPathCost（这是可以人为配置的）。
比较累计RootPathCost最小的
端口就是根端口，如果有两条开销相同的路径，那么就选择桥BID较小的。
指定桥就是对下游来说向它转发BPDC报文的桥，一个LAN上除了根桥以外的所有网桥都是
指定桥。
为什么这么说呢？
根据定义而来，指定桥上必定有指定端口（即使是网络边缘的网
桥也有一一连接到主机的端口），而指定端口就是用来转发BPDI报文的。
这里要注意的是拓
扑稳定后RootPort是不发送BPDL报文的，虽然它的状态是Forwarding，它只接收BPDU
指定端口：
即在一个LAN里面负责转发BPDU的端口，根桥和指定桥上都有它，但根端口只
在指定桥上有，同样block端口也只存在于指定桥上。
Block端口：
即被对方的指定端口抑制的端口，Block端口不转发任何报文，但他接收BPDU
监听网络变化。
根端口、指定端口、Block端口即为STP网桥端口的三个角色。
1.4端口状态：
如图所示，一共有5种端口状态：
Forwarding
转发用户流量的状态，只有根端口或指定端口才有这种状态。
Learning
构建MAC地址表，这时接收到用户帧，网桥会填充自己MAC也
址表。
所以是学习“状态”。
Listening
根桥、根端口、指定端口的选择就是在该状态内完成。
Blocking
仅仅接收ConfigurationBPDU。
Disabled
或Down,认为阻断或物理上断掉。
表1STP的五种端口状态
前三个状态之间的转换各需要经过一个ForwardingDelayTime（15s），这也是可以人为配
置的。
关于几个计时器将在后面的内容加以介绍。
1.5STP工作原理
生成树算法及验证（STP选举过程）
1.生成树算法
生成树协议运行生成树算法（STA）。
生成树算法很复杂，但是其过程可以归纳为以下三个步骤。
（1）选择根网桥（ROOTBRIDGE
（2）选择根端口（ROOTPORT）
（3）选择指定端口（DESIGNATEDPORTS
*******************************************************************************
名词解释：
网桥的交换机的前身，由于STP是在网桥基础上开发的，因此现在交换机的网
络中仍然沿用网桥这一术语。
******************************************************************************
F面以一个例子来讲解这几个步骤的选择过程，它采用如图4.5所示的网络拓扑。
图4.5STP收敛过程示例拓扑图
要将图所示的网络结构变成一个无环的拓扑，首先，STP要选择根网桥，前面讲过,
STP是将一个环形的拓扑变成一个树状的拓扑结构，因此选择根网桥实现上就是为网络选出
一个树根，那么选择根网桥的依据是什么呢？
1）选择根网桥
选择根网桥的依据是网桥ID，网桥ID是一个八字节的字段，其组成结构如图4.6所示,
前面两个字节的十进制数称为网桥优先级，后六个字节是网桥的MAC地址。
网桥优先级是用于衡量网桥在生成树算法中优生级的十进制数，取值范围为0~65535,默认
值是32768.
网桥ID中的MAC地址是交换机自身的MAC地址.
按照生成树算法的定义，当比较那个STP参数的两个取值时，值小的优先级高。
因此,
在选择根网桥的时候，比较的方法是看哪台交换机的网桥ID的值最小，优先级小的被选择
为根网桥，在优先级相同的情况下，MAC地址小的为根网桥。
在如图4.5所示的拓扑中，SW2的优先级为4096,SW1与SW3的优先级为默认值32768,因此，SW2被选为根网桥，如图4.7所示。
图4.7收敛过程选择根网桥
如果SW2的优先级也是32768时，三台交换机的优先级相同。
比较三台交换机的MAC
地址，SW2的MAC地址最小，所以SW2被选为根网桥。
2）选择根端口
选出了根网桥之后，网络中的每台交换机必须和根网桥建立关联，因此，STP将开始选择根
端口的过程。
根端口存在每个非根网桥上，需要在每个非根网桥上选择一个根端口。
选择根端口的依据按照顺序依次如下：
到根网桥最低的根路径成本。
直连的网桥ID最小
端口ID最小
根路径成本是两个网桥间的路径上所有链路的成本之和，也就是一个网桥到达根网桥的中间
所有链路的路径成本之和，如图4.8所示
图4.8根路径成本与路径成本
路径成本用来代表一条链路带宽的大小，见表4-1，一条链路的带宽越大，它的传输数据的
成本也就越低。
4-1带宽与路径成本的关系
端口ID是一个二字节的STP参数，由一个字节的端口优先级和一个字节的端口编号组成,如图4.9所示。
端口优先级是一个可配置的STP参数，在基于IOS的交换机上，端口优先级的十进制取值范
围是0~255,默认值是128。
端口编号是catalyst用于列举各个端口的数字标识符。
在STP选择根端口的时候，首先比较交换机端口的根路径成本，根路径成本低的为根端口，
当根路径成本相同的时候，比较连接的交换机的网桥ID值，选择网桥ID值小的作为根端口;
当网桥ID相同的时候，比较端口ID值，选择较小的作为根端口。
*******************************************************************************
注意啦：
在比较端口ID时，比较的是接收到的对端的端口ID值
****************************************************************************
在如图4.10所示的拓扑中，已经选出了根网桥，那么下一步就需要在SW1和SW3上各选择
一个根端口，在本例中，所有的链路都是100MB/S的，那么下一步就需要在SW1和SW3上直接与SW2相连的接口的根路径成本是19,而SW1与SW3之间连接的端口，其根路径成本应
该是19+19=38;因此，在SW1与SW3上，直连SW2的端口被选为根端口，如图4.10
图4.10STP收敛过程选择根端口
3）选择指定端口
选择完根网桥和每台交换机的根端口后，一个树形结构已初步形成，但是，所有
链路仍连接在一起，并可以都处于活动状态，最后导致形成环路。
为了消除环路形成的可能，STP进行最后的计算，在每一个网段上选择一个指定端
口，选择指定端口的依据有三个：
根路径成本较低
所在的交换机的网桥ID值较小
端口ID较小
在STP选择指定端口的时候，首先比较同一网段上端口中根路径成本最低的，也就是将
到达根网桥最近的端口作为指定端口；当根路径成本相同的时候，比较这个端口所在的交换
机的网桥ID值，选择一个网桥ID值小的交换机上的端口作为指定端口；当网桥ID相同的时候，也就是说，有几个位于同一交换机上的端口时，比较端口ID值，选择较小的作为指
定端口。
另外，根网桥上的接口都是指定端口，因为根网桥上端口的根路径成本为0
如图4.11所示的拓朴中，首先，作为根网桥的SW2上的端口都是指定端口。
那么在SW1与SW3连接的网段上需要在两个端口之间选出一个指定端口来。
首先比较两个端口的根路径成本，这两个端口的根路径成本的值都是38（19+19），那么
只能比较网桥的ID了，现在SW1与SW3的网桥优先级相同，SW3勺MAC地址小于SW1的MAC地址，因此，SW3的网桥ID小，所以SW3上的端口选作指定端口（如图4.11所示）。
STP的计算过程结束，这时，只有在SW1
上连接到SW3的端口既不是根端口，也不是指定端口，那么这个端口被阻塞（BLOC）被阻
塞的端口不能传输数据。
由于SW1上连接SW3的接口被阻塞，所以图4.11所示的拓朴可以等价为图4.12SW1和SW3之间的链路成为备份链路。
1.6STP算法
现在重点讲一下STP算法的实现，纯理论的讲算法过于枯燥，这儿以三台全互连的交换机为
例描述一下实现过程。
（注：
关于状态机的标准实现可以参考IEEE.802.1D，这里只用容易
理解的语言描述整个过程，可能有细节说法上不太规范，但更方便理解。
）
图2STP算法拓扑图
为了描述方便，这里指比较BPDU的前四项：
根桥ID（以以太网交换机的优先级表示），根路径开销，指定交换机ID（以以太网交换机的优先级表示），指定端口ID（以端口号表示）。
假设SWA,SWB,SWC桥优先级分别为0,1,2。
各链路开销为2，3，6。
这里要特别说明一点：
RootPathCost不是一个可配置项，即它是由交换机根据PortPathCost比较而累积
得出的，PortPathCost才是一个可配置的选项。
图中的链路开销可理解为2端端口的Port
PathCost，只不过它们恰好相同而已。
（1）初始状态
各台交换机的各个端口在初始时会生成以自己为根的配置消息，根路径开销为0，指定交换
机ID为自身交换机ID，指定端口为本端口。
SwitchA:
端口AP1配置消息：
{0，0，0，AP1}
端口AP2配置消息：
{0，0，0，AP2}
SwitchB:
端口
BP1配置消息：
{1，
0，1,
BP1}
端口
BP2配置消息：
{1，
0，
1,
BP2}
SwitchC:
端口
CP2配置消息：
{2，
0，
2,
CP2}
端口
CP1配置消息：
{2，
0，
2,
CP1}
（2）
选出最优配置消息
各台交换机都向外发送自己的配置消息。
当某个端口收到比自身的配置消息优先级低的配置
消息时，交换机会将接收到的配置消息丢弃，对该端口的配置消息不作任何处理。
当端口
收到比本端口配置消息优先级高的配置消息的时候，交换机就用接收到的配置消息中的内容
替换该端口的配置消息中的内容。
然后以太网交换机将该端口的配置消息和交换机上的其
它端口的配置消息进行比较，选出最优的配置消息。
配置消息的比较原则是:
树根ID较小的配置消息优先级高；若树根ID相同，则比较根路径开销，比较方法为：
用配置消息中的根路径开销加上本端口对应的路径开销之和（设为S）,则S较小的配置消息优
先级较高；若根路径开销也相同，则依次比较指定交换机ID、指定端口ID、接收该配置消
息的端口ID等。
为便于表述，本例中假设只需比较树根ID就可以选出最优配置消息。
（3）确定根端口，并阻塞冗余链路，然后更新指定端口的配置消息。
交换机接收最优配置消息的那个端口定为根端口，端口配置消息不作改变；其它端口中，如
果某端口的配置消息在过程“选出最优配置消息”中更新过，则交换机将此端口阻塞，端
口配置消息不变，此端口将不再转发数据，并且只接收但不发送配置消息；如果某端口的配
置消息在过程“选出最优配置消息”中没有更新过，则交换机就将其定为指定端口，配置
消息要作如下改变：
树根ID替换为根端口的配置消息的树根ID;根路径开销替换为根端口
的配置消息的根路径开销加上根端口对应的路径开销；指定交换机ID替换为自身交换机的
ID;指定端口ID替换为自身端口ID。
例子中各台交换机的比较过程如下:
SwitchA:
端口API收到SwitchB的配置消息，SwitchA发现本端口的配置消息优先级优于接收到的配置消息的优先级，就把接收到的配置消息丢弃。
端口AP2的配置消息处理过程与端口AP1
类似。
SwitchA发现自己各个端口的配置消息中树根和指定交换机都是自己，则认为自己是树根，各个端口的配置消息都不作任何修改，以后周期性的向外发送配置消息。
此时两个
端口的配置消息如下：
端口AP1配置消息：
｛0,0，0，AP1｝。
端口AP2配置消息：
｛0，0，0，AP2｝。
SwitchB:
端口BP1收到来自SwitchA的配置消息，经过比较后SwitchB发现接收到的配置消息的优
先级比端口BP1的配置消息的优先级优，于是更新端口BP1的配置消息。
端口BP2收到来自SwitchC的配置消息，SwitchB发现该端口的配置消息优先级优于接收到的配置消息的优先级，就把接收到的配置消息丢弃。
则此时各个端口的配置消息如下：
端口BP1配置消息：
｛0，0,0，AP1｝，端口BP2配置消息：
｛1，0，1，BP2｝。
SwitchB对各个端口的配置消息进行比较，选出端口BP1的配置消息为最优配置消息，
然后将端口BP1定为根端口，这个过程中端口BP2的配置消息没有更新过，则将端口BP2
定位指定端口。
整台交换机各个端口的配置消息都进行如下更新：
根端口BP1配置消息不作
改变：
｛0，0，0，AP1｝。
端口BP2配置消息中，树根ID更新为最优配置消息中的树根ID，
根路径开销更新为2,指定交换机ID更新为本交换机ID，指定端口ID更新为本端口ID，配置消息变为：
｛0，2，1，BP2｝。
然后SwitchB各个指定端口周期性向外发送自己的配置消息。
SwitchC:
端口CP2先会收到来自SwitchB端口BP2更新前的配置消息｛1，0，1，BP2｝，SwitchC触
发更新过程，更新后的配置消息如下：
｛1,0,1,BP2｝。
端口CP1收到来自SwitchA的配置消息｛0,0,0,AP2｝后SwitchC也触发更新过程，更新
后的配置消息如下：
｛0，0，0，AP2｝。
经过比较，端口CP1的配置消息被选为最优的配置消息，端口CP1就被定为根端口；而端口
CP2就会被选为指定端口，并发送更新后的BPDU｛0，6，2，CP2｝
接着端口CP2会收到SwitchB更新后的配置消息｛0，2，1，BP2｝，由于收到的配置消息比原配置消息优，则SwitchC触发更新过程，更新后的配置消息为：
｛0，2，1，BP2｝。
同时端口CP1收到来自SwitchA配置消息，比较后SwitchC不会触发更新过程，配置消息
仍然为：
｛0，0，0，AP2｝。
经过内部比较，（CP1｛0，6，0，AP2｝,CP2｛0，5，1，BP2｝）端口CP2的配置消息被选为最
优的
配置消息，端口CP2就被选为根端口，端口CP1的配置消息因为更新过，所以端口CP1就被
阻塞，状态稳定后，不接收从SwitchA转发的数据，直到新的情况触发生成树的计算，比
如从SwitchA到SwitchC的链路down掉，或者端口收到更优的配置消息。
1.7关于STP协议的手工选举方法
交换机接收BPDU时开销值增加，发送BPDU时开销值不变
选举根端口，比较接收的BPDU
选举指定端口，比较发送的BPDU
下面通过一个示例具体介绍，首先是拓扑图。
1选举根桥（RootBridge）。
优先级一样，比较MAC地址，SW1为根桥。
2、选举每台非根桥交换机上的根端口（RootPort），比较接收到的BPDU（BPD由根桥发出，
即SW1发出）：
SW2从f0端口收到的BPDU代价为19；从fl端口收到的BPDU代价为19+4+19=42；因此f0端口为根端口。
SW3从g0端口收到的BPDU代价为19+19=38;从g1端口收到的BPDU代价为19+4=23;因此g1端口为根端口。
SW4从g0端口收到的BPDU代价为19;从g1端口收到的BPDU代价为19+19+4=42；因此g0端口为根端口。
3、选举每个网段上的指定端口（DesignatedPort），比较发出的BPDU
SW1-SW2网段：
从SW1/fO口发出的BPDU代价为0;从SW2/fO口发出的BPDU代价为
19+4+19=42;因此SW1/fO口为指定端口。
SW1-SW4网段：
从SW1/f1口发出的BPDU代价为0;从SW4/gO口发出的BPDU代价为19+19+4=42;因此SW1/f1口为指定端口。
SW3-SW网段：
从SW3/g1口发出的BPDU代价为19+19=38;从SW4/g1口发出的BPDU代价为
19;因此SW4/g1口为指定端口。
SW2-SW网段：
从SW2/f1口发出的BPDU代价为19;从SW3/g0口发出的BPDU代价为19+4=23;
因此SW2/f1口为指定端口。
4、非根端口，非指定端口即为阻塞端口（BlockPort），即SW3/g0口为阻塞端口。
好了，有什么问题大家可以互相交流，这个方法在考试的时候很好用。
欢迎您的下载，
资料仅供参考!
致力为企业和个人提供合同协议，策划案计划书，学习资料等等
打造全网一站式需求
升级会员 