修改的基于树的多播路由方案

摘要

本发明公开了一种修改的基于树的多播路由方案。在具有在多个彼此之间传递数据的节点的网状网络中，可以发起并执行大量数据传输来将数据送到正确的处理节点进行执行。为了将数据送到该数据需要去的地方(例如，正确的目的地节点)，使用路由算法定义来定义规则集，用于在节点之间高效地传送数据直到达到目的地节点。为了保证所有数据以合理地高效方式在节点之间正确传输的目的，路由算法可以将节点子集定义成区域，继而经由该区域发送数据。通过识别一组目的地节点之间的特定相邻关系，并且通过重新路由数据使其通过不同于目的地节点所驻留区域的区域来利用这种相邻，可以实现更好的整体效率。

说明书

技术领域

本发明涉及网状网络中的路由。

背景技术

网状联网是这样一种类型的联网，其中网络中的每个节点都可以 充当独立的路由器，无论该节点是否连接到另一网络。网状网络可以 由任意数量的计算实体来实现。例如，若干无线计算设备(诸如，移 动智能电话)可以形成一个网状网络。如另一示例，单个集成电路(IC) 芯片或多个IC上的若干处理部件可以形成一个网状网络。这种网状 网络，利用多个处理节点以及节点之间的路径，允许实现持续连接以 及在坏掉的或阻塞的路径周围通过使用节点之间用于数据传输的不 同路径来重新配置。节点全部彼此连接的网状网络是全连通网络。

网状网络的一个特定方面已经在被分类为超大规模集成(VLSI) 芯片的IC中实现。在这些IC中，处理节点的二维(2D)网可以在单 个扁平IC芯片上实现。这种多处理器IC越来越广泛地被用来高效地 使用现代VLSI技术可获得的越来越多数量的晶体管。随着处理节点 数量的增加，片上网络(即，2D网状网络)的实现促进了各个处理 节点之间的通信和数据传输。用于促进这种通信和数据传输的整体方 案被称为路由算法或简单路由。针对IC上的2D网状网络的常规路由 提供了非常简单的网格状网络，该网格状网络可以得到芯片架构中的 短连接。然而，当形成多个通信和数据传输路径时，存在大量问题。 当一个节点可能需要向若干节点广播数据时，常规路由算法效率不高 并且麻烦，这是因为即便可以获得较短且较高效的路由，但在并发路 径或并行分支路径中一些数据可能被复制。

发明内容

根据本发明的一个方面，提供了一种方法，包括：确定从源节点 向多个目的地节点发送的多播消息；针对每个目的地节点，在多个区 域之中确定将与相应的目的地节点关联的一个区域；标识在不同区域 中且彼此相邻的目的地节点对；针对每个节点对，确定从所述源节点 开始的更高效的数据传输路径；以及改变与所述节点对中的被确定为 未与所述更高效的数据传输路径关联的目的地节点相关联的区域。

根据本发明的另一方面，提供了一种方法，包括：标识网状网络 中用于接收数据集的多个节点；以及根据路由算法将所述数据路由到 每个节点，所述路由算法针对数据传输利用最少数量的中间节点。

根据本发明的另一方面，提供了一种网状网络，包括：节点矩阵； 以及所述节点矩阵中的源节点，可操作用于向所述矩阵中的多个其他 节点发送数据；其中所述网状网络由支持通过相邻目的地节点路由数 据的路由算法管理。

根据本发明的另一方面，提供了一种处理器，包括：按行和列布 置在网状网络中的多个节点，可操作用于根据路由算法发送和接收数 据。所述路由算法包括：确定源节点以及从所述源节点接收数据的多 个目的地节点；将每个目的地节点与多个区域中的一个区域相关联； 确定一个区域中的目的地节点是否与另一区域的目的地节点相邻，并 且如果相邻，则计算对于将从所述源节点传输的数据而言哪个区域是 更高效的区域；将不同区域中的相邻的目的地节点与所述更高效的区 域相关联；以及向所有目的地节点传输数据。

根据本发明的另一方面，提供了一种系统，包括：网络中的多个 处理节点，可操作用于根据路由算法从第一节点向多个其他节点传输 数据。所述算法包括：将除了所述第一节点之外的每个节点与多个区 域中的一个区域相关联；确定一个区域中的节点是否与另一区域中的 节点相邻，并且如果相邻，则计算对于将从所述第一节点传输的数据 而言哪个区域是更高效的区域；将不同区域中的相邻节点与所述更高 效的区域相关联；以及向所述节点传输数据。

附图说明

结合附图参考下面的详细描述，将会更容易以及更好地理解这里 所公开主题的实施方式。

图1是根据这里所公开主题的实施方式的具有用于基于树的二维 网络的映射方案的4×4网络的框图。

图2是根据这里所公开主题的实施方式的具有用于基于树的二维 网络的未修改路由方案的6×6网络的框图。

图3是根据这里所公开主题的实施方式的具有用于基于树的二维 网络的经修改的路由方案的6×6网络的框图。

图4是可以实现图3的网状网络系统300的计算机系统400的实 施方式的框图。

具体实施方式

下面的讨论是为了使本领域技术人员能够制作并使用这里所公 开的主题而提出的。本文所描述的一般原理可以在不背离当前具体描 述的实施方式的精神与范围的情况下应用于除以上详述的实施方式 和应用之外的其他实施方式和应用。当前公开内容并非旨在限于示出 的实施方式，而是应符合同本文所公开或建议的原理和特征相一致的 最广泛的范围。

在讨论各种实施方式的特定细节之前，介绍对该主题的概述。在 具有多个在彼此之间传递数据的节点的网状网络中，可以发起和执行 大量数据传输来将消息(例如，数据)送到正确的处理节点进行执行。 为了将数据送到该数据需要去的地方(例如，正确的目的地节点)， 使用路由算法来定义在节点之间高效地传送数据直到到达目的地节 点的规则集。为了保证所有数据以合理地高效方式在节点之间正确传 输的目的，路由算法可以将节点子集定义成区域，继而将数据发送至 这些区域中以便进行路由。如下面将更加详细地进行讨论的那样，通 过识别一组目的地节点之间的特定相邻关系，并且通过重新路由数据 使其通过不同于目的地节点所驻留区域的区域来利用这种相邻，可以 实现更好的整体效率。因此，数据传输活动的总等级可以通过使用单 个路径将类似的数据路由到多个相邻的目的地节点而得到减少。这些 和其他概念参考图1-图4进一步详细描述。

图1是根据这里所公开主题的一个实施方式的具有用于基于树的 二维网络100的映射方案的4×4矩阵(例如，网络)的框图。在基 于树的二维网络中，每个节点110可以由映射方案的上下文和最终是 路由算法的上下文中的特定标识符来引用。因此，映射方案的基础固 有地影响基于每个节点的标识的路由算法的本性。

任何给定的二维网状网络将具有m行和n列。为了实现基于树的 多播路由算法，网络中的所有节点必须首先利用标识分配函数l进行 标识。用于m×n的2D网状网络的函数l可以依据节点的x与y坐 标表示如下：

在该4×4网络的映射方案中，可以用标识符0-15将节点110标 识为16个不同节点中的一个。此示例中的第一节点可以是左下方的 节点并且标识为节点0。映射方案继而沿底行向右相继地将节点标识 为节点1-3。接下来，标识方案移至第二行，但停留在该网络的右方 的节点4。方案在标识节点5-7的过程中移回到左方，继而类似地移 至第三行并且再次向右移动。重复该模式直到所有节点都由唯一节点 标识符标识-在此示例中，如图1中所示为0与15之间的节点标识符。 利用这种适当的映射方案，路由算法可以使用这些用于数据路由的节 点标识来实现。下面参考图2和图3描述两个此类路由算法。

图2是根据这里所公开主题的实施方式的具有用于基于树的二维 网络的简单路由方案的6×6矩阵(例如，网络)200的框图。为了示 例说明的目的，贯穿本公开将使用一个示例场景。该示例包括将向网 络200中的若干目的地节点发送多播消息(例如，数据)的源节点 Pi。因此，为了易于说明，在该示例中，源节点Pi不是边缘节点(edge  node)并且对应于标识为P15的节点。这种源节点Pi将必然具有四 个相邻节点，其根据映射方案中标识分配的标号按递减方式标注为 J1、J2、J3和J4。即，节点标识符确定标签，使得J1＞J2＞J3＞J4，例 如，对于具有P15标识符的源节点Pi，J1将是标识为节点P20的最 大相邻节点，J2将是节点P16，J3将是节点P14以及J4将是节点P8。 对于该映射方案和路由算法，相邻节点定义为在垂直或水平方向直接 相邻于源节点Pi的节点，例如，在相同行或列中并且没有任何中间 节点。对角线节点不认为是相邻。

利用定义为J1-J4的四个相邻节点，可以将所有其他节点定义为 与一个且只与一个相邻节点J1-J4相关联的标号区域(适当地命名为 区域1-4)的一部分。根据以下等式，将网状网络200中的所有其他 节点定义到区域中：

■区域1：标号在[J1，(m×n)-1]之间的节点；

■区域2：标号在[J2，J1-1]之间的节点；

■区域3：标号在[J4+1，J3]之间的节点；以及

■区域4：标号在[0，J4]之间的节点。

当Pi接收多播消息时，其从消息的分组报头中提取该消息的目的 地集D，继而生成对应于每个区域中的目的地节点的四个新目的地子 集D1、D2、D3和D4。规则集可以如下：

■通过从D中选出区域1中的目的地节点来生成D1，并且如 果D1不为空(例如，区域1中存在集合D中的至少一个 目的地节点)，则利用新目的地集D1信息向J1发送消息；

■通过从D中选出区域2中的目的地节点来生成D2，并且如 果D2不为空，则利用新目的地集D2信息向J2发送消息；

■通过从D中选出区域3中的目的地节点来生成D3，并且如 果D3不为空，则利用新目的地集D3信息向J3发送消息； 以及

■通过从D中选出区域4中的目的地节点来生成D4，并且如 果D4不为空，则利用新目的地集D4信息向J4发送消息。 根据该适当的规则集，继而向四个相邻节点J1或J2或J3或J4 中的一个发送来自消息集D的适当消息。当适当的相邻节点利用新目 的地子集信息接收多播消息时，可以高速缓存该多播消息数据。如果 该相邻节点是真正的目的地节点(即，该节点是消息集D中的特定数 据指定的最终目的地)，则不需要将该数据传向另一目的地节点。然 而，对于所有其他数据，可以重复该过程使得从新的源节点的角度定 义新区域1-4以及四个新相邻节点和多播消息D的四个新子集D1、 D2、D3和D4。重复此过程直到所有数据都到达其目的地节点。因此， 图2所示示例中的每个目的地节点的数据路径揭示了由不同节点之间 的箭头所标记的路径。

为了继续上文的示例，源节点P15可以肩负向目的地节点集 D＝{P2、P5、P6、P9、P13、P22、P29、P33、P35}发送多播消息的任 务。在向后续节点传输多播消息之前，源节点P15将首先生成四个新 目的地集D1、D2、D3和D4。对于源节点P15，其四个相邻节点J1、 J2、J3和J4是P20、P16、P14和P8，相应地对应于四个区域1-4， 该四个区域在每个区域中具有如下相应的节点：[P20-P35]、[P16-P19]、 [P9-P14]和[P0-P8]。因此可以计算四个新目的地集D1-D4：D1＝{P22、 P29、P33、P35}；D2＝{空}；D3＝{P9、P13}以及D4＝{P2、P5、P6}。

因为目的地集D1、D3和D4不为空，所以源节点P15将利用新 目的地集D1、D3和D4的信息向J1、J3和J4传输消息。源节点P15 不需要向J2传输消息，因为D2为空，这意味着区域2中没有目的地 节点。

当P20、P14或P8均接收多播消息D的相应子集(例如，分别为 D1、D3或D4)时，这些节点中的每个节点现在都变成肩负发送其相 关联的子集作为新多播消息的任务的源节点，该新多播消息具有以与 上文讨论的方式相同的方式确定的其相应目的地集。因此，重复该两 步过程直到所有目的地集为空(例如，所有消息都已经达到其相应的 目的地节点)。

虽然图2中描绘的基于树的多播路由算法成功地向所有适当的目 的地节点传输了多播消息D，但是该执行没有利用节点架构。即，一 旦将目的地节点置于一个目的地集中，对多播消息的路由便限制于完 全通过单个区域的路径。因此，多播消息为了达到目的地节点必须通 过的非目的地节点的数量(即，节点传输的数量-贯穿本公开的剩余 部分，节点传输的数量被称为“跳(hop)”并且由图2中节点之间 的箭头表示)可能更大，虽然某些目的地节点彼此相邻，但是位于不 同的初始区域中。

考虑图2中的示例，目的地节点P2和P9以及目的地节点P13和 P22是出现在不同区域(关于原始源节点Pi而言)中的相邻目的地节 点对的示例。目的地节点P2和P9分别在区域4和区域3中。类似地， 目的地节点P13和P22分别在区域3和区域1中。因此，关于目的地 节点P13和P22的比较，目的地节点P22将从节点P21接收多播消息， 而P13将经由两跳从P14接收多播消息D。为了到达目的地节点P22， 尽管节点P20和P21不是目的地节点，但是多播消息D必须经历三 跳从源节点P15通过节点P20和节点P21。因此，通过一定程度的冗 余和并行路径，总共需要5跳才能将多播消息送到这两个相邻节点 (P13和P22)。事实上，通过使目的地节点P22能够直接从目的地 节点P13接收多播消息D可以获得更高的性能。从节点P13到节点 P22传输多播消息只需要一跳，而从节点P20到节点P21到节点P22 传输多播消息D需要两跳。对图2所示路由算法中的跳数进行分析揭 示了总数为19。因此，如下面参考图3所讨论的，通过识别不同区域 中的相邻目的地节点可以实现更高效的路由算法。

图3是根据这里所公开主题的实施方式的6×6网络300的框图， 该6×6网络300使用修改的路由算法在基于树的二维网络中进行数 据通信。图3中所示的路由算法示例支持不同区域中相邻目的地节点 之间的直接通信。因此，可以实现高效率，因为使用图3中所示算法 的总跳数仅为17，其小于使用图2中所示路由算法所需的19跳。这 可以通过在第一遍分析来自源节点Pi的多播消息D时在确定目的地 子集中添加附加步骤来完成。

如前所述，当Pi接收多播消息时，其从消息的分组报头中提取该 消息的目的地集D(D＝{P2、P5、P6、P9、P13、P22、P29、P33、P35})， 继而生成对应于每个区域中目的地节点的四个新目的地集D1、D2、 D3和D4。应用与之前相同的规则集：

■通过从D中选出区域1中的目的地节点来生成D1，并且如 果D1不为空(例如，区域1中存在集合D中的至少一个 目的地节点)，则利用新目的地集D1信息向J1发送消息；

■通过从D中选出区域2中的目的地节点来生成D2，并且如 果D2不为空，则利用新目的地集D2信息向J2发送消息；

■通过从D中选出区域3中的目的地节点来生成D3，并且如 果D3不为空，则利用新目的地集D3信息向J3发送消息； 以及

■通过从D中选出区域4中的目的地节点来生成D4，并且如 果D4不为空，则利用新目的地集D4信息向J4发送消息。

接下来，执行对目的地节点的分析，以便确定是否存在任何目的 地节点彼此相邻并且在不同区域中。根据该路由算法中的该新步骤， 可能存在区域1中的节点与区域2的节点相邻；可能存在区域1中的 节点与区域3中的节点相邻；可能存在区域3中的节点与区域4中的 节点相邻；以及可能存在区域2中的节点与区域4中的节点相邻。在 检查多播消息目的地集D的过程中，按照定义，区域1不可能具有任 何节点与区域4中的节点相邻，以及区域2不可能具有任何节点与区 域3中的节点相邻。因此，将不同区域之间的、还是目的地节点的所 有边缘节点命名为目的地边缘节点(DEN)。因此，在此示例中，确 定目的地边缘节点集包括：

■针对区域1，对区域2的边缘节点是DEN_1，2＝{P₂₉}，并且对 区域3的边缘节点是DEN_1，3＝{P₂₂}；

■针对区域2，对区域1的边缘节点是DEN_2，1＝{}，并且对区 域4的边缘节点是DEN_2，4＝{}；

■针对区域3，对区域1的边缘节点是DEN_3，1＝{P₁₃}，并且对 区域4的边缘节点是DEN_3，4＝{P₉}；以及

■针对区域4，对区域2的边缘节点是DEN_4，2＝{P₆}，并且对 区域3的边缘节点是DEN_4，3＝{P₂}。

接下来，该过程可以基于对相邻目的地节点要求的跳数的比较， 将目的地节点从一个区域改变到另一区域(例如，从目的地集D1向 目的地集D2移动目的地节点)。通过查看目的地边缘节点集DEN_1，2、 DEN_1，3、DEN_2，1、DEN_2，4、DEN_3，1、DEN_3，4、DEN_4，2和DEN_4，3，可以 确定相邻目的地节点对，称为目的地边缘相邻对(DEAP)。在图3 所示的示例中，目的地边缘相邻对集是DEAP＝{{P13、P22}、{P2、 P9}}。

如果DEAP为空，则该算法不改变任何目的地集(D1、D2、D3 或D4)，并且所有多播消息与上文关于图2的示例相同地进行路由。 然而，如果DEAP不为空，则针对每个相邻节点对，对所识别出的对 中的每个节点进行跳数的比较。这可以通过针对该对中每个相邻目的 地节点计算距源节点Pi到的x-y距离来完成。例如，对于P13和P22， x-y距离(即，跳数)分别是2和3。因此，经由目的地节点P13向 目的地节点P22提供多播消息D更加高效，因为总跳数从5降至3。 因此，将目的地节点P22从目的地集D1移至目的地集D3。类似地， 将目的地节点P2从目的地集D4移至目的地集D3。结果修改的目的 地集变为：D1＝{P29、P33、P35}、D2＝{空}、D3＝{P2、P9、P13、P22} 和D4＝{P5、P6}。

这种修改的路由算法是占优势的，因为使用较少的资源在网状网 络300中路由多播消息D。在没有利用相邻目的地节点的未修改的算 法中，如图2的示例中所示总跳数为19。使用利用相邻目的地节点的 修改的路由算法，该总跳数减至17。跳数的减少意味着用于在网状网 络中不同节点之间传输数据的资源和功率的减少。这对于处理核、多 核处理器和布置在集成电路上的处理器而言可能特别有利。此外，通 过使用这种修改的路由算法，任何计算机网络都可以因节点之间流量 的减少而受益。此外，尽管参考图2和图3示出的示例应用于二维网 状网络，但是相同的原理可以应用于三维网络或多维网络，只要贯穿 整个路由算法保持“相邻节点(adjacent node)”的定义。可以存在 任何数量其中可以实现利用相邻目的地节点的修改的路由算法的场 景。图4中示出了一个这种示例。

图4是可以实现一个或多个图3的网状网络系统300的计算机系 统400的实施方式的框图。在该系统实施方式中，系统400可以包括 计算设备405，该计算设备405具有通过系统总线耦合至本地存储器 425的第一处理器410和第二处理器412。每个处理器410和412可 以包括如上文参考图3讨论的网状网络300。每个处理器410和412 可以操作用于在网状网络300中的部件(例如，节点)之间传输数据 以及与存储器415之间传输数据时，控制存储器415和每个相应网状 网络300。此外，可以使用附加的数据存储库和通信信道(诸如，通 过网络接口430)来与网状网络300传输数据，该网状网络300可以 是远程计算设备450的一部分。

在另一实施方式中，每个计算设备405和450还可以被看成是更 大的网状网络(未示出)的场景中的节点，使得每个更大的“计算设 备”节点可以相对于每个计算设备405和450处理器中的二维网状网 络300被看成是第三维。此外，每个网状网络300可以包括单个集成 电路管芯(die)或多个集成电路管芯。

在附图中示出并且在上文中详细描述了本文所讨论的主题的某 些示例说明的实施方式，但是对其易于做出各种改进和替代构造。然 而，应当明白，我们并无意将权利要求限制在所公开的特定形式，而 正相反，我们的意图是涵盖所有属于权利要求书的精神和范围内的改 进、替代构造以及等效形式。