US 12,413,503 B2 · Deadlock-free multipath routing for direct interconnect networks

Abstract

A method of routing for direct interconnect networks which generates multiple edge-disjoint paths between all source and destination nodes, while providing deadlock-free routing. The method requires limited use of virtual layers, which makes it suitable for less complex and more energy efficient hardware devices, and inter-layer edge-disjointedness is preferably integrated, which improves the throughput capacity of multipath traffic patterns. The method allows for distributed route calculation, wherein each node is responsible for generation of its own routes without the need for a centralized algorithm controller or elected master (with global knowledge), as it is, for instance, with InfiniBand. The method also involves a method of mapping arbitrary topologies from any dimension to bi-dimensional coordinate system. In addition, the method employs a lower number of turn restrictions than other prior solutions because it uses six direction types instead of only four as used in Up*/Down*. This increase in the number of directions translates into a more diversified set of routes, and consequently, better routing solutions.

Claims19

Dependent claims

A method for determining multiple deadlock-free pathways between nodes for routing packets in a direct interconnect network of n-dimensional topology comprising the steps of:

discovering all nodes and all connections between each such nodes in the direct interconnect network of n-dimensional topology, said connections comprising links for data transmission;
dividing the direct interconnect network into one or more virtual layers using a limited number of virtual channels, and selecting a distinct root node for each of the one or more virtual layers to act as a reference for dimensional reduction;
dimensionally reducing the direct interconnect network of n-dimensional topology to a bi-dimensional topology by mapping each node in the direct interconnect network into an (x, y) coordinate system based on each such node's relative position to the distinct root node within each of the one or more virtual layers;
assigning directions for each link from each node and determining turn restrictions to forbid turns that are not deadlock-free;
for each of the one or more virtual layers, discovering multiple edge-disjointed pathways between each node that adheres to the turn restrictions, whereby all such discovered pathways are deadlock-free, and each of the one or more virtual layers has a different set of such discovered pathways;
and
restricting the discovered pathways between each node to those pathways that are intra-layer edge-disjointed.

4 more elements

A method for deadlock-free routing of packets between nodes along multiple pathways in a direct interconnect network of n-dimensional topology comprising the steps of:

discovering all nodes and all connections between each such nodes in the direct interconnect network of n-dimensional topology via use of a link-state protocol, said connections comprising links for data transmission;
dividing the direct interconnect network into virtual layers using a limited number of virtual channels, and selecting a distinct root node for each of the virtual layers to act as a reference for dimensional reduction;
dimensionally reducing the direct interconnect network of n-dimensional topology to a bi-dimensional topology by mapping each node in the direct interconnect network into an (x, y) coordinate system based on each such node's relative position to the distinct root node within each of the virtual layers, wherein the x coordinate of the (x, y) coordinate system increases incrementally for each node in the order that nodes are visited by a pre-order traversal starting from the distinct root node, and the y coordinate of the (x, y) coordinate system represents hop-distance from the distinct root node;
assigning directions for each link from each node comprising assigning one of edge direction left-up, left, left-down, right-up, right, or right-down to each link from each node, and determining turn restrictions to forbid turns that are not deadlock-free comprising only allowing a sequence of two directions that will result in acyclic routing of packets;
for each of the virtual layers, discovering multiple edge-disjointed pathways between each node that adheres to the turn restrictions, whereby all such discovered pathways are deadlock-free, and each of the virtual layers has a different set of such discovered pathways, and wherein such discovering utilizes a greedy path discovery algorithm to ensure such discovered pathways are shortest pathways between each such node, and further comprises discovering as many such pathways as possible to increase path diversity;
restricting the discovered pathways between each node to those pathways that are intra-layer and inter-layer edge-disjointed;
and
removing any remaining paths that do not fall within any hardware or software-based restrictions, including one or more of maximum pathway length, maximum number of pathways, and maximum pathway length difference between pathways, and finalizing a routing table.

5 more elements

Dependencies are inferred from the claim text.

Deadlock-free multipath routing for direct interconnect networks

Life of this patent

Deadlock-free multipath routing for direct interconnect networks

Life of this patent

Abstract

Claims19