GB2489281A

GB2489281A - Automatic Repeat Request (ARQ) scheme

Info

Publication number: GB2489281A
Application number: GB1104972.3A
Authority: GB
Inventors: Patrice Nezou; Pascal Viger; Julien Sevin
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 2011-03-24
Filing date: 2011-03-24
Publication date: 2012-09-26
Anticipated expiration: 2031-03-24
Also published as: GB201104972D0; GB2489281B

Abstract

A method is proposed for sending from a transmitter to a receiver a set of data comprising at least a data frame including a plurality of data blocks each comprising a plurality of data units; the data frame including a plurality of error detection codes each associated with a corresponding data block. The method comprises the following steps: - sending the data frame with error detection data adapted to allow the receiver to determine of a number of erroneously received data units in a block 620; - receiving, at the transmitter 650, 660, information from the receiver indicating which blocks in the frame were received erroneously and indicating, for at least an erroneous block, a number of data units received in error in said erroneous block. The error detection data may include a plurality of error detection codes each associated with a corresponding data unit 620. The transmitter may use the indicated number of erroneous data units to determine a re-transmission scheme 670, wherein a redundancy packet is computed according to the re-transmission scheme determined and sending the redundancy packet to the receiver to allow it to correct the previously erroneously received data units. The redundancy packet may be obtained by encoding the erroneous block according to a selected coding algorithm such as Reed-Solomon coding 691. The information from the receiver may comprise a bitmap indicating erroneous blocks within the frame 640. One embodiment of the method described is for use with aggregated packets (Figure 3) such that the number of erroneous MSDU data units in each MPDU block of a received A-MPDU frame is indicated. The corresponding receiving method is described in Figure 7.

Description

SENDING METHOD, RECEIVING METHOD AND ASSOCIATED DEVICES,

COMPUTER PROGRAM AND INFORMATION STORAGE MEANS

The invention lies in the technical field of communication networks and relates to a sending method, to a receiving method and to associated devices, computer program and information storage means.

The invention pertains to a technique for transmitting a data stream by means of a sending device to a receiving device through a communications network, and more particularly to wireless communication stations.

Error control techniques are extensively used in data communication systems to restore data integrity when data is corrupted by transmission errors or is lost.

As an example, a radio channel can cause errors in transmitted packets under the influence of interferences among users, noises and so forth.

There are many error correction algorithms. One of the most used techniques is the ARQ (Automatic Repeat Request) algorithm. In the ARQ technique, a return link is used to request re-transmission of the wrong or lost packets. An error-detecting code, a checksum for example, is used in combination with a certain retransmission protocol. Thus the receiver can send an Acknowledgment (ACK)/Negative Acknowledgment (NACK) signal for notifying a transmitter of whether or not received packets are erroneous. The ACK signal confirms to the transmitter that the receiver has received the corresponding packets. In contrast, the NACK signal confirms to the transmitter that the receiver has failed to receive the corresponding packets. If the transmitter receives the NACK signal, the transmitter retransmits the corresponding packets to the receiver. Corrupted or lost data packets are transmitted repeatedly until correctly received by the receiver.

An improved ARQ scheme is the block ARQ scheme. A transmitting device can transmit up to N data packets in a transmission window before receiving any acknowledgement (ACK) messages from a receiving device. The receiving device may acknowledge data packets received from the transmitting device using a conventional flat bitmap. In such a flat bitmap, one bit, called an acknowledge/negative acknowledge (ACK/NACK) bit, is used to indicate acknowledgement or absence of acknowledgement for each individual data packet in the transmission window. In practice, an ACK/NACK bit is set to "1"if a corresponding packet has been received. Otherwise, the ACK/NACK bit is set to "0".

To limit the bandwidth overhead of the retransmitted data packet, the prior art (such as described for instance in patent application US 2006/034 277) proposes a hierarchical ARQ scheme in which reception results of a plurality of transmitted packets or blocks are acknowledged as a group through a block ARQ message. For instance, each data block can be divided into M data units of data. In such an ARQ scheme, when one or more data units in a block is erroneous, the basic bitmap of the ACK message is extended by an additional bitmap indicating the position (within the block) of each erroneous data unit.

Using this kind of information, the sender can retransmit only the erroneous data unit(s) (i.e. not the whole block), thus reducing the bandwidth overhead of retransmitted data.

The main problem targeted by the hierarchical ARQ scheme is the extra bandwidth consumed. However, such an extended ACK message requires additional bandwidth in the return link, in order to indicate in details the erroneous data unit(s), and thus to allow a better tuned retransmission.

Nowadays, for instance in the context of heavy interactive video wireless transmissions, the two directions (e.g. either downlink or uplink with respect to a wireless access point) should be optimized.

It is thus desirable to propose a new ARQ scheme, optimizing the two directions (DATA and ACK) in order to minimize overall bandwidth and global latency in delivery.

In this context, the invention provides a method for sending a set of data comprising at least a data frame including a plurality of data blocks each comprising a plurality of data units, said data frame including a plurality of error detection codes each associated with a corresponding data block, said method comprising the following steps: -sending the data frame with error detection data adapted to allow determination of a number of erroneous data units in a block; -receiving information indicating which blocks in the frame are erroneous and designating, for at least an erroneous block, a number of erroneous data units in said erroneous block.

By exchanging data designating the number of erroneous data units without having to precisely locate these erroneous data units within the concerned block, the size of data representing the feedback info martion can be reduced.

According to a possible embodiment, said information includes a first message indicating which blocks in the frame are erroneous and a second message separate from the first message and designating said number of erroneous data units. The first message can thus be the acknowledgement message used in a standard method.

Said error detection data includes for instance a plurality of error detection codes each associated with a corresponding data unit. As further explained below, the number of erroneous data units can then be computed by determining which data units are erroneous and counting these erreoneous data units.

In order to allow retrieval of the erroneous data units without knowledge of their location at the transmitter side, the method may for instance comprise the following steps: -determining a retransmission scheme based on said number of erroneous data units; -computing a redundancy packet according to the retransmission scheme determined; -sending the computed redundancy packet.

The redundancy packet (in particular its size) is thus adapted for recovery of the original block (received with errors at the receiver side) taking into account the number of erroneous data units.

Determining the retransmission scheme includes for instance selecting a coding algorithm; said redundancy packet may then be obtained by encoding said erroneous block according to the selected coding algorithm. A coding algorithm best suited for the recovery of the original block can thus be selected in consideration of the number of erroneous data units in the block.

In an embodiment described below, the coding algorithm is selected such that data forming the erroneous data units and data forming the redundancy packet are of equal size. It may then be expected that data forming the redundacy packet is suficient to recover the original packet, in particular due to the fact that the location of the erroneous data units is known at the receiver side.

In a possible embodiment, said information (in particular said first message) includes a bitmap designating erroneous blocks within said frame.

The number of erreoneous data units exchanged between the receiver and the transmitter as feedback information may for instance in practice be coded on a number of bits.

The method may then comprise a step of receiving a data field indicative of said number of bits. The number of bits used may thus vary, for instance depending on the number of erroneous blocks within the frame. A fixed data size may accordingly be used for designating the numbers of erroneous data units for the respective erroneous blocks of the frame. This further contributes in reducing the size of the feedback information.

It can also be noted that the invention makes it possible that the number of bits mentioned above can in practice be strictly smaller than the number of data units per block.

The invention also provides a method for receiving a set of data comprising at last a data frame including a plurality of data blocks each comprising a plurality of data units, said frame including a plurality of error detection codes each associated with a corresponding data block, said method comprising the following steps: -receiving the data frame with error detection data adapted to allow determination of a number of erroneous data units in a block; -sending information indicating which blocks in the frame are erroneous and designating, for at least an erroneous block, a number of erroneous data units in said erroneous block.

Some of the possible features of this receiving method are common with those of the corresponding transmitting method described above and will not be repeated.

As mentioned above, said error detection data may include error detection codes associated with respective data units of said erroneous blocks.

The method may thus comprise the following steps: -determining erroneous data units in said erroneous block by applying an error detection algorithm using said error detection codes; -determining said number of erroneous data units by counting said determined erroneous data units.

In order to adapt to the possible transmitting method described above, the receiving method may comprise the following steps: -selecting an error correcting scheme based on said number of erroneous data units -receiving redundancy data; -correcting said erroneous data units using said erroneous block and said redundancy data, based on said error correcting scheme.

In addition, the receiving method may comprise a step of storing data indicative of the location of said erroneous data units in said erroneous block the step of correcting said erroneous data units further may then use said indicative data. As explained above, recovery of the original block will thus be possible with redundancy data having a limited size.

The invention also provides a device for sending a set of data comprising at least a data frame including a plurality of data blocks each comprising a plurality of data units, said data frame including a plurality of error detection codes each associated with a corresponding data blocks, said device comprising means for sending the data frame with error detection data adapted to allow determination of a number of erroneous data units in a block; and means for receiving information indicating which blocks in the frame are erroneous and designating, for at least an erroneous block, a number of erroneous data units in said erroneous block.

The invention further provides a device for receiving a set of data comprising at last a data frame including a plurality of data blocks each comprising a plurality of data units, said frame including a plurality of error detection codes each associated with a corresponding data block, said device comprising means for receiving the data frame with error detection data adapted to allow determination of a number of erroneous data units in a block; and means for sending information indicating which blocks in the frame are erroneous and designating, for at least an erroneous block, a number of erroneous data units in said erroneous block.

The invention also provides a computer program comprising instructions for implementing one of the methods proposed above when the program is loaded and executed by a programmable apparatus.

Lastly, the invention provides information storage means, readable by a programmable apparatus, storing computer program instructions for implementing one of the methods proposed above when the program is loaded and executed by the programmable apparatus.

Other features and advantages of the invention will appear in light of the following description, made with reference to the appended drawings, where: -Figure 1 shows an examplary communication system; -Figure 2 shows a possible embodiment of a communication apparatus; -Figure 3 illustrates the aggregation scheme proposed by the 802.lln standard; -Figure 4 illustrates the structure of a 802.lla/b/g block acknowledgement message; -Figure 5 illustrates the structure of an extended block acknowledgement message according to a possible embodiment of the invention; -Figure 6 is a block diagram showing a method for transmitting data according to a possible embodiment of the invention; -Figure 7 is a block diagram showing a method for receiving data according to a possible embodiment of the invention; -Figure 8 illustrates an example of a block acknowledgment message proposed in an embodiment of the invention.

Figure 1 shows an example of a communication system where the present invention can be implemented. A sending device 101 transmits a plurality of data packets or blocks to a receiving device 102 through a transmission channel 100 that may drop or corrupt the data packets. Feedback information is transmitted from the receiving device 102 to the sending device 101 in order to provide status information on the received data packets.

Figure 2 is a block diagram illustrating a schematic configuration of a communication apparatus 200. The sending device 101 and the receiving device 102 of Figure 1 are for instance each implemented by such a communication apparatus.

Reference numeral 202 corresponds to a random-access memory or RAM, which functions as a main memory, used by a central processing unit (or CPU) 201. The memory capacity of RAM 202 can optionally be expanded by an optional RAM connected to an expansion port (not illustrated). CPU 201 is capable of executing instructions stored in program read-only memory or ROM 203 on powering up of the communicating apparatus. After the powering up, CPU 201 is capable of executing instructions from main memory 202 relating to a software application after those instructions have been loaded from the program ROM 203 or the hard-disc (HD) 206 for example. Such software application, when executed by the CPU 201, causes the steps of the process shown in the flowcharts of Figure 6 and/or Figure 7 to be performed.

Reference numeral 204 corresponds to a network interface that allows the connection of the communication apparatus 200 to the communication channel 100. Data blocks are written to the network interface for transmission or read from the network interface for reception under the control of the software application running in the CPU 201. Reference numeral 205 represents a user interf ace to display information to, and/or receive inputs from, a user.

An example of a communication system as shown in Figure 1 is a wireless network, such as Wireless Local Area Network (WLAN), where a sending device 101 and a receiving device 102 may operate. An example of such environments is described in IEEE 802.lln-2009, which is an amendment to the IEEE 802.11-2007 wireless networking standard aiming at improving network throughput over the two previous standards -802.lla and 802.llg -with a significant increase in the maximum raw data rate from 54 Mbit/s to 600 Mbit/s.

Aside many improvements, IEEE-802.1 in has improved the efficiency of the MAC (Media Access Control) protocol using a single acknowledgment (ACK) mechanism for multiple frames and the ability to aggregate multiple frames into a single transmission.

The 802.11 n standard provides that multiple data blocks can be sent per single access to the medium by combining blocks together into one larger set of data, called a frame herebelow. Thus, there are two forms of aggregation: Aggregated Mac Service Data Unit (A-MSDU) and Aggregated Mac Protocol Data Unit (A-MPDU): -A-MSDU creates a block (almost 8 kbytes) by combining data units with the same physical source and destination end points and the same traffic class (i.e. QoS) into a (larger) block with a common MAC header; -A-MPDU (up to 64k bytes) is essentially a chain of individual 802.11 blocks sent back-to-back with one access to the medium. All the MPDU blocks within an A-MPDU frame are addressed to the same receiver address.

Figure 3 shows the complete aggregation scheme proposed by 802.lln.

The typical 802.11 MAC block (MPDU block 320) can transport an A-MSDU encapsulation 322, formed of K unitary MSDU data units 330, each containing: -an MSDU 340 received from the upper layer; -the data unit header 3301, having a length of 14 octets (Le. 14 8-bit bytes) and consisting of a 1 6-bit MSDU length field, a 6-octet source address of the constituent MSDU 340, and a 6-octet destination address of the constituent MSDU. The MSDU length field indicates the length, in octets, of the constituent MSDU 340; -padding 3302: the header 3301 together with MSDU 340 are padded with 0 to 3 bytes to round the data unit 330 to a 32-bit word boundary.

The MAC header 321 of MFDU block 320 is a classical 802.11 MAC header (30 byte-long) comprising: -the destination address of the A-MSDU, Le. the address of the receiving device that is the next immediate intended receiver of the aggregated frame; -the source address of the A-MSDU, Le. the MAC address of the transmitting device that created the A-MSDU; -other fields (Frame control, Duration/ID, Sequence Control, QoS control and HT Control) that characterize the MSDUs of the A-MSDU body 322: the QoS control contains for example one bit flag indicating the presence of an A-MSDU in the body of the MAC frame.

The FCS (Frame Check Sequence) field 323 of MPDU block 320 is the classical CRC-32 checksum (i.e. error detection code), used to validate the integrity of the MFDU block 320.

In an A-MPDU frame 300, fully formed MAC PDU blocks 320 are logically aggregated at the bottom of the MAC. Each MPDU block 320 is prefixed by a MPDU delimiter 310 and possibly padded (by padding zone 3102) to round to a 32-bit word boundary. The MFDU delimiter 3101 embeds a proper CRC field and a length field, useful for a receiver to respectively validate its integrity and parse the A-MFDU framing structure.

In order to improve transport efficiency, A-MSDU aggregation may be used in combination with A-MFDU aggregation to increase the amount of data in a single transmission.

Like any wireless transmission, the larger the frame is, the less likely it will be received with no errors. Accordingly the standard provides that, unlike in an A-MSDU, individual MPDU blocks have their own error detecting code or CRC: an error in one MPDU block can thus be distinguished from errors affecting other MPDU blocks in the A-MPDU frame.

It should be noticed also that error in wireless transmission are generally related to data integrity, whereas error in wired transmission are mostly due to data loss (due to network congestion).

Figure 4 displays the format of a 802.lla/b/g Block-Acknowledgement message (BA message, 400).

To inform the sender which blocks have been lost in a frame, a "Block ACK Bitmap" field 440 is designed in the BA message 400 as illustrated.

It is a 8-byte field in case of compressed BA or 128-byte field in case of uncompressed BA, and thus it can support up to 128 * 8 = 1024 blocks in a single frame.

A "Block ACK Starting Sequence Control' field 430 is used to record the sequence number of the first block in the frame concerned. A "BA control' field 420 is used for quality-of-service negotiation between sender and receiver MAC layers (e.g. acknowledgement policy, compressed BA or not, traffic identifiers). A "BA heade( 410 contains the address of the transmitter and of the receiver, for instance. The FCS field 450 is the classical CRC-32 checksum, used to validate the integrity of the BA message.

According to the 802.lla/b/g, each frame is acknowledged immediately following each transmission. This added robustness is however to the detriment of flexibility as no one can thus transmit a frame while the current sender is waiting for an ACK.

802.11 n adds a block acknowledgement (BA) mechanism in which multiple frames can be streamed out and acknowledged by a single message.

This cuts the waiting time between frame transmission and allows just the missing frames or frames received in error to be resent by checking a compressed bitmap. The transmitter needs send only one BA request (BAR) to the receiver.

Figure 5 displays the format of an extended Block-Acknowledgement message (Multi-TID BA frame, or multi-traffic-identifier BA frame 500) defined in conformity with the 802.lln standard in order to inform the sender which blocks have been lost in an A-MFDU frame and have to be retransmitted. Such a Multi-TID BA message may cover several data flows identified by corresponding traffic identifiers.

The BA header 510 is the same as the one of the 802.1 la/bIg Block-Acknowledgement message 400 just described. The BA Control field 520 is extended with additional fields such as a multi-TID field 522. Associated with the compressed bitmap field 523, it defines the format of the Block Acknowledgement Information field 540. In the case of a Multi-TID BA message, the Tb_INFO field 526 contains the number of TIDs (Le. traffic identifiers) present in the Multi-TID BA message. The 802.11 n standard provides no specific use for the field 524 in the standard Multi-TID Block Ack message and is viewed as a reserved field as the field 525 shown in Figure 5.

The Block Ack information field 540 comprises multiple sets of "Per TID lnfd' subfield 541, "Block Ack Starting Sequence Control' subfield 542 and "Block Ack bitmap" subfield 543 (La one such set per data flow or TID). As a standard usage, the "Block Ack Starting Sequence Control' contains the sequence number of the first MSDU or A-MSDU for which this Block Acknowledgement message is sent. The "Block Ack bitmap" subfield 543 indicates, for each MPDU block of the concerned TID, whether the MPDU block has been correctly received or not.

It is proposed here to use an extended Multi-TID BA message, called thereafter a redundancy Multi-TID Block Acknowldegement message, formed by the receiver to notify to the transmitter the number of erroneous MSDU data units in each erroneous MPDU block of the A-MPDU frame.

In such a redundancy Multi-TID Block Acknowldegement message, the "Block Ack bitmap" subfield 543 contains the number of erroneous MSDU units for erroneous MPDU blocks only. An additional subfield 524, called "Number of significant bits per block' field, is used by the receiver to notify to the transmitter the number of significant bits per block in the "Block Ack bitmap" field 543. This number is the same for all blocks acknowledged in the same Multi-TID BA message. Thus, the use of n significant bits per block allows defining 2 combinations to notify the number of erroneous MSDU units in an MFDU block. As the "Block Ack bitmap" subfield is an 8-byte field, the number of significant bits per block depends on the number of erroneous MSDU data units, as further explained below.

Figure 6 shows a method for transmitting data from the sending device 101 according to a possible embodiment of the invention. This method allows the transmission of data units from a list L of data units to be transmitted.

The list L represents for example a buffer memory containing data units. A data unit is written in the buffer if it is to be transmitted, and is removed from the buffer after being well received. Consequently, the buffer memory, and thus the list L, is assumed to be continuously updated by the sending device 101 in order to contain only data units that are waiting for transmission. The way of implementing the list L just mentioned is not limitative and any other implementation can be used, such as using one buffer memory for storing all units and tagging those that are waiting for transmission.

In accordance with 802.lln usage, the L data units are MSDU data units (such as data unit 340 shown in figure 3). According to the used aggregation scheme (mostly related to MSDU size), those units are encapsulated in any of the following modes according to the figure 3: -as MSDU data units 330 in an A-MSDU 322; -as MFDU blocks 310 in an A-MFDU frame 300.

Upon the reception of data units to transmit to a receiver (step 610), the sending device aggregates a list L of k MSDU data units into a MFDU block b and fills the appropriate headers such as the sequence number (step 620).

In accordance with the 802.lln standard, a dedicated field 323 allows to add an error detection code (FCS) relating to each MFDU block of the A-MFDU frame.

Additional error detection codes or FCS, related to each MSDU data unit 340, can furthermore be included inside the MSDU data unit itself. As a variation, it is possible to insert this FCS in all padding fields 3302 and 3102 provided by the 802.11 standard. This solution avoids additional overhead.

These error detection codes or FCS validate the integrity of each MSDU data unit and each MPDU block on the reception side.

The A-MFDU aggregated frame is transmitted to the receiver in step 630. This A-MPDU frame may include other MPDU blocks than the MPDU block b just mentioned.

In accordance to 802.11 n usage, an acknowledgement for any of the MPDU blocks is a 802.lln Block-acknowledgement message 400 (following 802.11 standard recommendations). The "Block ACK Starting Sequence Control' field 430 associated with the "Block ACK Bitmap" field 440 indicates the MPDU block(s) in error (considered as "unacknowledged', or "negatively acknowledged').

Upon the reception of 802.lln Block Acknowledgement message, there are three possible algorithms chosen by analyzing steps 640, 641 and 650 as now explained.

If the BA message is a standard Block Acknowledgement message (answer NO in step 640), the standardized algorithm is applied: -if some MPDU blocks are erroneous (answer NO in step 641), each complete MFDU block is retransmitted at step 680 and the process jumps from step 681 to step 640 where it receives a further BA message; -if not (answer YES in step 641), the MPDU blocks are positively acknowledged and removed from the buffer; the transmitter then waits for others blocks to transmit (610).

If the BA message is a Multi-TID Block Acknowledgement message (answer YES in step 640) with no redundancy Block Acknowledgement message included (answer NO in step 650), the standardized algorithm is also applied: -if some MPDU blocks are erroneous (answer NO in step 641), the complete MPDU block is retransmitted at step 680 and the process jumps from step 681 to step 640 where it receives a further BA message; -if not (answer YES in step 641), the MPDU blocks are positively acknowledged and removed from the buffer and the transmitter waits for other blocks to transmit (610).

If the BA message is a Multi-TID Block Acknowledgement message with redundancy Block Acknowledgement message included (answer YES in both steps 640 and 650), the sending device 101 analyzes the acknowledgement related to the first referenced MFDU block (step 660). In particular, the sending device 101 reads the number of erroneous MSDU data units in this first referenced MPDU block; as noted above and further explained below, this number is indicated in the "Block Ack bitmap" subfield 543 of the redundancy Multi-TID Block Acknowldegement message.

The sending device 101 retransmits the complete MPDU block (step 671) if the number of erroneous MSDU data units is set to a predefined value, "0" for instance (as determined in step 670). In 802.lln context, the MAC Header 320 of the retransmitted block has to be composed as follow: the retry' flag is set to 1 in the Frame control field, and the Sequence Control' duplicates the starting sequence number used for the erroneous source block.

If the number n of erroneous MSDU data units for a dedicated MPDU block b is determined in step 670 to be different from the previous predefined value, a recovery procedure is executed as now explained. This recovery procedure builds and transmits a redundancy packet correcting all erroneous MSDU data units inside the currently analyzed MPDU block. Only the redundancy packet is transmitted, not the original MPDU block.

As recalled above, for a dedicated MPDU block, the redundancy Block Acknowledgement message indicates the number of erroneous MSDU data units. It is proposed here, as a possible implementation, to encode in step 690 the redundancy data (to be sent by the sender device 101 as a redundancy packet) thanks to a Reed Solomon code RS(k-i-n,k) where k is the total number of MSDU units included in the concerned MPDU block and n is the number of erroneous MSDU units in the concerned MPDU block. The parity (or redundancy) data is for instance sent in step 691 as n MSDU units included in the redundancy packet. It may be noted that parity data have to be used for retransmission (instead of the n original data units) because the sending device 101 does not know which MSDU units are erroneous (but only their number).

It has to be noticed that this redundancy packet is able to correct entirely the original MFDU block because the receiver device 102 already knows the location of the erroneous MSDU units thanks to additional error detection codes (relating to each MSDU unit) previously sent from the sender device 101 to the receiver device 102 as mentioned above. It may be reminded in this respect that, as the location of symbols in error is known, a RS(k+n,k) code can correct up to (k+n)-k, Le. n symbols, in each set of k information symbols, Le. the ratio between erroneous MSDU units and the total number of MSDU units in the concerned MFDU block.

In 802.11 n context, MAC Header 321 of the parity packet, thus corresponding to retransmission, has to be composed as follows: the "retry"flag is set to 1 in the "Frame control" field, and the "Sequence Control" duplicates the starting sequence number used for the erroneous source block.

Step 692 allows analyzing the next MFDU block referenced in the received redundancy Block Ack message. The loop ends when all MFDU blocks referenced are analyzed: step 692 then jumps to step 640 to wait for a further BA message.

Figure 7 is a flowchart describing the receiving method implemented at the receiving device 102. This method allows the recovery of erroneous data units from the list L of data units (e.g. MSDU in 802.11 context) transmitted by the sending device 101, when a sufficient number of parity data (e.g. parity MSDU units forming a parity packet according to step 691 for 802.11 context) have been received, thereby avoiding the reception of whole-size retransmitted data blocks.

At step 710, data blocks, including redundancy packets, are received by the receiving device 102. In step 720, the receiving device uses control information included in the header of the received blocks (according to the 802.11 n standard, the "retry' flag should be set to 1 in the "Frame control' field of MAC header 321 for retransmission) to identify the existence of a set of data corresponding to retransmission. A redundancy packet is identified by the number of MSDU data units contained inside the block. If the number of MSDU units is different from the number of units in the original MPDU block, it is a redundancy packet.

If test step 720 is positive, redundancy data are processed by steps 730 to 733 explained further below.

If test step 720 is negative, step 750 is executed (normal behaviour).

If it is determined at step 750 that any of the received data blocks is erroneous (FCS 323 is false), the receiving device 102 requests for additional retransmission blocks belonging to the same sequence by building a standard Block Ack message (step 751) notifying, for each MPDU block, whether it has been correctly received or not. Otherwise (i.e. if the received data frame has no error), step 740 builds a standard Block Acknowledgement message to be sent to the transmitter (sender device 101).

Back to the situation when a received block is erroneous, step 751 just mentioned is followed by step 752, which allows calculating the number n and the location of erroneous MSDU data units that can be deduced by checking the dedicated FCS for each MSDU data unit (included as noted above in the received data in relation with the concerned MSDU unit). The location of erroneous MSDU units is stored (to be used when redundancy data is received as explained below, see step 731). In the 802.11 standard context, the length of the "Block Ack bitmap" field 543 is 64-bit. In order to remain in conformity with the 802.11 standard, it is proposed to determine the number of significant bits (used for coding the number of erroneous units in a block) by dividing the length of the "Block Ack bitmap" field 543 by the number of erroneous MFDU blocks.

Based on these elements, the receiving device 102 builds at step 753 a redundancy Block Acknowledgement message as described above with reference to Figure 5. The "Block Ack bitmap" field contains the number n of erroneous MSDU data units for only erroneous MFDU blocks. As the number of significant bits is limited, all potential values cannot be encoded. In such a case, a predefined value (for instance 0) is reserved to notify that the complete MFDU block must be retransmitted. The potential encoded values vary from 1 to a maximum value depending on the number of significant bits. Figure 8 gives an example of a redundancy Block Acknowledgement message which is described below.

Step 754 stores the erroneous MFDU block to be recovered when redundancy packets are received. Step 755 builds a multi-TlD Block Acknowledgement message 500 comprising both the Block Acknowledgement message built in step 751 and the redundancy Block Acknowledgement message built in step 753. It has to be noted that this multi-TID Block Acknowledgement message can include in addition other Block Acknowledgement messages relating to other received MPDU blocks.

The receiving process then ends (step 760) until further data blocks are received (at which time the process starts again at step 710).

Steps 730 to 733 mentioned above use the received redundancy packet(s) to recover the original MPDU block and requests to the sender additional information if required.

The MFDU block concerned by the received redundancy data is determined at step 730 by reading the "Sequence Control" field of the received MAC Header 321.

Received redundancy data are then used at step 731 to recover the original MPDU block, here by Reed-Solomon decoding, based on the erroneous MPDU block previously stored (when received, see step 754) and on the stored location of erroneous MSDU units in this MFDU block.

As already recalled above, when the location of the erroneous MSDU units is known in advance, then a Reed-Solomon code can correct as many errors as there are redundant MSDU units received. In that case, the Reed Solomon code is able to obtain its highest correcting capacity.

As a result, if recovery was successfully performed (answer YES at step 732), the reconstructed block is positively acknowledged at step 740 and transmitted to the upper layer (step 733). If not (answer NO at step 732), an acknowledgement procedure is performed (step 751 to 755 described above).

Figure 8 shows an example of a multi-TID Block Acknowledgment message 800, based on a multi-TID Block Ack format described in Figure 5 and composed of a standard Block Acknowledgement message (first message) and of its associated redundancy Block Acknowledgement message (second message). Such a BA message is constructed as per the process of Figure 7.

Field 821 indicates that it is a multi-TID Block Acknowledgement message.

The standard Block Acknowledgement message (first message) is dedicated to the MPDU blocks related to the data flow referenced 3 (information in field 841 of the first message) starting from the sequence number referenced 21 (information in field 842 of the first message). This message notifies that ten MPDU blocks are erroneous (bits of value 0 in field 843). As the length of the Block Acknowledgement bitmap is 64-bit, the number of significant bits per erroneous MPDU block is equal to 6 (information in field 822), Le. the integer result of the bitmap length divided by the number of erroneous MFDU blocks.

The remaining bits are shown as padding (field 847 of the second message now described).

The next Block Acknowledgement message (second message) is understood as a redundancy Block Acknowledgement by the transmitter (sending device 101) because the transmitter has already received standardized acknowledgement information related to the data flow referenced 3 starting at the sequence number referenced 21 (mentioned in respectively

fields 844, 845 of the second message).

In that case, by reading the "number of significant bits per block' field 822, the transmitter deduces the granularity of the number of erroneous MSDU units notified in the Block Acknowledgement bitmap field 846 of the second message. Each 6-bit word of field 846 notifies the number of erroneous MSDU units for the corresponding erroneous MPDU block identified in the previous (standard) Block Acknowledgement message (first message).

In this respect, the MFDU blocks concerned by the respective numbers of erroneous MSDU units in the bitmap field 846 of the second message are, in the present embodiment, ordered in the same manner as erroneous MPDU blocks defined by the bitmap field 843 of the first message.

The transmitter can thus easily determine to which MFDU blocks respectively relate the received numbers of erroneous MSDU units.

The above example is only a possible implementation of the invention, which is not limited thereto.

Claims

CLAIMS1. Method for sending a set of data comprising at least a data frame including a plurality of data blocks each comprising a plurality of data units, said data frame including a plurality of error detection codes each associated with a corresponding data block, said method comprising the following steps: -sending the data frame with error detection data adapted to allow determination of a number of erroneous data units in a block; -receiving information indicating which blocks in the frame are erroneous and designating, for at least an erroneous block, a number of erroneous data units in said erroneous block.
2. Method according to claim 1, wherein said information includes a first message indicating which blocks in the frame are erroneous and a second message separate from the first message and designating said number of erroneous data units.
3. Method according to claim 1 or 2, wherein said error detection data includes a plurality of error detection codes each associated with a corresponding data unit.
4. Method according to any of claims 1 to 3, comprising the following steps: -determining a retransmission scheme based on said number of erroneous data units; -computing a redundancy packet according to the retransmission scheme determined; -sending the computed redundancy packet.
5. Method according to claim 4, wherein determining the retransmission scheme includes selecting a coding algorithm, and wherein said redundancy packet is obtained by encoding said erroneous block according to the selected coding algorithm.
6. Method according to claim 5, wherein the coding algorithm is selected such that data forming the erroneous data units and data forming the redundancy packet are of equal size.
7. Method according to any of claims 1 to 6, wherein said information includes a bitmap designating erroneous blocks within said frame.
8. Method according to any of claims 1 to 7, wherein said number of erreoneous data units is coded on a number of bits.
9. Method according to claim 8, comprising a step of receiving a datafield indicative of said number of bits.
10. Method according to claim 8 or 9, wherein said number of bits is strictly smaller than a number of data units per block.
11. Method for receiving a set of data comprising at last a data frame including a plurality of data blocks each comprising a plurality of data units, said frame including a plurality of error detection codes each associated with a corresponding data block, said method comprising the following steps: -receiving the data frame with error detection data adapted to allow determination of a number of erroneous data units in a block; -sending information indicating which blocks in the frame are erroneous and designating, for at least an erroneous block, a number of erroneous data units in said erroneous block.
12. Method according to claim 11, wherein said information includes a first message indicating which blocks in the frame are erroneous and a second message separate from the first message and designating said number of erroneous data units.
13. Method according to claim 11 or 12, wherein said error detection data includes error detection codes associated with respective data units of said erroneous blocks and wherein the method comprises the following steps: -determining erroneous data units in said erroneous block by applying an error detection algorithm using said error detection codes; -determining said number of erroneous data units by counting said determined erroneous data units.
14. Method according to any of claims 11 to 13, comprising the following steps: -selecting an error correcting scheme based on said number of erroneous data units -receiving redundancy data; -correcting said erroneous data units using said erroneous block and said redundancy data, based on said error correcting scheme.
15. Method according to claim 14, comprising a step of storing data indicative of the location of said erroneous data units in said erroneous block, wherein the step of correcting said erroneous data units further uses said indicative data.
16. Method according to any of claims 11 to 15, wherein said information includes a bitmap designating erroneous blocks within said frame.
17. Method according to any of claims 11 to 16, wherein said number of erreoneous data units is coded on a number of bits.
18. Method according to claim 17, wherein the method comprises receiving a data field indicative of said number of bits.
19. Method according to claim 17 or 18, wherein said number of bits is strictly smaller than a number of data units per block.
20. Device for sending a set of data comprising at least a data frame including a plurality of data blocks each comprising a plurality of data units, said data frame including a plurality of error detection codes each associated with a corresponding data blocks, said device comprising: -means for sending the data frame with error detection data adapted to allow determination of a number of erroneous data units in a block; and -means for receiving information indicating which blocks in the frame are erroneous and designating, for at least an erroneous block, a number of erroneous data units in said erroneous block.
21. Device for receiving a set of data comprising at last a data frame including a plurality of data blocks each comprising a plurality of data units, said frame including a plurality of error detection codes each associated with a corresponding data block, said device comprising: -means for receiving the data frame with error detection data adapted to allow determination of a number of erroneous data units in a block; and -means for sending information indicating which blocks in the frame are erroneous and designating, for at least an erroneous block, a number of erroneous data units in said erroneous block.
22. Computer program comprising instructions for implementing the method according to any claims 1 to 19 when the program is loaded and executed by a programmable apparatus.
23. Information storage means, readable by a programmable apparatus, storing computer program instructions for implementing the method according to any claims 1 to 19 when the program is loaded and executed by the programmable apparatus.