Source: https://patents.justia.com/patent/8341485
Timestamp: 2020-08-14 14:32:06
Document Index: 461948121

Matched Legal Cases: ['art 11', 'art 15', 'art 16', 'art 11', 'art 15', 'art 16']

US Patent for Increasing hybrid automatic repeat request (HARQ) throughput Patent (Patent # 8,341,485 issued December 25, 2012) - Justia Patents Search
Justia Patents Including Forward Error Correction CapabilityUS Patent for Increasing hybrid automatic repeat request (HARQ) throughput Patent (Patent # 8,341,485)
Sep 14, 2010 - Intel
This application is related to U.S. patent application Ser. No. 12/561,126, entitled “Method And System To Increase The Throughput of A Hybrid Automatic Repeat Request (HARQ) Protocol,” filed on 16 Sep. 2009 by Eilon Riess, et al., assigned to a common assignee, the entire subject matter which is herein incorporated by reference.
An embodiment of the present invention relates generally to wireless uplink and downlink communications and, more specifically, to methods for increasing throughput in hybrid automatic repeat request message overhead used in a wireless network.
In a wireless network, a hybrid automatic repeat request (HARQ) protocol is used to ensure high reliability and high data transmission efficiency of the wireless network. The HARQ protocol combines a forward error correction (FEC) scheme and an automatic repeat request (ARQ) scheme.
FIG. 1A illustrates a block diagram 100 of a prior art HARQ burst 120. When data is to be sent from a sending station to a receiving station in a wireless network, the data is sent in the form of medium access control (MAC) packet data units (PDUs), or sub-packets 110. The MAC layer of the sending station concatenates the PDUs 112, 114, 116, and 118 and the physical (PHY) layer of the sending station adds a preamble 122 to the concatenated PDUs 112, 114, 116, and 118 to form a HARQ burst 120 for transmission. The PDUs 112, 114, 116, and 118 are divided or partitioned into the FEC blocks 124, 126, and 128 by the PHY layer of the sending station.
The downlink (DL) throughput of the HARQ protocol used in a station may be limited to a maximum limit to guarantee that the throughput of the HARQ protocol does not exceed the buffering capabilities of the station. FIG. 1B illustrates two scenarios 150 of the memory state of a buffer in a prior art station. The first scenario, where there is no overflow of memory 160, occurs when the buffer in the station has sufficient free memory space 166 to store a HARQ sub-burst 170 that fails a cyclic redundancy check. The HARQ sub-burst 170 may be a retransmission of the same burst that has been stored in the station as the HARQ sub-bursts 162 and 164.
To increase the throughput of the HARQ protocol used in a station, the size of each HARQ sub-burst can be increased. However, increasing the size of each HARQ sub-burst has a drawback because the station may experience more memory overflows in its buffer. This is illustrated in the second scenario, where there is an overflow of memory 180, that occurs when the buffer in the station has insufficient free memory space 186 to store the HARQ sub-burst 170 that fails a cyclic redundancy check. The station therefore aborts storing the HARQ sub-burst 170 and clears the HARQ sub-burst 170.
The current HARQ protocol implementation does not allow the throughput of the HARQ protocol to be increased or to decrease the number of occurrences of memory overflow events in a wireless network.
When transmitting an HARQ burst, the burst needs to be stored until an indication that it has been received correctly from the receiver arrives at the transmitter. In the case that the burst was not received correctly, the transmitter retransmits the stored HARQ burst. As such the longer the burst needs to be stored, usually referred to as round trip time (RTT) the lower the overall throughput can be reached.
FIG. 1A illustrates a block diagram of a prior art HARQ burst;
FIG. 1B illustrates two scenarios of the memory state of a buffer in a prior art station;
FIG. 2 is a block diagram illustrating the partitioned PDUs and FECs, according to an embodiment of the invention;
FIG. 3 is an illustration of an HARQ flow in a WiMax system, according to an embodiment of the invention; and
FIG. 4 illustrates a computing system to implement the methods disclosed herein, in accordance with an embodiment of the invention.
An embodiment of the present invention is a system and method relating to increasing throughput of HARQ bursts by storing only the PDUs that are known to have errors. Another embodiment of the present invention shorten the RTT by managing the HARQ buffers to take advantage of the UL MAPs and by a buffer clearing prioritization method based on known versus un-known reception status of transmitted HARQ bursts.
In an HARQ operation, in the case a CRC failure indicates that the decoded HARQ burst is not received correctly. The HARQ burst's soft metrics are stored, i.e. for each of the received bits several LLRs (log likely-hood ratio) bits are stored. The LLR of each bit is typically represented by several bits (6 to 8 bits). Thus a stored HARQ burst of size L bits will typically occupy L×6 to L×8 bits of memory.
An HARQ burst fails if one or more of its bits have been received incorrectly.
The received HARQ bursts may be partitioned and stored into two groups:
Group 1: Group of bits that are known to not contain the error received bits
Group 2: All the rest of the bits
The bits of Group 1 are then stored, discarding the LLR representation. However, the LLR of the bits for Group 2 are stored. But avoiding having to save all of the LLR bits from Group 1, the requirements on the HARQ memory are reduced from:
Occupied memory=Size(Group 1)+(Y-Size(Group 1))×LLR_Res,
where Y is the size of the HARQ burst and LLR_Res is the number of bits by which the LLR is represented.
In one particular case, where the HARQ burst is compactly constructed by higher layer PDUs, where each PDU has its own CRC, then Group 1 may be determined by identifying FEC blocks that carry only bits from PDUs that pass the CRC check. All other FEC blocks would belong to Group 2.
In existing systems, standards with commercially deployed networks typically only have indication if the HARQ burst as a whole fails. Thus, if necessary, the entire HARQ burst needs to be stored along with the LLR expansion. Some standards, still under development, are adding CRC per FEC block.
Embodiments of the invention which partition received bits by failure/no failure, and store only the failed portion, do not involve any intervention of the transmitter or any change of standard, but allows currently deployed standards using existing hardware yield much higher HARQ throughput.
FIG. 2 is a block diagram illustrating the partitioned PDUs and FECs, according to an embodiment of the invention. A HARQ burst 200 is sent with packet data units (PDUs) A, B, C and D (201, 203, 205, and 207, respectively). The PDUs comprise a number of forward error correction (FEC) blocks 1-9 (211, 213, 215, 217, 219, 221, 223, 225 and 227, respectively). In this illustration, the CRC for PDUs A (201) and C (205) pass, so these bits are not in error. The CRC indicates that FEC blocks 4 (217) and 9 (227) have been detected with errors. Thus, the FEC blocks FEC4 (217) and FEC9 (227) must be saved for retransmission.
In an embodiment, the FEC blocks are partitioned into groups A (231) and B (233). Group A comprises the FEC blocks within the PDUs that have passed the CRC. In this example, Group A comprises FEC blocks 1, 2, 6 and 7. Group B comprises the FEC blocks within the PDUs that have failed the CRC, e.g., FEC blocks 3, 4, 5, 8 and 9. Only the PDUs in Group B must be saved for retransmission, instead of the entire HARQ burst. Assuming, for example, that the LLR_RES is 8 bits, the amount of memory saved is 1−(8×5+4)/(8×9)=1−44/72. In this example, the memory saved is about 39%.
In another embodiment, the HARQ throughput may be increased by shortening the time that the HARQ burst is stored. This time may be referred to as the round trip time (RTT). When transmitting an HARQ burst, if the burst is not correctly received, the burst needs to be stored at the transmitter until the transmitter receives an indication that the burst has been correctly received by the receiver. The transmitter must retransmit the stored HARQ burst until it has been properly received and acknowledged. As such, the longer the burst needs to be stored (RTT) the lower the overall throughput, because fewer bursts may be stored in the limited memory space.
Shortening the actual time an HARQ burst is stored from RTT to RTT-1 may be achieved by relying on the property that the uplink (UL) command (UL mobile application parts, or MAPs, in the case of 802.16 Standard, or WiMax) is known one frame before the actual UL transmission. In such a case, the UL throughput may be increased by RTT/RTT-1. For example, when RTT=5 then the HARQ throughput may be increased by 5/4=1.25. This throughput increase may be performed by HARQ buffer management, pushing up the HARQ throughput (as an example by declaring higher transmit HARQ throughput capability). In the case of memory overflow, the buffer management will store new HARQ bursts at the expense of clearing already stored HARQ bursts. This clearing is not done arbitrarily, but according to a prioritizing method based on known versus un-known reception status of transmitted HARQ bursts.
When an HARQ burst does not to need retransmission, this status may be devised from the UL MAP for WiMax and known one frame before the actual UL allocation. Existing systems have failed to take advantage of this knowledge. If the transmission has succeeded, the HARQ burst may be cleared from the HARQ memory one frame in advance of when it is cleared in existing systems. If more memory space is required for the new HARQ bursts for that frame then other stored HARQ bursts would be cleared. After clearing bursts that are known to be successful, bursts having an unknown retransmission requirement at a frame may be cleared. When an HARQ burst is known to need retransmission, then it would be kept in the HARQ memory and other bursts, at that stage/frame, have unknown retransmission needs will be cleared from the HARQ buffer, making space for the new HARQ burst.
If an HARQ burst that has been cleared needs retransmission at a later frame, the mobile station (MS) sends physical zeros at the related allocation. The faulty package is then treated by an outer-loop correction, if one exists. (e.g. ARQ, or transmission control protocol (TCP) loops).
FIG. 3 is an illustration of an HARQ flow in a WiMax system, according to an embodiment of the invention. DL1 301 and UL1 302, for instance, are downlink (DL) and uplink (UL) subframe of frame 1, respectively. Ch. A 303a-b and Ch. B 305 are carrying HARQ burst A and HARQ burst B, respectively. M A 307 and M B 309 contain the indications of the reception status of HARQ burst A and B, respectively.
In this example, the UL MAP (M A 307) for HARQ burst A is sent at DL frame 5 (DL5). This frame may indicate whether HARQ burst A was received correctly at the receiver. A determination is made at block 320 as to whether a retransmission of HARQ burst A will be required. If so, the bursts/channels from bursts other than Ch. A are cleared from HARQ memory, in priority order, as discussed above, in block 322. The next frame shows the reception of Ch. B. Ch. B is stored and transmitted.
When a channel that has been cleared needs a retransmission, the MS sends physical zeros at the allocation, in block 324. The faulty package is treated by the ARQ loop, or other error correction protocol.
When it has been determined by the UL map that Ch. A does not need retransmission, in block 320, Ch. A may be cleared from HARQ memory, in block 326. If Ch. B requires more space for storage, then other bursts are cleared in a random order until reaching enough free memory space to store the Ch. B burst. Ch. B is then stored and transmitted.
When a channel that has been cleared needs a retransmission, the MS sends physical zeros at the allocation, in block 328. The faulty package is treated by the ARQ loop, or other error correction protocol. The probability that a burst cleared from memory needs retransmission may be one time every few tens of seconds.
The processor 410 has a processing core 412 to execute instructions of the system 400. The processing core 412 may include, but is not limited to, pre-fetch logic to fetch instructions, decode logic to decode the instructions, execution logic to execute instructions and the like. The processor 410 may have a cache memory 416 to cache instructions and/or data of the system 400. In another embodiment of the invention, the cache memory 416 includes, but is not limited to, level one, level two and level three, cache memory or any other configuration of the cache memory within the processor 410.
A memory control hub (MCH) 414 ma perform functions that enable the processor 410 to access and communicate with a memory 430 that includes a volatile memory 432 and/or a non-volatile memory 434. The volatile memory 432 may include, but is not limited to, Synchronous Dynamic Random Access Memory (SDRAM), Dynamic Random Access Memory (DRAM), RAMBUS Dynamic Random Access Memory (RDRAM), and/or any other type of random access memory device. The non-volatile memory 434 may include, but is not limited to, NAND flash memory, phase change memory (PCM), read only memory (ROM), electrically erasable programmable read only memory (EEPROM), or any other type of non-volatile memory device.
The memory 430 stores information and instructions to be executed by the processor 410. The memory 430 may also stores temporary variables or other intermediate information while the processor 410 is executing instructions. The chipset 420 may connect with the processor 410 via Point-to-Point (PtP) interfaces 417 and 422. The chipset 420 enables the processor 410 to connect to other modules in the system 400. In one embodiment of the invention, the interfaces 417 and 422 operate in accordance with a PtP communication protocol such as the Intel® QuickPath Interconnect (QPI) or the like. The chipset 420 may connect to a display device 440 that may include, but is not limited to, liquid crystal display (LCD), cathode ray tube (CRT) display, or any other form of visual display device.
In addition, the chipset 420 connects to one or more buses 450 and 455 that interconnect the various modules 474, 460, 462, 464, and 466. Buses 450 and 455 may be interconnected together via a bus bridge 472 if there is a mismatch in bus speed or communication protocol. The chipset 420 couples with, but is not limited to, a non-volatile memory 460, a mass storage device(s) 462, a keyboard/mouse 464 and a network interface 466. The mass storage device 462 includes, but is not limited to, a solid state drive, a hard disk drive, an universal serial bus flash memory drive, or any other form of computer data storage medium. The network interface 466 is implemented using any type of well known network interface standard including, but not limited to, an Ethernet interface, a universal serial bus (USB) interface, a Peripheral Component Interconnect (PCI) Express interface, a wireless interface and/or any other suitable type of interface. The wireless interface (not shown) operates in accordance with, but is not limited to, the IEEE 802.11 standard and its related family, Home Plug AV (HPAV), Ultra Wide Band (UWB), Bluetooth, WiMax (IEEE 802.16), or any form of wireless communication protocol. In an embodiment, the HARQ module including wireless interface and buffer, may reside on the chipset 420.
While the modules shown in FIG. 4 are depicted as separate blocks within the system 400, the functions performed by some of these blocks may be integrated within a single semiconductor circuit or may be implemented using two or more separate integrated circuits. For example, although the cache memory 416 is depicted as a separate block within the processor 410, the cache memory 416 may be incorporated into the processor core 412 respectively. The system 400 may include more than one processor/processing core in another embodiment of the invention.
1. A computer implemented method in a wireless transmitting device, comprising:
anticipating whether a hybrid automatic repeat request (HARQ) sub-packet having one or more forward error correction (FEC) blocks is expected to be received correctly by a receiving device;
grouping the sub-packet into one of two groups, the groups comprising a first group for sub-packets with a detected error and a second group for sub-packets with no detected error; and
storing for retransmission, only those sub-packets falling into the first group, in anticipation of retransmission.
2. The method of claim 1, wherein anticipating whether an HARQ sub-packet is to be received correctly, further comprises:
determining whether each FEC block within the sub-packet contains an error based on results of a cyclic redundancy check (CRC) of each FEC block; and
when no error is detected in any FEC block in the sub-packet, indicating that the sub-packet is expected to be received correctly; and
when an error is detected in any FEC block in the sub-packet, indicating that the sub-packet is expected to be received incorrectly.
logic to detect errors in a forward error correction (FEC) block; and
logic coupled with the retransmission buffer to: identify a hybrid automatic repeat request (HARQ) sub-packet as having one or more forward error correction (FEC) blocks with either at least one detected error, or no detected errors; associate the sub-packet with one of two groups, the groups comprising a first group for sub-packets with a detected error in any FEC block, and a second group for sub-packets with no detected error, and store in the retransmission buffer, only those sub-packets falling into the first group.
5. The apparatus as recited in claim 4,
The method of claim 1, wherein identifying whether an HARQ sub-packet has a detected error, further comprises logic to: determine whether each FEC block within the sub-packet contains an error based on results of a cyclic redundancy check (CRC) of each FEC block; and when no error is detected in any FEC block in the sub-packet, indicate that the sub-packet is expected to be received correctly; and when an error is detected in any FEC block in the sub-packet, indicate that the sub-packet is expected to be received incorrectly.
sending a hybrid automatic repeat request (HARQ) burst having one or more forward error correction (FEC) blocks to a receiving device, by a transmitting device, the HARQ burst to be sent as a plurality of sub-packets in a plurality of frames;
receiving by the transmitting device, a sub-packet error status from the receiving device at least one frame in advance of receiving a full receipt acknowledgement from the receiving device of sub-packet receipt; and
reducing a length of time that the HARQ sub-packet is stored in a retransmission buffer in the transmitting device for possible retransmission to a receiving device, when the sub-packet error status indicates that the sub-packet will be received correctly by the receiving device.
clearing the buffer of older HARQ bursts to allow space in the buffer for new HARQ bursts.
10. The method as recited in claim 9, wherein clearing the older HARQ bursts from the retransmission buffer further comprises:
first, clearing HARQ bursts that are known to have been received without error;
second, clearing HARQ bursts that are anticipated to be received correctly, but have an unknown status; and
continuing to store HARQ bursts that are known to require retransmission.
receiving a message of physical zeros indicating a request for retransmission of a HARQ burst;
determining whether the requested HARQ burst is stored in the buffer;
when the requested HARQ burst is not stored in the buffer, then utilizing an outer-loop correction mechanism to restore the requested HARQ burst; and
when the requested HARQ burst is stored in the buffer, then retransmitting the HARQ burst.
logic coupled with the retransmission buffer to:
send a hybrid automatic repeat request (HARQ) burst having one or more forward error correction (FEC) blocks to a receiving device, by a transmitting device, the HARQ burst to be sent as a plurality of sub-packets in a plurality of frames;
receive by the transmitting device, a sub-packet status message from the receiving device at least one frame in advance of receiving a full receipt acknowledgement from the receiving device of sub-packet receipt; and
reduce a length of time that the HARQ sub-packet is stored in a retransmission buffer in the transmitting device for possible retransmission to a receiving device, when the sub-packet status message indicates that the sub-packet will be received correctly by the receiving device.
14. The apparatus as recited in claim 12, further comprising logic to:
clear the buffer of older HARQ bursts to allow space in the buffer for new HARQ bursts.
15. The apparatus as recited in claim 14, wherein clearing the older HARQ bursts from the retransmission buffer further comprises logic to:
first, clear HARQ bursts that are known to have been received without error;
second, clear HARQ bursts that are anticipated to be received correctly, but have an unknown status; and
continue to store HARQ bursts that are known to require retransmission.
16. The apparatus as recited in claim 14, further comprising logic to:
receive a message of physical zeros indicating a request for retransmission of a HARQ burst;
determine whether the requested HARQ burst is stored in the buffer;
when the requested HARQ burst is not stored in the buffer, then utilize an outer-loop correction mechanism to restore the requested HARQ burst; and
when the requested HARQ burst is stored in the buffer, then retransmit the HARQ burst.
20080244352 October 2, 2008 Kwon et al.
20100050041 February 25, 2010 Chang et al.
20110041023 February 17, 2011 Shimezawa et al.
20110066912 March 17, 2011 Riess et al.
International Search Report mailed Feb. 29, 2012 from International Application No. PCT/US2011/049509.
Part 11: “Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications,” IEEE Standard for Information technology—Telecommunications and information exchange between systems—Local and metropolitan area networks—Specific requirements, Jun. 12, 2007, 1232 pages, IEEE Std 802.11-2007, IEEE, New York, NY.
Part 15.1: “Wireless medium access control (MAC) and physical layer (PHY) specifications for wireless personal area networks (WPANs),” IEEE Standard for Information technology—Telecommunications and information exchange between systems—Local and metropolitan area networks—Specific requirements, Jun. 14, 2005, 598 pages, IEEE Std 802.15.1-2005, IEEE, New York, NY.
Part 16: “Air Interface for Fixed Broadband Wireless Access Systems,” IEEE Standard for Local and metropolitan area networks, Oct. 1, 2004, 893 pages, IEEE Std 802.16-2004, IEEE, New York, NY.
IEEE Computer Society, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, IEEE Standard for Information technology—Telecommunications and information exchange between systems—Local and metropolitan area networks—Specific requirements, Jun. 12, 2007, 1232 pages, IEEE Std 802.11-2007, IEEE, New York, NY.
IEEE Computer Society, Part 15.1: Wireless medium access control (MAC) and physical layer (PHY) specifications for wireless personal area networks (WPANs), IEEE Standard for Information technology—Telecommunications and information exchange between systems—Local and metropolitan area networks—Specific requirements, Jun. 14, 2005, 598 pages, IEEE Std 802.15.1-2005, IEEE, New York, NY.
IEEE Computer Society, Part 16: Air Interface for Fixed Broadband Wireless Access Systems, IEEE Standard for Local and metropolitan area networks, Oct. 1, 2004, 894 pages, IEEE Std 802.16-2004, IEEE, New York, NY.
Riess et al., U.S. Appl. No. 12/561,126 entitled “Method and System to Increase the Throughput of a Hybrid Automatic Repeat Request (HARQ) Protocol”, filed on Sep. 16, 2009, 34 pages.
Patent Publication Number: 20120066562
Inventors: Eilon Riess (Zichron Yaakov), Amir Rubin (Ramat Gan), Timor Israeli (Kfar Shmuel)
Application Number: 12/881,836
International Classification: H04L 1/18 (20060101); H03M 13/00 (20060101);