生成树网桥（Spanning Tree）

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

　　网桥为了能够解决是否转发一个帧，必须为每个转发端口保存一个转发数据库，该数据库中保存这必须通过转发端口的所有站的地址。当网桥收到一个帧时，就可以根据目标地址和这两个数据库的内容决定是否把它从一个端口转发到另一个端口。作为一般情况，我们可以假定网桥从端口X收到一个MAC帧，则它按以下算法进行路由决策。

　　（1）查找除X端口之外的其他数据库；

　　（2）如果没有发现目标地址，则丢弃该帧；

　　（3）如果在某个端口 Y 的转发数据库中发现目标地址，并且 Y 端口没有阻塞（阻塞的原因下面讲述），则把收到的MAC帧从 Y 端口发送出去，若 Y 端口阻塞，则丢弃该帧。

　　以上转发方案假定网桥已经装入了转发数据库。如果采用静态路由策略，转发信息可以预先装入网桥。然而还有一种更有效的自动学习机制，可以使网桥从无到有地自动决定每一个站的转发方向。获得转发信息的一种简单方案利用了MAC帧中的源地址字段。

　　如果一个MAC帧从某个端口到达网桥，显然它的源工作站处于网桥的入口LAN一边，从帧的源地址字段可以知道该站的地址，于是网桥就据此更新相应端口的转发数据库。

　　为了应付网格拓扑结构的改变，转发数据库的每一数据项（站地址）都配备一个定时器。当一个新的数据项加入数据库时，定时器复位；如果定时器超时，则数据项被删除，从而相应传播方向的信息失效。每当接收到一个MAC帧时，网桥就取出源地址字段并查看该地址是否在数据库中，如果已在数据库中，则对应的定时器复位，在方向改变时可能还要更新该数据项；如果地址不在数据库中，则生成一个新的数据项并置位其定时器。

　　以上讨论假定在数据库中直接存储站地址。如果采用两级地址结构（LAN编号，站编号），则数据库中只需存储LAN地址部分就可以了，这样可以节省网桥中的存储空间。

　　以上讨论的学习算法适用于互联网络为树形拓扑结构的情况，即网络中没有环路，任意两个站之间只有惟一通路，当互联网络中出现环路时这种方法就失效了。我们通过右图说明问题是怎样产生的。假设在时刻t0站A向站B发送了一个帧。每一个网桥都捕获了这个帧并且在各自的数据库中把站A地址记录在LAN X一边，随之把该帧发往LAN Y。在稍后某个时刻t1或t2（可能不相等）网桥a和b又收到了源地址为A、目标地址为B的MAC帧，但这一次是从LAN Y的方向传来的，这时两个网桥又要更新各自的转发数据库，把站A的地址记在LAN Y一边。

　　可见由环路引起的循环转发破坏了网桥的数据库，使得网桥无法获得正确的转发信息。克服这个问题的思路就是要设法消除环路，从而避免出现互相转发的情况。幸好，图论中有一种提取连通图生成树的简单算法，可以用于互联网络消除其中的环路。在互联网络中，每一个LAN对应于连通图的一个顶点，而每一个网桥则对应于连通图的一个边。删去连通图的一个边等价于移去一个网桥，凡是构成回路的网桥都可以逐个移去，最后得到的生成树不含回路，但又不改变图（即网络）的连通性。我们需要一种算法，使得各个网桥之间通过交换信息自动阻塞一些传输端口，从而破坏所有的环路并推导出互联网络的生成树。这种算法应该是动态的，即当网络拓扑结构改变时，网桥能觉察到这种变化，并随即导出新的生成树。我们假定：

　　每一个网桥有唯一的 MAC地址和唯一的优先级，地址和优先级构成网桥的标识符；

　　有一个特殊的地址用于标识所有网桥；

　　网桥的每一个端口有唯一的标识符，该标识符只在网桥内部有效。

　　另外我们要建立以下概念。

• 根桥：即作为生成树树根的网桥，例如可选择地址值最小的网桥作为根桥。

• 通路费用：为网桥的每一个端口指定一个通路费用，该费用表示通过哪个端口向与其连接的LAN传送一个帧的代价。两个站之间的通路可能要经过多个网桥，这些网桥的有关端口的费用相加就构成了两站之间的通路的费用。例如，假定沿路每个网桥端口的费用为1，则两个站之间通路的费用就是经过的网桥数。另外也可以把网桥端口的通路费用与有关LAN的通信速率联系起来（一般为反比关系）。

• 根通路：每一个网桥通向根桥的费用最小的通路。

• 根端口：每一个网桥与根通路相连接的端口。

• 指定桥：每一个LAN有一个指定桥，这是在该LAN上提供最小费用根通路的网桥。

• 指定端口：每一个LAN的指定桥连接该LAN的端口为指定端口。对于直接连接根桥的LAN，根桥就是指定桥。该LAN连接根桥的端口即为指定端口。

　　根据以上建立的概念，生成树算法可采用下面的步骤：

　　（1）确定一个根桥；

　　（2）确定其他网桥的根端口；

　　（3）对每一个LAN确定一个唯一的指定桥和指定端口，如果有两个以上网桥的根通路费用相同，则选择优先级最高的网桥作为指定桥；如果指定桥有多个端口连接LAN，则选取标识符值最小的端口为指定端口。

　　按照以上算法，直接连接两个LAN的网桥中只能有一个作为指定桥，其他都删除掉。这就排除了两个LAN之间的任何环路。同理，以上算法也排除了多个LAN之间的环路，但保持了连通性。

　　为了实现以上算法，网桥之间要交换信息。这种信息以网桥协议数据单元BPDU的形式在所有网桥之间传播。网桥发出的BPDU包含：

• 该网桥的地址标识符和端口标识符；

• 该网桥认为可作为根桥的地址标识符；

• 该网桥的根通路费用。

　　开始时每个网桥都声明自己是根桥并把以上信息广播给所有与它相连的LAN上的所有网桥。在每一个LAN上只有一个地址值最小的标识符，仅该网桥可坚持自己的声明，其他网桥则放弃声明，并根据收到的信息确定其根端口，重新计算根通路费用。当这种BPDU在整个互联网络中传播时所有网桥可最终确定一个根桥，其他网桥据此计算自己的根端口和根通路。在同一个LAN上连接的各个网桥还需要根据各自的根通路费用确定惟一的指定桥和指定端口。显然这个过程要求在网桥之间多次交换信息，自认为是根桥的那个网桥不断广播自己的声明。例如在上图的互联网络中通过交换信息导出生成树的过程可简述如下：

　　（1）与LAN2相连的3个网桥1、3和4选出网桥1为根桥，网桥3把它与LAN2相连的端口确定为根端口（根通路费用为10）。类似地，网桥4把它与LAN2相连的端口确定为根端口（根通路费用为5）。

　　（2）与LAN1相连的3个网桥1、2和5也选出网桥1为根桥，网桥2和5相应地确定其根通路费用和根端口。

　　（3）与LAN5相连的3个网桥通过比较各自的根通路费用的优先级选出网桥4为指定网 桥，其根端口为指定端口。

　　其他计算过程从略。最后导出的生成树如右图所示。只有指定桥的指定端口可转发信息，其他网桥的端口都必须阻塞起来。在生成树建立起来以后，网桥之间还必须周期性地交换BPDU，以适应网络拓扑、通路费用以及优先级改变的情况。