Addressing Scheme and Message Routing for a Networked Device

• US 20100250784A1
• Filed: 03/26/2009
• Published: 09/30/2010
• Est. Priority Date: 03/26/2009
• Status: Abandoned Application

• Current Assignee: Terascale Supercomputing Inc.
• Original Assignee: Terascale Supercomputing Inc.
• Inventors: Merryfield, Veronica Frances, Henry, Ronald Michael
• Application Number:
  US12/412,269
• Publication Number:
  US 20100250784A1
• Time in Patent Office: Days
• US Class Current: 709/252
• 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

Abstract

Methods and apparatus for addressing and/or routing packets in a network are described. A networked device in the network can include a hierarchical structure of nodes and a processor. The hierarchical structure of nodes includes n layers including n−1 layers of switch nodes and 1 layer of computational nodes. L represents a layer in the hierarchical structure and is an integer with L=0 representing a lowest layer and L=n−1 representing a highest layer. The networked device can include a processor configured for processing n groups of bits received in a packet, where each computational node is fully addressed by the n groups of bits and each switch node of a layer L is fully addressed by n−L groups of most significant bits.

Claims

1. A networked device comprising:

a hierarchical structure of nodes comprising n layers including n−

1 layers of switch nodes and 1 layer of computational nodes, where L represents a layer in the hierarchical structure and is an integer with L=0 representing a lowest layer and L=n−

1 representing a highest layer; and

a processor for processing n groups of bits received in a packet, where each computational node is fully addressed by the n groups of bits and each switch node of a layer L is fully addressed by n−

L groups of most significant bits.

2. The networked device of claim 1, where each of the n groups of bits comprises the same number of bits.

3. The networked device of claim 1, wherein:

each layer comprises one or more units of nodes and each unit comprises a local 2×

2×

2 cubic network with two nodes per side in each of three dimensions x, y and z; and

each node is logically located within the cubic network using a three-dimensional address {x,y,z} ranging from {0,0,0} to {1,1,1}, where the three-dimensional address logically locating each node within the cubic network comprises one of the n groups of bits.

4. The networked device of claim 1, wherein:

each layer comprises one or more units of nodes and each unit comprises a local 2×

4×

4 network with two nodes per side in an x dimension and four nodes per side in each of an y and z dimension; and

each node is logically located within the local network using a three-dimensional address {x,y1,y2,z1,z2} ranging from {0,0,0,0,0} to {1,1,1,1,1}, where the three-dimensional address logically locating each node within the local network comprises one of the n groups of bits.

5. A method of routing packets in a network, the network having a topology characterized by a hierarchical structure of nodes comprising n layers including n−

1 layers of switch nodes and 1 layer of computational 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, the method comprising;

receiving a packet at a switch node of layer L of the structure, the packet including a header with a first address comprising n groups of bits, the switch node having a second address comprising n−

L groups of bits; and

forwarding the packet to a node in either the layer L, the layer L+1, or the layer L−

1 based on a comparison of the first address and the second address.

6. The method of claim 5, wherein:

if the n−

L groups of most significant bits of the first address match the n−

L groups of bits of the second address, then forwarding the message on a point to point link to a node of layer L−

1 of the structure fully addressed by the n−

L+1 groups of most significant bits of the first address;

if the n−

L groups do not match but the n−

L−

1 groups of most significant bits of the first address do match the n−

L−

1 groups of most significant bits of the second address, then forwarding the message on a point to point link to a switch node of layer L of the structure fully addressed by the n−

L groups of most significant bits of the first address; and

if the n−

L−

1 groups of most significant bits of the first address do not match the n−

L−

1 groups of most significant bits of the second address, then forwarding the message on a point to point link to a switch node of layer L+1 of the structure fully addressed by the n−

L−

1 groups of most significant bits of the second address.

7. A method of routing packets in a network, the network having a topology characterized by a hierarchical structure of nodes comprising n layers including n−

1 layers of switch nodes and 1 layer of computational 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, the method comprising;

transmitting a packet from a computational node of layer L to either a second computational node of layer L or to a switch node of layer L+1, the packet including a header with a first address comprising n groups of bits and the computational node having a second address comprising n groups of bits, where transmitting is based on a comparison of the first and the second address.

8. The method of claim 7, wherein:

if n−

1 groups of most significant bits of the first address match n−

1 groups of most significant bits of the second address, then forwarding the message on a point to point link to the second computational node of layer L of the structure fully addressed by the n groups of bits of the first address; and

if the n−

1 groups do not match, then forwarding the message on a point to point link to the switch node of layer L+1 of the structure fully addressed by the n−

1 groups of most significant bits of the second address.