Static end to end retransmit apparatus and method

• US 6,938,091 B2
• Filed: 03/08/2002
• Issued: 08/30/2005
• Est. Priority Date: 03/08/2002
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Das Sharma, Debendra
• Primary Examiner(s): Prieto, Beatriz
• Assistant Examiner(s): LIN, KELVIN Y
• Application Number:
  US10/092,501
• Publication Number:
  US 20030172181A1
• Time in Patent Office: 1,271 Days
• Field of Search: 709/230, 714/748, 711/138, 375/232, 370/227, 369/47.25
• US Class Current: 709/230
• CPC Class Codes: H04B 1/74 for increasing reliability, e.g. using redundant or spare channels or apparatus replacing by standby devices for amplifiers H03F1/52, H03F1/542
• CPC Class Codes: H04L 1/1874 Buffer management

Abstract

In a multiprocessor computer system with multiple nodes, a static end to end retry apparatus and method uses the concept of sequence numbers combined with a path number. All transactions sent along a path are delivered in order to remove any time dependency. The apparatus and method ensure there are no duplicate transactions through the use of special probe and plunge transactions and their respective responses. The apparatus and method also allow for any number of alternate paths being active simultaneously, such that if one path fails, the remaining alternate paths can continue on the communication (along with the backup alternate path if desired) as usual without any loss of transactions. Each node keeps track of transactions the node has sent over time to every other node, as well as every transaction the node has received from every other node along each active path for each flow control class. To accomplish this tracking function, two data structures exist. A send_seqid, representing the sequence identification (ID) (or sequence number) for the last transaction sent by the sending (or source) node to a given destination node exists along any given active path, and a flow control class. A second structure is a receive_seqid, representing the sequence ID (sequence number) of the last transaction that a destination node received and for which the destination node sent an acknowledgement (ACK) back to the source node, for each node, along every active path, and for each flow control class. The send_seqid and the receive_seqid may be stored in send_seqid and receive_seqid tables at each node in the multiprocessor computer system.

Claims

1. A method for retransmission of transactions in a multi-processor computer architecture, comprising:

at a source node in the computer architecture, the source node comprising a retransmit buffer, designating a transaction for transmission to a destination node in the computer architecture, the destination node comprising a receive buffer, wherein the transaction is designated for transmission over a first path in a first flow control class;

retrieving a sequence number for the designated transaction;

comparing the retrieved sequence number for the designated transaction to sequence numbers in the retransmit buffer, wherein if the comparison does not show a match;

attaching the retrieved sequence number to the designated transaction,

placing the designated transaction in the retransmit buffer, and

sending the designated transaction to the destination node; and

wherein if the comparison shows a match, transmitting the designated transaction over a second path.

2. The method of claim 1, wherein the designated transaction in the retransmit buffer times out, comprising:

retrieving the sequence number of a most recent transaction sent to the destination node along the first path;

sending a probe request to the destination node along the second path, the probe request including the sequence number of the timed-out transaction and the sequence number of the most recent transaction;

deconfiguring the first path; and

updating the sequence number in the retransmit buffer.

3. The method of claim 2, wherein the destination node receives the probe request, the method at the destination node, comprising:

determining a sequence number for a most recent transaction entry in the receive buffer for a transaction from the source node along the first path and the first flow control class; and

determining;

(a) if the sequence number for the most recent transaction entry in the receive buffer equals the timed-out transaction sequence number minus one, and

(b) if the sequence number for the most recent transaction entry in the receive buffer lies between the timed-out transaction sequence number and the sequence number of the last transaction sent by the source node.

4. The method of claim 3, wherein if either (a) or (b) are met:

sending a probe response to the source node along the second path;

indicating to the source node if the timed-out transaction is received at the destination node; and

sending the source node the most recent sequence number acknowledged.

5. The method of claim 4, wherein the source node receives the probe response, comprising resuming transmission for all transactions in the retransmit buffer for which an acknowledgement has not been received.

6. The method of claim 2, wherein the probe request times out, comprising:

determining if a third path is available;

if the third path is available;

sending a second probe response along the third path,

deconfiguring the second path, and

updating the sequence number in the retransmit buffer; and

if the third path is not available, designating an error condition.

7. The method of claim 3, wherein neither (a) nor (b) are met, and wherein an error condition is designated.

8. The method of claim 4, further comprising:

sending a plunge transaction to the destination node over the first path, the plunge transaction indicating a sequence number for retransmission of transactions should the first path be reconfigured; and

updating the sequence number.

9. The method of claim 8, wherein the destination node receives the plunge transaction, the method at the destination node, comprising:

determining if the first path is deconfigured from the source node; and

if the first path is deconfigured from the source node, sending a plunge response to the source node over the first path.

10. The method of claim 9, wherein the destination node determines that the first path is not deconfigured, wherein an error condition exists, comprising:

informing the source node; and

deconfiguring the first path from the destination node.

11. The method of claim 9, further comprising:

receiving the plunge response; and

reconfiguring the first path from the source node.

12. The method of claim 1, wherein the destination node receives the designated transaction, the method at the destination node, comprising:

determining from the receive buffer a sequence number from a most recent transaction from the source node along the first path in the first flow control class; and

comparing the sequence numbers of the designated transaction and the most recent transaction.

13. The method of claim 12, wherein the sequence number of the designated transaction is subsequent to the sequence number of the most recent transaction, comprising, determining if the first path is configured.

14. The method of claim 13, wherein the first path is configured, comprising:

accepting the transaction;

updating a receive sequence number in the receive buffer; and

sending an acknowledgement to the source node along the first path.

15. The method of claim 12, wherein the sequence number of the designated transaction is not subsequent to the sequence number of the most recent transaction, comprising dropping the transaction.

16. An apparatus for retransmission of transactions in a multi-processor computer architecture, comprising:

a source node having a retransmit buffer, wherein the source node stores transactions transmitted from the source node;

a send_seqid table comprising a sequence number for each transaction sent from the source node;

a destination node comprising a receive buffer, wherein the destination node stores transactions transmitted from the destination node;

a receive_seqid table comprising a sequence number for each transaction sent from the destination node, wherein the source node sends normal transactions to the destination node and the destination node sends acknowledgements for the normal transactions to the source node, wherein if the source node does not receive an acknowledgement within a specified time, a corresponding normal transaction in the retransmit buffer times out; and

a probe transaction, whereby the source node queries the destination node for a timed-out transaction.

17. The apparatus of claim 16, wherein the probe transaction comprises a sequence number of the timed-out transaction and the sequence number of the most recent transaction sent from the source node to the destination node, wherein the source node comprises:

means for deconfiguring the first path; and

means for updating the sequence number in the retransmit buffer.

18. The apparatus of claim 17, wherein the destination node receives the probe transaction, the destination node, further comprising:

means for determining a sequence number for a most recent transaction entry in the receive buffer for a transaction from the source node along the first path and the first flow control class; and

means for determining;

(a) if the sequence number for the most recent transaction entry in the receive buffer equals the timed-out transaction sequence number minus one, and

(b) if the sequence number for the most recent transaction entry in the receive buffer lies between the timed-out transaction sequence number and the sequence number of the last transaction sent by the source node.

19. The apparatus of claim 18, wherein if either (a) or (b) are met, the destination node:

sends a probe response to the source node along the second path;

indicates to the source node if the timed-out transaction is received at the destination node; and

sends the source node the most recent sequence number acknowledged.

20. The apparatus of claim 19, wherein the source node receives the probe response, wherein the source node comprises means for resuming transmission for all transactions in the retransmit buffer for which an acknowledgement has not been received.

21. The apparatus of claim 18, wherein neither (a) nor (b) are met, and wherein an error condition is designated.