Method and apparatus for packet routing

• US 7,957,385 B2
• Filed: 03/26/2009
• Issued: 06/07/2011
• Est. Priority Date: 03/26/2009
• Status: Expired due to Fees

• Current Assignee: Terascale Supercomputing Inc.
• Original Assignee: Terascale Supercomputing Inc.
• Inventors: Merryfield, Veronica Frances, Henry, Ronald Michael
• Primary Examiner(s): Sheikh; Ayaz R
• Assistant Examiner(s): LEE, ANDREW CHUNG CHEUNG
• Application Number:
  US12/412,289
• Publication Number:
  US 20100246581A1
• Time in Patent Office: 803 Days
• Field of Search: 370/392, 370/389, 370/327, 370/279, 370/235
• US Class Current: 370/392
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing
• CPC Class Codes: H04L 45/40 Wormhole routing
• CPC Class Codes: H04L 45/64 using an overlay routing layer

Abstract

Methods and apparatus for routing a packet in a network are described. The network has a topology characterized by a hierarchical structure of nodes including n layers. L represents a layer in the structure and is an integer with L=0 representing a lowest layer and L=n−1 representing a highest layer. The method includes receiving at least a packet header of a packet at a first node and based on the packet header, determining whether to transmit the packet to a second node in either layer L, layer L+1, or layer L−1. The packet can be transmitted to the second node as soon as the packet is received at the first node without waiting to receive the entire packet and without copying the packet prior to transmission from the first node.

Claims

1. A method of routing a packet in a network, the network having a topology characterized by a hierarchical structure of nodes comprising n layers wherein n is an integer greater than 1 and each of the n layers is represented by L being an integer from 0 to n−

1 with L=0 representing a lowest layer and L=n−

1 representing a highest layer in the hierarchical structure and wherein the n layers comprise n−

1 layers of switch nodes and 1 layer of computational nodes, the method comprising;

receiving at least a packet header of a packet at a first node, wherein the first node is a switch node included in the layer of switch nodes represented by L;

based on a destination address included in the packet header, determining whether to transmit the packet to a second node in either layer L, layer L+1, or layer L−

1; and

beginning transmission of the packet to the second node without waiting to receive the entire packet at the first node and without copying the packet prior to transmission from the first node;

wherein the destination address identifies a destination comprising a computational node included in the 1 layer of computational nodes and the packet is not copied to a memory until received at the destination comprising the computational node.

2. The method of claim 1, wherein each layer in the structure includes nodes grouped into units having more than one node per unit and wherein a unit comprises a set of nodes, and each node in a layer other than the computational layer comprises a switch node for a unit in a next lower layer in the structure;

and wherein;

transmitting a packet to a second node in the layer L comprises transmitting the packet to the second node in a same unit as the first node by a point to point link; and

transmitting a packet to a second node in the layer L+1 or the layer L−

1 comprises transmitting the packet to the second node in a different unit than the first node by a point to point link.

3. A system comprising:

a hierarchical structure of nodes comprising n layers, wherein n is an integer greater than 1 and the n layers comprise n−

1 layers of switch nodes and 1 layer of computational nodes, where each layer in the hierarchical structure includes one or more units of nodes, a unit comprising a set of nodes, where each of the n layers is represented by L being an integer from 0 to n−

1 with L=0 representing a lowest layer and L=n−

1 representing a highest layer and a number of nodes in a unit is greater than 1;

where the switch nodes are configured to;

receive at least a packet header of a packet;

based on a destination address included in the packet header, determine whether to transmit the packet to a second node in either layer L, layer L+1, or layer L−

1; and

begin transmission of one or more packets comprising a message to the second node without waiting to receive the entire packets at the switch node and without copying the packets prior to transmission from the switch node;

wherein the destination address identifies a destination comprising a computational node included in the 1 layer of computational nodes and the packet is not copied to a memory until received at the destination comprising the computational node.

4. The system of claim 3, wherein the computational nodes each include:

at least one processor;

communication hardware; and

a memory.

5. The system of claim 4, wherein the at least one processor comprises an application processor and an operating system processor.

6. The system of claim 4, wherein the communication hardware comprises a field-programmable gate array (FPGA).

7. The system of claim 4, wherein the communication hardware is configured to monitor traffic to the computational node.

8. The system of claim 4, wherein the communication hardware is configured to:

direct a message received at the computational node to the processor; and

receive a message from the processor for transmission to a different node.

9. The system of claim 3, where each node in a layer other than the computational layer comprises a switch node for a unit in a next lower layer in the structure;

and

where for each unit;

each node in the unit is connected to each other node in the unit by a point to point link;

each node in the unit is connected to a local switch node for the unit by a point to point link; and

each node in the unit is connected to each other node in the unit and to the local switch node by a local broadcast network for the unit.

10. The system of claim 3, where the switch nodes each comprise:

a processor; and

communication hardware.