Efficient automatic repeat request method using variable...

Details Efficient automatic repeat request method using variable... Efficient automatic repeat request method using variable...

1999-05-14

2003-11-25

Chin, Stephen (Department: 2634)

Pulse or digital communications

Bandwidth reduction or expansion

Television or motion video signal

C375S358000, C714S748000

Reexamination Certificate

active

06654422

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to communications; more particularly, an efficient automatic repeat request method.
2. Description of the Prior Art
FIG. 1
illustrates transmitter
10
and receiver
20
. Data messages are communicated from transmitter
10
to receiver
20
, and feedback regarding the reception of the data messages is provided from receiver
20
to transmitter
10
. The bytes in the data message are numbered sequentially to identify them uniquely at the transmitter and the receiver. The data messages from transmitter
10
to receiver
20
typically include a header field, a sequence number field, a field for bytes of data and a CRC (cyclic redundant code) field. The header field provides information such as information indicating whether the data message contains new data or a retransmission of data that was corrupted in an earlier transmission. The sequence number field contains a sequence number that identifies the bytes of data contained in the message. For example, the sequence number may identify the sequence number of the first byte of data in the data field. The second through last byte of data in the data field are associated with sequence numbers that begin with the sequence number plus 1 and continuing consecutively until a number is associated with the last data byte. The data field contains the bytes of data being transmitted from the transmitter to the receiver, and the CRC field contains a code used to detect and sometimes correct errors in the data message. When receiver
20
receives the data message, it uses the CRC field to determine whether errors have occurred. If errors have occurred, the receiver uses the sequence number field in a subsequent transmission to identify a sequence number associated with byte or bytes of data that were received incorrectly. The receiver provides feedback to transmitter
10
by sending a ACK (acknowledgment) or NAK (negative acknowledge) message to transmitter
10
. The negative acknowledge message typically includes two fields: a header field, and a sequence number and length field. Header field provides information such as information indicating that the NAK message is identifying incorrectly received data bytes, or that the NAK message is providing control information to the transmitter. The sequence number and length field include a sequence number that identifies the first byte of data that was received incorrectly and the length portion identifies the number of bytes following the sequence number that were not received or received with errors. Transmitter
10
uses the sequence number and length in the NAK message to identify bytes of information to be retransmitted in another data message to receiver
20
. In a data message containing data that is being retransmitted, the header field will indicate that the data message is a retransmission of prior data that was not received properly by receiver
20
. The sequence number of retransmitted bytes will be the same that was used when the data bytes were originally transmitted to receiver
20
. Again, the sequence number field contains a sequence number that identifies the bytes of retransmitted data contained in the message; for example, the sequence number of the first byte. The remaining bytes are consecutive.
FIG. 2
illustrates high rate and low rate data message. A high rate data message has a header field, the sequence number field, a data field and a CRC field. It should be noted that sequence number field typically includes three bytes, and in the case of a high data rate transfer, a data field may include as many as 4,000 bytes. From a point of view of efficiency, using 3 bytes for a sequence number with 4,000 bytes of information can be considered an efficient transfer. Conversely, the low rate message is inefficient. In this case, three bytes per sequence number are used to identify only 21 bytes in a data transfer message. As a result, the present scheme for providing sequence numbers used in automatic repeat request schemes are not suitable for transmission protocols that involve variable rate transmissions where messages may include either a large number of bytes or a small number of bytes.
SUMMARY OF THE INVENTION
The present invention solves the aforementioned problem by providing a variable length sequence number. The sequence number associated with the most recent data that has been received successfully and the sequence number expected with the next data message to be received are examined to determine the minimum size sequence number necessary to unambiguously identify incorrectly received data that will be retransmitted in a later message. The receiver periodically provides the transmitter with the sequence number associated with the last successfully received byte of data and the sequence number associated with the next expected byte of data. The receiver communicates this information to the transmitter using a control message. The transmitter then uses the sequence number of the next byte of data to be transmitted and the information received in the control message from the receiver to determine the smallest number of bits necessary to represent the sequence numbers for both data transmissions and the retransmission of data that was not received properly by the receiver.
V
(
S
)−
V
T
(
R
)<2
m
  (1)
Equation 1 specifies the smallest m number of bits that may be used to represent the sequence number for new data being transmitted to a receiver. V(S) represents the sequence number that the transmitter will associate with the next byte of data to be transmitted and V
T
(R) represent the sequence number received in the control message that identifies the next byte of data expected to be received at the receiver.
V
(
S
)−
V
T
(
N
)<2
n
  (2)
Equation 2 indicates the smallest value of n that can be used to represent a sequence number used to retransmit data to a receiver. In equation 2, V
T
(N) is the sequence number received in the control message from the receiver that identifies the last successfully received byte of data by the receiver.


REFERENCES:
patent: 4617657 (1986-10-01), Drynan et al.
patent: 4841526 (1989-06-01), Wilson et al.
patent: 6317430 (2001-11-01), Knisely et al.
Brown, G.M. et al.,Computer Communication Review, “Block Acknowledgement Redesigning the Window Protocol”, vol. 19, No. 4, pp. 128-135, Sep. 1, 1989.

Affiliated with

Also associated with

Rating

Efficient automatic repeat request method using variable... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient automatic repeat request method using variable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient automatic repeat request method using variable... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3172025