生成树协议（Spanning Tree Protocol，STP）

真正的桥接式网络，它的拓扑通常很像一棵树，主机只（或主要）位于叶子节点上。
使用多台网桥的优点：
1、有助于分离流量。L2网络的整体带宽增加，最坏的情况下，一个以太网帧可能必须穿越整颗树才能抵达其目的地。
2、很容易管理大量的主机。主机可以散落在不同的区域，布线也比较简单。

一、生成树协议的基本元素

寻找最佳无根生成树（best nonrooted spanning tree）或最佳有根生成树（best rooted spanning tree）的搜寻问题是运筹学的经典问题。
有了一个图形以及你想作为根的节点之后，所谓的最佳生成树就是一个无环路拓扑（树），每个节点到根节点的距离为最小。对于某些图形，可能有一颗以上的树可以作为最佳生成树。
当链路没有指定开销，或者都设置成相同的开销（称为对等）时，则一个节点到根的距离用链路数目（也就是网络跃点）来测量。但是，当你把开销指派给链路后，跃点数目就不一定是路径长短的指标了。

STP通过让各个网桥之间交换称为网桥协议数据单元（bridge protocol data unit,BPDU）的特殊帧来达到其目标。用BPDU交换的信息可以让网桥：
a)、为每个网桥端口指定一个明确的状态，例如转发或阻塞，以定义该端口可否接收数据流量。
b)、通过对端口状态的设定，从环路拓扑中选择或丢弃适当的链路，以这种方式最终生成无环路拓扑。

根网桥在整个算法中扮演关键角色。根网桥是唯一能产生BPDU的网桥。其他网桥只有在其接收到BPDU时才会传输BPDU（对接收到的信息，更新其中一些字段）。当拓扑发生改变时，根网桥确保网络中的每台网桥都知道此事。
虽然每棵树只能有一个根网桥，但是，每个LAN都可以有一个指定网桥，它成为该LAN中所有主机和网桥到达根节点的网桥。指定网桥的选择是根据LAN上哪台网桥通往根网桥的路径开销最低而定。

分类	指定桥	指定端口
对一台设备而言	与本机直接相连且负责向本机转发配置消息的设备	指定桥向本机转发配置消息的端口
对一个局域网而言	负责向本网段转发配置消息的设备	指定桥向本网段转发配置消息的端口

二、生成树端口

端口状态
关闭（Disabled），该端口已关闭（通过管理性操作），它不再接收或传输任何流量。
阻塞（Blocking），该端口已开启，但是STP将其阻塞了。该端口不能转发任何数据流量。
监听（Listening），该端口已开启，但是不能用于转发任何数据流量。
学习（Learning），该端口已开启，但是不能用于转发任何数据流量；然而，该网桥的地址学习进程是激活的。
转发（Forwarding），该端口已开启，地址学习是激活的，且可以转发数据流量。

学习态可以让网桥减少地址的扩散次数，当转发数据库为空时就需要扩散。
除了处于关闭状态的口外，无论其他端口状态为何，都会处理入口BPDU。


注意：
1、一个端口往转发状态转换时，可以在进入转发状态前退回到阻塞状态。例如，当拓扑尚未稳定而其状态会在短时间内不断改变时，就有可能发生这种情况。
2、从阻塞状态到转发状态过渡的中间状态是由定时器驱动的，此种策略是为了避免临时环路。
另外，管理员可以手动地把端口从任何状态中移出并将其关闭。当一个端口经由管理手段关闭时，则只有再度以管理手段干预才能重新启用；STP没有超越人工管理手段的能力。然而，网桥可以在协议定义的基本功能之外实现一些可选功能，以开启和关闭端口，而无需管理手段干预。

端口角色
根，对每台网桥来说（根网桥除外），通往根网桥的路径开销最低的端口就会被选为根端口。
指定，在每个LAN上，通往根网桥的路径开销最小的端口就会被选为指定端口。指定端口所属的网桥就称为该LAN的指定网桥。需要注意的是，一台网桥上的端口连接不同的LAN时，可以有一个以上的指定端口。
根端口可通往生成树根，而指定端口可通往叶子。
有些STP端口既不是根端口也不是指定端口；当在网桥间有冗余链路时，就有可能发生这种情况。

网桥ID(Bridge ID):  每个网桥都会分配一个ID，称为网桥ID，此ID是一个8字节的数，分成两部分。低6位是某个桥接端口的Ethernet MAC地址，而最高的两个字节是一个可配置的优先级，称为网桥优先级（bridge priority）。2 + 6，即16个二进制位+ 48个二进制位。
端口ID(Port ID):  每个端口都会被指定一个ID。这个ID的一部分（低位）代表一个唯一的识别码。另一部分称为端口优先级（port priority），其值较低表示有较高优先级。1+1，即8个二进制位+8个二进制位。

802.1t规范之前是上面的ID定义方式，之后是下面的定义方式：
 网桥优先级现在只用4位二进制表示。为了和旧版本兼容，网桥优先级范围依然是0--64K，但是因为只有4位可以设置，所以优先级的增量就变成了4096。
网桥ID中多了一个新元素，系统ID扩展（system ID extension）。此元素可以设4096个不同的值，可以让4096个不同的网桥ID共享同单一MAC地址。之前，则需要有4096个不同的MAC地址。
端口号现在是一个12位二进制数，可以让网桥有多达4096个端口。端口优先级现在是4位二进制数，为了和旧版本兼容，优先级范围依然是1--256，因此，优先级现在的增量是16。

4096代表802.1q协议中所允许的VLAN的最大数目。

三、网桥协议数据单元（BPDU）

BPDU有两种：
1、配置BPDU，用于定义无环路拓扑。
2、TCN(Topology Change Notification，拓扑变化通知)BPDU，当检测到拓扑变化时，网桥用于通知根网桥。



BPDU版本

协议名称	协议ID	协议版本号
STP(802.1D-1998)	0	0
RSTP(802.1D-2002或802.1w)	0	2
MSTP(802.1Q-2002或802.1s)	0	3

标识，只使用两个标识，TC（Topology Change，拓扑变化）和TCA（Topology Change Acknowledgment，拓扑变化确认）。
配置BPDU的四个元素--根网桥ID、根路径开销、网桥ID及端口ID--构成了优先级向量（Priority Vector）。因为这四个元素是按照顺序排列的，所以这个向量可以视为一个独立的22字节的数字。此数越小网桥在拓扑中的重要性越高；换句话说，优先级向量决定谁赢得根网桥和指定网桥这类竞争性角色的牌权。

配置BPDU的传输

在下列情况，一台网桥会从其指定端口传输出配置BPDU：
1、根网桥会运行一个定时器（Hello 定时器），该定时器到期后就触发配置BPDU的传输。同一个BPDU从根网桥的每一个指定端口传输出去。只有根网桥能产生新的BPDU，但当一个网桥加电启动时，它会以为自己就是根网桥。所以，该网桥会将其所有端口都设为指定角色，启动Hello定时器，然后开始产生BPDU。
2、非根网桥只有在应答其根端口收到的BPDU时才产生BPDU；也就是说，非根网桥会传递BPDU。但是传递过程会更新以下字段：
    a)、传输者的网桥ID和端口ID会被该网桥自己的信息替换。
    b)、该网桥会把开销更新为其所接收的开销加上其本地网桥中接收BPDU的端口（根端口）的开销之和。
    c)、消息生存期会根据某个逻辑更新，之后描述。

无论网桥是否为根网桥，在下列情况也会传输一个配置BPDU：
1、当一台网桥接收到一个BPDU，如果其优先级向量低于该网桥在其端口上所用的，那么，网桥就会以其自己的信息应答。
2、当一台网桥接收到一个TCN BPDU时，会立即发出一个设有特殊标识的配置BPDU作为应答。有利于快速传播拓扑中的变化。

BPDU的老化
因为BPDU只由网桥生成，而且其他网桥只有在其根端口接收到一个BPDU时才会重新产生一个，所以，根网桥从其生成BPDU所用的信息到BPDU抵达叶子网桥的时间是实时变化的。在一个稳定的网络中，这个时间主要取决于网桥的负载情况及网桥处理BPDU有多快。

携带过期信息的BPDU不应该用来建立无环路拓扑。因此接收到该BPDU的网桥会拿消息生存期字段该BPDU中的最大生存期字段比较。
消息生存期字段最初由根网桥初始化为0，而每个非根网桥在对其转发前都会更新该字段。一般做法是把消息生存期视作跃点计数，类似IP报头中的TTL（Time To Live，存留时间）。当网桥在其端口上所接收到的BPDU尚未过期时，网桥会启动Message Age定时器，该定时器会在由最大生存期和消息生存期的时间差确定的一段时间后到期。

四、定义活跃拓扑

每台网桥按照本地配置信息和接收到的入口配置BPDU中的信息，可完成以下工作（配置更新）：
1、选出根网桥。
2、从其几个端口中选出一个作为根端口。
3、对每个端口，为该端口所属的LAN分配指定网桥和指定端口。
每当网络有变动而使得拓扑需变化时，就需执行这些更新，例如：
1、开启或关闭一个端口。
2、如果一个端口的Message Age定时器到期了。此端口会重新启动，重新分配指定角色。
3、一台网桥的本地配置信息发生变化。
4、一个网桥端口接收的一个配置BPDU，其优先级向量比该端口先前所接收到的BPDU的优先级向量高级。

注意，触发配置更新的是配置有变化的武器或者处于管理目的改变了某个端口状态的网桥。其他网桥接下来看见这些改变，通过它所接收的BPDU中携带的信息可以反映出来。

选择根网桥
MAC地址是全球唯一的，所以根据所用的MAC地址来选择根网桥的算法可足够保证选择的确定性。然而，优先级元素的使用可让管理员把较高的优先级指派给他们想选为根网桥的网桥。管理员甚至可以给不同的网桥指派策略性优先级，使得在当前根网桥失效时，特定网桥可以接手。

网桥首次启动时，认为自己就是根网桥。该网桥把指定角色分配给它的所有端口，并在这些端口上启用Forward Delay定时器，因此它们最终都会设置转发状态，然后以自己的网桥ID作为BPDU中根网桥ID字段并且根路径开销为0，从而开始传输BPDU。这种方式可以很方便地将该BPDU变成广播数据，尽可能快速地向四处散布，使得自己和其他网桥都可以发现真正最佳的根网桥，从而让这棵树能重新平衡。
当该网桥ID就是最佳网桥ID时，它就会不断地在其指定端口上发送BPDU，因为其他网桥都无法声明自己有更高级别的优先级向量。如果该网桥ID不是最佳网桥ID，最后它就会收到一个配置BPDU，里面包含一个比较高级的根网桥ID，然后：
1、接收并记录这些级别较高的信息（包括根网桥ID和定时器）。
2、相应得更新其端口的状态和角色。

选择根端口
根端口就是具有通往根网桥最短路径（或最低开销）的端口。根网桥是唯一没有根端口的网桥；非根网桥则有唯一一个根端口。
对每个端口（管理手段关闭的除外）来说，网桥都会保留一份接收自入口BPDU的最佳优先级向量的复本。这样一来，网桥就知道每个端口到达根网桥的最佳路径（或最低开销）是多少。
根端口的选择就是遍历所有端口，选出拥有最佳优先级向量的那个端口。若最佳优先级向量端口有多个，则选择有最低端口ID的本地端口作为根端口。

选择指定端口
指定端口应该是具有通往根网桥最低路径开销的那个端口，也就是拥有最佳优先级向量的端口。每台网桥通常都连接一个以上的LAN，所以，它必须知道每个LAN的指定端口。

五、定时器

STP为每个网桥和每个端口都设有定时器。
注意，并不是所有的定时器都可由用户配置。有些定时器使用系统的配置（例如，TCN和Hello定时器），因此，若更新一个定时器的配置，也会影响其他定时器。

网桥定时器

定时器	默认值（s）	取值范围	作用
Hello	2	1~10	用于定期产生配置BPD。
Topology Change	转发延迟+最大生存期	未定义	由检测到拓扑变化而其必须通知根网桥的网桥使用。
TCN	Hello时间	未定义	根网桥使用，以便记住要在其配置BPDU中设定一个特殊标识，此标识用于将拓扑变化通知其他网桥。
Address Aging	300 或 转发延迟	未定义	用于从转发数据库中清理无效的地址。网桥使用，而无论其是否开启STP。

每个网桥都会保存其定时器配置的两个副本：一个来自管理员的本地配置信息，一个是接收自根网桥的配置信息。根网桥是唯一使用其自身定时器配置的网桥；根网桥让其他所有网桥都采用它的配置。非根网桥使用它们在其根端口所接收到的BPDU中携带的定时器配置。

端口定时器

定时器	默认值（s）	取值范围	作用
Message Age	20	6~40	BPDU所携带的信息的生存期是有限的。Message Age定时器用于强制执行这个生存期。每当端口收到一个BPDU之后，该定时器就重新启动。只要接收到一个BPDU，就会对它的消息生存期和网络允许的最大生存期作比较，前者大于后者，帧丢弃。此定时器在非指定端口（接收到较高级BPDU的端口）上运行。 在没有任何问题的稳定网络上，该定时器绝不会过期。定时器过期时，该端口就会重新启动，重新分配角色。
Forward Delay	15	4~30	该定时器负责状态转移：从监听到学习以及从学习到转发。
Hold	1	未定义	配置BPDU的传输是有速率限制的：每个端口每秒一个。在稳定网络中，每个指定端口每隔Hello时间就会发出一个BPDU。然而，在一个大而复杂的网络中，当拓扑发生变化时，由于STP算法的分布式特性，使得拓扑收敛至新拓扑的时间可能要花上几分钟。

六、消除临时环路

根端口和指定端口是唯一处于转发状态的端口。当一个端口被分配为根角色或者指定角色时，不会立刻设为转发状态：首先必须经过两个中间状态。这些中间状态会在网络收敛为一个稳定的无环路拓扑时，减少形成临时性环路的风险。
当一台网桥刚启动时：
1、自认为自己是根网桥。
2、两台网桥的端口都设为指定角色和阻塞状态。
3、每个端口的状态会变成监听状态，接着启动Forward Delay定时器，发出一个配置BPDU。

注意，这些端口都还没有处于转发状态，还不能接收和转发数据流量，只可以传输和接收BPDU。

七、拓扑变化

  非转发态的网桥端口变成转发态（或者反之）
这种情况包括关闭的端口被启动，和因为协议的裁决仅改变了端口状态。从数的角度看，相当于给树增加一条链路或从树上删除一条链路。
 根网桥ID变化
这种情况的发生可能是因为当前根网桥已被关闭，或者有更高优先级的网桥被开启了，还有可能是因为当前根网桥或另一台网桥更新了优先级。
 网桥端口上接收到TCN拓扑变化通知
这种情况下，拓扑的变化已由另一台网桥探测到了。

注意，对无环路拓扑而言，仅仅通过增加一条链路（即有个新端口进入转发状态）就可以建立一个环路，而删除一条链路（等于将一个转发状态的端口切换到阻塞状态）并不会建立环路。

Short Aging 定时器
转发数据库中的地址若不再被使用，过一段时间才被删除。数据库中的过期数据的清理就是通过缩短这段时间来实现的。其具体做法就是当网桥接收到拓扑变化通知后，就把Aging定时器缩短（默认值是5min）为转发延迟的时间（默认为15s）。通过在配置BPDU中设定一个特殊标识来通知其他网桥拓扑发生变化。

让所有网桥知道拓扑变化
当网桥探测到有拓扑变化，必须通知所有网桥，以使其可以用缩短的aging时间来清理它们转发数据库内的过期数据项。其过程为：
1、探测到拓扑变化的网桥通知根网桥此变化。
    利用TCN BPDU实现。探测到拓扑变化的网桥会从根端口发出一个TCN BPDU至其指定网桥。该网桥每隔Hello时间就会发出一个TCN BPDU，知道指定网桥确认，其确认方式为，在发出的下一个配置BPDU中设定TCA标识。此时，指定网桥重复相同过程。当TCN最终到达根网桥时，这个过程就结束。若拓扑变化是由根网桥自己探测到的，就不需要TCN BPDU。
2、根网桥通知所有网桥拓扑发生变化。
    根网桥发出配置BPDU，并在该配置BPDU中设定一个特殊标识（TC）。其他非根网桥重新产生的BPDU中都会附带该标识，使得网桥上所有网络最后都会接收到拓扑变化的通知。当一个网桥看到该标识被设置时，就会启动Short Aging定时器。注意，网桥可在不同的端口上接收设有TC标识的配置BPDU。

八、BPDU封装

位于01:80:C2:00:00:00~01:80:C2:00:00:FF之间的L2多播地址由IEEE保留给标准协议使用。特别地，该范围内的第一个地址01:80:C2:00:00:00是由802.1D STP所用：配置BPDU和TCN BPDU都会发往这个地址。该地址就是让网桥识别出BPDU帧。
IEEE标准指出，在01:80:C2:00:00:00~01:80:C2:00:00:0F范围内的地址不应该由运行802.1D协议的网桥转发：既可以由目的地址协议做本地处理，也可以丢掉。

九、收敛时间

配置更新发生在复杂环境下时，网络可能需要好几分钟才能重新收敛并稳定。在那段时间内，拓扑依然是无环路的，但是无法传输正常网络流量。
然而，不论网桥配置得多好，仍然有无法消除或减少的最小时延。例如：
1、当一个端口改变状态以替换一个失效的网桥端口时（例如，从阻塞态变为转发态），并不是立刻切换到转发状态，而是花了两次Forward Delay定时器时间（默认是30s）。
2、根端口和非指定端口（即接收BPDU的端口）只有在其消息生存期定时器超时后，才会发现它们和相应的指定网桥失去连接。
这两个事件都是由定时器驱动的。

十、新版生成树协议概况

RSTP的一些改进
1、每个网桥端口现在都会分派一个角色。那些既不是指定角色又不是根角色的端口，会分派替代（alternate）角色或备用（backup）角色。替代是由于表示通往根网桥的替代路径的端口（是当前根路径的潜在替换路径），而备用则表示通往字树的替代路径的端口（指定端口的潜在替换端口）。
2、可能分派给端口的状态经过简化：新的丢弃状态包括老旧、关闭、阻塞以及监听状态。
3、RSTP把端口切换到转发状态的速度快很多，通过端口间的握手和称为sync的机制，sync机制能确保够避开环路。但是这种改进只对点对点链接有效。
4、根端口被替换，它可以立即进入转发状态，不必等待定时器。因为该协议有一个机制可确保定时转移到转发状态时不会造成任何环路。
5、前两项改进意味着收敛时间大幅加快，也许在一秒内。
6、所有网桥都运行Hello定时器，且独立产生配置BPDU。这样可以更快探测连通性问题。
7、探测连通性问题不再依靠Max Age定时器。当一个应该接收BPDU的端口连续三个Hello时间内都没有接收到BPDU时，就会启动恢复机制。旧的Max Age定时器依然在运行，但只有当先前涉及的新的RSTP进程不可用时，才会用到该定时器。
8、拓扑变化的处理也有所不同，不再需要TCN BPDU了。现在当网桥检测到拓扑变化时，只需从其根端口和指定端口发出有设置TC标识的BPDU就行。其他接收到这个BPDU的网桥会重复这个过程：把设有TC标识的BPDU从其每个转发端口传送出去（接收原有BPDU的端口除外）。这个简单的机制可以向四面八方广播拓扑变化。当一台网桥接收到设有TC标识的BPDU时，不会启动Short Aging定时器，相反，会清除其所有端口上所学习到的MAC地址。
9、结构只有一点变化。标识字段使用全部的8位以适应新的需求。

MSTP
MSTP引入主要的改进是可以定义多颗独立的生成树。每颗生成树都有其可传送数据流量的子集。
根据每个数据封包来自的VLAN的不同，为该封包选择所以的生成树。此种方式可以让网络带宽得到更好的利用。可以降低每条链路的负载。
MSTP让它的每个生成树实体都使用RSTP。