一种针对路由方向单调变化网络的容错曼哈顿路由方法

摘要

本发明公开一种针对路由方向单调变化网络的容错曼哈顿路由方法，包括步骤：判断源节点和目标节点是否为错误节点，若至少有一个为错误节点则结束流程；判断每一个中间节点的被最小路由策略允许的下一跳节点，并记录每一个中间节点的被最小路由策略允许的上一跳节点；将源节点的路径计数值设为非0，并计算中间节点和目标节点的路径计数值；判断目标节点的路径计数值是否为0，若为0则结束流程；将目标节点作为起点，开始逐跳查找路径计数值不为0且被最小路由策略允许的上一跳节点直至查找到源节点，得到容错曼哈顿路径。本发明复杂度低、普适性高且不牺牲可用容错曼哈顿路径。

说明书

技术领域

本发明涉及可靠性计算技术领域。更具体地，涉及一种针对路由方向单调变化网络的容错曼哈顿路由方法。

背景技术

在诸多类型的计算机网络和片上网络中，曼哈顿路由方法(也称为最小路由方法)以其实现开销小、复杂度低等特性而得到了广泛的应用。由于网络中错误节点的不可避免性，使得设计能够避让错误节点的曼哈顿路由算法(也称为最小路由算法)成为一项很有意义的工作。

国内外有很多容错曼哈顿路由算法的工作，其中一个典型的做法就是基于错误块模型来设计容错路由算法，可以分为三个阶段：第一阶段是提出一种错误块模型以及相应的错误块构建方法；所谓的错误块是指包含了多个错误节点的、具有一定形状特征的节点的集合。错误块中的节点，无论是错误节点还是非错误节点，都不能被路由算法所到达。第二阶段是根据错误块来判断容错路径的存在性；如果存在容错路径，则进入第三阶段来寻找容错路径。已有的错误块模型下，错误块本身的构建过程复杂度较高如MCC错误块模型，而且判断是否存在容错路径的算法也比较复杂，有一些错误模块模型如只能容忍一个错误的容错路由算法、凸错误块模型以及防御区模型等甚至还会牺牲掉许多可用的非错误节点以及可用的容错路径，最终使得容错路由算法的复杂度很高以及可用性较低。这些错误块模型还有一个普遍存在的问题，那就是只能适用特定拓扑的网络以及特定的路由算法，普适性较低。

因此，需要提供一种复杂度低、普适性高且不牺牲可用容错曼哈顿路径的针对路由方向单调变化网络的容错曼哈顿路由方法。

发明内容

本发明的目的在于提供一种采用路径计数的策略的针对路由方向单调变化网络的容错曼哈顿路由方法，可以快速判断出路由方向单调变化的网络中是否存在容错曼哈顿路径，并给出了灵活的容错曼哈顿路径的寻路策略。

为达到上述目的，本发明采用下述技术方案：

一种针对路由方向单调变化网络的容错曼哈顿路由方法，该方法包括如下步骤：

S1、判断源节点和目标节点是否为错误节点，若两者至少有一个为错误节点则说明源节点和目标节点之间不存在容错曼哈顿路径，结束流程；若两者均非错误节点，则转入步骤S2；

S2、在源节点和目标节点在网络中位置已知的情况下，判断源节点和目标节点之间的每一个中间节点的被最小路由策略允许的下一跳节点，并记录每一个中间节点的被最小路由策略允许的上一跳节点，下一跳的方向是源节点到目标节点的方向，即可得知上一跳的方向是目标节点到源节点的方向，还需要说明的是：在完全适应性最小路由策略的情况下，不需要计算，原因在于每个节点的下一跳节点和上一跳节点都是被最小路由策略允许的下一跳节点和上一跳节点；而在部分适应性最小路由策略的情况下，则需要执行该部分适应性最小路由策略来计算出每个节点的被最小路由策略允许的下一跳节点和上一跳节点；

S3、将源节点的路径计数值设为非0；根据中间节点及其被最小路由策略允许的所有下一跳节点是否是错误节点，计算中间节点和目标节点的路径计数值，计算方法为：若中间节点为错误节点，则该中间节点的路径计数值为0；若中间节点非错误节点，则该中间节点的路径计数值为其所有被最小路由策略允许的上一跳节点的路径计数值的总和；目标节点的路径计数值为其所有被最小路由策略允许的上一跳节点的路径计数值的总和；需要说明的是：由于源节点的路径计数值是设定好的，所以计算中间节点和目标节点的路径计数值的计算先后顺序为由作为源节点的下一跳节点的中间节点至目标节点；源节点已经获取了网络中错误节点的位置信息；

S4、判断目标节点的路径计数值是否为0，若为0则说明源节点和目标节点之间不存在容错曼哈顿路径，结束流程；若不为0则说明源节点和目标节点之间存在容错曼哈顿路径，并且源节点和目标节点之间的容错曼哈顿路径的总数目等于目标节点D的路径计数值，转入步骤S5；

S5、将目标节点作为寻路的起点，从起点开始逐跳查找路径计数值不为0且被最小路由策略允许的上一跳节点直至查找到源节点，将由查找过程中被查找到的中间节点组成的路径作为源节点到目标节点之间的容错曼哈顿路径。

优选地，步骤S2中最小路由策略包括完全适应性最小路由策略和部分适应性最小路由策略，若步骤S2中的最小路由策略为完全适应性最小路由策略，则源节点和目标节点之间的每一个中间节点的下一跳节点均被直接判定为被最小路由策略允许的，并直接记录每一个中间节点的上一跳节点，不必再执行该完全适应性最小路由策略来加以判断；若步骤S2中的最小路由策略为部分适应性最小路由策略，则根据部分适应性最小路由策略判断源节点和目标节点之间的每一个中间节点的被部分适应性最小路由策略允许下一跳节点，并根据部分适应性最小路由策略记录每一个中间节点的被部分适应性最小路由策略允许的上一跳节点。

优选地，步骤S3中源节点的路径计数值设为1，这样，可以在最后得到源节点到目标节点之间的容错曼哈顿路径的同时，直接得到源节点到目标节点之间的容错曼哈顿路径的总数量。

优选地，步骤S5进一步包括如下子步骤：

S5.1、将目标节点作为寻路的起点，查找起点的路径计数值不为0且被最小路由策略允许的上一跳节点；

S5.2、将查找到的上一跳节点作为起点，查找起点的路径计数值不为0的且被最小路由策略允许的上一跳节点；

S5.3、迭代执行步骤S5.2直至查找到源节点，将由查找过程中被查找到的中间节点组成的路径作为源节点到目标节点之间的容错曼哈顿路径。

优选地，若查找到的路径计数值不为0且被最小路由策略允许的上一跳节点的数量为至少两个，则依据随机策略，维度优先策略或节点拥塞程度最小策略等选择上一跳节点，维度优先策略包括第一维优先策略或者最后一个维度优先策略等。

下面对本发明中的一些基本定义作进一步说明：

(1)曼哈顿路径(最小路径)的说明：路径长度为曼哈顿距离的路径。

(2)下一跳节点和上一跳节点的说明：给定两个相邻的节点A和B，如果从A节点到目标节点D的曼哈顿距离比从B节点到目标节点D的曼哈顿距离要多一跳，那么B节点就被称为A节点的下一跳节点，A节点就被称为B节点的上一跳节点。在不同的拓扑结构下，一个节点的下一跳或者上一跳节点的数目可能是不同的。例如，在一个M*N规模的2DMesh拓扑网络中，假设源节点S(1,1)位于目标节点D(M,N)的X-和Y-方向。如果当前节点为(i,j)(1<＝i<＝M,1<＝j<＝N),那么节点(i+1,j)(1<i+1<＝M)和节点(i,j+1)(1<j+1<＝N)都被称为当前节点的“下一跳节点”，原因在于当前节点与这两个节点都是相邻节点，并且这两个相邻节点离目标节点D的曼哈顿距离要比当前节点到D的曼哈顿距离小1；同时，当前节点也被称为这两个节点的“上一跳节点”。需要说明的是，在完全适应性路由算法下，当前节点的下一跳转发数据包的方向可以是其所有“下一跳节点”中的任意一个；如果网络中采用的是部分适应性路由算法，那么当前节点的多个下一跳节点中只能有一部分能够作为其下一跳的数据包转发节点。

(3)最小路由(minimalrouting)的说明：数据包从源节点出发沿着曼哈顿路径被传输到目标节点，该曼哈顿路径的寻找过程就称为最小路由。

(4)被最小路由策略允许的下一跳节点和被最小路由策略禁止的下一跳节点的说明：假设某当前节点一共存在M(M为大于等于0的整数)个下一跳节点。在完全适应性最小路由策略下，不用调用完全适应性最小路由策略进行计算，该节点能够向这M个下一跳节点转发数据包，这M个下一跳节点都被称为“被路由策略允许的下一跳节点”；而在部分适应性最小路由策略下，由于一些限制如转弯模型的限制，比如负向优先转弯模型和奇偶转弯模型等，需要调用转弯模型依次计算当前节点的“被部分适应性路由策略允许的下一跳节点”，则当前节点只能向部分下一跳节点转发数据包，这部分下一跳节点的数目被记为C’，C’值将小于M，这C’个下一跳节点被称为“被路由策略允许的下一跳节点”；那些虽然是该当前节点的下一跳节点但当前节点并不能向其转发数据包的节点被称为“被路由策略禁止的下一跳节点”，其数目为M-C’。

(5)被最小路由策略允许的上一跳节点和被最小路由策略禁止的上一跳节点的说明：假设某当前节点一共存在N(N为大于等于0的整数)个上一跳节点。在完全适应性最小路由策略下，不用调用完全适应性最小路由策略进行计算，这N个上一跳节点都有可能向当前节点转发数据包，这N个上一跳节点都被称为“被路由策略允许的上一跳节点”；在部分适应性最小路由策略下，由于一些限制如转弯模型的限制，比如负向优先转弯模型和奇偶转弯模型等，需要调用转弯模型依次计算当前节点的“被部分适应性路由策略允许的下一跳节点”，则这N个上一跳节点并不是都能够向当前节点转发数据包，可能只有其中的一部分上一跳节点能够向当前节点转发数据包，这部分上一跳节点的数目记为C’，其值将小于N。这C’个上一跳节点被称为当前节点的“被路由策略允许的上一跳节点”；其余的N-C’个虽然是该当前节点的上一跳节点但不能向当前节点转发数据包的节点被称为“被路由策略禁止的上一跳节点”。

(6)路径计数值的说明：在给定的最小路由策略下，从源节点出发，能够到达当前节点的容错曼哈顿路径的总数，该总数就被称为当前节点的路径计数值。显然，如果当前节点为错误节点，那么能够到达当前节点的容错曼哈顿路径的总数为0，即当前节点的路径计数值为0；如果当前节点为目的节点D，那么D的路径计数值就是从源节点到D的所有可用的容错曼哈顿路径的总数。

(7)路由方向的单调变化的说明：是指在寻路过程中，下一跳节点始终位于当前节点的、从源节点指向目标节点的方向。举个2DMesh网络中的例子：如果目标节点D位于源节点S的X+和Y+方向，那么从源节点指向目标节点的方向就包括X+和Y+方向，如果路由方向是单调变化的，无论当前节点位于何处，那么下一跳节点将始终位于当前节点的X+或Y+方向。

本发明的有益效果如下：

本发明所述技术方案由于与网络规模成线性关系，所以其复杂度很低，不会遗漏能够成为容错曼哈顿路径上中间节点的非错误节点；能够容忍任意位置处的错误节点；能够快速判断出容错曼哈顿路径的存在性；在存在容错曼哈顿路径的情况下，能够使用多种不同的策略来寻找出容错曼哈顿路径；而且，可以在基本不修改已有的多种完全或部分适应性最小路由算法的情况下来增强其容错功能，可以看做是已有的、路由方向单调变化的最小路由算法的容错功能添加版方法，大幅度提升了本发明的普适性，能够适用于所有路由方向单调变化、执行最小路由策略的网络，例如2DMesh片上网络、3DMesh片上网络或其它的Mesh结构的网络，具有较广的适用性等。

附图说明

下面结合附图对本发明的具体实施方式作进一步详细的说明；

图1示出针对路由方向单调变化网络的容错曼哈顿路由方法的流程图。

图2示出实施例一中在使用完全适应性最小路由策略的2DMesh网络中，当目标节点D位于源节点S的X+和Y+方向时，中间节点的路径计数值的示意图。

图3示出实施例一中在使用完全适应性最小路由策略的2DMesh网络中，当目标节点D位于源节点S的X+和Y+方向时，三种典型的寻找容错曼哈顿路径策略的执行过程的示意图。

具体实施方式

为了更清楚地说明本发明，下面结合优选实施例和附图对本发明做进一步的说明。附图中相似的部件以相同的附图标记进行表示。本领域技术人员应当理解，下面所具体描述的内容是说明性的而非限制性的，不应以此限制本发明的保护范围。

实施例一

如图1所示，本实施例提供的针对路由方向单调变化网络的容错曼哈顿路由方法，应用于使用完全适应性最小路由策略且路由方向是单调变化的2DMesh网络中，该方法包括如下步骤：

S1、判断源节点S和目标节点D是否为错误节点，若两者至少有一个为错误节点则说明源节点S和目标节点D之间不存在容错曼哈顿路径，结束流程；若两者均非错误节点，则转入步骤S2；

S2、在源节点S和目标节点D在网络中的位置已知的情况下，判断源节点S和目标节点D之间的每一个中间节点的被最小路由策略允许的下一跳节点，并记录每一个中间节点的被最小路由策略允许的上一跳节点，中间节点也称作中间路由器；在这里，由于2DMesh网络执行的是完全适应性最小路由策略，所以当前节点的所有下一跳节点都是“被最小路由策略允许的下一跳节点”，当前节点的所有上一跳节点都是“被最小路由策略允许的上一跳节点”。

S3、将源节点S的路径计数值设为1；根据中间节点及其被最小路由策略允许的所有下一跳节点是否是错误节点，计算中间节点和目标节点的路径计数值，计算方法为：若中间节点为错误节点，则该中间节点的路径计数值为0；若中间节点非错误节点，则该中间节点的路径计数值为其所有被最小路由策略允许的上一跳节点的路径计数值的总和；目标节点的路径计数值为其所有被最小路由策略允许的上一跳节点的路径计数值的总和；计算中间节点和目标节点的路径计数值的计算公式具体如下：

I)当目标节点D位于源节点S的X+和Y+方向时，计算公式为：

II)当D位于S的X-和Y-方向时，计算公式为：

III)当D位于S的X-和Y+方向时，计算公式为：

IV)当D位于S的X+和Y-方向时，计算公式为：

本实施例中的2DMesh网络的维度为2，可以按从低维到高维的顺序就是从X维(第0维)到Y维(第一维)或者从高维到低维的顺序来设计两重循环结构，依次计算每个节点的路径计数值；本实施例选择从低维到高维的顺序设计两重循环结构。根据源节点S与目标节点D的相对方向的不同，每个中间路由器的路径计数的次序也是不同的：

I)当目标节点D位于源节点S的X+和Y+方向时，采用对应的公式(1-1)来计算中间路由器的路径计数值，计算次序就是从S点开始沿着X+方向依次计算出本行(即第一行，Y维度上为1)所有的中间路由器的路径计数值；然后Y维度加1(因为在Y+方向上)，即开始在Y+方向的下一行上从X+方向上最初的节点开始沿着X+方向一一计算出本行所有的中间路由器的路径计

数值；然后Y维度上继续加1，即在Y+方向的再下一行上沿着X+方向一一计算出本行所有的中间路由器的路径计数值；依次类推，直到计算出Y+方向上最后一行上的、并且是X+方向上最后一个的中间路由器，即目标节点D，的路径计数值为止。

II)当目标节点D位于源节点S的X-和Y-方向时，采用对应的公式(1-2)来计算中间路由器的路径计数值，计算次序就是从S点开始沿着X-方向依次计算出本行(即最后一行)所有的中间路由器的路径计数值；然后Y维度减去1(因为在Y-方向上)，即开始在Y-方向的下一行上从X-方向上最初的节点沿着X-方向一一计算出本行所有的中间路由器的路径计数值；然后Y维度上继续减1，即在Y-方向的再下一行上沿着X-方向一一计算出本行所有的中间路由器的路径计数值；依次类推，直到计算出Y-方向上最后一行上的、并且是X-方向上最后一个的中间路由器，即目标节点D，的路径计数值为止。

III)当目标节点D位于源节点S的X-和Y+方向时，采用对应的公式(1-3)来计算中间路由器的路径计数值，计算次序就是从S点开始沿着X-方向依次计算出本行(即最后一行)所有的中间路由器的路径计数值；然后Y维度加1(因为在Y+方向上)，即开始在Y+方向的下一行上从X-方向上最初的节点沿着X-方向一一计算出本行所有的中间路由器的路径计数值；然后Y维度上继续加1，即在Y+方向的再下一行上沿着X-方向一一计算出本行所有的中间路由器的路径计数值；依次类推，直到计算出Y+方向上最后一行上的、并且是X-方向上最后一个的中间路由器，即目标节点D，的路径计数值为止。

IV)当目标节点D位于源节点S的X+和Y-方向时，采用对应的公式(1-4)来计算中间路由器的路径计数值，计算次序就是从S点开始沿着X+方向依次计算出本行(即最后一行)所有的中间路由器的路径计数值；然后Y维度减去1(因为在Y-方向上)，即开始在Y-方向的下一行上从X+方向上最初的节点沿着X+方向一一计算出本行所有的中间路由器的路径计数值；然后Y维度上继续减1，即在Y-方向的再下一行上沿着X+方向一一计算出本行所有的中间路由器的路径计数值；依次类推，直到计算出Y-方向上最后一行上的、并且是X+方向上最后一个的中间路由器，即目标节点D，的路径计数值为止。

S4、判断目标节点的路径计数值是否为0，若为0则说明源节点和目标节点之间不存在容错曼哈顿路径，结束流程；若不为0则转入步骤S5；

S5、将目标节点D作为寻路的起点，从起点开始逐跳查找路径计数值不为0且被最小路由策略允许的上一跳节点直至查找到源节点S，将由查找过程中被查找到的中间节点组成的路径作为源节点S到目标节点D之间的容错曼哈顿路径。

其中，步骤S5进一步包括如下子步骤：

S5.1、将目标节点作为寻路的起点，查找起点的路径计数值不为0且被最小路由策略允许的上一跳节点；

S5.2、将查找到的上一跳节点作为起点，查找起点的路径计数值不为0的且被最小路由策略允许的上一跳节点；

S5.3、迭代执行步骤S5.2直至查找到源节点，将由查找过程中被查找到的中间节点组成的路径作为源节点到目标节点之间的容错曼哈顿路径。

当目标节点D位于源节点S的X+和Y+方向时，每个中间点路径计数值的计算过程(即步骤S3)的伪代码如下：

IFsourcenode(1,1)ordestinationnode(M,N)isonefaultnode,thenexit；

C(1,1)＝1；/*源节点的路径计数值C设为1；*/

for(j＝2toN)/*N为网络长度*/

if((1,j)是一个错误节点)thenC(1,j)＝0；

elseC(1,j)＝C(1,j-1)；/*节点(1,j)只有一个上一跳节点*/

for(i＝2toM)/*M为网络宽度*/

if((i,1)是一个错误节点)thenC(i,1)＝0；

elseC(i,1)＝C(i-1,1)；/*节点(i,1)只有一个上一跳节点*/

For(j＝2toN)

For(i＝2toM)

If((i,j)isonefaultnode)thenC(i,j)＝0；

ElseC(i,j)＝C(i-1,j)+C(i,j-1)；/*节点(i,j)有两个上一跳节点.*/

If(C(M,N)！＝0)theremustexistfault-tolerantManhattanpathsandthenumberofthemisC(M,N)；

Elsetherearen’tanyfault-tolerantManhattanpaths.

当目标节点D位于源节点S的其它方向时，上述伪代码可以根据步骤S3的对应情况来作出相应调整。

下面以如图2所示的8*8的2DMesh网络，目标节点D(8,8)位于源节点S(1,1)的X+和Y+方向的具体情况对本实施例作进一步的说明：

该网络中有5个错误节点。采用的是完全适应性最小路由策略。其中由于目标节点位于源节点的X+和Y+方向，因此步骤S3中路径计数公式采用公式(1-1)。最终每个中间路由器的路径计数值的计算结果如图2所示：C(4,2)的值为4，C(4,3)的值为10，C(4,7)的值为1，…,C(8,8)的值为568。这就意味着源节点S至目标节点D之间有568条可用的容错曼哈顿路径。

在计算出每一个中间路由器的路径计数值之后，可以看出，图2中有多个中间路由器的上一跳节点的路径计数值不为0，并且被最小路由策略允许，而且数目有多个，此时曼哈顿路径的寻路策略就有多种。基于图2的路径计数的结果，两种典型的寻路策略是：横向优先寻路策略和纵向优先寻路策略。所谓的横向优先寻路算法，其基本思路就是当X方向和Y方向同时存在上一跳节点的时候，优先选择X方向的上一跳节点作为目标路径的下一个中间节点。所谓的纵向优先寻路算法，其基本思路就是当X方向和Y方向同时存在上一跳节点的时候，优先选择Y方向的上一跳节点作为目标路径的下一个中间节点。其它的寻路策略可以是这两种策略的一个折中方案，其基本思路是当X方向和Y方向同时存在上一跳节点的时候，可以根据上一跳节点的拥塞程度或者其它因素，有目的地或随机地从中选择出一个上一跳节点作为目标路径的下一个中间节点。

给定源节点(1,1)和目标节点(M,N)(M,N均为大于1的整数)，则横向优先寻路策略(即步骤S5的一种实施方法)的伪代码如下：

当源节点S和目标节点D的相对位置变化时，上述伪代码可做相应的调整，本实施例不再对此进行赘述。

给定源节点(1,1)和目标节点(M,N)(M,N均为大于1的整数)，则纵向优先寻路策略(即步骤S5的第二种实施方法)的伪代码如下：

当源节点和目标节点的相对位置变化时，该伪代码可做相应的调整，本实施例不再对此进行赘述。

在图2所示的路径计数结果的基础上，图3示出了上述两种典型的寻路策略以及一种介于这两种策略之间的折中寻路策略(即步骤S5的其它实施方法)的执行的例子：从D点出发，按照横向优先(图3中虚线)、纵向优先(图3中点-线段)或者位于这两者之间的其它折中选择方法(图3中的实线，但其仅仅是其中一种折中情况，也可以有其它的折中方法，本实施例中对路径寻找方法不做限制)。

实施案例二

本实施例提供的针对路由方向单调变化网络的容错曼哈顿路由方法，应用于使用部分适应性最小路由策略且路由方向是单调变化的2DMesh网络中，该方法包括如下步骤：

S1、判断源节点S和目标节点D是否为错误节点，若两者至少有一个为错误节点则说明源节点S和目标节点D之间不存在容错曼哈顿路径，结束流程；若两者均非错误节点，则转入步骤S2；

S2、在源节点S和目标节点D在网络中的位置已知的情况下，执行已有的部分适应性最小路由算法如基于奇偶转弯模型或者负向优先转弯模型或者其它转弯模型的部分适应性最小路由算法，判断每一个中间节点(中间路由器)的“被最小路由策略允许的所有的下一跳节点”，并记录每一个中间节点的“被最小路由策略允许的所有的上一跳节点”；需要说明的是，这些部分适应性最小路由策略都是现有的方法，例如基于奇偶转弯模型的部分适应性最小路由算法或者基于负向优先转弯模型的部分适应性最小路由算法等，但这些方法并不具有容错功能。

S3、将源节点S的路径计数值设为1；根据中间节点及其被最小路由策略允许的所有下一跳节点是否是错误节点，计算中间节点和目标节点的路径计数值，计算方法为：若中间节点为错误节点，则该中间节点的路径计数值为0；若中间节点非错误节点，则该中间节点的路径计数值为其所有被最小路由策略允许的上一跳节点的路径计数值的总和；目标节点的路径计数值为其所有被最小路由策略允许的上一跳节点的路径计数值的总和；计算中间节点和目标节点的路径计数值的计算公式具体如下：

I)当目标节点D位于源节点S的X+和Y+方向时，计算公式为：

II)当目标节点D位于源节点S的X-和Y-方向时，计算公式为：

III)当目标节点D位于源节点S的X-和Y+方向时，计算公式为：

IV)当目标节点D位于源节点S的X+和Y-方向时，计算公式为：

本2DMesh网络的维度为2，这里选择的维度次序是从低维到高维的顺序，即从X维(第0维)到Y维(第一维)，来设计两重循环结构，如果要使用相反的维度次序时使用者可自行推导。根据S与D的相对方向的不同，每个中间路由器的路径计数的次序也是不同的：

I)当目标节点D位于源节点S的X+和Y+方向时，采用对应的公式(2-1)来计算中间路由器的路径计数值，计算次序就是从S点开始沿着X+方向依次计算出本行(即第一行，Y维度上为1)所有的中间路由器的路径计数值；然后Y维度加1(因为在Y+方向上)，即开始在Y+方向的下一行上从X+方向上最初的节点开始沿着X+方向一一计算出本行所有的中间路由器的路径计数值；然后Y维度上继续加1，即在Y+方向的再下一行上沿着X+方向一一计算出本行所有的中间路由器的路径计数值；依次类推，直到计算出Y+方向上最后一行上的、并且是X+方向上最后一个的中间路由器，即目标节点D，的路径计数值为止。

II)当目标节点D位于源节点S的X-和Y-方向时，采用对应的公式(2-2)来计算中间路由器的路径计数值，计算次序就是从S点开始沿着X-方向依次计算出本行(即最后一行)所有的中间路由器的路径计数值；然后Y维度减去1(因为在Y-方向上)，即开始在Y-方向的下一行上从X-方向上最初的节点沿着X-方向一一计算出本行所有的中间路由器的路径计数值；然后Y维度上继续减1，即在Y-方向的再下一行上沿着X-方向一一计算出本行所有的中间路由器的路径计数值；依次类推，直到计算出Y-方向上最后一行上的、并且是X-方向上最后一个的中间路由器，即目标节点D，的路径计数值为止。

III)当目标节点D位于源节点S的X-和Y+方向时，采用对应的公式(2-3)来计算中间路由器的路径计数值，计算次序就是从S点开始沿着X-方向依次计算出本行(即最后一行)所有的中间路由器的路径计数值；然后Y维度加1(因为在Y+方向上)，即开始在Y+方向的下一行上从X-方向上最初的节点沿着X-方向一一计算出本行所有的中间路由器的路径计数值；然后Y维度上继续加1，即在Y+方向的再下一行上沿着X-方向一一计算出本行所有的中间路由器的路径计数值；依次类推，直到计算出Y+方向上最后一行上的、并且是X-方向上最后一个的中间路由器，即目标节点D，的路径计数值为止。

IV)当目标节点D位于源节点S的X+和Y-方向时，采用对应的公式(2-4)来计算中间路由器的路径计数值，计算次序就是从S点开始沿着X+方向依次计算出本行(即最后一行)所有的中间路由器的路径计数值；然后Y维度减去1(因为在Y-方向上)，即开始在Y-方向的下一行上从X+方向上最初的节点沿着X+方向一一计算出本行所有的中间路由器的路径计数值；然后Y维度上继续减1，即在Y-方向的再下一行上沿着X+方向一一计算出本行所有的中间路由器的路径计数值；依次类推，直到计算出Y-方向上最后一行上的、并且是X+方向上最后一个的中间路由器，即目标节点D，的路径计数值为止。

S4、判断目标节点的路径计数值是否为0，若为0则说明源节点和目标节点之间不存在容错曼哈顿路径，结束流程；若不为0则转入步骤S5；

S5、将目标节点D作为寻路的起点，从起点开始逐跳查找路径计数值不为0且被最小路由策略允许的上一跳节点直至查找到源节点S，将由查找过程中被查找到的中间节点组成的路径作为源节点S到目标节点D之间的容错曼哈顿路径。

其中，步骤S5进一步包括如下子步骤：

S5.1、将目标节点作为寻路的起点，查找起点的路径计数值不为0且被最小路由策略允许的上一跳节点；

S5.2、将查找到的上一跳节点作为起点，查找起点的路径计数值不为0的且被最小路由策略允许的上一跳节点；

S5.3、迭代执行步骤S5.2直至查找到源节点，将由查找过程中被查找到的中间节点组成的路径作为源节点到目标节点之间的容错曼哈顿路径。

在举例说明上述实施步骤时，考虑到部分适应性路由算法能够采用的转弯模型的类型比较多，有西向优先转弯模型、负向优先转弯模型、北向最小转弯模型和奇偶转弯模型等。在相同的网络拓扑下，执行这些不同的部分适应性最小路由策略时，每个中间节点的“被最小路由策略允许的下一跳节点以及上一跳节点”也都是不同的，下面仅列举最为广泛使用的基于奇偶转弯模型的部分适应性最小路由策略，在基于奇偶转弯模型的部分适应性最小路由策略下，本实施例提供的上述步骤S2和S3的的伪代码如下：

当给定源节点S(1,1)和目标节点D(NumRow,NumColumn)并且假设D在S的东北方向时，进行路径计数的伪代码如下：

for(i＝1；i<＝NumRow；i++)

for(j＝1；j<＝NumColumn；j++)

{minimalOE(i,j,1,1,NumRow,NumColumn,DIRC1)；//步骤S2

if(fault[i][j]＝＝TRUE)c[i][j]＝0；

elseif(i＝＝1&&j＝＝1){c[i][j]＝1；}

elseif(i＝＝1&&j>1){

if(DIRC1[i][j-1][East]＝＝TRUE)c[1][j]＝c[1][j-1]；

elsec[1][j]＝0；

}

elseif(i！＝1&&j＝＝1){

if(DIRC1[i-1][j][North]＝＝TRUE)c[i][1]＝c[i-1][1]；

elsec[i][1]＝0；

}

else{

if(DIRC1[i-1][j][North]＝＝TRUE&&DIRC1[i][j-1][East]＝＝TRUE)

c[i][j]＝c[i-1][j]+c[i][j-1]；

elseif(DIRC1[i-1][j][North]＝＝TRUE&&DIRC1[i][j-1][East]＝＝FALSE)

c[i][j]＝c[i-1][j]；

elseif(DIRC1[i-1][j][North]＝＝FALSE&&DIRC1[i][j-1][East]＝＝TRUE)

c[i][j]＝c[i][j-1]；

elsec[i][j]＝0；//前一跳节点不可达到本节点的情况下，即上一跳节点是“被最小路由策略禁止的上一跳节点”，本节点路径计数值被初始化为0；

}

}

在上述伪代码中，minimalOE()函数为步骤S2的一种实施方法，其调用了已有的基于奇偶转弯模型的部分适应性最小路由算法函数，功能是在给定源节点(1,1,)和目标节点(NumRow,NumColumn)的情况下，计算出当前节点(i,j)的“被最小路由策略允许的下一跳节点”(用三维数组DIRC1[i][j][4]来表示节点(i,j)在东/西/南/北四个方向上允许转发数据包的情况)的情况，其过程可以参考Ge-MingChiu于2000年发表在IEEETransactionsonparallelanddistributedsystems杂志上的论文“TheOdd-EvenTurnmodelforadaptiverouting”，本文不再对此进行赘述。该函数的参数i,j是指当前节点的X和Y坐标值；第三、四、五、六个参数分别指源节点的X和Y坐标值和目标节点的X和Y坐标值，可以由程序员自由指定源节点和目标节点的坐标位置。当采用基于其它转弯模型的部分适应性最小路由算法时，可以直接将本函数替换为相应的部分适应性最小算法。除去minimalOE()函数之外的其它代码为步骤S3的实施过程。

当目标节点D位于源节点S的其它方向时，调整上述伪代码中的方位以及坐标即可，本实施例不再对此赘述。

在路径计数的基础上，查找容错曼哈顿路径的方法(即步骤S5)同样可以采用多种寻路策略，该部分伪代码类似实施例一中给出伪代码。以纵向优先策略为例，假设源节点为(1,1)，目标节点为(M,N)，其伪代码如下：

需要说明的是，只要当前节点的路径计数值不为0，则说明其必然存在至少一个“被最小路由策略允许的上一跳节点”；在2DMesh结构下，节点(i,j)的上一跳节点要么是(i,j-1)，要么是(i-1,j)，或者是这两个上一跳节点同时存在，不会存在同时不存在这两个上一跳节点的情况。也就是说，从目标节点开始，不断查询路径计数值不为0的“被最小路由策略允许的上一跳节点”，则总是能够找到一个从D到S的容错曼哈顿路径的，或者说总是能够找到一个从S到D的容错曼哈顿路径的。

如果要采用横向优先寻路策略或其它折中的寻路策略的话，将上述代码中“被最小路由策略允许的上一个节点”的部分进行相应的修改即可，本实施例不再对此赘述。

实施案例三

本实施例提供的针对路由方向单调变化网络的容错曼哈顿路由方法，应用于使用完全适应性最小路由策略且路由方向是单调变化的3DMesh网络中，该方法包括如下步骤：

S1、判断源节点S和目标节点D是否为错误节点，若两者至少有一个为错误节点则说明源节点S和目标节点D之间不存在容错曼哈顿路径，结束流程；若两者均非错误节点，则转入步骤S2；

S2、在源节点S和目标节点D在网络中的位置已知的情况下，判断源节点S和目标节点D之间的每一个中间节点(中间路由器)的被最小路由策略允许的下一跳节点，并记录每一个中间节点的被最小路由策略允许的上一跳节点；在完全适应性最小路由策略下，当前节点的所有下一跳节点都是“被最小路由策略允许的下一跳节点”，当前节点的所有上一跳节点都是“被最小路由策略允许的上一跳节点”；

S3、将源节点S的路径计数值设为1；根据中间节点及其被最小路由策略允许的所有下一跳节点是否是错误节点，计算中间节点和目标节点的路径计数值，计算方法为：若中间节点为错误节点，则该中间节点的路径计数值为0；若中间节点非错误节点，则该中间节点的路径计数值为其所有被最小路由策略允许的上一跳节点的路径计数值的总和；目标节点的路径计数值为其所有被最小路由策略允许的上一跳节点的路径计数值的总和；计算中间节点和目标节点的路径计数值的计算公式具体如下：

I)当目标节点D位于源节点S的X+、Y+和Z+方向时，计算公式为：

II)当目标节点D位于源节点S的X-，Y-和Z-方向时，计算公式为：

III)当目标节点D位于源节点S的X+，Y+和Z-方向时，计算公式为：

IV-VIII)目标节点D位于源节点S的相对位置还有其它5种，本领域技术人员很容易通过前述两个实施例中的计算公式以及这三个给出的计算公式推导出来，本实施例不再赘述其它5种计算公式；

本实施例中的3DMesh网络的维度为3，可以有三种维度次序；本实施例从X维(第0维)到Y维(第1维)再到Z维(第2维)的次序来设计三重的循环结构，以便遍历计算每一个网络节点的路径计数值。根据源节点S与目标节点D的相对方向的不同，每个中间路由器的路径计数的次序也是不同的：

I)当目标节点D位于源节点S的X+、Y+和Z+方向时，采用对应的计算公式(3-1)来以X->Y->Z的维度次序沿着X+,Y+以及Z+的方向依次计算每一个中间路由器的路径计数值，直到目标节点D的路径计数值计算完成为止。

II)当目标节点D位于源节点S的X-、Y-方向和Z-方向时，采用对应的计算公式(3-2)来以X->Y->Z的维度次序沿着X-,Y-以及Z-的方向依次计算每一个中间路由器的路径计数值，直到目标节点D的路径计数值计算完成为止。

III)当目标节点D位于源节点S的X+、Y+方向和Z-方向时，采用对应的计算公式(3-3)来以X->Y->Z的维度次序沿着X+,Y+以及Z-的方向依次计算每一个中间路由器的路径计数值，直到目标节点D的路径计数值计算完成为止。

IV-VIII)当目标节点D位于源节点S的其它5种方向之一时，分别采用对应的计算公式来以X->Y->Z的维度次序沿着相应的维度递增或递减方向依次计算每一个中间路由器的路径计数值，直到目标节点D的路径计数值计算完成为止。

S4、判断目标节点的路径计数值是否为0，若为0则说明源节点和目标节点之间不存在容错曼哈顿路径，结束流程；若不为0则说明存在容错曼哈顿路径，并且容错曼哈顿路径的总数目等于目标节点D的路径计数值，转入步骤S5；

S5、将目标节点D作为寻路的起点，从起点开始逐跳查找路径计数值不为0且被最小路由策略允许的上一跳节点直至查找到源节点S，将由查找过程中被查找到的中间节点组成的路径作为源节点S到目标节点D之间的容错曼哈顿路径。

其中，步骤S5进一步包括如下子步骤：

S5.1、将目标节点作为寻路的起点，查找起点的路径计数值不为0且被最小路由策略允许的上一跳节点；

S5.2、将查找到的上一跳节点作为起点，查找起点的路径计数值不为0的且被最小路由策略允许的上一跳节点；

S5.3、迭代执行步骤S5.2直至查找到源节点，将由查找过程中被查找到的中间节点组成的路径作为源节点到目标节点之间的容错曼哈顿路径。

在计算出每一个中间路由器的路径计数值之后，可以依照前面所提到的多种寻路策略和实施例一和二，从目标节点D点开始寻路，不断寻找当前节点的“被最小路由策略允许的、并且路径计数值不为0的上一跳节点”来作为路径上的一个中间节点，直到寻找到源节点S点为止，具体过程不再赘述。

依据上述三个实施例，本领域技术人员可以推演出3DMesh网络下基于部分适应性最小路由策略的容错曼哈顿路由方法。进一步的，还可以推演出其他路由方向单调变化的网络中的基于完全适应性最小路由策略或者部分适应性最小路由策略的容错曼哈顿路由方法。因此，说明书中不再一一列举。

显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定，对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动，这里无法对所有的实施方式予以穷举，凡是属于本发明的技术方案所引伸出的显而易见的变化或变动仍处于本发明的保护范围之列。