Method and apparatus for routing message packets

Claim 2

Apparatus for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising: means for generating a message packet that is routed from one node to another in said pattern in accordance with relative address information included in said message packet, said relative address comprising as many digits as there are dimensions, each digit representing the relative displacement of the message packet from the node to which it is addressed, means associated with each dimension for examining a digit of the address of said message packet received at a node to determine if the displacement in that dimension is zero, means associated with each dimension for routing said message packet to another node in the same dimension if an examined digit indicates that the message packet has not reached its destination and if a connection to such node is available, means for passing the message packet from one examining means to another when the message packet is not routed to another node in the same dimension, and storing and processing means for routing message packets that have reached their destination to a message sink, for temporarily storing message packets that have not been routed on to their destination and for recycling stored message packets to said examining means for further routing.

Claim 3

Apparatus for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising: means for generating a message packet that is routed from one node to another in said pattern in accordance with relative address information included in said message packet, said relative address comprising as many digits as there are dimensions, each digit representing the relative displacement of the message packet from the node to which it is addressed, at least first and second means for examining the first and second digits, respectively, of the address of said message packet received at a node to determine if the displacement in that dimension is zero, at least first and second means for routing said message packet to another node in the first and second dimensions, respectively, if the examined digit indicates that the message packet has not reached its destination and if a connection to such node is available, first means for providing the message packet to said second means for examining the second digit of the address information when said first connection is not available or said first digit indicates that the message packet has reached its destination in that dimension, second means for providing the message packet to additional examining means or to storing and processing means when a connection is not available or said second digit indicates that the message packet has reached its destination in that dimension, and storing and processing means for routing messages that have reached their destination to a message sink, for temporarily storing messages that have not been routed on to their destination and for recycling stored messages to said first examining means for further routing.

Claim 4

Apparatus for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising: means for generating a message packet that is routed from one node to another in said pattern in accordance with relative address information included in said message packet, said relative address comprising as many digits as there are dimensions, each digit representing the relative displacement of the message packet from the node to which it is addressed, at least first and second means for examining the first and second digits, respectively, of the address of said message packet received at a node to determine if the displacement in that dimension is zero, at least first and second means for routing said message packet to another node in the first and second dimensions, respectively, if the examined digit indicates that the message packet has not reached its destination and if a connection to such node is available, first means for providing the message packet to said second means for examining the second digit of the address information when said first connection is not available or said first digit indicates that the message packet has reached its destination in that dimension, second means for providing the message packet to additional examining means or to storing and processing means when a connection is not available or said second digit indicates that the message packet has reached its destination in that dimension, and storing and processing means for routing messages that have reached their destination to a message sink, for temporarily storing messages that have not been routed on to their destination and for recycling stored messages to said first examining means for further routing.

Claim 5

The apparatus of claim 2 further comprising means for updating the relative displacement at each node through which the message packet is routed.

Claim 6

The apparatus of claim 2 wherein two copies of the relative displacement are generated at the originating node and the displacement in one copy is up-dated at each node through which the message packet is routed while individual bits in the other copy of the relative displacement are examined by the routing means to control the routing of the message packet.

Claim 7

The apparatus of claim 2 wherein said first examining means, first routing means and first providing means at each node operate in synchronism with the first examining means, first routing means and first providing means at the other nodes of said network and said second examining means, second routing means and second providing means at each node operate in synchronism with the second examining means, second routing means and second providing means at the other nodes of said network.

Claim 8

Apparatus for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising: means for generating a message packet that is routed from one node to another in said pattern in accordance with relative address information included in said message packet, said relative address comprising as many digits as there are dimensions, each digit representing the relative displacement of the message packet from the node to which it is addressed, for each dimension of the address, a plurality of means for examining the digit associated with that dimension in the address of said message packet received at a node to determine if the displacement in that dimension is zero, for routing said message packet to another node in that dimension if the examined digit indicates that the message packet has not reached its destination in that dimension and if a connection to such node is available, and for providing the message packet to another means at the same node for performing the same steps with respect to another dimension when the examined digit indicates that the message packet has reached its destination in that dimension or when the connection to another node in that dimension is not available, and means connected to the examining, routing and providing means of the last dimension for routing to a data sink message packets that have reached their destination, for temporarily storing message packets that have not been routed on to their destination and for recycling stored message packets to the examining, routing and providing means of the first dimension.

Claim 9

Apparatus for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising: means for generating a message packet that is routed from one node to another in said pattern in accordance with relative address information included in said message packet, said relative address comprising as many digits as there are dimensions, each digit representing the relative displacement of the message packet from the node to which it is addressed, for each dimension of the address, a plurality of means for examining the digit associated with that dimension in the address of said message packet received at a node to determine if the displacement in that dimension is zero, for routing said message packet to another node in that dimension if the examined digit indicates that the message packet has not reached its destination in that dimension and if a connection to such node is available, and for providing the message packet to another means at the same node for performing the same steps with respect to another dimension when the examined digit indicates that the message packet has reached its destination in that dimension or when the connection to another node in that dimension is not available, and means connected to the examining, routing and providing means of the last dimension for routing to a data sink message packets that have reached their destination, for temporarily storing message packets that have not been routed on to their destination and for recycling stored message packets to the examining, routing and providing means of the first dimension.

Claim 12

The apparatus of claim 1 wherein the routing means associated with each dimension further comprises means for routing a message packet to another node in the same dimension even if the displacement in that dimension is zero when no other message packet is being routed to said node in that dimension and the routing means is filled to capacity.

Claim 13

The apparatus of claim 2 wherein the routing means associated with each dimension further comprises means for routing a message packet to another node in the same dimension even if the displacement in that dimension is zero when no other message packet is being routed to said node in that dimension and the routing means is filled to capacity.

Claim 14

The apparatus of claim 6 wherein the routing means associated with each dimension further comprises means for routing a message packet to another node in the same dimension even if the displacement in that dimension is zero when no other message packet is being routed to said node in that dimension and the routing means is filled to capacity.

Claim 15

The method of claim 7 further comprising the step of routing a message packet to another node in the same dimension even if the displacement in that dimension is zero when no other message packet is being routed to said node in that dimension and the routing means is filled to capacity.

Claim 18

The method of claim 12 further comprising the step of routing to a message sink message packets that have reached their destination.

Claim 19

The method of claim 12 wherein the address information is relative address information in which each digit represents the relative displacement of the message packet from the node to which it is addressed, said method further comprising the step of updating the relative displacement at each node through which the message packet is routed.

Claim 20

The method of claim 12 wherein the order in which the dimensions are traversed by said message packet depends on the presence of other message packets being routed through the network.

Claim 21

The method of claim 12 further comprising the step of routing a message packet to another node in the same dimension, even if the displacement in that dimension is zero, when no other message packet is being routed to said node in that dimension and the routing means is filled to capacity with other message packets, whereby a path traversed by a message packet from one node to another in said network varies depending on the presence of other message packets being routed through the same nodes in the network.

Claim 22

The method of claim 12 further comprising the step of acknowledging to a source of a message packet successful transmission of said message packet.

Claim 23

The method of claim 12 wherein the step of examining another digit of the address of the message packet is repeated until either the message packet is routed to another node or it is determined that the message packet has reached the node to which it is addressed.

Claim 24

The method of claim 12 wherein the steps of examining a digit of the address and routing the message packet are repeated until the message packet has reached the node to which it is addressed.

Claim 25

The method of claim 12 wherein a plurality of message packets are generated simultaneously at different nodes, the same digit of the address of each message packet is examined simultaneously at different nodes and message packets are routed simultaneously from different nodes to nodes of the same dimension.

Claim 26

The method of claim 20 wherein the order in which the dimensions are traversed by each of said message packets depends on the presence of other messages packets being routed through the network.

Claim 27

The method of claim 20 wherein the steps of examining a digit of the address and routing the plurality of message packets are repeated until all the message packets have reached the nodes to which they are addressed.

Claim 30

The method of claim 23 wherein the order in which the dimensions are traversed by said message packet depends on the presence of other message packets being routed through the network.

Claim 31

The method of claim 23 further comprising the step of routing a message packet to another node in the same dimension, even if the displacement in that dimension is zero, when no other message packet is being routed to said node in that dimension and the routing means is filled to capacity with other message packets, whereby a path traversed by a message packet from one node to another in said network varies depending on the presence of other message packets being routed through the same nodes in the network.

Claim 32

The method of claim 23 wherein the plurality of message packets are generated simultaneously at different nodes, the same digit of the address of each message packet is examined simultaneously at different nodes and message packets are routed simultaneously from different nodes to nodes in the same dimension.

Claim 33

The method of claim 23 further comprising the step of acknowledging to a source of a message packet successful transmission of said message packet.

Claim 34

The method of claim 23 wherein the steps of examining a digit of the address and routing the plurality of message packets are repeated until all the message packets have reached the nodes to which they are addressed.

Claim 37

The method of claim 29 wherein the order in which the dimensions are traversed by said message packet depends on the presence of other message packets being routed through the network.

Claim 38

The method of claim 29 further comprising the step of routing a message packet to another node in the same dimension, even if the displacement in that dimension is zero, when no other message packet is being routed to said node in that dimension and the routing means is filled to capacity with other message packets, whereby a path traversed by a message packet from one node to another in said network varies depending on the presence of other message packets being routed through the same nodes in the network.

Claim 39

The method of claim 29 further comprising the step of acknowledging to a source of a message packet successful transmission of said message packet.

Claim 40

The method of claim 29 wherein the routing cycle is repeated until the message packet has reached the node to which it is addressed.

Claim 41

The method of claim 29 wherein a plurality of message packets are generated simultaneously at different nodes, the same digit of the address of each message packet is examined simultaneously at different nodes and message packets are routed simultaneously from different nodes to nodes of the same dimension.

Claim 42

The method of claim 34 wherein the routing cycle is repeated until all the message packets have reached the node to which they are addressed.

Claim 45

The method of claim 36 wherein the order in which the dimensions are traversed by said message packet depends on the presence of other message packets being routed through the network.

Claim 46

The method of claim 36 wherein a plurality of message packets are generated simultaneously at different nodes, the same digit of the address of each message packet is examined simultaneously at different nodes and message packets are routed simultaneously from different nodes to nodes of the same dimension.

Claim 47

The method of claim 38 wherein the routing cycle is repeated until all message packets have reached the node to which they are addressed.

Claim 48

The method of claim 36 further comprising the step of acknowledging to a source of a message packet successful transmission of said message packet.

Claim 49

Apparatus for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising: means for generating a message packet that is routed from one node to another in said pattern in accordance with address information included in said message packet, said address information comprising as many digits as there are dimensions, each digit providing addressing information for one dimension, means operative during successive periods of a routing cycle for examining successive digits of the address of said message packet at a node where the digit being examined is then located to determine if the message packet has reached its destination in a dimension associated with that digit, and for routing said message packet to another node in that dimension if an examined digit indicates that the message packet has not reached its destination in that dimension and if a connection to such node is available, and means for repeating the routing cycle until the message packet has reached the node to which it is addressed.

Claim 50

Apparatus for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising: means for generating a message packet that is routed from one node to another in said pattern in accordance with address information included in said message packet, said address information comprising as many digits as there are dimensions, each digit providing addressing information for one dimension, means operative during successive periods of a routing cycle for examining successive digits of the address of said message packet at a node where the digit being examined is then located to determine if the message packet has reached its destination in a dimension associated with that digit, and for routing said message packet to another node in that dimension if an examined digit indicates that the message packet has not reached its destination in that dimension and if a connection to such node is available, and means for repeating the routing cycle until the message packet has reached the node to which it is addressed.

Claim 51

The apparatus of claim 41 wherein the order in which the dimensions are traversed by said message packet depends on the presence of other message packets being routed through the network.

Claim 52

The apparatus of claim 41 wherein a plurality of message packets are generated simultaneously at different nodes, the same digit of the address of each message packet is examined simultaneously at different nodes and message packets are routed simultaneously from different nodes to nodes of the same dimension.

Claim 53

The apparatus of claim 43 wherein the routing cycle is repeated until all message packets have reached the node to which they are addressed.

Claim 54

The apparatus of claim 41 further comprising means for acknowledging to a source of said message packet successful transmission of said message packet.

Claim 55

The apparatus of claim 1 wherein the order in which the dimensions are traversed by said message packet depends on the presence of other message packets being routed through the network.

Claim 56

The apparatus of claim 1 wherein a plurality of message packets are generated simultaneously at different nodes, the same digit of the address of each message packet is examined simultaneously at different nodes and message packets are routed simultaneously from different nodes to nodes of the same dimension.

Claim 57

The apparatus of claim 47 wherein the routing cycle is repeated until all message packets have reached the node to which they are addressed.

Claim 58

The apparatus of claim 1 further comprising means for acknowledging to a source of said message packet successful transmission of said message packet.