Error-correcting communication method for transmitting data packets in a network communication system

• US 6,574,770 B1
• Filed: 06/29/2000
• Issued: 06/03/2003
• Est. Priority Date: 06/29/2000
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Daudelin, Douglas Streeter
• Primary Examiner(s): MOISE, EMMANUEL LIONEL
• Application Number:
  US09/606,347
• Time in Patent Office: 1,069 Days
• Field of Search: 714/776, 714/748, 714/749, 370/362, 370/395, 370/401, 370/466, 370/392, 370/404, 370/471, 370/474, 370/394, 370/428, 375/231, 375/241, 375/371, 709/232, 709/237
• US Class Current: 714/776
• CPC Class Codes: H04L 1/1809 Selective-repeat protocols
• CPC Class Codes: H04L 1/188 Time-out mechanisms
• CPC Class Codes: H04L 1/1887 Scheduling and prioritising arrangements

Abstract

In the method, each transmitting endpoint separates its traffic to be transmitted into distinct queues. The packet at the head of one queue is transmitted, and no other packet is transmitted until a transmit complete signal (TCS) is generated. When a packet is received without error and accepted by a destination endpoint, the destination endpoint returns an acknowledgment indicating successful reception. The TCS is generated at the transmitting endpoint when the receiver acknowledgment should have been received. When the TCS is processed by the transmitting endpoint, if a receiver acknowledgment has been received, the packet previously sent is removed from the head of its queue. Otherwise, the packet is left at the head of its queue, the queue is placed in a “pending retry” state, and a timer is started. When the timer expires, queues are moved out of the “pending retry” state, enabling their packets to be transmitted again.

Claims

1. A method for transmitting data packets in a network communication system connecting a plurality of endpoints via at least one transmission medium, where packets to be transmitted from a transmitting endpoint are separated into a plurality of queues, each of said plurality of queues having at least one corresponding destination endpoint of said plurality of endpoints to which its packets are to be transmitted, said method comprising the steps of:

transmitting, at any time, from said transmitting endpoint a packet from a head of a queue of a plurality of queues, but only if said queue is not in a pending retry state and has no incomplete transmissions, to said at least one corresponding destination endpoint of said queue; and

servicing, at any time, at said transmitting endpoint, a transmit complete signal for said transmitted packet, by removing or leaving removed said transmitted packet from the head of said queue, if an acknowledgment was received from said at least one corresponding destination endpoint of said queue indicating that said packet was successfully received, otherwise placing said queue in the pending retry state, leaving said transmitted packet at or returning said transmitted packet to the head of said queue, and removing said queue from the pending retry state after a period of time has elapsed.

2. The method according to claim 1, further comprising the step of retransmitting said packet from said transmitting endpoint to said at least one corresponding destination endpoint of said queue whenever said acknowledgment has not been received at said servicing step up to a limited number of times, said step of retransmitting said packet up to said limited number of times being performed without placing said queue in the pending retry state.

3. The method according to claim 2, wherein said step of retransmitting is not performed for at least one particular type of unsuccessful transmission.

4. The method according to claim 1, further comprising the steps of:

maintaining a retry count for each queue of consecutive, unsuccessful retries from that queue; and

initiating a recovery action if said retry count exceeds a predetermined number.

5. The method according to claim 1, wherein said packet is transmitted from the head of said queue only if there is no incomplete transmission from said transmitting endpoint to any of said at least one corresponding destination endpoint of said queue.

6. The method according to claim 1, wherein said packet is transmitted from the head of said queue only if there is no incomplete transmission from said transmitting endpoint.

7. The method according to claim 1, wherein said period of time is timed by a timer.

8. The method according to claim 7, wherein said timer expires periodically and independent of the time at which any queue of said plurality of queues is placed in the pending retry state.

9. The method according to claim 7, wherein said timer is started at a time when a transmit complete signal is serviced at said transmitting endpoint, if said timer is not already started.

10. The method according to claim 1, wherein said transmit complete signal does not occur until after said acknowledgment from said at least one corresponding destination endpoint should have been received by said transmitting endpoint.

11. The method according to claim 1, wherein said step of transmitting said packet comprises the steps of:

transmitting said packet to said at least one corresponding destination endpoint of said queue with an identifier;

keeping track at said at least one corresponding destination endpoint of said queue of a next-expected identifier from said queue; and

discarding successfully received packets at said at least one corresponding destination endpoint of said queue which have a corresponding identifier which is not identical to said next-expected identifier.

12. The method according to claim 11, wherein said identifier is a number.

13. The method according to claim 11, wherein said identifier is a sequence number.

14. The method according to claim 13, wherein said sequence number is a single bit which toggles with each new packet transmitted to said at least one corresponding destination endpoint of said queue.

15. A method for transmitting data packets in a network communication system connecting at least three endpoints via at least one transmission medium, said method comprising the steps of:

a) separating packets to be transmitted from a transmitting endpoint into a plurality of queues, each of said plurality of queues having at least one corresponding destination endpoint of said at least three endpoints to which its packets are to be transmitted;

b) determining whether there is an incomplete transmission from said transmitting endpoint to any of said at least three endpoints;

c) transmitting a packet at the head of a queue of said plurality of queues to said at least one corresponding destination endpoint of said at least three endpoints, if there is no incomplete transmission from said transmitting endpoint to any of said at least three endpoints, otherwise proceeding to step (e);

d) sending, from said at least one corresponding destination endpoint of said plurality of endpoints upon successfully receiving said transmitted packet, an acknowledgment indicating that said packet was successfully received to said transmitting endpoint;

e) servicing at said transmitting endpoint a transmit complete signal after said signal has occurred, said signal does not occur until after said acknowledgment from said at least one corresponding destination endpoint should have been received by said transmitting endpoint;

e.1) determining whether said acknowledgment indicating that said packet was successfully received was received by said transmitting endpoint;

e.2) if not, then leaving said packet at or returning said packet to the head of said queue and placing said queue in a pending retry state, otherwise proceeding to step (f);

e.3) determining if a corresponding pending retry timer is on;

e.4) starting said corresponding pending retry timer if said corresponding pending retry timer is determined to be off; and

e.5) proceeding to step (g);

f) removing said transmitted packet from or leaving removed said transmitted packet from the head of said queue;

g) determining if there is at least one more packet to be transmitted from any of said plurality of queues which are not in said pending retry state;

h) transmitting another packet at the head of said queue or other queue of said plurality of queues which is not in said pending retry state, if it is determined in step (g) that there is at least one more packet to be transmitted, and proceeding to step (d); and

said method further comprises the step of;

servicing, at any time, an expired pending retry timer at said transmitting endpoint by removing each of said plurality of queues corresponding to said expired pending retry timer from said pending retry state and proceeding to step (b).

16. The method according to claim 15, wherein said method further comprises the steps of:

placing each of said plurality of queues from an empty state to a ready state when at least one packet is placed within each of said plurality of queues; and

moving said plurality of queues from said pending retry state to said ready state upon expiration of said corresponding pending retry timer.

17. The method according to claim 15, wherein step (a) comprises the step of separating data packets into said plurality of queues such that all packets to be transmitted to the same destination endpoint of said at least three endpoints are placed in the same queue.

18. The method according to claim 17, wherein each of said plurality of queues has only one corresponding destination endpoint of said at least three endpoints.

19. The method according to claim 15, wherein each of said plurality of queues has only one corresponding destination endpoint of said at least three endpoints.

20. The method according to claim 15, wherein said corresponding pending retry timer is set to permit at least one of the following:

1) short enough that errors or busy conditions will not significantly slow down throughput to a given endpoint;

     2) long enough for a busy endpoint to execute a software routine to make room for another packet in said busy endpoint'"'"'s buffer;

     3) short enough to enable said transmitting endpoint to keep said at least one corresponding destination endpoint as busy receiving packets as said transmitting endpoint is able to handle said packets; and

     4) long enough to prevent said transmitting endpoint from spending a great percentage of processor cycles on continually retransmitting packets to said at least one corresponding destination endpoint where such transmissions continuously fail.

21. The method according to claim 15, wherein said corresponding pending retry timer includes a pending retry busy timer and a pending retry error timer.

22. The method according to claim 15, wherein said corresponding pending retry timer is used by each of said plurality of queues.

23. The method according to claim 15, further comprising the step of terminating the method if it is determined in step (g) that there is no at least one more packet to be transmitted.

24. The method according to claim 15, wherein said step (c) comprises the steps of:

transmitting said packet to all of said at least one corresponding destination endpoint of said at least three endpoints with an identifier;

keeping track at all of said at least one corresponding destination endpoint of said at least three endpoints of a next-expected identifier from all queues of said plurality of queues from each transmitting endpoint from which said at least one destination endpoint can receive packets; and

discarding successfully received packets at all of said at least one corresponding destination endpoint which have a corresponding identifier which is not identical to said next-expected identifier.

25. The method according to claim 24, wherein said identifier is a number.

26. The method according to claim 24, wherein said identifier is a sequence number.

27. The method according to claim 26, wherein said sequence number is a single bit which toggles with each new packet transmitted to said at least one corresponding destination endpoint of said at least three endpoints.

28. The method according to claim 15, wherein said at least one transmission medium includes a physical or media access control layer protocol which requires each transmission from said transmitting endpoint of said at least three endpoints connected to said at least one transmission medium to be acknowledged by said at least one corresponding destination endpoint.

29. The method according to claim 28, wherein said at least one transmission medium is an IEEE Standard 1394 High Performance Serial Bus.

30. The method according to claim 28, wherein said at least one transmission medium is an ANSI/ATA 878.1 bus.

31. The method according to claim 15, wherein steps (c) and (h) comprise the step of servicing each queue of said plurality of queues with a different frequency and/or a different retransmit timeout interval of said corresponding pending retry timer than other queues.

32. The method according to claim 15, wherein said transmit complete signal is generated by hardware.

33. A network communication system comprising:

at least one processor for processing an error-correcting communication method; and

a plurality of endpoints connected via at least one transmission medium, where packets to be transmitted from a transmitting endpoint are separated into a plurality of queues, each of said plurality of queues having at least one corresponding destination endpoint of said plurality of endpoints to which its packets are to be transmitted, where said error-correcting communication method comprises the steps of;

transmitting, at any time, from said transmitting endpoint a packet from the head of a queue of said plurality of queues, which is not in a pending retry state and has no incomplete transmissions, to said at least one corresponding destination endpoint of said queue;

sending to said transmitting endpoint from said at least one corresponding destination endpoint of said queue, upon successfully receiving said transmitted packet, an acknowledgment indicating that said packet was successfully received; and

servicing, at any time, at said transmitting endpoint, a transmit complete signal for said transmitted packet, by removing or leaving removed said transmitted packet from the head of said queue, if said acknowledgment was received from said at least one corresponding destination endpoint of said queue, otherwise placing said queue in the pending retry state, leaving said transmitted packet at or returning said transmitted packet to the head of said queue, and removing said queue from the pending retry state after a period of time has elapsed.

34. The system according to claim 33, wherein said error-correcting communication method further comprises the step of retransmitting said packet from said transmitting endpoint to said at least one corresponding destination endpoint of said queue whenever said acknowledgment has not been received at said servicing step up to a limited number of times, said step of retransmitting said packet up to said limited number of timers being performed without placing said queue in the pending retry state.

35. The system according to claim 34, wherein said step of retransmitting is not performed for at least one particular type of unsuccessful transmission.

36. The system according to claim 33, wherein said error-correcting communication method further comprises the steps of:

maintaining a retry count for each queue of consecutive, unsuccessful retries from that queue; and

initiating a recovery action if said retry count exceeds a predetermined number.

37. The system according to claim 33, wherein a packet is transmitted from the head of said queue if there is no incomplete transmission from said transmitting endpoint to any of said at least one corresponding destination endpoint of said queue.

38. The system according to claim 33, wherein a packet is transmitted from the head of said queue only if there is no incomplete transmission from said transmitting endpoint.

39. The system according to claim 33, wherein said transmit complete signal does not occur until after said acknowledgment from said at least one corresponding destination endpoint should have been received by said transmitting endpoint.

40. The system according to claim 33, wherein said step of transmitting said packet comprises the steps of:

transmitting said packet to all of said at least one corresponding destination endpoint of said queue with an identifier;

keeping track at all of said at least one corresponding destination endpoint of said queue of a next-expected identifier from said queue; and

discarding successfully received packets at all of said at least one corresponding destination endpoint of said queue which have a corresponding identifier which is not identical to said next-expected identifier.

41. The system according to claim 33, wherein said at least one transmission medium includes a physical or media access control layer protocol which requires each transmission from said transmitting endpoint to be acknowledged by said at least one corresponding destination endpoint of said queue.

42. A network communication system comprising:

at least one processor for processing an error-correcting communication method; and

at least three endpoints connected via at least one transmission medium, where said error-correcting communication method comprises the steps of;

a) separating packets to be transmitted from a transmitting endpoint into a plurality of queues, each of said plurality of queues having at least one corresponding destination endpoint of said at least three endpoints to which its packets are to be transmitted;

b) determining whether there is an incomplete transmission from said transmitting endpoint to any of said at least three endpoints;

c) transmitting a packet at the head of a queue of said plurality of queues to said at least one corresponding destination endpoint of said at least three endpoints, if there is no incomplete transmission from said transmitting endpoint to any of said at least three endpoints, otherwise proceeding to step (e);

d) sending, from said at least one corresponding destination endpoint of said plurality of endpoints upon successfully receiving said transmitted packet, an acknowledgment indicating that said packet was successfully received to said transmitting endpoint;

e) servicing at said transmitting endpoint a transmit complete signal after said signal has occurred, said signal does not occur until after said acknowledgment from said at least one corresponding destination endpoint should have been received by said transmitting endpoint;

e.1) determining whether said acknowledgment indicating that said packet was successfully received was received by said transmitting endpoint;

e.2) if not, then leaving said packet at or returning said packet to the head of said queue and placing it in a pending retry state, otherwise proceeding to step (f);

e.3) determining if a corresponding pending retry timer is on;

e.4) starting said corresponding pending retry timer if said corresponding pending retry timer is determined to be off; and

e.5) proceeding to step (g);

f) removing said transmitted packet from or leaving removed said transmitted packet from the head of said queue;

g) determining if there is at least one more packet to be transmitted from any of said plurality of queues which are not in said pending retry state;

h) transmitting another packet at the head of said queue or other queue of said plurality of queues which is not in said pending retry state, if it is determined in step (g) that there is at least one more packet to be transmitted, and proceeding to step (d); and

said method further comprises the step of;

servicing, at any time, an expired pending retry timer at said transmitting endpoint by removing each of said plurality of queues corresponding to said expired pending retry timer from said pending retry state and proceeding to step (b).