快速生成树协议在多CPU环境下的分布式实现方法

摘要

本发明公开了一种快速生成树协议在多CPU环境下的分布式实现方法，包括：各设备只保存本地端口的数据和状态机信息；每台设备维护一个虚拟端口，所述虚拟端口所保存的信息为分布式系统内当前的根端口信息；RSTP(快速生成树协议)根据本地端口信息和虚拟端口所保存的信息，选择系统内唯一的外部根端口；各设备之间通过信息同步方式来保证分布式RSTP的快速收敛特性。如果分布式系统内某台设备收到的信息比该设备上虚拟端口所保存的信息优，则该设备会重新选择更优的该端口作为外部根端口，并且将该根端口信息发布给系统内其它所有设备，以通知其它设备重新选举根端口；反之，该设备会将这些端口选择为可选端口或者指定端口。

说明书

技术领域

本发明涉及分布式系统的快速生成树协议，特别是一种快速生成树协议在多CPU环境下的分布式实现方法。

背景技术

随着网络技术的发展，以太网交换网络的应用越来越普遍。以太网交换网络是指由多台以太网交换设备通过网线相互连接组成。以太网交换设备只对数据报文做转发处理，不对报文做任何修改和标识。

在交换网络中，网络的物理连接各种各样，因此，很多情况下，在交换网络中会存在环路。由于以太网设备对报文的处理是透明的，即不作任何修改和标识，因此当存在环路时，交换设备无法区分待转发的报文是否已经被转发过，报文会在该环路中重复转发，导致报文在环路中不断增生，最终造成整个网络由于报文拥塞而瘫痪。图1示出了这样的环路情况下的报文增生情况。

生成树算法(STP)就是为了解决上述问题出现的。生成树算法的的基本原理是通过在各交换设备之间传递桥管理数据单元(BPDU)来确定网络的拓扑结构，并阻塞冗余的物理链路。如图1所示，在这种组网环境下，通过交换BPDU，交换设备会发现自己与其它设备之间存在环路，此时其中一台设备会阻断冗余的端口，使该端口只能接收和发送BPDU报文，而无法接收和发送普通的数据报文，这样就可以解决环路时报文增生的问题，如图2所示。

为了防止出现临时回路，当网络的物理结构发生变化，需要将阻塞的链路迁移到转发状态时，需要等待30秒时间，这个时间值为经验值，一般来说，在这段时间内能够保证网络中其他交换设备已经发现该物理结构的变化，从而提前切断可能存在的冗余链路，这样当阻塞的链路切换为转发时，网络中不会出现临时回路而导致报文增生使整个网络瘫痪。

生成树协议的这个缺点是很明显的，即端口迁移到转发状态需要30秒时间延迟，这在很多应用场合下都是不允许的。针对这个缺点，出现了快速生成树协议(RSTP)。快速生成树协议无需等待30秒时间延迟，而只需要通过一次握手就可以将链路迁移到转发状态。快速生成树协议的工作原理如下：

1、对于直接与PC或者其它非交换设备相连的端口(可称之为边缘端口Edge Port)，这些端口可以直接迁移到转发状态而无需等待30秒。这样就可以保证用户在开机后可以立即连通到网络中。

2、网络中所有设备只允许有一条路径连往根桥(即生成树的树根)，也就是说，每台设备只能有一个端口连往根桥(我们称该端口为根端口Root Port)，而其它连往根桥的端口将被作为冗余端口存在，该端口被阻塞(我们称该端口为可选端口Alternate Port)。同一时刻，每台非根桥设备有且仅有一个端口为转发状态。因此，当快速生成树协议确定原来的根端口变为阻塞状态时，其可以从Alternate Port中选择一个端口作为新的根端口，并且立即将其迁移到转发状态。

3、在交换网络中负责向下游转发报文的端口，我们称之为指定端口(Designated Port)，指定端口从阻塞状态迁移到转发状态时，需要先向下游设备发送一个请求BPDU，下游设备收到该请求BPDU时，如果接收到该BPDU的链路只连接上下游两台设备(我们称之为点对点链路Point to Point)，则下游设备会先向其他所有端口发送一个同步信号，收到该信号的端口将根据情况阻塞自己，然后设置自己同步完毕。当下游设备收到所有除接收到请求BPDU的端口外的其他所有端口的“同步完毕”信号后，该设备将通过接收端口向上游发送一个应答BPDU，指定端口收到该应答BPDU后，会立即迁移到转发状态。通过上述处理，快速生成树协议基本上可以避免30秒的等待时间，而快速地将端口迁移到转发状态，从而提高整个网络的网络收敛速度。

另一方面，随着网络技术的发展，越来越多的用户需要通过以太网设备接入到网络中，从而也就出现了256或超过256端口数的高端口密度的以太网交换设备(或称之为接入设备)。这种设备一般采用框式结构，即一块主控板外加多块接口板的结构，接口板作为一个插框插接在机架上。这种结构如图3所示，是一种典型的多CPU分布式结构，即主控板和每块接口板都有一个CPU来负责相关计算和控制功能。在图3中，SRPA(Switching & Routing ProcessingUnit)是交换路由板；LPU(Line Processing Unit)是业务板；PWR(Power)是电源模块；FAN是风扇框。

对于盒式设备，如图4所示，将多台相同的设备通过特殊的电缆连接共同组成一个堆叠系统，以提供高达几百端口数的高端口密度的接入设备。堆叠系统可以通过命令行以及标准网管进行管理，对用户和其他网络设备而言仅相当于一台设备。堆叠系统是另外一种常见的多CPU分布式系统。每台盒式设备都有至少一个CPU，各CPU根据设计不同在堆叠系统中起不同作用。

这种多CPU分布式系统下，生成树协议和快速生成树协议必须将其作为一台设备进行处理，其与普通的多台设备通过网线互连的交换网络不同点在于：

1、内部连接的链路(包括框式设备中各接口板与主控板之间的连接链路以及堆叠系统中各堆叠成员之间的堆叠电缆连接)必须始终保持为转发状态，这些链路的状态不能受到外部网络结构变化的影响；

2、框式设备和堆叠系统只能有一个连往根桥的端口，即只能有一个外部的根端口；

3、协议所需要管理的端口数比一般情况下要多，需要更高性能的CPU来计算。

对于这种多CPU分布式系统，尤其是框式设备，一般采用主从方式来实现快速生成树协议。主控板或者堆叠系统中的主设备主要负责实现对BPDU报文的处理和算法的实现，主设备将计算的端口STP状态通过远程控制指令下发到各接口板。接口板或从设备一般只负责接收从本地端口收到的BPDU，然后将该BPDU传送给主设备进行处理，此外接口板和堆叠系统从设备负责解析来自主设备的控制指令，根据指令完成对本地端口STP状态的设置。

在这种主从方案中，所有生成树算法的实现由主设备来完成，从设备不负责实现生成树算法。下面将根据图5说明主从方式的实现过程：

1、主设备上保存所有端口的协议状态机状态和端口状态参数；

2、从设备收到BPDU后，将BPDU传送给主设备，并且将接收端口号一并传送给主设备；

3、主设备根据收到的BPDU和对应的端口号，计算系统内所有端口的生成树角色并确定端口的STP状态。端口角色的选择和端口状态的确定请参见IEEE Std 802.1w-2001.Amendment 2：Rapid Reconfiguration。

4、主设备将端口的STP状态通过控制指令下发给从设备；主设备还将需要通过从设备上某个端口发送的BPDU传送给对应从设备；

5、从设备收到主设备下发的控制指令后，根据该指令设置端口STP状态；

6、从设备根据来自主设备BPDU和发送端口号将该BPDU报文从对应的端口发送出去。

该技术的缺点是：

1、主设备需要负责系统内所有端口的生成树计算，主设备的CPU需要高性能的CPU。从设备只需要完成简单功能的处理。这样对于堆叠系统，所有设备都需要高性能CPU，增加设备成本，并且从设备CPU资源浪费严重；

2、主设备计算出端口STP状态时，需要通过控制指令下发到各从设备。由于端口迁移到转发状态需要严格的时序控制，即端口进入转发状态之前需要阻塞所有潜在的回路。因此这种控制指令的下发和各从设备的分步执行很难保证这种时序要求，导致增加临时回路的可能性；

3、增加了BPDU报文转发的环节，导致BPDU丢失概率增加，严重时会导致由于BPDU丢失而引起网络拓扑结构动荡；

4、降低网络收敛的速度，对大量端口的管理，CPU需要花费更多的时间进行角色和状态计算，因此降低了端口状态的迁移快速性；

5、主设备需要保存所有端口的数据信息和状态机信息，需要更多的存储器来保存这些数据，增加了设备的制造成本；

6、主设备失效时，需要重新选择一个主设备来负责控制系统内所有端口，新主设备的切换过程会引起整个网络的拓扑结构动荡。

快速生成树协议在多CPU分布式系统(尤其是堆叠系统)中的另外一种实现方式是“集中对等式”实现方式。所谓“集中对等式”实现方式是指系统中所有CPU都参与生成树算法的计算，各CPU在计算端口角色和状态时，需要计算系统内的所有端口，每台设备收到BPDU报文后，都需要将该报文广播给系统内的所有其它设备；计算完毕后，各CPU只负责控制本地端口的STP状态。系统内的每个CPU都相当于技术一中的主设备，不同的是，技术一中的主设备负责控制系统内所有端口状态，而技术二中的各CPU虽然计算系统内所有端口的STP状态，但最后实际只控制本地的端口。

这种集中对等式实现方式需要将BPDU报文在系统内广播到所有设备，下面将结合图6说明这种技术的实现过程，其中在图6中，1-端口接收BPDU；2-接收设备将该BPDU传送给其他所有设备；3-端口发送BPDU：

1、所有设备上都需要保存系统内所有端口的数据信息和状态机信息；

2、设备从本地端口收到BPDU报文后，先送交本地CPU处理，然后再将该BPDU报文广播到其它所有设备并携带该BPDU的入端口号；

3、每台设备根据收到的BPDU和对应的端口号，计算系统内所有端口的生成树角色并确定端口的STP状态。端口角色的选择和端口状态的确定请参见IEEE Std 802.1w-2001.Amendment 2：Rapid Reconfiguration。

4、确定端口的STP状态后，如果该端口在本地，则直接设置该端口的STP状态，否则只计算状态，不进行实际控制；

5、每台设备根据当前的计算结果确定从本地端口发送的BPDU报文，并且将报文从本地端口发送出去。

这种技术的缺点是：

1、每台设备都需要负责系统内所有端口的生成树计算，设备需要高性能的CPU。会增加设备制造成本；

2、增加了BPDU报文转发的环节，导致BPDU丢失概率增加，严重时会导致由于BPDU丢失而引起网络拓扑结构动荡，而且可能会导致BPDU的丢失而引起各设备的计算结果不一致，导致整个系统的生成树状态计算错误；

3、降低网络收敛的速度，对大量端口的管理，CPU需要花费更多的时间进行角色和状态计算，因此降低了端口状态的迁移快速性；

4、每台设备都需要保存所有端口的数据信息和状态机信息，需要更多的存储器来保存这些数据，增加了设备的制造成本；

5、所有端口收到的BPDU都需要在系统内广播，会占用大量的带宽资源，造成设备间通讯带宽的浪费，从而造成系统性能下降。

发明内容

本发明的目的是提供一种快速生成树协议在多CPU环境下的分布式实现方法。

根据发明的一个方面，本发明提供了一种快速生成树协议在多CPU环境下的分布式实现方法，包括：

各设备只保存本地端口的数据和状态机信息；

每台设备维护一个虚拟端口，所述虚拟端口所保存的信息为分布式系统内当前的根端口信息；

RSTP(快速生成树协议)根据本地端口信息和虚拟端口所保存的信息，选择系统内唯一的外部根端口。

其中，RSTP通过比较所收到的BPDU(桥协议数据单元)中含有的端口优先级与虚拟端口保存的端口优先级来选择系统内唯一的外部根端口。

其中，当一个设备的虚拟端口保存的端口优先级低于所收到的BPDU中含有的端口优先级时，RSTP选择唯一的外部根端口位于该设备，然后将收到的BPDU以及该端口号作为同步消息发送给其他所有设备，以阻塞其它所有设备的根端口。

其中，当一个设备的虚拟端口保存的端口优先级高于所收到的BPDU中含有的端口优先级时，将该设备的本地根端口选择为可选端口或指定端口。

其中，当被阻塞根端口需要快速迁移到转发状态时，该被塞根端口向系统内所有端口下发“根端口重新选择”信号，该信号通过同步消息逻辑通道广播到系统内的其他所有端口；收到“根端口重新选择”信号的设备检查本地端口是否已经与被阻塞根端口同步，如果同步，则阻塞本地端口，然后设备将向被阻塞根端口所在设备发送“本设备已经同步根端口重新选择”标志；当被阻塞根端口所在设备收到系统内其他所有设备发来的“本设备已经同步根端口重新选择”标志，并且本地其他端口也全部同步完毕时，被阻塞根端口直接迁移到转发状态。

其中，当上游指定端口需要迁移到转发状态时，指定端口向下游发送同步请求消息，此时下游根端口向本地所有端口和系统内其他设备发送同步信号，同步信号通过同步消息逻辑通道广播给其他所有设备；收到该同步信号的设备在本地执行同步动作，根据需要阻塞潜在冗余端口，在同步完毕后，向根端口所在设备发送同步完毕消息；当根端口所在设备收到系统内其他所有设备的同步完毕消息，并且本地其他端口也已经全部同步完毕时，根端口向上游指定端口发送同步应答消息；上游指定端口收到同步应答消息后，直接迁移到转发状态。

根据本发明的另一个方面，本发明提供了一种快速生成树协议在多CPU环境下的分布式实现方法，其中各设备只保存本地端口的数据和状态机信息；每台设备维护一个虚拟端口，所述虚拟端口所保存的信息为分布式系统内当前的根端口信息；该方法包括以下步骤：

a)设备端口收到BPDU(桥协议数据单元)报文后，将报文送交本地RSTP(快速生成树协议)进行处理，RSTP根据本地端口信息和虚拟端口所保存的信息选择系统内唯一的外部根端口；

b)如果选择的外部根端口位于本设备，则RSTP将该端口收到的BPDU以及该端口号作为同步消息发送给其他所有设备，用于阻塞其它所有设备的根端口；

c)设备如果收到来自其他设备发来的根端口信息时，将该信息保存到本地的虚拟端口上，并且重新触发本地的根端口角色选择，如果自己的根端口信息没有远端根端口信息优时，本地根端口将被选择为可选端口或指定端口。

d)当被阻塞根端口需要快速迁移到转发状态时，该被塞根端口向系统内所有端口下发“根端口重新选择”信号，该信号通过同步消息逻辑通道广播到系统内的其他所有端口；

e)收到“根端口重新选择”信号的设备检查本地端口是否已经与被阻塞根端口同步，如果同步，则阻塞本地端口，然后设备将向被阻塞根端口所在设备发送“本设备已经同步根端口重新选择”标志；

f)当被阻塞根端口所在设备收到系统内其他所有设备发来的“本设备已经同步根端口重新选择”标志，并且本地其他端口也全部同步完毕时，被阻塞根端口直接迁移到转发状态；

g)当上游指定端口需要迁移到转发状态时，指定端口向下游发送同步请求消息，此时下游根端口向本地所有端口和系统内其他设备发送同步信号，同步信号通过同步消息逻辑通道广播给其他所有设备；

h)收到该同步信号的设备在本地执行同步动作，根据需要阻塞潜在冗余端口，在同步完毕后，向根端口所在设备发送同步完毕消息；

i)当根端口所在设备收到系统内其他所有设备的同步完毕消息，并且本地其他端口也已经全部同步完毕时，根端口向上游指定端口发送同步应答消息；

j)上游指定端口收到同步应答消息后，直接迁移到转发状态。

其中，当系统内的某台设备发现拓扑变化或者收到拓扑变化消息时，通过同步消息逻辑通道向其他所有设备发送拓扑变化消息，设备收到该消息后刷新本地的地址转发信息。

本发明具有以下优点：

1、降低单CPU的计算量，解决CPU性能需求问题，即在高端口密度的系统下，降低对CPU性能的要求，采用低性能CPU也可以完成快速生成树协议的计算过程。

2、避免BPDU在内部链路转发，解决BPDU在向主设备传送过程中的丢失对拓扑稳定所带来的影响。

3、每个CPU只控制本地端口的STP状态，避免由于需要向其他设备发送STP状态设置指令而带来的可靠性和临时回路问题。

4、每台设备只需要保存本地端口的数据和状态机信息，减少对存储器的需求，降低设备制造成本；

5、不需要在各设备之间广播BPDU报文，减少对设备之间通讯带宽的需求；

6、通过一种特殊的同步方式，避免了由于设备之间的信息同步而导致系统生成树状态计算错误；

7、采用对等式分布式方式设计，一台设备故障时不会导致整个系统的生成树状态重新计算；

8、每台设备只计算本地端口，端口数量的成倍减少提高了生成树协议的计算速度，降低网络的收敛时间。

本发明的上述目的、特点和效果将通过下面的结合附图的详细说明而变得更加清楚。

附图说明

图1是现有技术的环路下报文增生的示意图；

图2是现有技术的冗余的端口被阻塞的示意图；

图3是现有的多CPU框式设备示意图；

图4是现有的多CPU堆叠系统示意图；

图5是利用主从方式实现快速生成树协议的示意图；

图6是利用集中对等式实现方式的示意图；

图7是显示分布式系统与普通互联网的快速生成树计算区别的示意图；

图8是本发明的多CPU环境下的快速生成树协议分布式实现原理图；

图9是多CPU环境下分布式RSTP的根端口角色迁移状态机的示意图。

具体实施方式

在框式结构和堆叠系统等多CPU分布式情况下，快速生成树协议与普通的多设备互连情况下的快速生成树协议的计算特征是不同的，下面详细说明不同点：

1、对于分布式系统，对外只能存在一个根端口，而其他设备的根端口只能是连往根端口所在设备的内部端口。而在普通互连网络中，每台设备都可以独立选择自己的根端口，物理连接结构不同，参数配置不同，都会导致选择的根端口也不同；

2、分布式系统中，内部连接链路需要始终保持为转发状态，任何时候都不能够被生成树协议阻塞。而在普通互连网络中，互连的链路可以根据需要在任何时候被生成树协议阻塞；

3、端口STP状态快速迁移到转发状态时，需要保证所有潜在的冗余链路都被阻塞，在分布式系统中，由于内部链路不能够被阻塞，因此，端口迁移到转发状态时，快速生成树协议需要保证位于其他设备上的端口(远端的的端口)已经与其同步，必要时已经迁移到阻塞状态。而对于普通的互连设备，每台设备只需要确保本地的端口与需要迁移到转发状态的端口同步，无需关心其他设备上的端口；

4、当设备发现拓扑改变或者收到拓扑改变通知消息时，快速生成树协议需要刷新本地所有必要的端口所学到的地址转发信息。对于分布式系统，当发现拓扑改变或者收到拓扑变化通知时，快速生成树协议需要刷新系统内所有的必要的端口所学到的地址转发信息。而对于普通互连的设备，其只需要刷新本地端口所学到的地址转发信息，而无需关心其他设备的端口。

本发明采用“分布对等式”设计方案，该方案的特点为每台设备只负责保存本地端口的数据和状态机信息，只处理来自本地端口的BPDU报文，并且只控制本地端口，不对系统内其它设备的端口进行直接控制。为了为整个系统选择一个唯一的根端口和实现端口STP状态的快速迁移，在系统内各设备之间，快速生成树协议通过发送特定的报文来进行各设备RSTP状态的同步。

下面结合图8说明本发明的实现过程：

1、各设备只保存本地端口的数据和状态机信息。

2、每台设备维护一个虚拟端口，该端口所保存的信息为分布式系统内当前的根端口信息，如果系统内没有根端口，则该端口所保存的信息可以认为是无效的。

3、端口收到BPDU报文后，将报文送交本地RSTP进行处理。RSTP根据本地端口信息和虚拟端口所保存的信息来选择系统内的根端口。具体而言，RSTP在选举根端口的时候，会通过比较设备上所有端口所保存的信息(包括根桥ID，到根的距离，上游指定桥ID，上游指定端口ID以及自己的端口ID，如果该设备没有上游设备，则指定桥ID为自己的桥ID，指定端口ID为自己端口的ID)，来选举一个通过最短路径连往根桥的端口作为根端口。也就是说分布式RSTP特点在于在选举根端口时，不光会比较设备本身的所有端口(即本地端口)上所保存的信息，还会比较那个虚拟端口上的信息。

4、如果选择的根端口位于本设备，则RSTP协议将该端口收到的BPDU以及该端口号作为同步消息发送给其他所有设备。

5、设备如果收到来自其他设备发来的根端口信息时，将该信息保存到本地的虚拟端口上，并且重新触发本地的根端口角色选择，如果自己的根端口信息没有远端根端口信息优时，本地根端口将被选择为可选端口或指定端口。

6、当被阻塞的根端口需要快速迁移到转发状态时，根端口会向系统内所有端口下发“根端口重新选择”信号，该信号通过同步消息逻辑通道广播到系统内的其他所有端口。

7、如果设备收到“根端口重新选择”信号，设备会检查本地端口是否已经与该根端口同步，如果同步，则阻塞该端口，然后设备将向根端口所在设备发送“本设备已经同步根端口重新选择”标志。

8、根端口所在设备收到系统内其他所有设备发来的“本设备已经同步根端口重新选择”标志，并且本地其他端口也全部同步完毕时，根端口直接迁移到转发状态。

9、当上游指定端口需要迁移到转发状态时，指定端口会向下游发送同步请求消息，此时下游根端口需要向本地所有端口和系统内其他设备发送同步信号，同步信号也是通过同步消息逻辑通道广播给其他所有设备。

10、当设备收到该同步信号后，在本地执行同步动作，根据需要阻塞潜在冗余端口。同步完毕后，设备会向根端口所在设备发送同步完毕消息。

11、当根端口所在设备收到系统内其他所有设备的同步完毕消息，并且本地其他端口也已经全部同步完毕，则根端口将向上游指定端口响应同步应答消息。

12、上游指定端口收到同步应答消息后，会直接迁移到转发状态。

13、当系统内的某台设备发现拓扑变化或者收到拓扑变化消息，会通过同步消息逻辑通道向其他所有设备发送拓扑变化消息，设备收到该消息后会刷新本地的地址转发信息。

同步消息采用可靠传输方式发送，传输系统本身保证同步消息不被丢失。同步消息本身具备30秒的时效性，而不是普通BPDU的6秒老化时间。只要同步消息在30秒内到达，快速生成树协议即不会发生计算错误。而现有技术中，这个时间一般是6秒。因此，本发明可以提高分布式系统下快速生成树协议的可靠性。

下面参照图9说明本发明的具体技术特点。

1、选择唯一的外部根端口

(1)优先级向量的定义及优先级比较原则

RSTP的优先级向量定义为：V{R，RC，DB，DP，RP}，其中：

R表示网络中的根桥ID；

RC表示本桥到根桥的距离；

DB表示指定桥ID，即该消息的发送桥ID；

DP表示指定端口ID，即消息的发送端口ID；

RP表示收到该消息的端口ID；

RSTP的优先级向量包括桥优先级向量bridgePriority、端口优先级向量portPriority和消息优先级向量msgPriority。此外在角色计算时还使用到rootPriority和designatedPriority以及rootPathPriority。各优先级相当的定义请参见IEEE 802.1w-200117.4节。

两个向量V1、V2比较时如果：

((R1＜R2))||

((R1＝R2)&&(RC1＜RC2))||

((R1＝R2)&&(RC1＝RC2)&&(DB1＜DB2))||

((R1＝R2)&&(RC1＝RC2)&&(DB1＝DB2)&&(DP1＜DP2))||

((R1＝R2)&&(RC1＝RC2)&&(DB1＝DB2)&&(DP1＝DP2)&&(RP1＜RP2))

则V1比V2优(Better)。

(2)为每个设备增加一个虚拟端口，该端口参与设备的端口角色计算

如果分布式系统中的其它设备存在根端口，则该端口的portPriority为根端口的rootPathPriority，即{Rr，RCr，DBr，DPr，RPr}，各向量成员均表示该根端口所保存的信息，RPr表示根端口ID(也就是接收该信息的端口ID)。

如果分布式系统中没有根端口或者根端口在本设备上，则该端口的portPriority为{B，0，B，0，0}，其中B表示该分布式系统的桥ID。

如果该端口收到新的BPDU，则比较收到的BPDU是否比自己优，如果优则重新刷新本地的portPriority然后触发本设备的端口角色计算。

如果该端口收到{Rr，RCr，DBr，DPr，RPr}不可用信息，则比较是否与当前的portPriority一致，如果一致，则更新portPriority为bridgePriority，即{B，0，B，0，0}，然后触发本设备角色重新计算；如果不一致，则不作处理。

(3)端口角色选择过程

1)计算rootPathPriority：

a)对所有portPriority为received的端口，RSTP计算该端口的rootPathPriority。rootPathPriority＝portPriority，但是其中RC＝portPriority的RC+该端口的PathCost值；

b)对bridgePriority计算其rootPathPriority。rootPathPriority＝bridgePriority；

c)如果虚拟端口的portPriority不等于bridgePriority，则计算该端口的rootPathPriority。虚拟端口的rootPathPriority＝端口的portPriority＝该分布式系统的根端口的rootPathPrioriy；

2)选出最优的rootPathPriority，即本设备的rootPriority。

根据优先级向量比较原则比较所有的rootPathPriority，选出一个最优的作为本设备的rootPriority。

3)根据rootPriority计算所有端口的designatedPriority。designatedPriority用来确定该端口发送的BPDU内容。

4)根据上述计算结果确定本设备各端口角色。

2、根端口重新选择时端口状态同步(reRoot过程同步)

每个桥去往根桥的方向只能有一条路径(也就是说只能有一个根端口)，新的根端口迁移时，如果去往根方向没有其它路径，则该根端口可以立即迁移到转发状态。

新的根端口为了保证没有其它去往根桥的路径，其在向转发状态迁移之间，向所有端口发送reRoot信号，即通知所有端口自己变为根端口了，并且希望迁移到转发状态。

其它端口在收到reRoot信号后，如果自己最近是根桥(即定时器rrWhile没有超时)，则需要将自己迁移到阻塞状态，然后停止rrWhile定时器。

根端口监控所有其它端口的rrWhile定时，当所有定时器均已经停止时(即reRooted)，表示当前没有通往根桥的路径了，此时，根端口可以立即迁移到转发状态。

对于这种同步过程，扩展到整个分布式系统范围内，可以采用如下操作过程：

(1)发送reRoot信息

1)设置本地所有外部端口的reRoot标志；

2)通过同步消息传输通道，将该操作发送到系统内其他所有设备，设置这些设备的端口的reRoot标志；

3)各设备根据reRoot标志激励对应端口的状态机进行角色迁移。

(2)扩充reRooted定义

协议中定义reRooted：系统内除了根端口的rrwhile定时器外，其他所有端口的rrwhile定时器均已超时。

对于分布式系统，每个设备增加unitReRooted1、unitReRooted2、…、unitReRootedM，其中M为分布式系统内的最大设备数，用unitReRootedX表示其中任何一个。

另外，定义meReRooted为本设备已经同步，即本设备除了根端口外其他端口的rrwhile定时器均已超时。

这样的话，reRooted新的定义为：

meReRooted && unitReRooted1 && unitReRooted2 &&…&&unitReRootedM(除本设备的unitReRooted外)

(3)其它设备向根端口所在设备发送meReRooted信号

每个设备的meReRooted置位后，通过同步消息传输通道向根端口所在设备发送meReRooted信号，根端口所在设备收到该信号后，设置相应的unitReRooted变量，然后检查是否reRooted，如果是则激励根端口的状态机进行迁移，即快速迁移到转发状态。

3、指定端口的快速迁移同步过程(sync同步过程)

指定端口向转发状态迁移时需要向下游根端口发送proposal(同步请求)信号，根端口收到该信号后设置本地的proposed标志。如果由于最近发生拓扑变化，即根端口的synced被复位，则根端口需要向系统内的所有端口发送sync信号，通知这些端口上游有端口需要迁移到转发状态。

指定端口在收到sync信号后，如果自己的synced没有置位，则端口迁移到阻塞状态，然后将自己的synced置位。对于其它端口由于其不提供转发路径，不会构成环路危险，可以直接将端口的synced置位。

根端口检测到所有其它端口的synced置位后，即allsynced后，根端口设置自己的synced标志，然后向上游指定端口发送agree信号，表示自己已经同步。

上游在收到agree信号后可以立即迁移到转发状态。

对于这种同步过程，扩展到整个分布式系统范围内，可以采用如下操作过程：

(1)发送sync信息

1)设置本地所有外部端口的sync标志；

2)通过同步消息传输通道，将该操作发送到系统内其他所有设备，设置这些设备的端口的sync标志；

3)各设备根据sync标志激励对应端口的状态机进行角色迁移。

(2)扩充allSynced定义

协议中定义allSynced：系统内除根端口外的其他所有端口均为synced状态。

对于分布式系统，每个设备增加unitSynced1、unitSynced2、…、unitSyncedM，其中M为系统内的最大设备数，用unitSyncedX表示其中任何一个。

另外，定义meSynced为本设备已经同步，即本设备内除根端口外的其他所有端口均为synced状态。

这样的话，allSynced新的定义为：

meSynced && unitSynced1 && unitSynced2 && … &&unitSyncedM(除本设备的unitSynced外)

(3)其它设备向根端口所在设备发送meSynced信号

每个设备的meSynced置位后，通过同步消息传输通道向根端口所在设备发送meSynced信号，根端口所在设备收到该信号后，设置相应的unitSynced变量，然后检查是否allSynced，如果是则激励根端口向上游指定端口发送agree信号。

4、拓扑改变消息同步过程

端口在发现拓扑变化或者收到拓扑变化消息后，拓扑变化处理状态机通知其它所有端口向外发送拓扑改变信息。

对于分布式系统，处理过程如下：

1)设置本地除自己之外的其它所有端口的tcProp标志，从而激励这些端口的状态机，触发tcWhile定时器，清除端口所学到的地址转发信息；

2)通过同步消息传输通道，将该操作发送到系统内其他所有设备，设置这些设备上的所有端口的tcProp标志，从而激励这些设备的端口状态机，触发tcWhile定时器，清除端口的地址转发项。

综上所述，本发明具有以下有益效果：

1、减少快速生成树协议对CPU和存储器资源的需求，降低设备的制造成本；

2、避免BPDU在内部链路转发，解决BPDU在向主设备传送过程中的丢失对拓扑稳定所带来的影响。

3、每个CPU只控制本地端口的STP状态，避免由于需要向其他设备发送STP状态设置指令而带来的可靠性和临时回路问题。

4、不需要在各设备之间广播BPDU报文，减少对设备之间通讯带宽的需求；

5、本发明通过特殊的同步方式，避免了由于设备之间的信息同步而导致系统生成树状态计算错误；

6、本发明采用对等式分布式方式设计，一台设备故障时不会导致整个系统的生成树状态重新计算；

7、每台设备只计算本地端口，端口数量的成倍减少提供的生成树协议的计算速度，提高网络的收敛速度。