Asynchronous packet switching

• US 5,959,995 A
• Filed: 02/22/1996
• Issued: 09/28/1999
• Est. Priority Date: 02/22/1996
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Shimizu, Takeshi, Weber, Wolf-Dietrich, Helland, Patrick J., Wilcke, Winfried W., Wicki, Thomas M.
• Primary Examiner(s): TON, DANG T
• Application Number:
  US08/605,677
• Time in Patent Office: 1,314 Days
• Field of Search: 370/355, 370/388, 370/389, 370/392, 370/397, 370/400, 370/410, 370/411, 370/413, 370/422, 370/401, 370/406, 370/407, 370/408, 370/409, 370/412, 370/428, 370/394, 370/395 , 370/351, 370/352, 370/229, 370/231, 370/237, 370/238, 370/256, 340/825.05, 340/825.5, 340/826
• US Class Current: 370/400
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/34 Source routing

Abstract

A multiprocessor system includes a plurality of nodes and an interconnect that includes routers. Each node includes a reliable packet mover and a fast frame mover. The reliable packet mover provides packets to the fast frame mover which adds routing information to the packet to form a frame. The route to each node is predetermined. The frame is provided to the routers which delete the route from the routing information. If the frame is lost while being routed, the router discards the frame. If the packet is received at a destination node, the reliable packet mover in that node sends an acknowledgment to the source node if the packet passes an error detection test. The reliable packet mover in the source node resends the packet if it does not receive an acknowledgment in a predetermined time. The fast frame mover randomly selects the route from a plurality of predetermined routes to the destination node according to a probability distribution.

Claims

1. A system for communicating data in packets, each packet included in a frame, the system comprising:

a plurality of routers disposed to transmit and receive frames among one another; and

a plurality of nodes, each node including a frame mover disposed to transmit frames to and receive frames from the routers and including a packet mover disposed to supply packets to and receive packets from the frame mover, the packet mover of one of the nodes supplying a packet to the frame mover of said one of the nodes, with the packet indicating a destination node among the plurality of nodes, the frame mover of said one of the nodes, selecting a predetermined route through the routers to the destination node, including the packet and the route in the frame, and transmitting the frame to the routers;

the routers transmitting the frame to the frame mover of the destination node in response to the route included in the frame;

the frame mover of the destination node receiving the frame and supplying the packet included therein to the packet mover of the destination node, the packet mover of the destination node checking the packet for errors, discarding the packet in response to detecting an error, and transmitting an acknowledgment for the packet to said one of the nodes in response to detecting no errors; and

the packet mover of said one of the nodes retransmitting the packet to the destination node in response to receiving no acknowledgment for the packet within a predetermined period of time.

2. A system for transmitting data in packets, each packet include in a frame, the system comprising:

a plurality of mesh links each for carrying frames during transmission;

a plurality of routers linked in a network by the mesh links which carry frames between the routers; and

a plurality of nodes each linked to the plurality of routers by at least one of the mesh links, one of the nodes being a source node for selecting a predetermined route to another of the nodes being a destination node, the predetermined route from a routing table having a plurality of predetermined routes to the destination node, with said predetermined route indicating a sequence of the mesh linking said one of the nodes to said another of the nodes, generating a frame that includes said predetermined route and a packet, and transmitting the frame along the mesh line includes said beginning the sequence to one of the routers, each router linked by the sequence transmitting the frame along the sequence to said another of the nodes in response to the route included in the frame, said another of the nodes extracting the packet from the frame, checking the packet for errors, and processing the packet in response to detecting no errors.

3. The system of claim 2, wherein the nodes include:

a controller for selecting one of the plurality of predetermined routes for inclusion in the frame.

4. The system of claim 3 wherein the controller selects said one of the plurality of predetermined routes for inclusion in the frame according to a probability distribution weighting a likelihood of selection of each of the predetermined routes.

7. The system of claim 2, wherein each node has a identifier, and each predetermined route comprises the sequence of routers linked by the sequence of the mesh links, and further includes the identifier of said another of the nodes, for identifying the sequence of the mesh links in each predetermined route.

8. The system of claim 2, wherein:

said one of the nodes includes the predetermined route in a beginning portion of the frame; and

at least one of the routers linked by the sequence of the mesh links receives the beginning portion of the frame and prior to receiving an end portion of the frame transmits said beginning portion along the sequence of the mesh links to said another of the nodes in response the route included in the beginning portion of the frame.

5. A method for sending data in packets between nodes of a communication system, each node having a buffer, each packet including an identifier distinguishable from identifiers of other packets in the systems, the method comprising the steps of:

a) sending a copy of a packet including the identifier of the packet from a first node to a second node;

b) storing the packet of step a) in the buffer of the first node;

c) receiving an acknowledgment including a second identifier at the first node from another of the nodes;

d) removing the packet from the buffer of the first node in response to the second identifier matching the identifier of the packet; and

e) resending each packet in the buffer of the first node in response to not receiving the acknowledgment after a predetermined time.

6. The method of claim 5, wherein the identifier is a number and the step of removing the packet from storage includes the step of removing each packet from storage having an identifier less than or equal to the second identifier.

9. The method of claim 5, wherein steps a) and b) are performed a plurality of times without performing steps c), d), and e).

10. The method of claim 5, wherein steps c), d), and e) are performed a plurality of times without performing steps a) and b).

11. A system for communicating data in packets, each packet includes a sequence number and is included in a frame, the system comprising:

a plurality of routers disposed to transmit and receive frames among one another; and

a plurality of nodes, each node including a frame mover disposed to transmit frames to and receive frames from the routers and including a packet mover disposed to supply packets to and receive packets from the frame mover, each packet mover including;

a table or storing the sequence number of the next packet expected from each other packet mover;

a buffer for storing each packet received from another of the packet movers having a sequence number that follows the sequence number in the table corresponding to said another of the packet movers; and

a controller for comparing the sequence number of a packet received from one of the other packet movers to the stored sequence number in the table corresponding to said one of the other packet movers, storing the packet in the buffer in response to the sequence number of the packet following said stored sequence number, processing the packet and incrementing said stored sequence number in response to the sequence number of the packet matching said stored sequence number, and removing and processing another packet stored in the buffer in response to the incremented sequence number matching the sequence number of said another packet and then again incrementing the incremented sequence number;

the packet mover of one of the nodes supplying a packet to the frame mover of said one of the nodes, with the packet indicating a destination node among the plurality of nodes, the frame mover of said one of the nodes selecting a predetermined route through the routers to the destination node, including the packet and the route in the frame, and transmitting the frame to the routers;

the routers transmitting the frame to the frame mover of the destination node in response to the route included in the frame;

the frame mover of the destination node receiving the frame and supplying the packet included therein to the packet mover of the destination node, the packet mover of the destination node checking the packet for errors, discarding the packet in response to detecting an error, and transmitting an acknowledgment for the packet to said one of the nodes in response to detecting no errors; and

the packet mover of said one of the nodes retransmitting the packet to the destination node in response to receiving no acknowledgment for the packet within a predetermined period of time.

12. A method for sending data in packets between nodes of a communication system using a plurality of mark bits, each mark bit having a set state and an unset state, and each node having a buffer, and each packet including an identifier distinguishable from identifiers of other packets in the system, the method comprising:

a) sending a copy of a packet including the identifier of the packet from the first node to a second node;

b) storing the packet of step a) in the buffer of the first node, including;

associating a mark bit with the packet;

and placing the mark bit in the unset state;

c) receiving an acknowledgment including a second identifier at the first node from another of the nodes;

d) removing the packet from the buffer of the first node if the second identifier matches the identifier of the packet; and

e) resending each packet in the buffer of the first node after a predetermined time, including;

resending each packet in the buffer of the first node having a mark bit in the set state; and

placing into the set state the mark bit of each packet in the buffer of the first node and having a mark bit in the unset state.