JP3533385B2 - Method and system for acknowledgment of data reception - Google Patents

Abstract

A method for generating acknowledgement messages in a data transmission system having a receiver for receiving datagrams and being capable of determining which of a series of datagrams have been incorrectly received, the method comprising generating a plurality of a data units, each data unit comprising: a status bit indicative of the status of the data unit; and a plurality of spacing bits together forming a binary representation of a number at least partially indicative of the spacing between one incorrectly received datagram and a succeeding incorrectly received datagram. Apparatus for carrying out various aspects of the methods are also provided.

Description

Detailed Description of the Invention

TECHNICAL FIELD OF THE INVENTION The present invention relates to data acknowledgment, and more particularly to providing an indication of erroneously received data.

BACKGROUND OF THE INVENTION In many data transmission systems, data is transmitted in the form of multiple datagrams (eg, packets). The datagram is usually in the form of binary information. A datagram can represent self-contained information or a larger portion of a message that can be recovered at the receiver by combining several received datagrams together. The packets of messages may follow different routes on the data transmission network between the transmitter and the receiver, but can be recombined back when they arrive correctly. In addition to message (payload) data, datagrams often contain control information (eg, in the form of headers). The control information usually includes the following information.

1. 1. Information identifying the receiver to which the datagram is directed. Information that identifies the datagram, for example by means of a serial number. Error check information such as checksum. Thereby, when a datagram is received, the integrity of the datagram can be checked to determine if the datagram was corrupted in transit.

Datagrams can be corrupted during transmission, especially over noisy data links such as those carried by wireless connections, so that the receiver knows which packet was erroneously received at the transmitter. It is common to implement an acknowledgment (ARQ) scheme as can be shown.
When a datagram is received, the receiver uses the datagram's header or other means of error checking data to check whether each datagram was received correctly. Then, periodically or based on a request from the transmitter, the receiver sends an acknowledgment message to the transmitter indicating which datagram was erroneously received.

Two basic types of acknowledgment messages are common. In a bitmap acknowledgment system, the acknowledgment message contains a set of bits, each bit corresponding to a single datagram. One state of the bit (eg, 1) indicates that the corresponding datagram was received correctly. Other states of the bit (eg,
0) indicates that the corresponding datagram was received in error.

Therefore, this scheme requires one bit of acknowledgment message data for each received datagram to indicate whether it was received correctly. In the list acknowledgment scheme, the acknowledgment message is erroneously identified for each datagram (eg,
Serial number). In this scheme, the number of bits required for the acknowledgment message data is the product of the number of erroneously received datagrams and the bit length of the datagram identifier.

The efficiency of these schemes depends on the proportion of erroneously received datagrams. Bitmap systems are more efficient when many datagrams are received in error. This is because the wrist system requires a relatively large bandwidth to retransmit a large number of datagram identifiers. The list system is more efficient when there are few erroneously received datagrams. Because the bitmap system
This is because each 1-bit acknowledgment data will be used even for a correctly received datagram.

Hybrid systems have been proposed to reduce the amount of bandwidth required for acknowledgments. In that case, the receiving unit selects the more efficient one of the bitmap or list systems and indicates in the acknowledgment message which method is being used.

Higher data rates are used in next generation telecommunications systems, but payload-to-header
The optimal size of a datagram with good size ratio and good resolution for error correction can be quite small. This can result in a large number of datagrams having to be acknowledged by a single acknowledgment message. For this reason, and for other reasons, it is desirable to further reduce the bandwidth required for acknowledgment messages.

DISCLOSURE OF THE INVENTION According to one aspect of the invention, a data transmission system comprising a receiver capable of receiving a datagram and determining which of a series of datagrams was erroneously received. There is provided a method for generating an acknowledgment message in
Generating a plurality of data units, each data unit having a status bit indicating the status of that data unit; spacing between one erroneous received datagram and a subsequent erroneous received datagram ( spac
ing), and a plurality of spacing bits that together form a binary representation of a number that at least partially indicates the ing).

A single acknowledgment message suitably comprises a plurality of said data units and is generated by assembling said plurality of data units, optionally with flow control information such as routing or error checking information. be able to.

According to a second aspect of the present invention there is provided a receiver for receiving a series of datagrams from a transmitter, the receiver for determining which datagram was erroneously received. A datagram check unit; and an acknowledgment message generator for generating an acknowledgment message, each acknowledgment message including a plurality of data units, each data unit having a status of the data unit. A status bit indicating
A plurality of spacing bits together forming a binary representation of a number that at least partially indicates spacing between an erroneously received datagram and a subsequent erroneously received datagram.

One value of the status bit has a set of spacing bits that together represent a numerical value indicating a spacing between one erroneous received datagram and a subsequent erroneous received datagram. The corresponding data unit preferably has a value indicating that it is not the last data unit of the contiguous data units. Therefore, the spacing can be indicated by:

1. 1. Spacing bits of a single data unit whose status bit is set to another value than said one value, or Spacing bits for multiple (properly contiguous) data units, each status bit set to said one value, and subsequent (suitably immediately following) status bits set to said other value. Following) with the spacing bits of the data unit

A datagram whose status bit is set to another value and whose spacing bit represents a predetermined value (an appropriate non-zero value) indicates the number of consecutive error received datagrams. It is preferable to show the adjacent (appropriately subsequent) data units that it represents. Therefore, a plurality of datagrams received in succession are followed by one datagram with the status bit set to the other value and the spacing bit representing a predetermined number. It may be indicated by one or more data units representing the number of consecutive error received datagrams. The number can be indicated by one or more datagrams in the manner defined above to indicate spacing.

The number of spacings and / or consecutive erroneous received datagrams indicated is in each case directly or directly a function of the actual spacings and / or numbers. Can be indirectly indicated by means of a numerical value that is, for example, a predetermined numerical value less than its actual spacing and / or number.

The acknowledgment message suitably contains data whose receipt identifies the set of datagrams described by the message, eg, of the first and / or last datagram described by the message. Contains the number of datagrams whose identity and / or receipt is described by the message. The acknowledgment message can take the form of one or more datagrams or data packets.

Each data unit is suitably composed of 4 or more bits, preferably 4 or an integer multiple of 8 bits. Each most preferred data unit consists of 4 bits. The method preferably includes the steps of generating an acknowledgment message containing a plurality of data units and sending the message to a transmitter of the datagram.

The receiver preferably comprises a memory connected to the datagram checking unit for storing information indicating which datagram was erroneously received. The memory can also be connected to an acknowledgment generator. Each datagram may include a checksum or other error checking information. The receiver, most preferably the datagram check unit, calculates a checksum for the received datagram and compares the checksum with the checksum information contained in the datagram to determine which datagram Can be appropriately determined.

The acknowledgment generator is preferably implemented in hardware. The communication link from the transmitter to the receiver preferably comprises a wireless link, which may be all or part of the communication path between them. A radio receiver is suitable as the receiver. A cellular radio terminal is suitable as the receiver. The radio link is suitably a cellular telephone radio link. A wideband code division multiple access link is suitable for the wireless link.

BEST MODE FOR CARRYING OUT THE INVENTION The present invention is described below with reference to the accompanying drawings, which are merely illustrative. Figure 1
Shows a data transmission system with a transmitter 1 and a receiver 2 connected by a two-way communication link 3 of a telecommunication system 4. The communication link 3 has a forward channel 5 and a reverse channel 6. The transmitter can send a datagram (shown at 7, 8) to the receiver on the forward channel. Each datagram has a payload 7a, 8a and a header 7b and 8b.
, And the header contains the serial number of the packet and a checksum for the packet. If the communication link is implemented as a dedicated channel (eg circuit switched connection), the link itself can indicate the identity of the receiver. If the communication link (or a portion thereof) is implemented as a common or shared channel, then the receiver's identity is preferably indicated in the header of the packet, appropriately packed.

In the telecommunications system 4, the information in the header that dedicates the channel between the transmitter and the receiver and / or the identity of the receiver is used to route the packet to the receiver. It is used. At the receiver, the received datagram is checked
Analyzed by unit 9. The check unit calculates a checksum for the received datagram and compares the calculated checksum with the checksum received in the header of the datagram. If the two checksums match, the check unit accepts the datagram and sends it to datagram processor 1.
Pass to 0. If it determines that the datagram is a control datagram, the datagram processor can cause the necessary action to be taken depending on the content of the datagram. If the datagram payload represents message data, the datagram processor reassembles it with other datagram payloads if necessary, reassembles the entire message, and stores it in memory. It is stored in 11.

If the check unit determines that the calculated checksum does not match the received checksum, the check unit indicates to the acknowledgment unit that the datagram was erroneously received, eg the serial number of the erroneously received datagram. Notify the acknowledgment unit 12 by passing. Acknowledgment units are responsible for acknowledging messages 13, 1
4 can be transmitted to the transmitter on the reverse channel 6 to indicate to the transmitter which datagram was erroneously received. If the transmitter receives an indication that a datagram was erroneously received, the transmitter can retransmit the datagram to the receiver.

The datagram processor also informs the acknowledgment unit that the datagram was erroneously received if no expected datagram was received at the receiver after some time. To do this, the datagram processor determines the expected datagram serial number and sends it to the acknowledgment unit. The non-receipt of the datagram may occur, for example, if the datagram processor received only 6 out of 10 datagram messages.

Datagrams may not be received correctly because of damage in transit, such as noisy links.
Or due to other disturbances or due to loss or excessive transmission delay time due to a failure or overload in the telecommunication system. There are two modes of operation of the acknowledgment unit. Unsolicited
In the ed) mode, the acknowledgment unit sends an acknowledgment message to transmitter 1, periodically, for example after 100 datagrams have been received from the transmitter (or
Sent every time (after it should have been received). In solicited mode, the acknowledgment unit sends an acknowledgment message to transmitter 1 on demand, or to transmitter 1 when it determines that there should be such a request. (Eg, at the end of the received message).

The acknowledgment message 13, 14 transmitted from the acknowledgment unit to the transmitter 1 comprises a payload 13
It is sent in the form of a datagram containing a, 14a and headers 13b, 14b. Acknowledgment datagram 13,
The format of the header of 14 may be the same as or different from the format of the headers 7b and 8b, but it is preferable that both are compatible.

The payload of each acknowledgment datagram is
It contains a series of 4-bit elements. Each 4-bit element may contain information about at least one erroneous received datagram. Each 4-bit element contains two semantic parts. In most situations, the first three bits of the element are interpreted as the "offset part", a number from 0 to 7 is represented in binary form, and the last bit of the datagram is interpreted as the "state part". Which represents a logic state 1 or 0.

Upon receipt of the signal from the check unit or datagram processor, the acknowledgment unit locally receives the serial number of the erroneously received datagram.
It is stored in the memory 15. Upon determining that the acknowledgment message should be sent, the acknowledgment unit determines that the sending unit 1
Parse the stored list to generate a 4-bit element to send to the transmitter via 6.

4 to carry the acknowledgment message
Bit elements are used to represent a series of numbers. One number is represented by the following process. The number, represented in binary 1, is divided into chunks of three consecutive bits starting with the three least significant bits. The final, most significant chunk is padded with 0's if necessary so that it occupies 3 bits. 2. If the number represented is greater than 7, then there are two or more chunks. Each chunk except for the chunk of the most subordinate each chunk forms the offset portion is formed in the 4-bit elements consecutive its status bit is set to 0. 3. Chunk of most subordinate is formed in the last 4-bit elements, in which that chunk forms the offset portion, the status bit is set to 1.

For example, the following table shows some numerical values formed by the above method and their equivalent representation in 4-bit elements.

[Table 1]

To represent the erroneous reception of a series of datagrams by means of a 4-bit element, the acknowledgment unit carries out the following steps. 1. The number of the first erroneously received datagram in the series of datagrams is determined. The number is encoded in the payload of the acknowledgment message. 2. For each subsequent erroneous received datagram, the acknowledgment unit determines its offset by the number of datagrams between that datagram and the previous erroneous received datagram of the series. The number is encoded into 4-bit elements as described above.

The series of 4-bit elements generated in this way is formed into a bit stream and transmitted to the transmitter in one or more datagrams. At the receiver, the 4-bit element is decoded by the reverse process to know which datagram was not received correctly. The datagrams are then retransmitted to the receiver. The number of the first erroneous received datagram may be indicated as the number of that datagram (eg, 5 if the fifth datagram is the first erroneous received datagram).

In the above scheme, the 4-bit element 000
1 is never generated. This is because the acknowledgment unit has no reason to represent a zero offset between one erroneously received datagram and the next. Therefore, element 0001 is used to represent a burst of datagrams. A burst of datagrams represents, in the usual way, the first erroneous received datagram of that burst (by means of its offset), followed by the element 0001, followed by the number of subsequent consecutive erroneous received datagrams. The elements follow as above.

When the length of each element is 4 bits, preferably only the latter method is used to represent a burst of 4 or more erroneously received datagrams. Because,
Otherwise, the efficiency cannot be improved. If it is known that this method will only be used for bursts of four or more datagrams, the number represented by the element following element 0001 is, in some cases, the number of elements needed. Can be 1, 2, 3 or 4 less than the length of the burst.

One alternative method for representing bursts is
In normal binary notation using that element of all 4 bits, such as the first error received datagram of the burst, then element 0001, followed by an element that represents the number of subsequent consecutive error received datagrams. It is a method with a series of elements shown in the usual way. The maximum length of a burst that can be represented by three elements in this way is 20 (this method is not used for bursts of consecutively error-received datagrams less than four, and the latter datagram (Assuming the number represented is 4 less than the total burst length). However, in systems where long bursts of erroneously received datagrams are relatively infrequent (eg, in fast power control of the proposed W-CDMA / UMTS system), there may be a significant reduction in efficiency.

For completeness, the acknowledgment message is
It is also preferable to indicate the range of datagrams it covers. This allows the transmitter to lose the acknowledgment message or recover from its collapse.
The acknowledgment message is the number of received datagrams it covers and / or the first covered and / or
Or it can indicate the identity / serial number of the last datagram. In the most preferred arrangement, each acknowledgment datagram describes the first error packet within the range of packets covered by the acknowledgment datagram, followed by the subsequent error packets within that range. Contains a series of 4-bit elements.

As an example of the above method, if the datagrams numbered 5 to 14, 31, 33 and 36 out of 100 datagrams were erroneously received, the table below is generated by the acknowledgment unit. It shows those numbers and the corresponding 4-bit elements that can be made to be transmitted to the transmitter.

[0038]

[Table 2]

In general, the encoding of acknowledgments according to the above method can include: A data section indicating the position within the overall message of the start or end of the window of the datagram covered by the acknowledgment message; a data section indicating the position of the first erroneously received datagram within that window. A series of data sections indicating offsets for subsequent erroneously received datagrams and / or bursts of erroneously received datagrams

In some situations, the acknowledgment unit may further reduce the bandwidth by first determining the minimum spacing in the set of datagrams considered between erroneously received datagrams. That spacing can be sent to the transmitter in an acknowledgment message, and all transmitted offsets can be subtracted to reduce (in some cases) the number of bits required to represent them.

Instead of a 4-bit element, the number of bits of that element may be any other value, preferably less than or greater than four. In an n-bit element, it can also include one bit in the state part and (n-1) bits in the offset part. The optimum number of bits to give maximum efficiency for a particular application can be determined by simulation.
For efficient packing and alignment of elements, it is also preferred that the element length be an integral multiple of the system byte length or the system byte length divided by an integer. For example, in a system based on 8-bit bytes, the bit length of the element is 4 or 8
It is preferably an integral multiple of bytes or 8 bytes.
This facilitates byte alignment of elements for efficient coding and transmission.

The acknowledgment method described above can be applied to digital wireless communication systems, such as digital cellular telephone systems, and especially the proposed third generation W-CDM.
In A (Wideband Code Division Multiple Access) or 3GPP systems, it offers particular efficiency advantages for the following reasons.

1. In some systems, the use of bandwidth on the reverse link may be relatively unimportant. For example, if the reverse link is fixed and assigned, the bandwidth is relatively large. But W
-In CDMA systems, the use of bandwidth on the reverse link causes interference with other transmissions on the same frequency band, causing the signal-to-noise ratio of those other transmissions to decrease. Therefore, an efficient acknowledgment scheme is particularly advantageous. The use of an element with 2.4 bits is well suited to the bit / frame scheme of the proposed W-CDMA system and allows byte alignment. This conveniently sends a 4-bit element. 3. In order to achieve a very high data rate, the acknowledgment unit for generating the acknowledgment message is preferably implemented at a very low level of the terminal, possibly at the hardware level rather than the software. The acknowledgment method described above is not logically complex and is particularly suitable for low level implementations. Choosing element lengths that conveniently fit into the framework of existing protocols also supports low-level implementations. 4. In wireless systems, erroneously received datagrams occur in bursts relatively frequently, due to temporary interruptions or delays in power control, etc. The above method provides one way of describing bursts of erroneously received datagrams.

In the 3GPP / W-CDMA system, the method of the present invention uses the USTAT from the receiving unit in the acknowledged data transfer mode in which the format of the status PDU (Protocol Data Unit) is suitable.
It can be advantageously used for (unsolicited status) and / or STAT (solicited status) reporting.
Acknowledgment datagrams, such as those described above, can be stored in AMD (acknowledged mode data) PDU and / or UM
It can be used for D (data in non-acknowledged mode) PDU. The PDU may carry sequentially numbered protocol units containing RLC (Radio Link Control) SDU (Service Data Unit) data (3GPP RLC draft specification TS 25.322 V1.0. 0).

In simulation, the above acknowledgment method has been found to be more efficient than bitmap, list or hybrid systems. The following table shows the number of bits required to send an acknowledgment message for an erroneously received datagram shown from a set of 100 datagrams.

[0046]

[Table 3]

In another simulation,
Assume that datagram transmission on a W-CDMA data channel evaluates random frame loss for a selected frame error rate and that all datagrams inside the lost frame are erroneously received. Simulated by The simulation is UST
Performed for NRT data traffic with AT capabilities, a USTAT report was generated every third frame and every 100 sessions. 18,000 datagrams were generated. FSN (first sequence number) and MSN
The (highest sequence number) field was considered mandatory. The results are shown in the table below.

[0048]

[Table 4]

The length of the datagram may be fixed or variable. All or part of the communication link between the transmitter and receiver may be a wireless link. The transmitter and / or receiver may be a wireless terminal. The datagram may be a packet or protocol data unit. Suitably, the data transfer system or a part thereof is a mobile communication network or is a part thereof, for example a mobile telephone network such as the proposed UMTS system or a derivative thereof.

The invention limits any feature or combination of features disclosed herein, either implicitly or explicitly, or its general form to the scope of any of the claims of the invention. Note that it can be included without being done. From the above description, it will be apparent to those skilled in the art that various modifications can be made without departing from the scope of the invention. [Brief description of drawings]

FIG. 1 shows a data transfer system.

─────────────────────────────────────────────────── ─── Continuation of the front page (58) Fields surveyed (Int.Cl. ⁷ , DB name) H04L 1/16 H04L 29/08

Claims (20)

(57) [Claims] 1. A method for generating an acknowledgment message by a data transfer system having a receiver capable of receiving a datagram and determining which of a series of datagrams was erroneously received. Thus, the method comprises the step of generating a plurality of data units, each data unit comprising a status bit indicating a status of said data unit, an error received datagram and a subsequent error received datagram. 2 which is at least partially indicative of the spacing of
A plurality of spacing bits forming together a binary representation. 2. The method of claim 1, wherein an acknowledgment message comprises a plurality of said data units. 3. The method according to claim 1 or claim 2, wherein one value of the status bit is not the last data unit of which the corresponding data unit is of a set of consecutive data units. And the spacing bits together represent a numerical value that indicates the spacing between one erroneous received datagram and a subsequent erroneous received datagram. 4. A method as claimed in any one of claims 1 to 3, in which the other value of the status bit in the datagram in which the spacing bits represent a predetermined number indicates the number of consecutive error received datagrams. A method of indicating adjacent data units that represent a number. 5. The method of claim 4, wherein The method wherein the predetermined numerical value is 0. 6. A method according to any of claims 1 to 5, wherein the acknowledgment message comprises data identifying a set of datagrams the receipt of which is described by the message. 7. The method according to claim 1, wherein each data unit comprises 4 or more bits. 8. The method of claim 7, wherein A method in which each datagram consists of four bits. 9. A method as claimed in any one of claims 1 to 8 including the steps of generating an acknowledgment message containing a plurality of data units and sending the message to a transmitter of the datagram. How to include. 10. The method according to claim 1, wherein the communication link from the transmitter to the receiver comprises a wireless link. 11. The method of claim 10, wherein The method wherein the wireless link is a cellular telephone wireless link. 12. The method of claim 10 or claim 11, wherein the wireless link is a wideband code division multiple access link. 13. A receiver for receiving a series of datagrams from a transmitter, the receiver including a datagram check unit for determining which datagram was erroneously received, and a plurality of data units. An acknowledgment message generator for generating each acknowledgment message including, each data unit having a status bit indicating the status of the data unit, an erroneous received datagram and a subsequent erroneous received data. A plurality of spacing bits that together form a binary representation of a number that at least partially indicates the spacing to and from the gram. 14. The receiver according to claim 13, wherein the receiver comprises a transmitting unit for transmitting an acknowledgment message to the transmitter. 15. A receiver as claimed in claim 13 or claim 14, comprising a memory connected to the datagram checking unit for storing information indicating which datagram was erroneously received. Receiving machine. 16. The receiver according to claim 13, wherein each datagram includes checksum information, and the datagram check unit can calculate a checksum for the received datagram. A receiver capable of comparing the checksum with the checksum information contained in the datagram to determine if the datagram was received correctly. 17. The receiver according to claim 13, wherein each data unit is composed of 4 bits. 18. The receiver according to claim 13, wherein the acknowledgment generator is implemented in hardware. 19. The receiver according to claim 13, wherein the receiver is a wireless receiver. 20. The receiver according to claim 13, wherein the receiver is a cellular radio terminal.