# US 2008/0186853 A1 · Method and apparatus for routing data in an inter-nodal communications lattice of a massively parallel computer system by employing bandwidth shells at areas of overutilization > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2008/0186853 A1 - Document ID: US20080186853A1 - Status: Published application - Kind: A1 - Application number: 11/672,315 - Filed: 2007-02-07 - Published: 2008-08-07 - Earliest claimed: 2007-02-07 - Assignees: International Business Machines Corporation - Inventors: Charles Jens Archer; Roy Glen Musselman; Amanda Peters; Kurt Walter Pinnow; Brent Allen Swartz; Brian Paul Wallenfelt - Web page: https://patentgrep.com/patent/US20080186853A1 ## CPC - H04L 45/12: Shortest path evaluation - H04L 45/02: Topology update or discovery - H04L 45/06: {Deflection routing, e.g. hot-potato routing} - H04L 45/125: based on throughput or bandwidth - H04L 45/126: {minimising geographical or physical path length} - H04L 45/128: for finding disjoint paths - H04L 45/22: {Alternate routing} - H04L 45/24: Multipath - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A massively parallel computer system contains an inter-nodal communications network of node-to-node links. An automated routing strategy routes packets through one or more intermediate nodes of the network to reach a final destination. The default routing strategy is altered responsive to detection of overutilization of a particular path of one or more links, and at least some traffic is re-routed by distributing the traffic among multiple paths (which may include the default path). An alternative path may require a greater number of link traversals to reach the destination node. ## Claims ### Claim 1 A method for inter-nodal packet routing in a parallel computer system, said parallel computer system comprising a plurality of nodes arranged in a network of node-to-node communications links for inter-nodal communications, each node comprising at least one processor for executing a respective application sub-process and a nodal memory, said method comprising the steps of: generating a plurality of packets for transmission by said network, each said packet to be transmitted from a respective source to a respective destination node; identifying a subset of said plurality of packets to be routed along a first path between a first node and a second node of said parallel computer system in accordance with a default routing strategy, said first path comprising at least one said link, said subset comprising multiple said packets; detecting an overutilization condition of said first path; identifying at least one alternative path for use by packets of said subset of packets, each said at least one alternative path being different from said first path and from each other alternative path; responsive to detecting said overutilization condition of said first path, assigning each packet of said subset of packets to a respective path of a plurality of paths, said plurality of paths including said at least one alternative path, wherein at least one respective packet of said subset of packets is assigned to each path of said plurality of paths; and automatically routing each packet of said subset of packets along its respective path as assigned by said assigning step. ### Claim 2 (depends on 1) The method of claim 1, wherein said plurality of paths includes said first path. ### Claim 3 (depends on 1) The method of claim 1, wherein said first path is a path having a minimal number of links between said first node and said second node, and at least one said alternative path is a path having a number of links greater than said minimal number. ### Claim 4 (depends on 1) The method of claim 1, wherein said step of detecting an overutilization condition of said first path comprises determining that a number of packets in said subset exceeds a pre-determined threshold. ### Claim 5 (depends on 4) The method of claim 4, wherein said pre-determined threshold varies depending on at least one of: (a) a volume of traffic in at least one said alternative path; and (b) a number of links in at least one said alternative path. ### Claim 6 (depends on 1) The method of claim 1, wherein a respective threshold is associated with each of a plurality of said alternative paths, each alternative path being identified as an alternative path for use by packets of said subset if the number of packets in said subset exceeds the respective threshold of the path, wherein at least some said thresholds are different. ### Claim 7 (depends on 1) The method of claim 1, wherein said step of assigning each packet of said subset of packets to a respective path of a plurality of paths comprises allocating packets of said subset to respective paths of said plurality of paths on a round robin basis. ### Claim 8 (depends on 1) The method of claim 1, wherein said steps of generating a plurality of packets, identifying a subset of said plurality of packets to be routed along a first path, detecting an overutilization condition of said first path, identifying at least one alternative path, and assigning each packet of said subset of packets to a respective path of a plurality of paths, are performed within said source node of said packets, said source node automatically routing each packet of said subset of packets along a first link of its respective path as assigned by said assigning step. ### Claim 9 (depends on 1) The method of claim 1, wherein each said path comprises a respective set of links, each said set of links having no links in common with any other said set of links. ### Claim 10 A computer program product for inter-nodal packet routing in a parallel computer system, said parallel computer system comprising a plurality of nodes arranged in a network of node-to-node communications links for inter-nodal communications, each node comprising at least one processor for executing a respective application sub-process and a nodal memory, said program product comprising: a plurality of computer executable instructions recorded on signal-bearing media, wherein said instructions, when executed by a first node of said computer system, cause the first node to perform the steps of: identifying a subset of a plurality of packets for transmission by said network to be routed along a first path between said first node and a second node of said parallel computer system in accordance with a default routing strategy, each packet of said plurality of packets to be transmitted from a respective source to a respective destination node, said first path comprising at least one said link, said subset comprising multiple said packets; detecting an overutilization condition of said first path; identifying at least one alternative path for use by packets of said subset of packets, each said at least one alternative path being different from said first path and from each other said alternative path; responsive to detecting said overutilization condition of said first path, assigning each packet of said subset of packets to a respective path of a plurality of paths, said plurality of paths including said at least one alternative path, wherein at least one respective packet of said subset of packets is assigned to each path of said plurality of paths; and causing each packet of said subset of packets to be automatically routed along its respective path as assigned by said assigning step. ### Claim 11 (depends on 10) The program product of claim 10, wherein said plurality of paths includes said first path. ### Claim 12 (depends on 10) The program product of claim 10, wherein each said packet of said subset is to be routed from said first node as a source node to said second node as a destination node. ### Claim 13 (depends on 10) The program product of claim 10, wherein said first path is a path having a minimal number of links between said first node and said second node, and at least one said alternative path is a path having a number of links greater than said minimal number. ### Claim 14 (depends on 10) The program product of claim 10, wherein said step of detecting an overutilization condition of said first path comprises determining that a number of packets in said subset exceeds a pre-determined threshold. ### Claim 15 (depends on 14) The program product of claim 14, wherein said pre-determined threshold varies depending on at least one of: (a) a volume of traffic in at least one said alternative path; and (b) a number of links in at least one said alternative path. ### Claim 16 (depends on 10) The program product of claim 10, wherein a respective threshold is associated with each of a plurality of said alternative paths, each alternative path being identified as an alternative path for use by packets of said subset if the number of packets in said subset exceeds the respective threshold of the path, wherein at least some said thresholds are different. ### Claim 17 A parallel computer system, comprising: a plurality of nodes, each node having at least one processor for executing a respective application sub-process and a memory accessible by the at least one processor; a plurality of node-to-node communication links forming a network for inter-nodal communications of application data; a respective routing mechanism in each node of said plurality of nodes, each said routing mechanism automatically routing each packet of a respective plurality of packets from a respective source node to a respective destination node along said node-to-node communications links of said network; wherein each routing mechanism includes a distribution function which, responsive to detecting an overutilization condition in a first path of said network running between a pair of nodes of said parallel computer system, allocates packets of a subset of packets to be routed between the pair of nodes among a plurality of different paths in said network running between the pair of nodes, each said packet being allocated to a respective one of said plurality of different paths, each said path being allocated at least one said packet; and wherein each routing mechanism causes each said packet to be automatically routed along the respective path to which it is allocated by said distribution function. ### Claim 18 (depends on 17) The parallel computer system of claim 17, wherein said plurality of nodes are arranged in a logical N-dimensional lattice for inter-nodal communication, each said communication link of said network coupling a respective first node with a respective second node, the respective first and second nodes having identical coordinates in all except a respective Mth of the N dimensions of said N-dimensional lattice, the respective first and second nodes being logical neighbors in the respective Mth coordinate dimension. ### Claim 19 (depends on 17) The parallel computer system of claim 17, wherein a first node of said pair of nodes is a source node and a second node of said pair of nodes is a destination node, said distribution function residing in said source node. ### Claim 20 (depends on 17) The parallel computer system of claim 17, wherein said first path is a path having a minimal number of links between said first node and said second node, and at least one said path of said plurality of different paths is a path having a number of links greater than said minimal number.