基于多生成树的无死锁自适应路由方法

摘要

本发明公开了一种基于多生成树的无死锁自适应路由方法，涉及网络通信技术领域。该方法具体包括：确定多生成树的各个根节点，并构造多生成树；将不同的源/目的网络通信节点对分配给不同的生成树，使不同的源/目的网络通信节点对通过不同的生成树传递数据；打破通信网络拓扑图中的资源循环依赖，避免潜在的死锁；在路由器中，使用路由和仲裁单元来代替路由表；对所述路由器采用动态缓冲区分配策略。本发明方法有效减轻了各个生成树中根节点和气泡节点的拥堵情况，提高了不规则网络的通信性能，当网络规模增大时，本发明方法具有较好的可扩展性。

说明书

技术领域

本发明涉及网络通信技术领域，具体涉及一种基于多生成树的无 死锁自适应路由方法。

背景技术

传统的应用于不规则网络通信中的上/下路由方法是在网络中建立 一棵生成树并且只选择一个节点作为根节点。它是一个在不规则网络 中有一定自适应性的分布式无死锁路由方法。总的来说，上/下路由方 法就是在一棵生成树中为各个节点间的通信数据进行路由。从源节点 出发的数据包首先沿着这棵生成树向根节点运动，然后再沿着生成树 向目标节点运动。通常，我们在离其他所有节点距离最短的一些节点 中随机选择一个作为生成树的根节点。这样所有网络拓扑图中节点间 的链路就可以根据它们所连接的节点与根节点的位置关系被标记为上 或者下。例如，网络中的两个相邻节点u,v，如果u到根节点的距离比v 到根节点的距离远，那么链路(u,v)的状态为上，反之为下。如果u和v到 根节点的距离相等，那么它们之间链路的方向就为拥有小ID号的节点 指向拥有大ID号的节点。例如，如果节点u比节点v的ID号小，那么 链路(u,v)的状态就为上。图1（a）展示了一个八个节点的不规则网络 拓扑，图1（b）展示了以节点1为根节点的上/下路由方法中的生成树， 可以看出图中不存在环。

源节点与目标节点间的路由路线遵循以下规则：0个或者多个状态 为上的链路需要在0个或者多个状态为下的链路之前。也就是说，数 据包需要首先经过状态为上的链路然后再经过状态为下的链路。这样 的路由路线就避免了数据包传递中可能的资源循环依赖。也就是说， 上/下路由方法是一种无死锁的路由方法。而且在上/下路由方法所产生 的生成树中，不同的源/目标节点对可能存在着多条符合规则的路由路 线，这样就为上/下路由方法带来了一定的自适应性。

上/下路由方法的优点在于简单的路由器结构和一定的自适应性。 它的缺点在于源/目标节点间的路由路线有可能不是两个节点间的最短 路线，而且靠近根节点的物理链路有可能变得十分拥堵从而成为整个 网络通信的瓶颈。

避免死锁的传统方法是将一条物理链路分为多条虚拟链路，这样 不同的数据包就可以在同一条物理链路不同的虚拟链路中传递。另外 一种避免死锁的方法叫做气泡流量控制法，这种方法的原理是限制形 成循环依赖的数据包的注入。这样，网络拓扑图中有可能形成循环依 赖的环中的资源永远都不可能同时被占用，从而环中的数据包永远都 可以继续向他们的目的节点前进。同时，气泡流量控制法很容易实现， 事实上，本发明就是运用气泡流量控制法来避免死锁的。

在传统的上/下路由方法中，多数的数据包都会经过生成树的根节 点进行传递。这样，这个根节点在很多情况下都有可能变成网络通信 的瓶颈，特别是当网络的规模变大时。在多数情况下，根节点并不是 数据包的目的节点，它仅仅扮演了数据包传递中中间节点的角色。

发明内容

（一）要解决的技术问题

本发明主要解决现有上/下路由方法中生成树根节点附近的物理链 路容易发生拥堵的技术问题，并在很大程度上提高路由的灵活性与网 络规模的可扩展性。

（二）技术方案

为解决上述问题，本发明提供了一种基于多生成树的无死锁自适 应路由方法，包括以下步骤：

S1、确定多生成树的各个根节点，并构造多生成树；

S2、将不同的源/目的网络通信节点对分配给不同的生成树，使不 同的源/目的网络通信节点对通过不同的生成树传递数据；

S3、打破通信网络拓扑图中的资源循环依赖，避免潜在的死锁；

S4、在路由器中，使用路由和仲裁单元来代替路由表；

S5、对所述路由器采用动态缓冲区分配策略。

优选地，所述步骤S1进一步包括以下步骤：

S101、确定第一个根节点，使其余节点通过以其为根节点的生成 树进行通信的平均距离最短，所述第一个根节点根据以下公式得到：

$\mathrm{FR}={\min }_r\left\{\underset{u,v}{\Sigma }{\mathrm{dist}}_r(u,v)\right\},$

其中，dist_r(u,v)表示u节点和v节点在常规上/下路由方法中的距离；

S102、确定第二个根节点，使得通信网络拓扑中各个节点输入端 口缓存区的循环依赖所涉及的节点数和所有节点间通信的距离之和都 尽量最小，所述第二个根节点根据以下公式得到：

$\mathrm{SR}=\underset{u,v}{\Sigma }\frac{\mathrm{\Delta dist}(u,v)}{{\Sigma }_c\mathrm{size}\left(c\right)},$

其中，size(c)表示循环依赖中的节点数，∑_csize(c)表示识别出的所 有循环依赖所涉及的所有节点总数，Σ_u，vΔdist(u，v)表示新增根节点所带 来的所有节点间缩短的通信距离的总和；

S103、根据以下公式确定其余的根节点：

$h=\underset{u,v}{\Sigma }\frac{\mathrm{\Delta dist}(u,v)}{\mathrm{\Delta T}},$

$\mathrm{\Delta T}={\Sigma }_{{c\in c}_2}\mathrm{size}\left(c\right)-{\Sigma }_{{c\in c}_1}\mathrm{size}\left(c\right),$

其中c₁和c₂是新生成树建立前和建立后网络中循环依赖所涉及的 节点集合，Δdist(u,v)代表在新生成树建立后各个节点间减少的通信距 离。

优选地，所述步骤S2进一步包括以下步骤：

S201、将一组源/目的网络通信节点对分配给与其通信距离最短的 一个生成树；

S202、相同源节点、不同目的节点的网络通信节点对均衡分配给 不同的生成树；

S203、当一组源/目的网络通信节点对在多个生成树中的通信距离 都为最小且相等时，将这组源/目的网络通信节点对分配给任意一个生 成树。

优选地，所述步骤S3进一步包括以下步骤：

S301、在通信网络拓扑图中找到可能发生资源循环依赖的环；

S302、在每个环中找到限制端口，当所述限制端口满足预定规则 时，允许数据包通过其进行传递，当所述限制端口不满足预定规则时， 不允许数据包通过其进行传递，其预定规则是下一跳端口有多余或者 等于两个缓存区；

根据以下的效益计量公式能够确定一个节点中的输入端口作为限 制端口：

$m\left(v_i\right)=\underset{v_i\in C}{\Sigma }\mathrm{size}\left(C\right),$

其中，节点v的输入端口i是循环依赖C中的限制端口，size(C)是循 环依赖C的大小，选择上述效益计量值大的输入端口作为限制端口；

S303、当两个输入端口的效益计量值相等时，选择度数小的节点 中的输入端口作为限制端口；

S304、在选择出每一个限制端口后，每一个节点的每一个端口的 效益计量值都要进行更新，即在打破的循环依赖中所包含的节点和这 些节点中的输入端口的循环计量值都要减去循环依赖的大小；

S305、重复执行以上步骤，直到所有的循环依赖都被打破。

优选地，所述步骤S4进一步包括以下步骤：

S401、将经过路由器某一个端口的数据包分成两类：其中一类是 以该路由器为源节点的数据包；另一类是经过该路由器，以该路由器 为中间节点的数据包；

S402、将以该路由器为源节点的数据包根据其具体传递所在的生 成树分类，所述情况在路由方程中的表达为：表示生成树的标志位乘 以所述数据包在该生成树中的各个目的节点的标志位之和，如果该端 口在该生成树中为限制端口，则还需乘以限制端口标志位；

S403、将以该路由器为中间节点的数据包根据到达该路由器的物 理链路的状态分为两类：其中一类是经过状态为上的物理链路到达该 路由器的数据包；另一类是经过状态为下的物理链路到达该路由器的 数据包；

S404、将以该路由器为中间节点并且经过状态为上的物理链路到 达该路由器的数据包根据其具体传递所在的生成树分类，所述情况在 路由方程中的表达为：表示生成树的标志位乘以所述数据包在该生成 树中的各个目的节点的标志位之和，如果该端口在该生成树中为限制 端口，则还需乘以限制端口标志位；

S405、将以该路由器为中间节点并且经过状态为下的物理链路到 达该路由器的数据包根据其具体传递所在的生成树分类，所述情况在 路由方程中的表达为：表示生成树的标志位乘以上一跳标志位再乘以 所述数据包在该生成树中的各个目的节点的标志位之和，如果该端口 在该生成树中为限制端口，则还需乘以限制端口标志位；

S406、将上述各个路由方程中的表达式相加再乘以下一跳空闲缓 存区标志位，再乘以输出端口缓存区队列长度标志位取反。

优选地，所述步骤S5进一步包括以下步骤：

S501、将缓存区资源分为两类，一类是特定缓存区，另一类是中 央缓存区；

S502、将特定缓存区与某一个特定的输入端口绑定，使得每一个 输入端口都有一个足以装下一个数据包的特定缓存区；

S503、中央缓存区能够分配给任何一个输入端口；

S504、每一个缓存区都设有一个用来标记其状态的标志位、一个 用来标记其是否被申请占用的标志位、以及一个标记其是否已经被占 用的标志位；

S505、为连接根节点和限制端口的输入端口分配更多的中央缓存 区资源。

（三）有益效果

本发明方法有效减轻了各个生成树中根节点和气泡节点的拥堵情 况，提高了不规则网络的通信性能，当网络规模增大时，本发明方法 具有较好的可扩展性。

附图说明

图1（a）是拥有八个网络节点的不规则网络示意图，（b）是传统 上/下路由方法中的生成树示意图；

图2是拥有两棵符合传统路由方法生成树的不规则网络示意图；

图3是本发明方法的流程图；

图4是VCT交换路由器的路由逻辑示意图；

图5是拥有多棵生成树的不规则网络中的资源循环依赖示意图， 其中（a）表示只有输入端口的不规则网络，（b）表示网络中的资源循 环依赖，（c）表示在生成树8中2_a被选为限制端口，（d）表示生成树1 中的3_a和生成树8中的7_a、6_b被选为限制端口。

具体实施方式

下面结合附图和实施例，对本发明的具体实施方式作进一步详细 描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

本发明提出了一种新的基于多生成树的无死锁自适应路由方法， 该方法的核心思想是为一个不规则网络建立多棵生成树，使不同源/目 的节点间的数据包在不同的生成树上传递。这个技术可以平均地将网 络上的数据包分配给不同的生成树，使它们经过各自的根节点进行传 递，从而直接改善单生成树根节点附近的拥堵情况。如图2所示，在 网络中我们以节点1和节点8为根节点构造了两棵生成树。

在某一棵生成树的拓扑图中不可能存在环，但是在多棵生成树之 间有可能存在资源的循环依赖。本发明采用为每一个在拓扑图中存在 的环选择一个气泡节点的方法来避免潜在循环依赖的发生。气泡节点 相应的端口被限制而不是被完全禁止，被限制的端口只有当它能提供 足够的缓存区时它才被允许用来传递数据包。本发明还提出了一个新 的动态分配缓存区的方法来提高整个网络的性能和减轻各个生成树中 根节点和气泡节点的拥堵情况。

图3是本发明方法的流程图，本发明提供一种基于多生成树的无 死锁自适应路由方法，包括以下步骤：

步骤S1：选择多生成树的各个根节点并构造生成树。各个生成树 的根节点的选择对于所有基于生成树的路由方法都至关重要。不同于 以前的多种方法所使用的生成树根节点选择方法，本发明需要使用两 种不同的启发式算法来分别选择第一个根节点和其余的根节点。

步骤S101：第一个根节点需要具备其余节点通过它进行通信的平 均距离最短的特点。用公式：

$\mathrm{FR}={\min }_r\left\{\underset{u,v}{\Sigma }{\mathrm{dist}}_r(u,v)\right\}$

可以得到我们需要的根节点。其中dist_r(u,v)表示u节点和v节点在传统 上/下路由方法中的距离。

步骤S102：在选择第一个根节点后我们需要选择第二个根节点， 尽管所根据的算法思想相同，对于第二个根节点和其余根结点的选择 基于不同的公式。因为网络通信中涉及可能发生资源循环依赖的节点 越多对网络性能的影响就越大，所以在选择其余的根节点时我们应该 尽量使得网络拓扑中各个节点输入端口缓存区的循环依赖所涉及的节 点数和所有节点间通信的距离之和都最小。对于第二个根节点，根据 以下公式进行选择：

$\mathrm{SR}=\underset{u,v}{\Sigma }\frac{\mathrm{\Delta dist}(u,v)}{{\Sigma }_c\mathrm{size}\left(c\right)},$

其中size(c)表示循环依赖中的节点数，∑_csize(c)表示识别出的所有 循环依赖所涉及的所有节点总数，∑_u，vΔdist(u,v)表示新增根节点所带来 的所有节点间缩短的通信距离的总和。

步骤S103：第三个节点和第四个节点可以根据以下公式进行选择：

$h=\underset{u,v}{\Sigma }\frac{\mathrm{\Delta dist}(u,v)}{\mathrm{\Delta T}},$

$\mathrm{\Delta T}={\Sigma }_{{c\in c}_2}\mathrm{size}\left(c\right)-{\Sigma }_{{c\in c}_1}\mathrm{size}\left(c\right),$

其中c₁和c₂是新生成树建立前和建立后网络中循环依赖所涉及的 节点集合，Δdist(u,v)代表在新生成树建立后各个节点间减少的通信距 离。需要注意的是当ΔT＝0时，需要将它从上述公式中移除。

步骤S2：在本发明提出的方法中，一个网络拥有多棵生成树，这 样不同的源/目的网络通信节点对就可以通过不同的生成树传递数据 包。这样做的好处是可以使整个网络负载均衡的传递数据包，同时也 避免了不同生成树使用不同虚拟通道传递数据包所带来的物理链路不 能充分利用的问题。如何将不同的源/目的网络节点对分配给不同的生 成树，对于不规则网络的负载均衡是至关重要的。

步骤S201：将一组源/目的网络通信节点对尽量分配给它们通信距 离最短的一个生成树。

步骤S202：为了达到更好的负载均衡，相同源节点、不同目的节 点的网络通信节点对应该均衡的分配给不同的生成树。

步骤S203：当一组源/目的网络通信节点对在多个生成树中的通信 距离都为最小且相等时，这组网络通信节点对就可以分配给任意一个 生成树，这时就为数据包的分配提供了一些灵活性。

步骤S3：基于多生成树的无死锁自适应路由方法不仅仅为不同节 点间提供了更短的通信路径还有效的提升了整个路由算法的自适应 性。然而，这个算法同时也带来了在网络拓扑图中的一些可能发生的 资源循环依赖。通过遵循以下步骤，可以打破这些循环依赖从而避免 潜在的死锁：

步骤S301：在网络拓扑图中找到可能发生资源循环依赖的环。

步骤S302：然后在每个环中找到一些限制端口，当这些限制端口 满足预定要求时，允许数据包经过它们进行传递，当它们不满足预定 要求时，不允许数据包经过它们进行传递。在选择限制端口时，遵循 以下规则：

1、每一个循环依赖中至少包含一个含有限制端口的节点；

2、含有限制端口节点的选择是根据相应的输入端口而不是整个节 点；

3、尽量避免选择根节点中的输入端口作为限制端口；

4、网络中的所有节点所包含的限制端口的数量不能超过一个给定 的阈值；

5、尽量选择度数较小的网络节点中的输入端口作为限制端口。

可以根据以下的效益计量公式来选择一个节点中的输入端口作为 限制端口：

$m\left(v_i\right)=\underset{v_i\in C}{\Sigma }\mathrm{size}\left(C\right)$

其中，节点v的输入端口i是循环依赖C中的限制端口。size(C)是循 环依赖C的大小。循环依赖所涉及的节点越多对整个网络的性能影响就 越大。所以优先选择上述效益计量值大的输入端口作为限制端口。

步骤S303：当两个输入端口的效益计量值相等时，选择度数小的 节点中的输入端口，因为，度数大的节点在网络中会负责传递更多的 流量。

步骤S304：在选择出每一个限制端口后，每一个节点的每一个端 口的效益计量都要进行相应的更新，也就是在打破的循环依赖中所包 含的节点和这些节点中的输入端口的循环计量值都要减去循环依赖的 大小。

步骤S305：重复执行以上步骤，直到所有的循环依赖都被打破。

步骤S4：在路由器中，使用路由和仲裁单元来代替路由表。

步骤S401：将经过路由器某一个端口的数据包分成两类：其中一 类是以该路由器为源节点的数据包；另一类是经过该路由器，以该路 由器为中间节点的数据包；

步骤S402：将以该路由器为源节点的数据包根据其具体传递所在 的生成树分类，所述情况在路由方程中的表达为：表示生成树的标志 位乘以所述数据包在该生成树中的各个目的节点的标志位之和，如果 该端口在该生成树中为限制端口，则还需乘以限制端口标志位；

步骤S403：将以该路由器为中间节点的数据包根据到达该路由器 的物理链路的状态分为两类：其中一类是经过状态为上的物理链路到 达该路由器的数据包；另一类是经过状态为下的物理链路到达该路由 器的数据包；

步骤S404：将以该路由器为中间节点并且经过状态为上的物理链 路到达该路由器的数据包根据其具体传递所在的生成树分类，所述情 况在路由方程中的表达为：表示生成树的标志位乘以所述数据包在该 生成树中的各个目的节点的标志位之和，如果该端口在该生成树中为 限制端口，则还需乘以限制端口标志位；

步骤S405：将以该路由器为中间节点并且经过状态为下的物理链 路到达该路由器的数据包根据其具体传递所在的生成树分类，所述情 况在路由方程中的表达为：表示生成树的标志位乘以上一跳标志位再 乘以所述数据包在该生成树中的各个目的节点的标志位之和，如果该 端口在该生成树中为限制端口，则还需乘以限制端口标志位；

步骤S406：将上述各个路由方程中的表达式相加再乘以下一跳空 闲缓存区标志位，再乘以输出端口缓存区队列长度标志位取反。

在步骤S4中，提出了一种包含k个输入和输出端口的新的路由器 结构来满足基于多生成树的无死锁自适应路由方法在网络上应用的需 求。

新的路由报头包含两位用来表示该报文所属生成树的标志位，一 位用来表示上一跳是上还是下的标志位，还有一组用来表示目的地地 址的标志位，例如：拥有16个节点的网络需要四位长度的标志位来代 表目的地地址。

新的路由器结构包括：

k*n个表示输出端口状态的信号。n表示生成树的个数，k表示输 出端口的个数。例如：S_i，j＝1第i个输出端口在第j个生成树上是上否则 为下。这些信号在所有生成树建立之后即为固定不变的值。

k个代表各个输出端口队列长度的信号。例如：q_i＝1表示第i个端 口的输出队列长度至少为1，否则该队列为空。

k个代表各个输出端口是否为限制输出端口的信号。例如：C_i＝1表 示第i个输出端口及它所对应的物理链路是受限的。

2*k个代表各个输出端口所对应的下一跳节点输入端口的可用缓 存去数量。例如：b_i，1，b_i，2＝00,01,10,11就表示第i个输出端口所对应的下 一跳节点输入端口的可用缓存去数量为0个，1个，2个，和3个。

使用路由方程来实现路由表的功能，用于代替路由表的逻辑十分 的简洁。

如图2所示，节点5的b端口的路由方程为：

$R_b=b_{\mathrm{1,1}}·\overline{q_2}·C_2·(\bar{t}·(\overline{d_1}{d}_2\overline{d_3}+d_1{d}_2{d}_3)+t·s·({\overline{d_1}d}_2\overline{d_3}+d_1{d}_2{d}_3)+$

$\bar{t}·\overline{d_1}\overline{d_2}{d}_3+t·(\overline{d_1}{d}_2\overline{d_3}+d_1{d}_2{d}_3))$

$=b_{\mathrm{1,1}}·\overline{q_2}·C_2·(\overline{d_1}{d}_2\overline{d_3}+\bar{t}\overline{·d_1}\overline{d_2}{d}_3+d_1{d}_2{d}_3)$

q₂＝1表示输出端口的队列长度至少为1。代表在 生成树8上面传递的以节点5作为中间节点的数据包， 代表在生成树1上面传递的以节点5作为中间节点的 数据包，和代表在生成树1和生产树8上面以 节点5作为源节点的数据包。

步骤S5：为了充分利用有限的缓存去存储资源，本发明提出了一 种新的动态缓存区分配策略。

步骤S501：首先将缓存区资源分为两类，一类是特定缓存区，一 类是中央缓存区。

步骤S502：将特定缓存区与某一个特定的输入端口绑定，满足每 一个输入端口都有一个足以装下一个数据包的特定缓存区。

步骤S503：中央缓存区可以分配给任何一个输入端口。如果需要 的话一个输入端口可占有多个中央缓存区，并在数据包传递完成后释 放它们。

步骤S504：每一个缓存去都有一个用来标记它们状态的标志位， 一个用来标记它们是否被申请占用的标志位，还有一个它们是否已经 被占用的标志位。

步骤S505：为连接根节点和限制端口的输入端口分配更多的中央 缓存去资源，进而避免这些位置成为网络通信的瓶颈。

本发明用Java语言实现了上述基于多生成树的无死锁自适应路由 方法和动态缓存区分配策略，同时被实现的还有传统的上/下路由方法、 基于Duato原则的路由方法、多层路由方法、区域排序基于标签的路 由方法。其中基于Duato原则的路由方法和多层路由方法需要多条虚 拟链路，所以需要为所有的路由器的端口都分配两个或两个以上的缓 存区。用于测试的不规则网络拓扑是随机生成的，物理链路在满足每 个节点的度不超过4的条件下被随机添加到网络节点之间。

本发明实现了所有在网络拓扑中有三棵或者四个生成树的根节点 选择情况。下表1展示了在节点数为16、32、64、128、256、512的 网络中对第一个根节点进行选择的处理器时间和对剩余根节点进行选 择的处理器平均时间。

表1

节点的数量 16 32 64 128 256 512 第一个根节点 1.01 1.98 3.90 14.68 248.5 65428 其余根节点(3棵生成树) 1.02 2.09 4.11 16.79 260.4 66099 其余根节点(4棵生成树) 1.04 2.15 4.75 16.43 260.0 66048

通常以两个量来评估不同路由算法的性能：传递一个数据包的延 迟和整个网络的最大负载。在拥有32个节点和116条物理链路的网络 中。传统的上/下路由方法在网络负载稍大于0.1后就很快到达了饱和 点。基于Duato原则的扩展路由方法在网络负载为0.24时到达了饱和 点。多层路由方法的性能明显优于传统的上/下路由方法和基于Duato 原则的扩展路由方法，当网络负载为0.18时它所能接受的流量略多与 基于Duato原则的扩展路由方法。本发明提出的基于多生成树的无死 锁自适应路由方法，无论是否应用本发明提出的动态缓存区分配策略， 在任何情况下性能都明显优于区域排序基于标签的路由方法。

在64个网络节点232条物理链路的网络中，区域排序基于标签的 路由方法的表现要好于基于多生成树的无死锁自适应路由方法，但它 的表现在各种情况下都明显差于基于多生成树的无死锁自适应路由方 法的动态缓存区分配版本。

当网络的规模增大时，上述差异将更加明显。也就是说本发明提 出的方法具有更好的可扩展性。在128个网络节点464条物理链路的 网络中可以发现，当生成树的数目为3时，本发明方法的性能最佳。 一个网络中最佳生成树的数目受网络中网络节点的个数、物理链路的 条数和每一个输入端口的缓存区数量所影响。

下面详述基于多生成树的无死锁自适应路由方法具体的路由器实 施方法。假设路由器拥有k个输入或者输出端口，以VCT交换为基础。 如图4所示，数据包的路由头部包含两位用来标识该数据包在哪棵生 成树上传递的标识位t₁t₂。一组用来标识目的节点的标识位,例如拥有16 个节点的网络需要4位标识位d₁d₂d₃d₄来代表目的节点。一位用来标识 上一条状态的标识位s，当s＝1时表明上一跳为下，反之上一跳为上。

标识位s_1，1,s_1，2,s_2，1，s_2，2，…,s_k，1，s_k,2用来标识输出链路的状态。s_i,j=1表示 第j棵生成树的第i条输出链路的状态为上，反之则为下。当网络中的 生成树被建立之后，标识位s_1，1,s_1，2,s_2，1，s_2，2，…,s_k，1,s_k,2的值就是固定不变的 了。在整个路由过程中对输出链路的选择必须遵循上/下路由算法的规 则。也就是说当上一跳的状态为上时，所有的输出链路都是候选链路， 而当上一跳的状态为下时，只可以选择状态为下的输出链路。

标识位q₁,q₂,…,q_k也是标识与输出链路对应的缓存区队列的状态， 当q_i＝1时表示第i条输出链路所对应的缓存区队列的长度至少为1，否 则队列为空。这里使用k个标识位C₁,C₂,…,C_k来标识路由器中的k个输 出端口是否为限制端口。当C_i＝1时，路由器的第i个端口以及与它相连 的物理链路的状态为受限状态。当一条物理链路的状态为受限时，数 据包只能在与它相连的下一跳端口的空闲缓存区的数量大于等于2时， 选择这条物理链路进行传递。标识位b₁,b₂用来表示输出端口相应的下一 跳输入端口的空闲缓存区数量，当b₁,b₂的值分别为00,01,10和11时， 表示下一跳输入端口空闲缓存区的数量为0,1,2,3。

整个路由逻辑部分并不复杂，我们用路由和仲裁单元来实现路由 表的功能。实现路由表功能的逻辑十分的简洁。如图5所示，以节点5 为源节点的数据包可以被平均的分配给两棵生成树。具体的分配方式 如下：5→1(8)（数据包以5为源节点在生成树8上进行传递），5→6(8)， 5→2(8)，5→3(1)，5→4(1)，5→8(1)，5→7(1)。我们的网络中，只有目 的节点为3,2,8的数据包的传递可能会经过节点5的b端口。在生成树 1中传递的数据包5→3和5→8经过了限制链路。

现在考虑以节点5作为中转节点的数据包。通过状态为上的物理 链路到达节点5的数据包可以被传递给节点3,8,2；通过状态为下的物 理链路到达节点5的数据包可以被传递给节点3和节点8。这样，节点 5的b端口的路由方程为：

$R_b=b_{\mathrm{1,1}}·\overline{q_2}·C_2·(\bar{t}·(\overline{d_1}{d}_2\overline{d_3}+d_1{d}_2{d}_3)+t·s·({\overline{d_1}d}_2\overline{d_3}+d_1{d}_2{d}_3)+$

$\bar{t}·\overline{d_1}\overline{d_2}{d}_3+t·(\overline{d_1}{d}_2\overline{d_3}+d_1{d}_2{d}_3))$

$=b_{\mathrm{1,1}}·\overline{q_2}·C_2·(\overline{d_1}{d}_2\overline{d_3}+\bar{t}\overline{·d_1}\overline{d_2}{d}_3+d_1{d}_2{d}_3)$

q₂=1表示输出端口的队列长度至少为1，代表在 生成树8上面传递的以节点5作为中间节点的数据包， 代表在生成树1上面传递的以节点5作为中间节点的 数据包，和代表在生成树1和生产树8上面以 节点5作为源节点的数据包。

在路由单元提供的多个候选端口中，通常倾向选择非受限的端口， 从而使得下一跳的端口拥有更多的缓存区数量。当有两个状态为非受 限的端口时，通常选择端口所在节点度数较小的那个。因为选择度数 较小的节点往往会带来更小的网络拥堵。当候选端口的数量仍多于1 时，则在它们中间随机选择一个，因此本发明的选择逻辑也非常简单。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领 域的普通技术人员来说，在不脱离本发明技术原理的前提下，还可以 做出若干改进和替换，这些改进和替换也应视为本发明的保护范围。