Method and Apparatus for Routing Data in an Inter-Nodal Communications Lattice of a Massively Parallel Computer System by Routing Through Transporter Nodes

• US 20080084865A1
• Filed: 10/06/2006
• Published: 04/10/2008
• Est. Priority Date: 10/06/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Peters, Amanda, Musselman, Roy Glenn, Wallenfelt, Brian Paul, Archer, Charles Jens, Swartz, Brent Allen, Pinnow, Kurt Walter
• Granted Patent: US 7,835,284 B2
• Time in Patent Office: Days
• US Class Current: 370/351
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/42 Centralised routing

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 destination. Some packets are constrained to be routed through respective designated transporter nodes, the automated routing strategy determining a path from a respective source node to a respective transporter node, and from a respective transporter node to a respective destination node. Preferably, the source node chooses a routing policy from among multiple possible choices, and that policy is followed by all intermediate nodes. The use of transporter nodes allows greater flexibility in routing.

Claims

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:

at each of a plurality of said nodes of said parallel computer system, automatically routing each of a plurality of packets from a respective source node to a respective destination node along said node-to-node communications links of said network using an automated routing strategy, wherein at least some of said packets must traverse one or more respective intermediate nodes between the respective source node and the respective destination node;

with respect to a subset of said packets, said subset containing a plurality of said packets, receiving a designation of a respective transporter node for each said packet;

with respect to each packet of said subset, selecting a respective path along said network from the respective source node to the respective transporter node using said automated routing strategy;

with respect to each packet of said subset, selecting a respective path along said network from the respective transporter node to the respective destination node using said automated routing strategy; and

automatically routing each said packet of said subset along its respective path as determined by said step of selecting a respective path from the respective source node to the respective transporter node and said step of selecting a respective path from the respective transporter node to the respective destination node.

2. The method for inter-nodal packet routing of claim 1, further comprising the steps of:

obtaining network usage data with respect to said network each of a plurality of node-to-node communications links of said parallel computer system;

analyzing said usage data to identify at least one congested link; and

designating a respective transporter node for each of a plurality of said packets using the results of said analyzing step.

3. The method for inter-nodal packet routing of claim 2, wherein said step of obtaining network usage data is performed prior to an execution instance of an application which generates said packets for transmission on said network

4. The method for inter-nodal packet routing of claim 1, wherein said step of receiving a designation of a respective transporter node for each said packet comprises receiving a designation of a respective transporter node for each of a plurality of messages, each said message containing one or more said packets, wherein each packet within a message is designated the respective transporter node designated for the message in which it is contained.

5. The method for inter-nodal packet routing of claim 4, wherein said step of selecting a respective path along said network from the respective source node to the respective transporter node and said step of selecting a respective path along said network from the respective transporter node to the respective destination node comprise respectively selecting a respective path along said network from the respective source node to the respective transporter node for each of a plurality of messages, and selecting a respective path along said network from the respective transporter node to the respective destination node for each of said plurality of messages, each said message containing one or more said packets, wherein each packet within a message is assigned a respective path from the respective source node to the respective transporter node assigned to the message within which it is contained, and wherein each packet within a message is assigned a respective path from the respective transporter node to the respective destination node assigned to the message within which it is contained.

6. The method for inter-nodal packet routing of claim 1,

wherein said step of selecting a respective path along said network from the respective source node to the respective transporter node comprises selecting, in the respective source node, a respective routing policy of each said packet for routing from the respective source node to the respective transporter node;

wherein said step of selecting a respective path along said network from the respective transporter node to the respective destination node comprises selecting, in the respective transporter node, a respective routing policy of each said packet for routing from the respective transporter node to the respective source node; and

wherein said step of automatically routing each said packet of said subset along its respective path comprises transmitting routing policy data as selected by the respective source node with each said packet transmitted from the respective source node to the respective transporter node, each intermediate node from the respective source node to the respective transporter node routing said packet according to said routing policy as selected by the respective source node, and transmitting routing policy data as selected by the respective transporter node with each said packet transmitted from the respective transporter node to the respective destination node, each intermediate node from the respective transporter node to the respective destination node routing said packet according to said routing policy as selected by the respective transporter node.

7. The method for inter-nodal packet routing of claim 1, further comprising the steps of:

generating said packets of said subset of packets at respective source nodes of said parallel computer system, each said packet of said subset identifying a respective destination node as its destination;

associating a respective transporter node with each said packet of said subset;

encapsulating each said packet in a respective shell packet at the respective source node of the packet, the respective shell packet identifying the respective transporter node as its destination.

8. The method for inter-nodal packet routing of claim 1, wherein said automated routing strategy is constrained to route packets along a path containing a minimal number of links of said network.

9. The method for inter-nodal packet routing of claim 8, wherein at least one said transporter node does not lie on a path between the respective source node and the respective destination node containing a minimal number of links.

10. The method for inter-nodal packet routing of claim 1,

wherein said plurality of nodes are arranged in a logical N-dimensional lattice, 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;

and

wherein said automated routing strategy implements a routing policy comprising a preferential order of coordinate dimensions in said logical N-dimensional lattice, the preferential order specifying an order of coordinate dimensions in which the packet is to be preferentially transmitted.

11. 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 of a plurality of packets from a respective source node to a respective destination node along said node-to-node communications links of said network using an automated routing strategy, wherein at least some of said packets must traverse one or more respective intermediate nodes between the respective source node and the respective destination node;

wherein, with respect to a subset of said packets, said subset containing a plurality of said packets, said routing mechanism receives a respective designation of a respective transporter node for each said packet, and responsive to the respective designation, causes each said packet to be routed from the respective source node to the respective transporter node according to said automated routing strategy, and from the respective transporter node to the respective destination node according to said routing strategy.

12. The parallel computer system of claim 11, wherein said plurality of nodes are arranged in a logical N-dimensional lattice, 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.

13. The parallel computer system of claim 12, wherein said automated routing strategy implements a routing policy comprising a respective preferential order of coordinate dimensions in said logical N-dimensional lattice, the preferential order specifying an order of coordinate dimensions in which the packet is to be preferentially transmitted.

14. The parallel computer system of claim 11, wherein said automated routing strategy is constrained to route packets along a path containing a minimal number of links of said network.

15. The parallel computer system of claim 14, wherein at least one said transporter node does not lie on a path between the respective source node and the respective destination node containing a minimal number of links.

16. The parallel computer system of claim 11, further comprising the steps of:

a distributed application executing on a plurality of said nodes and generating a plurality of messages for transmission across said network, each message comprising at least one said packet, said distributed application associated a respective transporter node with each of a plurality of messages;

wherein said routing mechanism routes each packet contained in a message associated with a respective transporter node by encapsulating each said packet in a respective shell packet at the respective source node of the packet, the respective shell packet identifying the respective transporter node as its destination.

17. A 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, the program product comprising:

a plurality of computer executable instructions recorded on signal-bearing media, wherein said instructions, when executed by at least one node of said computer system, cause the at least one node to perform the steps of;

with respect to a subset of packets transmitted by said network, said subset containing a plurality of said packets, each packet of said subset having a corresponding destination node, receiving a designation of a respective transporter node for each said packet; and

with respect to each packet of said subset, encapsulating the packet in a respective shell packet for transmission to the respective transporter node, each said shell packet identifying the respective transporter node as its destination;

wherein said parallel computer system automatically routes each said shell packet to the respective transporter node, and upon reaching the respective transporter node, automatically routes each said packet encapsulated within a shell packet to its respective destination node.

18. The program product of claim 17, wherein said step of receiving a designation of a respective transporter node for each said packet comprises receiving a designation of a respective transporter node for each of a plurality of messages, each said message containing one or more said packets, wherein each packet within a message is designated the respective transporter node designated for the message in which it is contained.

19. The program product of claim 17, wherein said computer system implements an automated routing strategy in each node, said automated routing strategy being constrained to route packets along a path containing a minimal number of links of said network.

20. The program product of claim 19, wherein at least one said transporter node does not lie on a path between the respective source node and the respective destination node containing a minimal number of links.