Method and apparatus for routing packets in a multinode computer interconnect network
First Claim
1. A method for routing user packets in an interconnect network, the interconnect network having a plurality on nodes each having a plurality of output lines and packet storage, each user packet having a destination node, the method comprising the steps of:
- receiving a number of packets into a first node;
storing the packets;
sensing the destination node of at least one stored packet;
determining a preferred output line for the stored packet, the preferred output line being associated with the shortest nodal travel distance to the destination node, wherein each output line is associated with an input line, including the steps of;
originating a plurality of node distance packets at each node in the network, each node distance packet including a node identity and a distance number originally set to a base value,transmitting the node distance packets from each node to connected nodes,receiving the node distance packets by each node from connected nodes via input lines,at each node, incrementing the distance number of each received node distance packet by a constant,setting a value of a corresponding nodal distance array member to the distance number from each incremented distance packet, the array member being referred by the node identity and the output line associated with the input line on which the distance packet was received,retransmitting from each node to connected nodes the incremented distance packets,receiving the incremented distance packets by each node,at each node, further incrementing the distance number of each received incremented distance packet,at each node, comparing the further incremented distance number of each distance packet to the value of a corresponding array member,discarding any further incremented distance packet whose distance number equals or exceeds a nonzero value of the corresponding array member to the distance number,at each node, retransmitting the nondiscarded distance packets to all connected nodes,repeating the incrementing, comparing, discarding, setting and retransmitting steps until no nondiscarded node distance packets remain;
choosing the array member having the shortest nodal travel distance from all array members referenced by the destination node;
setting the preferred output line of the packet to the output line referencing the chosen array member; and
transmitting the packet on its determined preferred output line.
1 Assignment
0 Petitions
Accused Products
Abstract
A method for routing user packets in a multinode interconnect network is disclosed. Each packet has a destination node (10). Each node (10) is connected by input and output lines (12) and has a plurality of packet storage links (34) and (56-60). Each link (34) and (56-60) is connected to an input line (18-24) and has a number of packet storage buffers (38-44) and is connectable to any of the node'"'"'s output lines (26-32). During operation node (10) uses a set of routing instructions and a look-up table (192) to determine which user packets are sent out on which output lines (26-32). The routing rules determine which output line is connected to the shortest path to the destination node, and ensure that the node (10) will always have an empty storage buffer (38-44) for each input line (18-24) for receiving further user packets.
-
Citations
13 Claims
-
1. A method for routing user packets in an interconnect network, the interconnect network having a plurality on nodes each having a plurality of output lines and packet storage, each user packet having a destination node, the method comprising the steps of:
-
receiving a number of packets into a first node; storing the packets; sensing the destination node of at least one stored packet; determining a preferred output line for the stored packet, the preferred output line being associated with the shortest nodal travel distance to the destination node, wherein each output line is associated with an input line, including the steps of; originating a plurality of node distance packets at each node in the network, each node distance packet including a node identity and a distance number originally set to a base value, transmitting the node distance packets from each node to connected nodes, receiving the node distance packets by each node from connected nodes via input lines, at each node, incrementing the distance number of each received node distance packet by a constant, setting a value of a corresponding nodal distance array member to the distance number from each incremented distance packet, the array member being referred by the node identity and the output line associated with the input line on which the distance packet was received, retransmitting from each node to connected nodes the incremented distance packets, receiving the incremented distance packets by each node, at each node, further incrementing the distance number of each received incremented distance packet, at each node, comparing the further incremented distance number of each distance packet to the value of a corresponding array member, discarding any further incremented distance packet whose distance number equals or exceeds a nonzero value of the corresponding array member to the distance number, at each node, retransmitting the nondiscarded distance packets to all connected nodes, repeating the incrementing, comparing, discarding, setting and retransmitting steps until no nondiscarded node distance packets remain; choosing the array member having the shortest nodal travel distance from all array members referenced by the destination node; setting the preferred output line of the packet to the output line referencing the chosen array member; and transmitting the packet on its determined preferred output line. - View Dependent Claims (2)
-
-
3. A method for routing user packets in an interconnect network, the interconnect network having a plurality of nodes each having a plurality of output lines and packet storage, each user packet having a destination node, wherein each node has a plurality of packet storage links, each having a plurality of packet storage buffers, an input line being connected to each link, the method comprising the steps of;
-
receiving a number of packets into a first node; storing each received packet in a buffer; sensing the destination node of at least some stored packets; determining a preferred output line and an associated nodal travel distance to a packet,s destination node for each stored packet; for each link having at least one nonempty buffer, selecting a packet having the shortest nodal travel distance of all the packets stored in the link; assigning the selected packets, in increasing order of nodal travel distance, to their preferred output lines, if the preferred output line for a first packet has not already been assigned to another first packet; after assigning the selected packets, identifying which links would still be full after transmission of the assigned selected packets if any output lines remain unassigned; for each prospective full link, if any output lines remain unassigned, assigning a packet stored in the link to an unassigned line until the unassigned output lines are exausted or until no prospective full link remains; and transmitting ones of the portion of stored packets on their respective preferred output lines. - View Dependent Claims (4, 5)
-
-
6. An interconnect network for transmission of user packets including a plurality of nodes, each node being connected by input and output lines to a plurality of other nodes, each node comprising:
-
means for receiving a plurality of user packets each having a destination node; means for storing received packets; means for sensing the destination node of each stored packet; means for determining a preferred output line for each stored packet, said preferred output line being connected to a path having the shortest nodal travel distance to said storage packet'"'"'s destination node; means for assigning stored packets to their respective preferrred output lines, said means selecting packets for assignment according to the increasing order of the packets, respective nodal travel distances; and means for transmitting said packet on its preferred output line; wherein said sensing means, determining means and assigning means comprise processor means, said processor means including memory means for storing a set of packet routing rules, and wherein said node includes a plurality of links each comprising a plurality of said packet storage means, said routing rules, after selecting user packets for transmission according to their nodal travel distances and availability of preferred output lines, selecting packets for transmission on and remaining available output lines according to whether each said link prospectively has at least one empty packet storage means, said routing rules preferentially selecting one or more stored packets within prospectively nonempty links for transmission on the remaining available output lines. - View Dependent Claims (7, 8, 9, 10, 11, 12, 13)
-
Specification