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

STP生成树协议原理与算法简析简介在实际的网络环境中，物理环路可以提高网络的可靠性，当一条线路断掉的时候，另一条链路仍然可以传输数据。但是，在交换网络中，当交换机接收到一个未知目的地址的数据帧时，交换机的操作是将这个数据帧广播出去，这样，在存在物理的交换网络中，就会产生一个双向的广播环，甚至产生广播风暴，导致交换机死机。这就产生一个矛盾，需要物理环路来提高网络可靠性，而环路又可能产生广播风暴，如何才能两全其美呢？本章将要讲述的STP，就是用来解决这个矛盾的。STP（SpanningTreeProtocol，生成树协议）是根据IEEE802.1D标准建立的，用于在局域网中消除数据链路层物理环路的协议。运行该协议的设备通过彼此交互信息发现网络中的环路，并有选择的对某些端口进行阻塞，最终将环路网络结构修剪成无环路的树型网络结构，从而防止报文在环路网络中不断增生和无限循环，避免设备由于重复接收相同的报文所造成的报文处理能力下降的问题发生。STP采用的协议报文是BPDU（BridgeProtocolDataUnit，桥协议数据单元），也称为配置消息，BPDU中包含了足够的信息来保证设备完成生成树的计算过程。STP即是通过在设备之间传递BPDU来确定网络的拓扑结构。1STP生成树协议1.1STP的主要作用消除环路：通过阻断冗余链路来消除网络中可能存在的路径回环。链路备份：当前活动路径发生故障时，激活冗余备份链路，恢复网络连通性。1.2STP的基本原理：通过在交换机之间传递一种特殊的协议报文——BPDU（在IEEE802.1D中这种协议报文被称为“配置消息”）来确定网络的拓扑结构。配置消息中包含了足够的信息来保证交换机完成生成树计算。（注：此BPDU被称为配置BPDU，另外STP还有TCNBPDU。）DMASMAL/TLLCHeaderpayload0x0180c20000000x424203BPDU数据报文字节2协议版本11标志位184822MaxAge222目的MAC地址是一个固定的组播地址源MAC地址是发送配置消息的桥的MAC地址。配置消息固定的链路头帧长域值协议IDBPDU类型根桥ID最短路径开销指定桥ID指定端口IDHelloTimeForwardDelayMessageAgeDMASMAL/TLLCHeaderpayload0x0180c20000000x424203BPDU数据报文字节2协议版本11标志位184822MaxAge222目的MAC地址是一个固定的组播地址源MAC地址是发送配置消息的桥的MAC地址。配置消息固定的链路头帧长域值协议IDBPDU类型根桥ID最短路径开销指定桥ID指定端口IDHelloTimeForwardDelayMessageAge图1BPDU的报文格式注意看BPDU数据报文的最后8个字段，分别是：根桥ID：由树根的优先级（0-65535，默认32768）和MAC地址组合而成；到树根的最短路径开销(实际由PortPathCost叠加而成)，有两个标准——dot1d-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）向树中所有的网桥发送配置BPDU报文，其他网桥接收并转发。根端口即去往根桥路径最近的端口，这个最近的衡量是靠RootPathCost来判定的。有关PathCost的计算，是每当一个端口收到一个BPDU后，会在该BPDU所指示的PathCost上加上该端口的PortPathCost（这是可以人为配置的）。比较累计RootPathCost最小的端口就是根端口，如果有两条开销相同的路径，那么就选择桥BID较小的。指定桥就是对下游来说向它转发BPDU报文的桥，一个LAN上除了根桥以外的所有网桥都是指定桥。为什么这么说呢？根据定义而来，指定桥上必定有指定端口（即使是网络边缘的网桥也有——连接到主机的端口），而指定端口就是用来转发BPDU报文的。这里要注意的是拓扑稳定后RootPort是不发送BPDU报文的，虽然它的状态是Forwarding，它只接收BPDU。指定端口：即在一个LAN里面负责转发BPDU的端口，根桥和指定桥上都有它，但根端口只在指定桥上有，同样block端口也只存在于指定桥上。Block端口：即被对方的指定端口抑制的端口，Block端口不转发任何报文，但他接收BPDU，监听网络变化。根端口、指定端口、Block端口即为STP网桥端口的三个角色。1.4端口状态：如图所示，一共有5种端口状态：表1STP的五种端口状态前三个状态之间的转换各需要经过一个ForwardingDelayTime（15s），这也是可以人为配置的。关于几个计时器将在后面的内容加以介绍。1.5STP工作原理生成树算法及验证（STP选举过程）１.生成树算法生成树协议运行生成树算法（STA）。生成树算法很复杂，但是其过程可以归纳为以下三个步骤。（１）选择根网桥（ROOTBRIDGE）（２）选择根端口（ROOTPORTS）（３）选择指定端口（DESIGNATEDPORTS）*******************************************************************************Forwarding转发用户流量的状态，只有根端口或指定端口才有这种状态。Learning构建MAC地址表，这时接收到用户帧，网桥会填充自己MAC地址表。所以是学习“状态”。Listening根桥、根端口、指定端口的选择就是在该状态内完成。Blocking仅仅接收ConfigurationBPDU。Disabled或Down，认为阻断或物理上断掉。名词解释：网桥的交换机的前身，由于STP是在网桥基础上开发的，因此现在交换机的网络中仍然沿用网桥这一术语。******************************************************************************下面以一个例子来讲解这几个步骤的选择过程，它采用如图４.５所示的网络拓扑。图４.５STP收敛过程示例拓扑图要将图所示的网络结构变成一个无环的拓扑，首先，STP要选择根网桥，前面讲过，STP是将一个环形的拓扑变成一个树状的拓扑结构，因此选择根网桥实现上就是为网络选出一个树根，那么选择根网桥的依据是什么呢？１）选择根网桥选择根网桥的依据是网桥ID，网桥ID是一个八字节的字段，其组成结构如图4.6所示，前面两个字节的十进制数称为网桥优先级，后六个字节是网桥的MAC地址。网桥优先级是用于衡量网桥在生成树算法中优生级的十进制数，取值范围为０~65535,默认值是32768.网桥ID中的MAC地址是交换机自身的MAC地址.按照生成树算法的定义，当比较那个STP参数的两个取值时，值小的优先级高。因此，在选择根网桥的时候，比较的方法是看哪台交换机的网桥ID的值最小，优先级小的被选择为根网桥，在优先级相同的情况下，MAC地址小的为根网桥。在如图４.５所示的拓扑中，SW2的优先级为4096,SW1与SW3的优先级为默认值32768,因此，SW2被选为根网桥，如图４.７所示。图４.７收敛过程选择根网桥如果SW2的优先级也是32768时，三台交换机的优先级相同。比较三台交换机的MAC地址，SW2的MAC地址最小，所以SW2被选为根网桥。２）选择根端口选出了根网桥之后，网络中的每台交换机必须和根网桥建立关联，因此，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收敛过程选择根端口３）选择指定端口选择完根网桥和每台交换机的根端口后，一个树形结构已初步形成，但是，所有链路仍连接在一起，并可以都处于活动状态，最后导致形成环路。为了消除环路形成的可能，STP进行最后的计算，在每一个网段上选择一个指定端口，选择指定端口的依据有三个:根路径成本较低所在的交换机的网桥ID值较小端口ID较小在STP选择指定端口的时候，首先比较同一网段上端口中根路径成本最低的，也就是将到达根网桥最近的端口作为指定端口；当根路径成本相同的时候，比较这个端口所在的交换机的网桥ID值，选择一个网桥ID值小的交换机上的端口作为指定端口；当网桥ID相同的时候，也就是说，有几个位于同一交