Method and Apparatus for Packet Routing

• US 20100246581A1
• Filed: 03/26/2009
• Published: 09/30/2010
• Est. Priority Date: 03/26/2009
• Status: Active Grant

• Current Assignee: Terascale Supercomputing Inc.
• Original Assignee: Terascale Supercomputing Inc.
• Inventors: Merryfield, Veronica Frances, Henry, Ronald Michael
• Granted Patent: US 7,957,385 B2
• Time in Patent Office: Days
• 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, where 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 comprising;

receiving at least a packet header of a packet at a first node;

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; and

transmitting the packet 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.

2. The method of claim 1, wherein the n layers include n−

1 layers of switch nodes and 1 layer of computational nodes, each layer in the structure includes nodes grouped into units having more than one node per unit, 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

where the first node is a switch node and;

transmitting a packet to a second node in the layer L comprises transmitting the packet to the second node in the 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 including 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, where 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 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 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

transmit one or more packets comprising a message to the second node as soon as the packets are received at the switch node without waiting to receive the entire packets and without copying the packets prior to transmission from the switch 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.