华为技术培训课程-生成树原理.doc

课程 DA000028生成树原理ISSUE 1.0DA000028 生成树原理 ISSUE1.0ISSUE 1.0目 录目 录课程说明1课程介绍1课程目标1第1章 透明桥接概述21.1 透明网桥的应用21.2 路径回环的产生41.3 生成树协议的引入5第2章 STP协议62.1 生成树协议基本原理62.2 配置消息介绍72.3 生成树比较92.4 配置消息举例112.5 链路故障处理132.6 临时回路处理172.7 拓扑改变时处理212.8 生成树协议的不足25第3章 快速生成树协议（RSTP）263.1 快速生成树协议介绍263.2 快速生成树协议改进273.3 生成树和快速生成树的比较32iDA000028 生成树原理 ISSUE1.0课程说明课程说明课程介绍本课程主要介绍STP(Spanning Tree Protocol)。在以太网中为了避免单点故障进行链路冗余备份，链路的冗余备份又会导致路径环路，从而产生网络风暴。STP协议可应用于环路网络，通过一定的算法阻断某些冗余路径，将环路网络修剪成无环路的树型网络，从而避免报文在环路网络中的增生和无限循环。课程目标完成本课程的学习后，您应该能够： l 掌握路径环路产生的原因l 掌握STP协议的基本原理l 掌握RSTP协议的基本原理32DA000028 生成树原理 ISSUE1.0第2章 STP协议第1章 透明桥接概述1.1 透明网桥的应用对于一般的透明网桥来说，通常都具有以下的特点：拓展LAN能力：通过透明网桥的应用，可以使原先只在小范围LAN上操作的站点能够在更大范围的LAN环境中工作。l 透明网桥能够自主学习站点的地址信息，从而有效控制网络中的数据包数量。当网桥的某个端口上收到含有某个源MAC地址的数据帧时，它就把该MAC地址和接收该数据帧的端口号保存在MAC地址表中。MAC地址表能够指明该MAC地址与透明网桥的哪个端口相连。当网桥收到一个数据帧时，会查找这张地址表，找到目的MAC所对应的端口。然后分下列三种情况进行处理：如果目的端口是接收端口，则抛弃这个帧；如果不是接收端口，则从那个端口转发该帧。如果收到的数据帧不能从该表中找到对应目的地址的端口，则要从除收到该数据之外所有其他端口广播出去。另外如果网桥收到的是广播帧，也要把该帧从除接收端口以外的所有其他端口转发出去。但问题是“透明”网桥毕竟不是路由器，它不会对报文做任何修改的，报文中不会记录到底经过了几个网桥，如果网络中存在环路，报文有可能在环路中不断循环和增生，造成网络的拥塞，因而导致了网络中“路径回环”问题的产生。1.2 路径回环的产生图中是一个由于环路造成报文循环和增生的例子。假定A站点还没有发送过任何包，因此网桥B1、B2和B3的地址表中都没有A的地址的记录。当A发送了一个包，最初三个网桥都接受了这个包，记录A的地址在LAN1上，并排队等待将这个包转发到LAN2上。根据LAN的规则，其中的一个网桥将首先成功的发送包到LAN2上，假设这个网桥是B1，那么B2和B3将会再次接收到这个包，因为B1对于B2和B3来说是透明的，这个包就好像是A在LAN2上发送的一样，于是B2和B3记录A在LAN2上，排队等待将这个新包转发到LAN1上，假设这时B2成功将最初的包转发到LAN2上，那么B1和B3都接收到这个包。B3还好，只是认为A仍然在LAN2上，而B1又发现A已经转移到LAN2上了，然后B1和B3都会排队等待转发新包到LAN1上。如此下去，包就在环路中不断循环，更糟糕的是每次成功的包发送都会导致网络中出现两个新包。1.3 生成树协议的引入尽管透明网桥存在这个隐患，但是它的应用还是相当有诱惑力的，因为透明网桥在无回路的网络中发挥的作用是无可指摘的。那么是不是就认为我们不能组建有回路的网络呢？这显然是不合适的，因为回路的存在可以在拓扑结构的某条链路断开之后，仍然保证网络的连通性。为此，我们找到了一种很好的算法，它通过阻断冗余链路将一个有回路的桥接网络修剪成一个无回路的树型拓扑结构，这样既解决了回路问题，又能在某条活动（active）的链路断开时，通过激活被阻断的冗余链路重新修剪拓扑结构以恢复网络的连通。上面的图中给出了一个应用生成树的桥接网络的例子，其中字符ROOT所标识的网桥是生成树的树根，实线是活动的链路，也就是生成树的枝条，而虚线则是被阻断的冗余链路，只有在活动链路断开时才会被激活。第2章 STP协议2.1 生成树协议基本原理生成树算法的基本原理也很简单，网桥之间彼此传递一种特殊的配置消息，802.1D协议将这种配置消息称为“配置桥协议数据单元”或者“配置BPDU”。配置消息中包含了足够的信息来保证网桥完成生成树的计算。交换机会根据BPDU消息来完成如下的工作：l 在桥接网络的所有参与生成树计算的网桥中，选出一个作为树根（Root Bridge）；l 计算出其他网桥到这个根网桥的最短路径；l 为每一个LAN选出一个指定网桥，该网桥必须是离根网桥最近的。指定网桥负责将这个LAN上的包转发给根桥；l 为每个网桥选择一个根端口，该端口给出的路径是本网桥到根网桥的最短路径；l 选择包含在生成树上的端口，由根端口和LAN连接其指定网桥的那些端口（指定端口）组成。2.2 配置消息介绍配置消息也被称作桥协议数据单元（BPDU），它主要包括以下内容：即桥接网络中的根桥ID，从指定网桥到根网桥的最小路径开销，指定网桥ID和指定端口ID四项内容。网桥之间通过传递这些内容就足以能够完成生成树的计算。为了叙述方便，我们可以用矢量形式（RootID，RootPathCost，DesignatedBridgeID，DesignatedPortID）来描述某个网桥所发出的BPDU内容。最初，所有的网桥都发送以自己为根桥的配置消息，比如网桥B发送的配置消息为（B，0，B，PortID）； 网桥将接收到的配置消息和自己的配置消息进行优先级比较，保留优先级较高的配置消息，并据此完成生成树的计算。桥接网络中，每个网桥都有一个用来标识自己的唯一的48位地址，生成树协议中，使用网桥优先级和该48位地址的组合作为网桥的ID在配置消息的数据部分中来表示这个网桥。对每个网桥来说，这个网桥的所有端口可以使用端口优先级和端口索引值作为ID来表示，生成树协议使用这个ID在配置消息中唯一的表示网桥中的某个特定端口。BPDU配置消息是以以太网数据帧的格式进行传递的，它采用一个周知的多播MAC地址01-80-C2-00-00-00作为目的MAC地址，网络中所有的网桥收到该地址后都能够判断出该报文是生成树协议的协议报文。源MAC地址域中填的是本网桥的MAC地址。数据链路层报头中的S A P 值是0 1 0 0 0 0 1 0（0x42）。在报文的数据域中携带了用于生成树计算的所有数据。它除了上面所提到的根桥ID，到根的最小路径费用，指定桥ID和指定端口ID外，还包含其它一些辅助信息的值。2.3 生成树比较那么我们是如何根据优先级比较的结果计算生成树的呢？主要分如下的几个步骤进行：l 首先，配置消息中最小的那个根网桥ID将成为生成树的根；l 如果自己就是根网桥，则最短路径开销为0；否则将最优配置消息中的路径开销加上接收端口对应链路的路径开销就是本网桥到根的最短路径开销；l 然后选择根端口，一般来说对应最短路径开销的那个端口就是根端口，但是如果对应最短路径开销的端口不止一个，则ID号最小的端口将成为根端口。l 确定根和最短路径之后，网桥得到自己的配置消息，并将自己作为接收到的配置消息比之劣的那些端口的指定网桥，而这些端口就是指定端口。l 最后，网桥从指定端口将自己的配置消息发送出去。配置消息优先级比较的原则是：l 先比较根网桥的ID，数值较小的那个优先级较高；l 如果根网桥ID相同，则比较发送网桥到根桥的最短路径，数值较小的优先级较高；l 如果前两者都相同，则比较发送网桥的ID，数值较小的优先级较高；l 最后如果前三者都相同，则比较发送端口ID（即配置消息中的指定端口的ID），同样是数值较小的优先级较高。需要说明的是，如果前三者都相同，表明发送网桥的两个端口连接到一个物理LAN上。2.4 配置消息举例下面我们举个例子来说明这个过程。图中网桥B81总共有五个端口，分别接收到这样的配置消息：Port1：（32，0，32）Port2：（23，18，123）Port3：（23，14，321）Port4：（23，14，100）Port5：（23，15，80）注意：在计算过程中，指定端口ID不影响根桥的选择，但会影响根端口的选择。在此，我们为简化起见，暂且不考虑指定端口ID。表示BPDU消息的优先级矢量用（RootID，RootPathCost，DesignatedBridgeID）来表示。经过优先级比较，可以确定最好的根桥是23；而且本网桥到根桥的最短路径是14+1=15；网桥还必须从端口3和端口4中选出一个作为根端口，由于端口4的配置消息的发送桥ID为100，比端口3的321较小，所以端口4为根端口。网桥81将发送（23，15，81）的配置消息，该配置消息优于端口1和2收到的配置消息，因此网桥81为端口1和2所连接的网段的指定网桥，并把自己的配置消息从端口1、2发送出去。这样就确定了，阻塞端口3和端口5，端口4是根端口，端口1和端口2是指定端口。阻塞的端口不参与数据的转发，根端口或指定端口收到的需要转发的数据只能从其他的根端口或指定端口转发出去。从整个网络来看，就等于阻塞了某些链路，而其他的链路组成一个无回路的树型拓扑结构。2.5 链路故障处理如果活动的链路发生故障怎么办呢？生成树算法提供了一种定时器策略，配置消息中携带了一个生存期的域值，根网桥从它的所有端口周期性的发送生存期为0的配置消息，收到配置消息的网桥也同样从自己的指定端口发送自己的生存期为0的配置消息。如果生成树的枝条出现故障，则这条链路下游的端口将不会收到新鲜的配置消息，自己的配置消息的生存期值不断增长，直至到达一个极限。该网桥将抛弃这个过时的配置消息，重新开始生成树计算。其中，定时发送的周期为hello time；配置消息的生存期为message age；最大生存期为max age。假设网桥81的端口4上的配置消息过时了，则网桥81抛弃掉（23，14，100）这条配置消息，重新选择端口3为新的根端口，仍然阻塞端口5，将端口1、端口2和端口4作为指定端口，自己的配置消息也没有变化，从端口1、端口2和端口4发送（23，15，81）的配置消息。假设端口3的配置消息也过时了，则（23，14，321）这条配置消息也被丢弃，重新选择端口5为新的根端口，将端口1、2、3、4都作为指定端口，自己的配置消息变为（23，16，81），并从四个指定端口发送出去。如果端口5的配置消息也过时了，则配置消息（23，15，80）丢掉，网桥以自己为根发送（81，0，81）的配置消息，直到收到更好的配置消息，重新计算生成树。2.6 临时回路处理当链路发生故障，网络的拓扑发生改变，新的配置消息总要经过一定的时延才能传遍整个网络。那么在其他网桥发现拓扑改变之前会发生什么事情呢？有这样两种可能性存在：l 一种可能是：在旧的拓扑中处于转发状态的端口在新的拓扑中应该被阻塞，可是它自己并没有意识到这一点，造成临时的路径回环；l 另一种可能是：在旧的拓扑中被阻塞的端口应该在新的拓扑中参与数据转发，如果它自己不知道，则会造成网络暂时失去连通性。第二种可能没有太大关系，最多丢掉几个包。而第一种可能的危害前面已经说的很多，我想读者们可能也为此而着急。不过没关系，生成树算法的定时器策略提供了一种很好的解决方案。当一个被阻塞的端口要变成转发状态时，需要经历一定的延时。这个时延最起码必须是新的配置消息传播到整个网络所须时间的两倍。假设forward delay是配置消息传遍整个网络的时间，我们可以设计一个中间状态，处于中间状态的端口只能够学习站点的地址信息，而不能参与数据转发。端口从阻塞状态经过forward delay的延时后进入中间状态，再经过forward delay延时后，才能开始转发数据。为解决临时回路的问题，生成树协议引入了若干中间状态。在802. 1D的协议中，端口有这样几种状态：l Disabled：表示该端口不可用，不接收和发送任何报文。这种状态可以是由于端口的物理状态导致的，也可能是管理者手工配置的。l Blocking：处于这个状态的端口不能够参与转发数据报文，但是可以接收配置消息，并交给CPU进行处理。不过不能发送配置消息，也不进行地址学习。l Listening：处于这个状态的端口也不参与数据转发，不进行地址学习；但是可以接收并发送配置消息。l Learning：处于这个状态的端口同样不能转发数据，但是开始地址学习，并可以接收、处理和发送配置消息。l Forwarding：一旦端口进入该状态，就可以转发任何数据了，同时也进行地址学习和配置消息的接收、处理和发送。图中显示了端口的五种状态的迁移关系。从图中我们可以看出来，当一个端口被选为根端口或指定端口，就会从blocking状态迁移到一个中间状态listening状态；经历forward delay的延时，迁移到下一个中间状态learning状态；再经历一个forward delay延时，迁移到forwarding状态。当一个端口由于拓扑发生改变不再是根端口或指定端口了，就会立刻迁移到blocking状态。并且，处于任何状态的端口都可能因为端口可用或者不可用变成disabled状态。从listening迁移到learning，或者从learning迁移到forwarding状态，都需要经过forward delay延时，通过这种延时迁移的方式，能够保证网络中需要迁移到discarding状态（即为胶片中的Blocking状态）的端口已经完成了迁移，因此能够有效的避免临时环路的形成。2.7 拓扑改变时处理网桥通过“学习”了解站点信息，并把它保持在地址表中。由于站点可以被移动，因而网桥应该能够将某些站点老化，除非这个站点能够不断被证明仍然存在。站点信息的老化是通过站点信息在一段时间内没有重新确认而导致超时来实现的。如果站点位置的改变是由于站点物理上被移动了，则我们可以将站点信息老化时间以分钟为数量级，这是因为拔下某个站点的插头，再移动这个站点（物理上移动），然后再插上插头到站点可以开始工作，很可能花掉十几分钟时间。而且被移动的站点可以通过某种策略，以尽快开始工作。例如，它们可以向广播地址发送包。当所有的网桥看到从源S 发来的包后，它们将修正到S 的条目。基于上面考虑，一般将站点信息的老化时间设为15分钟。然而，重新生成一棵生成树会改变多个站点的位置。而且这种逻辑上的位置改变站点本身是无法主动觉察到的，因此也就不能通过某种特殊机制（如发广播包）来修正站点的地址信息。让很多站点在拓扑结构改变了1 5 分钟之后都不能被访问是不大现实的。因此，如果地址表的老化时间值大于生成树重新计算所需的时间，我们认为需要有两个缓冲区超时值：1) 一般情况下使用的较长值（较大值）。2) 生成树重新计算后使用的较短的缓冲区超时值。当站点的物理位置发生变化，网桥学习到的地址信息可能就不正确了，所以每条学习到的地址信息有一个生存期，如果在生存期内没有报文来确认这条地址是正确的，就丢弃它。大家可以想象到，如果站点的物理位置变化，比如把一台终端设备从一个接入端口拔下来，再插到另一个端口上，肯定会花费比较长的时间，那么这段时间就不会发送任何报文，它的地址信息就会因此而从网桥的地址表中删除掉。所以这种情况中的地址信息生存期可以是一个比较长的值。但是当生成树的拓扑发生变化，站点的相对位置也可能会相应的变化。比如图中，LANC上的站点对于根网桥来说，本来是端口1所在网段的；后来LANA的链路出现故障，导致生成树重新计算并为网桥B2选择了一条新的通往根桥的路径，这个时候LANC上的站点对于根网桥来说就转移到了端口2所在网段上。如果在很长一段时间内根网桥没有发现这个变化，就会将给LANC的报文从端口1转发出去，而真正的目的地可能会收不到这些报文。怎么办呢？我们的解决办法是给每条学习到的地址信息加上一个较短的生存期。在网桥发现拓扑变化期间，站点的相对位置变化的可能性最大，所以用这个较短的生存期来限制地址表项。这时您可能会问，为什么不担心站点的物理位置变化会导致很长时间收不到报文呢？很简单，因为站点物理位置变化期间是不需要收到任何报文的。但是问题又来了，并不是桥接网络中的所有网桥都会发现拓扑已经改变了的。比如上一页图中，B2的局部变化对网络的其他部分没有什么影响，网桥B1、B3和B4可能根本就没有意识到生成树已经和从前不同了，因为对这些网桥来说，各个端口的状态没有任何变化，链路也是正常畅通的。不同的只是LANC的相对位置，可是这一点只有LANC上的站点发送报文的时候才能被发现，而没有发送之前这些网桥都错误地用旧地址转发表项来转发到LANC的数据，所以有必要让网络中的所有网桥都意识到：网络拓扑已经变化了！地址转发表项可能已经出现异常了！必须给那些学习到的地址表项设置较短的生存期！这就是生成树协议中拓扑改变报文的用途。拓扑改变报文有三种：拓扑改变通知消息，拓扑改变应答消息，拓扑改变消息。下面分别来介绍一下三种报文的含义：(1) 拓扑改变通知消息：发现拓扑改变的网桥从根端口以hello time为周期定时向根网桥的方向发送拓扑改变通知消息，每一个收到这个通知消息的非根网桥也同样要向根桥的方向发送这个消息。这个消息是一个格式比较特殊的报文，它没有数据项，只需要让根知道拓扑改变即可。(2) 拓扑改变应答消息：收到拓扑改变通知消息的网桥如果不是根网桥需要响应一个拓扑改变应答消息，收到应答消息的网桥就知道了：哦，你已经收到我的通知消息，那我就停止发送通知消息吧。这个消息是携带在该网桥发送的下一个配置消息中，用一个拓扑改变应答标志位来标识。(3) 拓扑改变消息：根网桥收到拓扑改变通知消息，或者自己发现拓扑改变之后，则在一个时间段内，在以hello time为周期定时向其他网桥发送的配置消息中，携带一个拓扑改变的标志位。收到这个消息的网桥将会应用那个较短的地址表项生存期，直到收到的配置消息中不再有这个标志。上图中显示了拓扑改变通知的全过程。2.8 生成树协议的不足在前面我们介绍了有关生成树协议的一些特性。在实际的应用中，生成树协议也有很多美中不足的地方。最主要的缺点是端口从阻塞状态到转发状态需要两倍的forward delay时延，导致网络的连通性至少要几十秒的时间之后才能恢复。如果网络中的拓朴结构变化频繁，网络会频繁的失去连通性，这样用户就会无法忍受。为了尽量避免网络失去连通性，我们的交换机应用了一种“快速生成树”算法。DA000028 生成树原理 ISSUE1.0第3章 快速生成树协议（RSTP）第3章 快速生成树协议（RSTP）3.1 快速生成树协议介绍快速生成树（RSTP）是从生成树算法的基础上发展而来，承袭了它的基本思想，即也是通过配置消息来传递生成树信息，并通过优先级比较来进行计算。快速生成树能够完成生成树的所有功能，不同之处就在于：快速生成树在不会造成临时环路的前提下，减小了端口从阻塞到转发的时延，尽可能快的恢复网络连通性，提供更好的用户服务。3.2 快速生成树协议改进快速生成树从三个方面实现“快速”功能：1）一个新的根端口从阻塞到转发：如果旧的根端口已经知道自己不再是根端口了，并进入阻塞状态，且此时新的根端口连接的网段的指定端口正处于转发状态，那么这个新的根端口就可以无延时的进入转发状态。图中所示的情况就是一种典型的根端口快速状态迁移的例子。2）一个非边缘指定端口从阻塞到转发：“非边缘”的意思是这个端口连接着其他的网桥，而不是只连接到终端设备。等待进入转发状态的指定端口向下游发送一个握手请求报文，如果下游的网桥响应了一个赞同报文，则这个指定端口就可以无延时的进入转发状态。握手请求报文是在该端口发送的下一个配置消息中，用一个握手标志位来标识；握手响应报文也是携带在端口发送的下一个配置消息中，用一个赞同标志位来标识。图中所示的情况是一个典型的非边缘指定端口快速状态迁移的例子。不过这种快速状态迁移需要一个前提条件：发起握手的端口与响应握手的端口之间是一条点对点链路！如果这个条件不满足，握手将不会被响应。那么这个指定端口只好等待两倍的forward delay时延了。可见点对点链路对快速生成树的性能有很大的影响，下面列举了点对点链路的几种情况：l