00-STP生成树算法

学习目标生成树（STP）算法网桥间的路由回路为了提高可靠性，LAN之间会连接多个网桥，同时也带来路由回路广播帧带来的广播风暴：假设站点A发送一个广播帧，网桥α和β都会收到这个广播帧，并把广播帧转发到LANY上。然后又被网桥α和β收到并转发到LANX，如此往复单播帧也会带来问题网桥α网桥β站点B站点ALANXLANY网桥间的路由回路（续）单播帧带来的问题错误学习和重复转发：假设桥都已经知道站点A和B的信息，并且站点A传输一个到站点B的帧。网桥α和β都会从LANX收到帧，认为A在LANX的一方，并转发到LANY中。–站点B就会收到这个帧的两个拷贝–同时网桥α转发的帧被网桥β从LANY接收到，因而认为站点A在LANY的这一方。即网桥β会认为A和B都在LANY，这样A和B之间的帧就会被过滤单播帧的广播风暴假设两个桥都还不了解站点B的存在,并且A传输一个到B的帧每个桥收到这个帧后由于没有B的信息会扩散到LANY上，并且被另一个网桥收到后进一步扩散到LANX，如此继续形成单播帧的风暴引入生成树协议(STP)通过阻断冗余链路来消除桥接网络中可能存在的路径回环当前活动路径发生故障时激活冗余备份链路恢复网络连通性ROOTLANALANBLANCLANDLANE生成树算法解决路由回路的方法是让网桥互相通信，并且构造一棵到达每个LAN的生成树，路由根据生成树来进行来自于图论的结论：对于那些由许多节点以及连接节点的边组成的连通图，存在一个生成树，它保证了图的连通性，同时又没有一个闭合环。算法必须是动态的。也就是说，当拓扑结构改变时，桥应该能够发现它的改变，并且检测回路，通过关闭某些网桥的端口来自动生成一个新的生成树生成树算法中的基本术语每个桥分配一个唯一的标识BID。每个桥的端口，都分配一个该桥中的16比特的唯一标识，称为“端口号标识”。每个端口都分配一个路径花费，指的是通过该端口在其连接的LAN上传输帧的花费。两个节点间的路径有一个总花费，等于经过的桥的端口路径花费的和。两个站点间的路径将会通过零或多个桥。在每个桥都加上通过相应端口传输的花费，从而对于每个特定路径有一个总的花费。在最简单的情况下，所有路径花费都为1；因此一条路径的花费将是在路上经过的桥的个数。生成树算法中的基本术语（续）根桥：标识BID最低的网桥被选为生成树的根根端口：每个桥有一条到根桥的具有最少花费的路径，该路径上面的第一个跳段所使用的端口就是根端口。如果有两个端口有同样的花费，则选择具有更低端口号的端口，以保证建立一个唯一的生成树。根路径花费：对于每个桥，到根桥的具有最少花费的路径（该路径由网桥的根端口开始）的花费就是桥的根路径花费。选取桥：在每个LAN中都有一个桥被选为选取桥。这个桥是在那个LAN中具有最少的到根桥的路径花费的桥。只有这个选取桥允许把帧转发给那个LAN或把来自于那个LAN的帧转发出去。选取端口：选取桥的那个用来把桥连接到该LAN上的端口称为选取端口。对于所有根桥连接的LAN而言，根桥就是选取桥。所有到达LAN或从LAN出发的互连网中的通信都要经过选取端口。生成树算法中的BPDU消息生成树算法要求网桥之间通过桥协议数据单元（BPDU）交换信息该BPDU被送到在同一个LAN上的所有其它桥每个BPDU由下列信息组成：产生该BPDU消息的桥标识发送该BPDU消息的端口标识产生该BPDU消息的桥所了解到的根桥标识到根桥的路径花费：直接连接到根桥的端口花费一般为0。生成树算法的基本步骤生成树的构造的基本步骤：首先决定根桥：标识最低的网桥被选为生成树的根然后决定所有其它桥的根端口桥到根桥的最短路径上的端口就是根端口如果有两个端口有同样的花费，则选择具有更低端口号的端口最后决定每个LAN的选取桥和选取端口：LAN上的具有最少根路径花费的网桥就是选取桥，如果有两个或多个桥具有同样的根路径花费，具有最高优先级的桥选取为选取桥。如果选取桥有两个或多个端口连在这个LAN上，具有最低端口标识的端口被作为选取端口。只有选取桥允许执行其选取端口连接的LAN的帧转发过程生成树算法的基本步骤（续）开始所有桥都认为自己是根桥。每个桥都会在它连接的每个LAN上广播一个BPDU来宣告这个信息其他桥收到该BPDU后，比较根桥ID的大小，如果新的根桥更小，则更新根桥BID；否则发送一BPDU给新启动的桥，新的桥将更新根桥。直接连到根桥上的那些LAN上的所有桥可以决定它们的根端口（那个具有到根桥的最少路径花费的端口）。这些桥接着在它所连接的其它LAN（除了它的根端口所在的其它LAN）上广播一个BPDU，在转发BPDU时更新其中包括的根路径花费，宣称它离根桥有一个跳段。如此继续，每个桥都可以决定自己的根路径花费和根端口对根桥来说，其所有端口花费为0，对于所有根桥连接的LAN而言，根桥就是选取桥，而根桥的所有端口则为选取端口。生成树算法的基本步骤（续）在任一LAN中，宣称最靠近根的桥（具有最少的到根桥的路径花费的桥）成为选取桥。如果收到一个具有更小路径花费或者路径花费相同但BID更小的BPDU则说明自身不是该端口直接连接的LAN的选取桥知道了选取桥，也就知道选取桥直接连接到该LAN上的端口就是选取端口，如果选取桥有多个端口连接到该LAN，则把具有更小端口号的端口作为选取端口。只有每个LAN中的选取桥允许向其选取端口连接的该LAN转发帧，设置为转发状态。而其他桥中所有端口置为阻塞状态，不允许转发帧。系统稳定时，只有根桥定期产生BPDU，各个LAN中只有选取桥通过选取端口转发BPDU消息。如果生成树中的某个网桥出故障，下游的网桥将无法收到BPDU消息，在等待一定时间的超时后，下游的网桥将宣称自己就是根桥，从而重新开始配置生成树的过程。生成树算法的基本步骤（续）任何时候一个桥从某个端口收到一个BPDU时，要判断是否是一个“更好”的BPDU消息：收到的BPDU标识一个具有更小BID的根桥的BPDU。这说明自己不是根桥，从而停止生成BPDU，只转发来自其他桥的消息；在转发时当然要更新路径花费（加上连接到该LAN上的端口花费）如果收到的BPDU标识同一个根桥，但是具有更小的路径花费，或者根桥BID和路径花费相同，但是发送该BPDU的桥BID更小。这说明自己不是该LAN的选取桥，停止通过该端口转发BPDU消息。例子用三元组来表示一个BPDU消息，(Y,D,X)表示桥X发送的BPDU消息，其中到根桥Y的花费为D，假设所有网桥开始加电，都宣称自己是根桥：1.B3收到B2来的BPDU消息(B2,0,B2)；2.因为23，因此B3接受B2为根桥；B3B2B5B7B1B6B4ABCDEFGHIJK3.接着B3转发该BPDU，在转发时更新路径花费，因此B3往LANA转发BPDU(B2,1,B3)，该BPDU将被B5收到；4.同时这个时候B2收到B1来的BPDU消息，发现B1的BID更小，因此接受B1为根桥，同时往LANC转发BPDU消息(B1,1,B2)，该BPDU将被B3接收；5.B5也收到B1发送的BPDU，接受B1为根桥；6.B5会把刚收到的BPDU转发给LANA，B3会收到(B1,1,B5)，B3接受B1为根桥，并且发现B2和B5都更靠近B1，停止转发消息广播帧和组播帧的转发广播帧：网桥按照生成树来进行转发，即通过其活跃端口（即选取端口）来转发广播帧。组播帧许多网桥采用和广播帧类似的处理，即通过其活跃端口来转发组播帧组播帧都会转发到互连的所有LAN上如果属于那个组播地址的站点只位于少数几个LAN，那么往所有LAN转发就会浪费带宽。GARP组播登记协议GMRP（GARPMulticastRegistrationProtocol）协议每个组里面的站点会定期发送一个目的地址为组播地址的帧，网桥就可以了解到端口里面有站点属于这个组播组网桥之间通过GMRP协议交换组播组的信息，从而网桥可以知道所连接的端口对应的那方是否有站点属于哪个组播组如果一个网桥收到一个组播帧，可以采取和单播帧类似的转发逻辑：如果有属于该组播地址的站点连接到某个端口上，则往该端口转发，否则不转发。链路故障怎么办HelloTime网桥从指定端口以HelloTime为周期定时发送配置消息MessageAge和MaxAge端口保存的配置消息有一个生存期MessageAge字段,并按时间递增.每当收到一个生存期更小的配置消息,则更新自己的配置消息.当一段时间未收到任何配置消息,生存期达到MaxAge时,网桥则认为该端口连接的链路发生故障,进行故障的处理23，18，123链路故障处理一Port4的配置消息生存期超时了,则抛弃该配置消息,重新进行生成树计算,选择Port3为新的根端口，而网桥81的配置消息没有变化Port1Port2Port3Port4Port5blocking23，14，32123，15，8023，15，81rootB8132，0，3223，15，8123，15，81链路故障处理二Port3的配置消息生存期也超时了，则抛弃该配置消息，重新进行生成树计算，选择Port5为新的根端口，网桥81的配置消息变为（23，16，81）Port1Port2Port3Port4Port523，15，8023，16，81root23，16，8132，0，3223，18，12323，16，8123，16，81B81链路故障处理三Port5的配置消息生存期也超时了，则抛弃该配置消息，以自己为根桥发送配置消息（81，0，81），直到从任一个端口收到优先级更高的配置消息Port1Port2Port3Port4Port581，0，8181，0，8181，0，8181，0，8181，0，81B81端口的几种状态端口能力不收发任何报文DisabledBlockingListeningLearning端口状态Forwarding不接收或转发数据,接收但不发送BPDUs,不进行地址学习不接收或转发数据,接收并发送BPDUs,不进行地址学习不接收或转发数据,接收并发送BPDUs,开始地址学习接收并转发数据,接收并发送BPDUs,进行地址学习端口的状态迁移DisabledListeningBlockingForwardingLearning1）端口enabled2）端口disabled3）端口被选为根端口或指定端口4）端口被选为备用端口（阻塞）5）ForwardDelay延时（1）（2）（1，2）（1，2）（1，2）（1）（2）（4）（4）（5）（4）（5）（3）配置消息处理实例根据收到配置消息的优先级，选择Port4为根端口，选择Port1和Port2为指定端口，同时阻塞端口Port3和Port5。从Port1和Port2发送新的配置消息：（23，15，81），其中，RootId=23RootPathCost=14+1=15RootPort=Port4Port1Port2Port3Port4Port5blockingblocking40，0，3223，18，12323，14，32123，14，10023，15，80root23，15，81B8123，15，81生成树协议不足端口从阻塞状态进入转发状态必须经历两倍的ForwardDelay时间，所以网络拓扑结构改变之后需要至少两倍的ForwardDelay时间，才能恢复连通性如果网络中的拓朴结构变化频繁，网络会频繁的失去连通性，这样用户就会无法忍受。