一种基于容错计算机网络结构的无死锁自适应路由方法

摘要

本发明提出了一种基于容错计算机网络结构的无死锁自适应路由方法，包括如下步骤：对容错计算机网络结构中的每个节点进行编号，对每一条链路根据链路的始发节点和到达节点的编号设置链路的跨度方向；根据源节点和目的节点的编号确定从源节点到目的节点的最短路径，作为初始备选路径；判断每个节点是否为局部安全节点，生成局部失效信息表；根据负向优先策略及每个节点的局部失效信息表，对初始备选路径进行筛选，如果初始备选路径中存在可用的传输路径，则选用该传输路径；如果不存在可用的传输路径，则采用绕道路由选择策略寻找传输路径。本发明在不使用虚拟通道的情况有效避免死锁产生、提高路由效率，提升了计算机网络结构的健壮性和稳定性。

主权项

一种基于容错计算机网络结构的无死锁自适应路由方法，其特征在于，包括如下步骤：对容错计算机网络结构中的每个节点进行编号，对所述网络结构中的每一条链路，根据所述链路的始发节点和到达节点的编号设置所述链路的跨度方向，其中，所述对容错计算机网络结构中的每个节点进行编号，包括如下步骤：所述容错计算机网络结构包括第一子网络和第二子网络，分别对所述第一子网络和所述第二子网络进行编号，其中，所述第一子网络包括N个节点，按0～N－1标号，所述第二子网络包括N个交换器节点，按N～2N－1标号；若分别位于所述第一子网络和所述第二子网络的两个节点的编号对N取模的值相同，则位于不同子网络的所述两个节点之间存在一条链路；所述设置所述始发节点到所述到达节点的链路的跨度方向，包括如下步骤：如果所述始发节点的编号大于所述到达节点的编号，则设置所述跨度方向为负向跨度，否则设置所述跨度方向为正向跨度；根据数据传输的源节点和目的节点的编号确定从所述源节点到所述目的节点的最短路径，作为初始备选路径；判断所述每个节点是否为局部安全节点，并生成局部失效信息表；根据负向优先策略及所述每个节点的局部失效信息表，对所述初始备选路径进行筛选，如果所述初始备选路径中存在可用的传输路径，则按照所述可用的传输路径从所述源节点向所述目的节点传输数据，其中，所述负向优先策略包括：如果数据报文沿负向跨度传输后，则允许所述数据报文继续沿负向跨度以及正向跨度进行传输；如果所述数据报文沿正向跨度传输后，则仅允许所述数据报文继续沿正向跨度传输；根据负向优先策略及所述每个节点的局部失效信息表，对所述初始备选路径进行筛选，包括如下步骤：判断所述初始备选路径是否满足负向优先策略；若满足负向优先策略的所述初始备选路径为两条，则根据所述局部失效信息表判断所述初始备选路径是否均为可用的传输路径，如果是，则从所述两条初始备选路径中随机选择一个作为所述传输路径；若满足负向优先策略的所述初始备选路径为一条，则根据所述局部失效信息表判断所述初始备选路径是否为可用的传输路径，如果是，则选择所述初始备选路径作为所述传输路径；若所述初始备选路径经上述步骤判断为均不可用，则采用绕道路由选择策略寻找从所述源节点到所述目的节点的传输路径；以及如果所述初始备选路径中不存在可用的传输路径，则采用绕道路由选择策略寻找从所述源节点到所述目的节点的传输路径，其中，所述绕道路由选择策略包括：判断所述源节点与所述目的节点是否位于同一子网络中；若所述源节点与所述目的节点位于不同子网络中，并且根据所述局部失效信息表判断不存在可用的最短路径，则执行子网间容错无死锁自适应绕道路由选择策略；若所述源节点与所述目的节点位于同一自网络中，并且根据所述局部失效信息表判断不存在可用的最短路径，则执行子网内容错无死锁自适应绕道路由选择策略。