Limited automatic repeat request protocol for frame-based communication channels

• US 20020034182A1
• Filed: 09/18/2001
• Published: 03/21/2002
• Est. Priority Date: 05/21/1999
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Mallory, Tracy D.
• Granted Patent: US 7,236,494 B2
• Time in Patent Office: Days
• US Class Current: 370/394
• CPC Class Codes: H04L 1/1635 Cumulative acknowledgement, i.e. the acknowledgement message applying to all previous messages
• CPC Class Codes: H04L 1/1664 the supervisory signal being transmitted together with payload signals; piggybacking
• CPC Class Codes: H04L 1/1685 the supervisory signal being transmitted in response to a specific request, e.g. to a polling signal
• CPC Class Codes: H04L 1/1809 Selective-repeat protocols
• CPC Class Codes: H04L 1/1832 Details of sliding window management
• CPC Class Codes: H04L 1/1838 for semi-reliable protocols, e.g. for less sensitive applications such as streaming video buffer level management for video bitstream receiver H04N21/44004
• CPC Class Codes: H04L 1/1841 Resequencing
• CPC Class Codes: H04L 1/1848 Time-out mechanisms
• CPC Class Codes: H04L 1/1858 Transmission or retransmission of more than one copy of acknowledgement message
• CPC Class Codes: H04L 1/1877 for semi-reliable protocols, e.g. for less sensitive applications like streaming video buffer level management for video bitstream control arrangements H04N21/44004
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint
• CPC Class Codes: H04L 2001/125 Arrangements for preventing errors in the return channel
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04L 69/324 in the data link layer [OSI layer 2], e.g. HDLC

Abstract

In a frame-switched network, a sender sends frames to a receiver over a possibly unreliable channel. Sent frames include frame identifiers that can be used for a limited automatic repeat request. Upon receipt of a frame, the receiver determines, from the frame identifier, if frames prior to the received frame were lost in transit. If the receiver determines that it missed a prior frame, the receiver sends the sender a negative acknowledgment (nack) for the missed prior frame or frames. Otherwise, if the receiver receives a frame correctly, it does not acknowledge the frame. The frame identifiers can be a set of sequential integers with frames transmitted in sequential frame order. In some embodiments, when a receiver receives a frame out of order, the receiver buffers the out of order frame in a receiver buffer for a receive buffer period until preceding frames are received or a receive buffer period expires. The sender can send a reminder frame to the receiver to allow the receiver to detect a missed prior frame missing from an end of a frame sequence. The channel between the sender and the receiver can be a bidirectional channel over a telephone wire, a cable, a radio frequency link or a power wire. Multiple logical channels might be set up between a given sender-receiver pair, to allow for traffic of varying priorities.

Claims

1. In a frame-switched network apparatus, a method of sending frames from a sender to a receiver over a possibly unreliable channel, the method comprising the steps of:

forming a frame at the sender, wherein the frame contains data to be transmitted to the receiver;

including a frame identifier in the frame selected from a set of frame identifiers;

retaining a copy of the frame at the sender;

sending the frame from the sender to the receiver over the channel, independent of the availability of the receiver;

upon receipt of a frame at the receiver, identifying a frame identifier for the received frame;

detecting, from the frame identifier, if a prior frame was missed;

if a missed prior frame is detected in the step of detecting, sending a negative acknowledgment (nack) from the receiver to the sender, the nack including an indication of the missed prior frame;

if a nack is received at the sender, determining the frame identifier of the missed prior frame and resending the missed prior frame if a copy of the missed prior frame is still retained at the sender; and

releasing the retained copy of the transmitted frame when a storage constraint is reached.

2. The method of claim 1, wherein the sender transmits the transmitted frame to more than one receiver.

3. The method of claim 1, wherein the set of frame identifiers is a set of sequential integers and the frame identifiers are used in sequence and transmitted in sequential frame order.

4. The method of claim 3, wherein the indication of the missed prior frame is a nack containing a frame identifier and a missing frame count that together identify a sequence of one or more frames that includes the missed prior frame.

5. The method of claim 1, wherein the indication of the missed prior frame is a nack containing a frame identifier and a missing frame count that together identify one or more frames including the missed prior frame.

6. The method of claim 1, further comprising the steps of:

identifying, at the receiver, when frames are received out of order; and

when a frame is received out of order, buffering the out of order frame in a receiver buffer for a receive buffer period, until preceding frames are received or the receive buffer period expires.

7. The method of claim 1, further comprising a step of sending a reminder frame from the sender to the receiver, to allow the receiver to detect a missed prior frame missing from an end of a frame sequence.

8. The method of claim 1, further comprising a step of including nack indications in frames containing data transmitted from the receiver to the sender when the receiver has data to send to the sender and has detected at least one missing prior frame.

9. The method of claim 1, wherein the step of sending a nack comprises a step of sending the nack at least two times from the receiver to the sender.

10. The method of claim 9, further comprising the steps of:

detecting when multiple nacks are sent for a single missed prior frame; and

sending only one retransmitted frame for each missed prior frame multiply nacked.

11. The method of claim 9, further comprising the steps of:

delaying a second nack from the receiver for a response period, wherein the response period is related to the time delay expected between sending the first nack and expected receipt of a retransmitted frame; and

retransmitting the missed prior frame once for each nack received.

12. The method of claim 11, wherein the response period is a predetermined time.

13. The method of claim 11, wherein the response period is a dynamically determined time determined from measured frame travel times.

14. The method of claim 1, wherein the channel is a bidirectional channel and each node on the channel sends and receives frames.

15. The method of claim 1, further comprising the steps of:

assigning a priority to each frame being transmitted, the priority selected from a set of priorities; and

handling frames of differing priorities with differing logical channels.

16. The method of claim 1, wherein the channel is part of a network connecting a plurality of senders and a plurality of receivers, the method further comprising the steps of:

including a source identifier and a destination identifier in each frame transmitted from a source sender; and

selectively processing, at a destination receiver, those frames having a destination identifier identifying the destination receiver.

17. The method of claim 16, wherein the destination identifier identifies a plurality of broadcast receivers, the method further comprising a step of broadcasting a frame sent from the sender by including, in the frame, the destination identifier identifying the plurality of broadcast receivers.

18. The method of claim 1, wherein the channel is one of a telephone wire, a cable, a radio frequency link or a power wire.

19. The method of claim 1, wherein the indication of the missed prior frame includes a frame identifier of a first missed frame and a number of sequential missed frames following the first missed frame.

20. The method of claim 1, wherein the frame identifiers are reusable frame identifiers.

21. The method of claim 1, wherein the step of storing contents of the frame is a step of storing contents of the frame for a buffer period.

22. The method of claim 21, further comprising a step of tracking a buffer period for each frame.

23. The method of claim 1, wherein the storage constraint is either a time constraint, where frames are released after a buffer period, or a storage constraint, where an oldest frame is released when a new frame is to be stored in the frame buffer and the frame buffer is full.

24. In a frame-switched network apparatus, a method of sending frames from a sender to a receiver over a possibly unreliable channel, the method comprising the steps of:

forming a frame at the sender, wherein the frame contains data to be transmitted to the receiver;

including a frame identifier in the frame selected from a set of frame identifiers;

retaining a copy of the frame at the sender;

sending the frame from the sender to the receiver over the channel, independent of the availability of the receiver;

upon receipt of a frame at the receiver, identifying a frame identifier for the received frame;

detecting, from the frame identifier, if a prior frame was received in error;

if an errored prior frame is detected in the step of detecting, sending a negative acknowledgment (nack) from the receiver to the sender, the nack including an indication of the errored prior frame;

if a nack is received at the sender, determining the frame identifier of the errored prior frame and resending the errored prior frame if a copy of the errored prior frame is still retained at the sender; and

releasing the retained copy of the transmitted frame when a storage constraint is reached.