计算机网络网桥生成树算法

㈠ 生成树协议的结构思路

生成树协议拓扑结构的思路是: 不论网桥(交换机)之间采用怎样物理联接,网桥(交换机)能够自动发现一个没有环路的拓扑结构的网路，这个逻辑拓扑结构的网路必须是树型的。生成树协议还能够确定有足够的连接通向整个网络的每一个部分。所有网络节点要么进入转发状态，要么进入阻塞状态,这样就建立了整个局域网的生成树。当首次连接网桥或者网络结构发生变化时，网桥都将进行生成树拓扑的重新计算。为稳定的生成树拓扑结构选择一个根桥, 从一点传输数据到另一点, 出现两条以上条路径时只能选择一条距离根桥最短的活动路径。生成树协议这样的控制机制可以协调多个网桥(交换机)共同工作, 使计算机网络可以避免因为一个接点的失败导致整个网络联接功能的丢失, 而且冗余设计的网络环路不会出现广播风暴。
例如，网络中，A点到C点，有两条路可以走，当ABC的路径不通的时候，可以走ADC。C点到A点也是，路径CDA不通的时候可以走CBA。

如果某一时刻的网络，使能生成树协议，阻塞了B到C的端口，那么网络拓扑就会变成下图。如果有广播包，一定会终结于B点或者C点，不会循环转发。

㈡ 什么是生成树

生成树算法的网桥协议STP(Spanning Tree Protocol) 它通过生成生成树保证一个已知的网桥在网络拓扑中沿一个环动态工作。网桥与其他网桥交换BPDU消息来监测环路，然后关闭选择的网桥接口取消环路，统指IEEE802·1生成树协议标准和早期的数字设备合作生成树协议，该协议是基于后者产生的。IEEE版本的生成树协议支持网桥区域，它允许网桥在一个扩展本地网中建设自由环形拓扑结构。IEEE版本的生成树协议通常为在数字版本之上的首选版本。

㈢ 生成树协议IEEE802.1D的简介

网络环路的发生有多种原因，最常见的一种是有意生成的冗余 － 万一一个链路或交换机失败，会有另一个链路或交换机替代。
STP 允许网桥之间相互通信以发现网络物理环路。该协议定义了一种算法，网桥能够使用它创建无环路（loop-free）的逻辑拓朴结构。换句话说，STP 创建了一个由无环路树叶和树枝构成的树结构，其跨越了整个第二层网络。
生成树协议操作对终端站透明，也就是说，终端站并不知道它们自己是否连接在单个局域网段或多网段中。当有两个网桥同时连接相同的计算机网段时，生成树协议可以允许两网桥之间相互交换信息，这样只需要其中一个网桥处理两台计算机之间发送的信息。
网桥之间通过桥接协议数据单元（Bridge Protocol Data Unit － BPDU）交换各自状态信息。生成树协议通过发送 BPDU 信息选出网络中根交换机和根节点端口，并为每个网段（switched segment）选出根节点端口和指定端口。
网桥中的程序能够决定如何使用生成树协议，这称为生成树算法，该算法能够避免网桥环路，并确保在多路径情形下网桥能够选择一条最有效的路径。如果最佳路径失败，可以使用该算法重新计算网络路径并找出下一条最佳路径。 利用生成树算法可以决定网络（哪台计算机主机在哪个区段），并通过 BPDU 信息交换以上数据。该过程主要分为以下两个步骤：
步骤1：通过评估它所接收到的所有配置信息和选择最优选项，来决定一个网桥可发送的最佳信息。
步骤2：一旦选定某网桥发送的信息，网桥将该信息与来自无根（non-root）连接的可能配置信息相比较。如果步骤1中选择的最佳选项并不优于可能配置信息，便删除该端口。

㈣ 计算机网络 生成树

选择根网桥、根端口、指定端口的判断依据：
一、 选择根网桥的依据：交换机之间选择网桥ID值最小的交换机作为网络中的根网桥。
交换机优先级（缺省32768）和MAC地址构成网桥ID。

二、选择根端口的依据是：
1>根路径成本最低 （根据链路带宽大小来定的，链路带宽越大成本越低）
2>直连的网桥ID最小
3>端口ID最小 （每个交换机的端口都有一个端口ID ：0、1、2、3、4、5....）
我只是略懂。。。。。只能答这个样子

㈤ 简单说明思科交换生成树的算法是如何实现的

交换机内的生成树算法（STA）使你可以创建一条备用链路（当网络中存在多台交换机时）。在主链路正常工作时，备用链路处于空闲状态（不工作）；只有在主链路出现问题时，备用链路才不需要任何人工干预自动地接替主链路。这种自动重构的功能，使得网络上的用户能够最大限度地与网络保持正常的连接。生成树算法较复杂，所以，建议最好在充分研究理解其之后，再更改其一些设置。请仔细阅读并理解下述内容之后，再去更改交换机上的生成树的默认设置。
网络环路的侦测和预防（Network
loop
detection
and
prevention）：任何两个局域网之间应该只有一条路径，否则，网络中将出现环路。如果存在着多于一条的路径，那么生成树算法将会侦测到环路的发生，并自动选择开销值（c
ost）最低的那条路径作为可使用的路径（主链路），而阻断其它路径，将它们作为备用路径（备用链路）。
自动拓扑重构（Automatic
topology
re-configuration）：当主链路出现故障时，生成树算法将自动启用备用链路，重构网络结构。
生成树的级别（STA
Operation
Levels）
生成树有两种工作级别：桥级别（bridge
level）和端口级别（port
level）。在桥一级上，生成树算法为每台交换机计算桥的标志级数（Bridge
Identifier），然后设定根桥（Root
Bridge）和指定桥（Designated
Bridges）。而在端口一级上，生成树算法设定根端口（Root
Port）和指定端口（Designated
Ports）。详述如下：
在桥一级上（On
the
Bridge
Level）：
根桥（Root
Bridge）：具有最小桥标志级数的（lowest
Bridge
Identifier）交换机是根桥（Root
Bridge）。当然，你希望根桥是环路中所有交换机当中最好的一台（交换机），以保证能够提供最好的网络性能和可靠性。
桥标志级数（Bridge
Identifier）：桥标志级数是桥的优先级（Bridge
Priority）和交换机的MAC地址的综合数值，其中桥的优先级（Bridge
Priority）是一个你可以设定的参数。例如，“4
00
80
C8
00
01
00”中的“4”是桥的优先级，“00
80
C8
00
01
00”是交换机的MAC地址。交换机的桥标志级数越低，则交换机的优先级越高，这样可以增加其成为根桥的可能性。
指定桥（Designated
Bridge）：在每个网段中，到根桥（Root
Bridge）的路径开销最低的（lowest
Root
Path
Cost）桥将成为指定桥（Designated
Bridge），数据包将通过它转发到网段。一旦所有的交换机具有相同的根路径开销（Root
Path
Cost），那么具有最低的桥标志级数的（lowest
Bridge
Identifier）交换机才会被定为指定桥（De
signated
Bridge）。
根路径开销（Root
Path
Cost）：一台交换机的根路径开销（Root
Path
Cost）是根端口（Root
Port）的路径开销（Path
Cost）与数据包经过的所有交换机的根路径开销（Root
Path
Cost）之和。根桥（Root
Bridge）的根路径开销（Root
Path
Cost）是零。
桥的优先级（Bridge
Priority）：是一个用户可以设定的参数。设定的值越小，优先级越高。交换机具有越高的优先级，才越有可能成为根桥。
在端口一级上（On
the
Port
Level）：
根端口（Root
Port）：每台交换机都有一个根端口（Root
Port），这个端口到根桥的路径开销最低。一旦多个端口具有相同的到根桥的路径开销时，那么具有最低的端口标志级别的才会成为根端口。
指定端口（Designated
Port）：指定端口就是指定桥（Designated
Bridge）上的端口。
端口优先级（Port
Priority）：数值越小，端口的优先级就越高。具有越高端口优先级，才越有可能成为根端口。
路径开销（Path
Cost）：这是一个可变的参数，它将随着生成树中的设定值的变化而变化。依据STA的默认参数值，每个1000Mbps网段有一个指定的路径开销值为4
，100Mbps网段的路径开销值19，10Mbps网段的路径开销值100.
生成树参数（STA
Parameters）
生成树的参数用户可以根据自己的需要进行修改，但是建议最好使用出厂时的默认设置。除非确实需要对出厂设置值进行变动时，再去改动默认值。用户可以改动的生成树参数有如下几个：
桥优先级（Bridge
Priority）：数值范围从0到65535.“0”的优先级最高。
呼叫时间（Bridge
Hello
Time）：数值范围从1秒到10秒。是指根桥向其它所有交换机发出BPDU数据包的时间间隔，以告知其它所有交换机它是根桥。如果你的交换机还未是根桥时为其设置了呼叫时间，那么，一旦你的交换机成为根桥，该呼叫时间就会派上用处。
注意：呼叫时间不能大于桥的最大老化时间（Max.
Age），否则，将出现错误信息。
最大的桥老化时间（Bridge
Max.
Age）：数值范围从6秒到40秒。如果在超出最大老化时间之后，还没有收到根桥发出的BPDU数据包，那么，在允许的条件下你的交换机将充当根桥向其它所有的交换机发出B
PDU数据包。如果交换机确实具有最小的桥标志级数，那么，它将随之成为根桥。
桥转发时延（Bridge
Forward
Delay）：数值范围从4秒到30秒。是指交换机的端口从阻塞状态转为转发状态所用的监听时间。
当你欲变动生成树参数时，请一定记住下述公式：
最大的桥老化时间≤
2
x（桥转发时延
–
1秒）
即：Max.
Age
≤
2
x
（Forward
Delay
-
1
second）
最大的桥老化时间≥
2
x（呼叫时间
+
1秒）
即：Max.
Age
≥
2
x
（Hello
Time
+
1
second）
端口优先级（Port
Priority）：数值范围从0到255.数值越小，那么该端口越可能成为根端口。

㈥ 透明网桥的生成树算法

透明网桥还使用了一个生成树（spanning tree）算法，即互连在一起的网桥在进行彼此通信后，就能找出原来的网络拓扑的一个子集。在这个子集里，整个连通的网络中不存在回路，即在任何两个站之间只有一条路径。
为了得能够反映网络拓扑发生变化时的生成树，在生成树上的根网桥每隔一段时间还要对生成树的拓扑进行更新。

㈦ 生成树网桥的介绍

生成树网桥（Spanning Tree）网桥是一种完全透明的网桥，这种网桥插入电缆后就可以自动完成路由选在的功能，无需由用户装入路由表或设置参数，网桥的功能是自己学习获得的。以下从帧转发、地址学习、环路分解来讲述这种网桥的工作原理。

㈧ 交换机生成树协议的工作原理

交换机生成树协议基本原理
生成树协议的基本原理非常简单，自然界生长的树是不会出现环路的。如果网络也能够像一棵树一样的生长就不会出现环路。因此STP协议中定义了根桥(Root Bridge)、根端口(Root Port)、指定端口(Designated Port)、路径开销(Path Cost)等概念目的就在于通过构造一棵自然树的方法达到剪裁冗余环路的目的同时实现链路备份和路径最优化。为了实现这些功能交换机之间就必须进行一些信息交流这些信息交流单元成为配置消息BPDU(Bridge Protocol Data Unit)STP BPDU为二层报文数据区携带了用于生成树计算的所有有用信息所有支持STP协议的交换机都会接收并处理收到的BPDU报文。用于构造这棵树的算法称为生成树算法SPA(Spanning Tree Algorithm)STP的基本思想是生成“一棵树”树的根是称为根桥的交换机根据桥ID不同较优的交换机被选为根桥任意时刻只能有一个根桥。由根桥开始逐级形成一棵树根桥定时发送配置消息非根桥接收配置报文并转发如果某台交换机能够从两个以上的端口收到配置报文则说明从该交换机到根有不止一条路径便构成了循环回路从此交换机根据端口的配置选出一个端口并把其他的端口阻塞消除循环。当某个端口长时间不能接收到配置报文的时候交换机认为端口的配置超时网络拓扑可能已经改变此时重新计算网络拓扑重新生成一棵树。
生成树协议的主要功能有两个：
一是在利用生成树算法、在以太网络中，创建一个以某台交换机的某个端口为根的生成树，避免环路。
二是在以太网络拓扑发生变化时，通过生成树协议达到收敛保护的目的。

㈨ 生成树协议IEEE802.1D的工作原理

STP协议的基本思想十分简单。大家知道，自然界中生长的树是不会出现环路的，如果网络也能够像一棵树一样生长就不会出现环路。于是，STP协议中定义了根桥（Root Bridge）、根端口（Root Port）、指定端口（Designated Port）、路径开销（Path Cost）等概念，目的就在于通过构造一棵自然树的方法达到裁剪冗余环路的目的，同时实现链路备份和路径最优化。用于构造这棵树的算法称为生成树算法STA（Spanning Tree Algorithm）。要实现这些功能，网桥之间必须要进行一些信息的交流，这些信息交流单元就称为配置消息BPDU（Bridge Protocol Data Unit，网桥协议数据单元）。STP BPDU是一种二层报文，目的MAC是多播地址01-80-C2-00-00-00，所有支持STP协议的网桥都会接收并处理收到的BPDU报文。该报文的数据区里携带了用于生成树计算的所有有用信息。
了解生成树协议的工作过程也不难，首先进行根桥的选举。选举的依据是网桥优先级和网桥MAC地址组合成的桥ID（Bridge ID），桥ID最小的网桥将成为网络中的根桥。在图6-15所示的网络中，网桥都以默认配置启动，在网桥优先级都一样（默认优先级是32768）的情况下，MAC地址最小的网桥成为根桥（如图中的交换机1），它的所有端口的角色都成为指定端口（Designated port），进入转发状态。接下来，其他网桥将各自选择一条“最粗壮”的树枝作为到根桥的路径，相应端口的角色就成为根端口。假设图6-15中交换机2和交换机1、交换机3之间的链路都是千兆GE链路，交换机1和交换机3之间的链路是百兆FE链路，交换机3从端口1到根桥的路径开销的默认值是19，而从端口2经过交换机2到根桥的路径开销是4+4=8（千兆位链路的默认开销为4，百兆位链路的默认开销为19），因为后者的开销要远小于前者，所以端口2就成为根端口（Root Port），进入转发状态。根据同样的计算道理可以得出，交换机2的端口2成为根端口，端口1成为指定端口，进入转发状态。
根桥和根端口都确定之后一棵树就生成了，如图6-15中的网桥就是从交换机1→交换机2的2号端口→交换机3的2号端口。下面的任务是裁剪冗余的环路。这个工作是通过阻塞非根桥上相应端口来实现的，例如交换机3的端口1的角色成为禁用端口，进入阻塞状态（图中用“×”表示）。生成树经过一段时间（默认值是30秒左右）稳定之后，所有端口要么进入转发状态，要么进入阻塞状态。STP BPDU仍然会定时从各个网桥的指定端口发出，以维护链路的状态。如果网络拓扑发生变化，生成树就会重新计算，端口状态也会随之改变。
STP协议给透明网桥带来了新生。但是，随着应用的深入和网络技术的发展，它的缺点在应用中也被暴露出来。STP协议的缺陷主要表现在收敛速度上。当拓扑发生变化，新的配置消息要经过一定的时延才能传播到整个网络，这个时延称为Forward Delay（转发延时），协议默认值是15秒。在所有网桥收到这个变化的消息之前，若旧拓扑结构中处于转发的端口还没有发现自己应该在新的拓扑中停止转发，则可能存在临时环路。为了解决临时环路的问题，生成树使用了一种定时器策略，即在端口从阻塞状态到转发状态中间加上一个只学习MAC地址，但不参与转发的中间状态，两次状态切换的时间长度都是Forward Delay，这样就可以保证在拓扑变化的时候不会产生临时环路。但是，这个看似良好的解决方案实际上带来的却是至少两倍Forward Delay的收敛时间！