Cours 7: Protocoles ARQ/HARQ - ENSEAperso-etis.ensea.fr/andriyanova/documents/cours/cours7-ComNum2.pdf · Cours 7: Protocoles ARQ/HARQ ... carrier concept enables the operation of

Cours 7: Protocoles ARQ/HARQ Communications sans fil, M2 ISIM 2012-2012

Iryna Andriyanova

Sunday, November 11, 12

Adaptation du lien sans fil

• Canal sans fil : variation rapides de qualité

• Adaptation du lien

• avant la transmission : • couche physique et MAC - type de modulation, codage de

canal, puissance émise

• après la transmission : • protocoles de retransmission de type Hybrid ARQ (HARQ)


Exemple de HSDPA (3G)

• QPSK pour les canaux bruités et 16-QAM pour les canaux de bonne qualité

• 14 Mbps pour les canaux de bonne qualité (16-QAM + code de rendement proche de 1)

• 2.4 Mbps pour les canaux bruités (QPSK + code de rendement 1/3)

• le contrôle du lien s’effectue jusqu’a 500 fois par sec


Hybrid ARQ

ARQ - mécanisme de contrôle ou on utilise les aquittements (ACK/NACK) et les timeouts pour assurer une transmission fiable lors d’une transmission peu fiable. Implementation usuelle : bit(s) CRC

HARQ = ARQ + FEC. C’est une variation d’ARQ où :✷ le code utilisé est un code plus puissant que CRC (code de canal = FEC), par exemple un turbo code ou un code convolutif, d’un certain rendement Rc✷ les paquets reçus très bruités ne sont pas “oubliés”, mais gardés et utilisés lors du décodage - on effectue le “soft combining”


HARQ de type CC (Chase combining)

• Retransmission du même paquet (codage à répétition)

• Combinaison de tous les paquets reçus (diversité et SNR cumulé plus grand)

• Décodage du paquet

SUBMITTED TO THE IEEE TRANSACTIONS ON INFORMATION THEORY SEPTEMBER 2005 2

I. INTRODUCTION

In conventional automatic repeat request (ARQ) schemes, frame errors are examined at the receiving

end by an error detecting (usually cyclic redundancy check (CRC)) code. If a frame passes the CRC,

the receiving end sends an acknowledgement (ACK) of successful transmission to the receiver. If a

frame does not pass the CRC, the receiving end sends a negative acknowledgement (NAK), requesting

retransmission. User data and its CRC bits may be additionally protected by an error correcting code

which increases the probability of successful transmission. Such ARQ schemes which combine the ARQ

principle with error control coding are known as hybrid ARQ (HARQ) schemes.

The standard measure of ARQ protocol efficiency is throughput, defined as the average number of user

data bits accepted at the receiving end in the time required for transmission of a single bit. Therefore the

level of redundancy of the error correcting code employed in an HARQ scheme has two opposing effects

on the scheme efficiency, namely, with increased redundancy the probability of successful transmission

increases but the percentage of user data in the frame decreases. Usually, a fixed rate code which is well

suited to the channel characteristics and throughput requirements is selected.

In applications with fluctuating channel conditions within a range of signal-to-noise ratios (SNRs),

such as mobile and satellite packet data transmission, the so called incremental redundancy (IR) HARQ

schemes exhibit higher throughput efficiency by adapting their error correcting code redundancy to

different channel conditions. An IR-HARQ protocol operates as illustrated by the example in Figure 1. At

at the transmitter

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

2 2 2 2 2

2 2 2 2 2

3 3 3 3 3

3 3 3 3 3

4 4 4 4 4

4 4 4 4 4

transmission # 1

at the receiver

transmission # 2

transmission # 3

transmission # 4

Fig. 1. Incremental redundancy HARQ protocol.

the transmitter, the information and CRC bits are encoded by a systematic “mother” code. Initially, only

September 8, 2005 DRAFT


I. INTRODUCTION


















at the transmitter

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

2 2 2 2 2

2 2 2 2 2

3 3 3 3 3

3 3 3 3 3

4 4 4 4 4

4 4 4 4 4

transmission # 1

at the receiver

transmission # 2

transmission # 3

transmission # 4





HARQ de type IR (Incremental Redundancy)

• Transmission du paquet fraction par fraction, en commençant par la partie “données”

• Assemblage à la réception et décodage commun


I. INTRODUCTION


















at the transmitter

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

2 2 2 2 2

2 2 2 2 2

3 3 3 3 3

3 3 3 3 3

4 4 4 4 4

4 4 4 4 4

transmission # 1

at the receiver

transmission # 2

transmission # 3

transmission # 4





Exemple de LTE (Long Term Evolution)

IEEE Communications Magazine • April 2009 53

the radio channel. In addition to its advantagesfor a low-complexity receiver design, the multi-carrier concept enables the operation of LTE invarious system bandwidths up to 20 MHz byadapting the number of subcarriers used to theallocated system bandwidth. Finally, OFDM sup-ports multi-user access because within a trans-mission interval, subcarriers can be allocated todifferent users.

The LTE uplink employs a discrete Fouriertransform (DFT)-spread OFDM (also denotedas single-carrier frequency division multipleaccess [SC-FDMA]). Compared to conventionalOFDM, this OFDM variant provides animproved peak-to-average power ratio thatenables more power-efficient terminals.

The basic LTE radio resource that is address-able for data transmission in the two-dimension-al time-frequency grid is called a resource block.This type of resource block assembles 12 subcar-riers and has a bandwidth of 180 kHz. In thetime domain, the resource block has a subframeduration of only 1 ms. Such a short subframeenables the exploitation of channel variations byscheduling users depending on their currentchannel quality. At the same time, a short hybridARQ (HARQ) round-trip time of only 8 ms canbe obtained.

By allocating a variable number of resourceblocks to a certain user and selecting a modula-tion and coding scheme to meet the currentchannel conditions, widely scalable transportblock sizes are possible, resulting in a wide rangeof user-data rates. In addition, it is possible toaggregate up to two streams by utilizing multi-ple-input multiple-output (MIMO) transmissionsto increase the data rate even further underfavorable radio conditions.

USER PLANE PROTOCOL STACKWhile the physical layer essentially provides a bitpipe, protected by turbo-coding and a cyclicredundancy check (CRC), the link-layer proto-cols enhance the service to upper layers byincreased reliability, security, and integrity. Inaddition, the link layer is responsible for themulti-user medium access and scheduling.

One of the main challenges for the LTE link-layer design is to provide the required reliabilitylevels and delays for Internet Protocol (IP) dataflows with their wide range of different servicesand data rates. In particular, the protocol over-head must scale. For example, it is widelyassumed that voice over IP (VoIP) flows can tol-erate delays on the order of 100 ms and packetlosses of up to 1 percent. On the other hand, itis well-known that TCP file downloads performbetter over links with low bandwidth-delay prod-ucts. Consequently, downloads at very high datarates (e.g., 100 Mb/s) require even lower delaysand in addition, are more sensitive to IP packetlosses than VoIP traffic.

Overall, this led to the following design of theLTE link layer: it consists of three sublayers(Fig. 2) that are partly intertwined. The PacketData Convergence Protocol (PDCP) sublayer [4]is responsible mainly for IP header compressionand ciphering. In addition, it supports losslessmobility in case of inter-eNB handovers and pro-

vides integrity protection to higher layer-controlprotocols. The radio link control (RLC) sublayer[5] comprises mainly ARQ functionality and sup-ports data segmentation and concatenation. Thelatter two minimize the protocol overhead inde-pendent of the data rate, as is explained in moredetail below. Finally, the medium access control(MAC) sublayer [6] provides HARQ and isresponsible for the functionality that is requiredfor medium access, such as scheduling operationand random access.

Figure 3 depicts the data flow of an IP packetthrough the link-layer protocols down to thephysical layer. The figure shows that each proto-col sublayer adds its own protocol header to thedata units.

This figure is used in subsequent sections as areference when relevant functionality is intro-duced.

RETRANSMISSION HANDLINGAs in any communication system, there are occa-sional data transmission errors, for example, dueto noise, interference, and/or fading. Link-layer,network-layer (IP), and transport-layer protocolsare not prepared to cope with bit errors in head-

!!

Figure 1. Overview of the EPC/LTE architecture.

Control interfaceUser data interface

S10

EPC

E-UTRAN

S11

S1-MME

MME

S5/S8

P-GW

S-GWMME

eNB eNB

Internet,operator services, etc.

S1-U S1-U

X2-U

X2-C

!!

Figure 2. User plane protocol stack.

UE

ARQ(incl. Seg/Conc.)

Re-ordering

Headercompression

Ciphering

HARQ

PDCP

RLC

MAC

PHY

eNB

PDCP

RLC

Sche

dulin

g

MAC

PHY

MEYER LAYOUT 3/25/09 2:18 PM Page 53

Stack de protocole :


Exemple de LTE (Long Term Evolution)


the radio channel. In addition to its advantagesfor a low-complexity receiver design, the multi-carrier concept enables the operation of LTE invarious system bandwidths up to 20 MHz byadapting the number of subcarriers used to theallocated system bandwidth. Finally, OFDM sup-ports multi-user access because within a trans-mission interval, subcarriers can be allocated todifferent users.

The LTE uplink employs a discrete Fouriertransform (DFT)-spread OFDM (also denotedas single-carrier frequency division multipleaccess [SC-FDMA]). Compared to conventionalOFDM, this OFDM variant provides animproved peak-to-average power ratio thatenables more power-efficient terminals.

The basic LTE radio resource that is address-able for data transmission in the two-dimension-al time-frequency grid is called a resource block.This type of resource block assembles 12 subcar-riers and has a bandwidth of 180 kHz. In thetime domain, the resource block has a subframeduration of only 1 ms. Such a short subframeenables the exploitation of channel variations byscheduling users depending on their currentchannel quality. At the same time, a short hybridARQ (HARQ) round-trip time of only 8 ms canbe obtained.

By allocating a variable number of resourceblocks to a certain user and selecting a modula-tion and coding scheme to meet the currentchannel conditions, widely scalable transportblock sizes are possible, resulting in a wide rangeof user-data rates. In addition, it is possible toaggregate up to two streams by utilizing multi-ple-input multiple-output (MIMO) transmissionsto increase the data rate even further underfavorable radio conditions.

USER PLANE PROTOCOL STACKWhile the physical layer essentially provides a bitpipe, protected by turbo-coding and a cyclicredundancy check (CRC), the link-layer proto-cols enhance the service to upper layers byincreased reliability, security, and integrity. Inaddition, the link layer is responsible for themulti-user medium access and scheduling.

One of the main challenges for the LTE link-layer design is to provide the required reliabilitylevels and delays for Internet Protocol (IP) dataflows with their wide range of different servicesand data rates. In particular, the protocol over-head must scale. For example, it is widelyassumed that voice over IP (VoIP) flows can tol-erate delays on the order of 100 ms and packetlosses of up to 1 percent. On the other hand, itis well-known that TCP file downloads performbetter over links with low bandwidth-delay prod-ucts. Consequently, downloads at very high datarates (e.g., 100 Mb/s) require even lower delaysand in addition, are more sensitive to IP packetlosses than VoIP traffic.

Overall, this led to the following design of theLTE link layer: it consists of three sublayers(Fig. 2) that are partly intertwined. The PacketData Convergence Protocol (PDCP) sublayer [4]is responsible mainly for IP header compressionand ciphering. In addition, it supports losslessmobility in case of inter-eNB handovers and pro-

vides integrity protection to higher layer-controlprotocols. The radio link control (RLC) sublayer[5] comprises mainly ARQ functionality and sup-ports data segmentation and concatenation. Thelatter two minimize the protocol overhead inde-pendent of the data rate, as is explained in moredetail below. Finally, the medium access control(MAC) sublayer [6] provides HARQ and isresponsible for the functionality that is requiredfor medium access, such as scheduling operationand random access.

Figure 3 depicts the data flow of an IP packetthrough the link-layer protocols down to thephysical layer. The figure shows that each proto-col sublayer adds its own protocol header to thedata units.

This figure is used in subsequent sections as areference when relevant functionality is intro-duced.

RETRANSMISSION HANDLINGAs in any communication system, there are occa-sional data transmission errors, for example, dueto noise, interference, and/or fading. Link-layer,network-layer (IP), and transport-layer protocolsare not prepared to cope with bit errors in head-

!!

Figure 1. Overview of the EPC/LTE architecture.

Control interfaceUser data interface

S10

EPC

E-UTRAN

S11

S1-MME

MME

S5/S8

P-GW

S-GWMME

eNB eNB

Internet,operator services, etc.

S1-U S1-U

X2-U

X2-C

!!

Figure 2. User plane protocol stack.

UE

ARQ(incl. Seg/Conc.)

Re-ordering

Headercompression

Ciphering

HARQ

PDCP

RLC

MAC

PHY

eNB

PDCP

RLC

Sche

dulin

g

MAC

PHY


Stack de protocole :

ers, and the majority of the protocols are notcapable of handling errors in the payload either.Therefore, a fundamental design choice for LTEhas been not to propagate any bit errors to high-er layers but rather to drop or retransmit theentire data unit containing bit errors. As illus-trated in Fig. 3, the physical layer attaches a 24-bit CRC checksum to the data units, thusallowing the receiver to detect bit errors and toforward only error-free packets to the IP layer.

Most TCP/IP protocols are designed to copeonly with rather low packet-loss rates. State-of-the-art voice codecs perform well at error ratesup to at most 10–2. High-speed, TCP-based filedownloads requires loss rates on the order of10–5 to 10–6 [7]. The HARQ scheme on the MACsublayer performs retransmissions of corruptedtransport blocks and thereby corrects the majori-ty of all transmission errors. The HARQ mecha-nism is very similar to the solution adopted forHSDPA [2], that is, the protocol uses multiplestop-and-wait HARQ processes. The functionali-ty and performance is comparable to that of awindow-based selective repeat protocol. In par-ticular, it allows continuous transmission, whichcannot be achieved with a single stop-and-waitscheme. Instead of a status message containing asequence number, a single-bit HARQ feedbackacknowledgment/negative acknowledgment(ACK/NACK), with a fixed-timing relation tothe corresponding transmission attempt, pro-vides information about the successful receptionof the HARQ process. Thereby, it gains in termsof delay, simplicity, and control overhead com-pared to a window-based selective repeat proto-col.

It is important that the HARQ protocol isfast yet consumes as few radio resources as pos-sible. The single-bit HARQ feedback fulfilsthese requirements, but the probability for mis-interpreting a negative acknowledgment as a

positive acknowledgment, and thereby causing aresidual packet loss, is in the order of 10–4 to10–3. It would be expensive, in terms of transmitpower, to reduce the feedback error rate furtherand thereby, to ensure the desired very lowresidual loss rates required by TCP for achievinghigh-data rates. Furthermore, certain errors inother control signaling, such as scheduling infor-mation, result in HARQ failures. When suchfailures are detected by the receiver, the HARQprocess typically has been re-used for new data,and the single-bit HARQ feedback is not a validreference for the desired retransmission.

Due to the error cases mentioned above, thefast HARQ protocol with low-overhead,ACK/NACK feedback and retransmissions withincremental redundancy is complemented by ahighly reliable window-based selective repeat-ARQ protocol that resides in the RLC sublayeras depicted in Fig. 4.

When the CRC check is successful, the MACHARQ receiver delivers RLC protocol dataunits (PDUs) to the corresponding RLC entity.If the RLC receiver detects a gap in thesequence of received PDUs based on the RLCsequence number, it starts a reordering timerassuming that the missing packet still is beingretransmitted in the HARQ protocol. Note thatthe reordering functionality required on top of amulti-process stop-and-wait mechanism reusesthe same RLC sequence numbers as the ARQmechanism, saving additional overhead com-pared to a sequence, number-based re-orderingmechanism in MAC, like in HSPA. In the rarecase that the reordering timer expires, an RLCacknowledged-mode (AM) receiver sends a sta-tus message comprising the sequence number ofthe missing RLC PDU(s) to its transmitting peerentity. The MAC layer treats the RLC statusmessage as any other data, meaning that it alsoapplies the same HARQ operation and CRC to

IEEE Communications Magazine • April 200954

!!

Figure 3. Illustration of data flow through L2 protocol stack.

L1Coding,interleaving,modulation

RLCSegmentationconcatenation

MACMultiplexing

IPIPvia S1 or fromUE’s stack

PDCPHeader compressionand ciphering

UDP Payload

H H

PDCP PDCP SDU

RLC RLC SDU

MAC MAC SDU

MAC

CRC

MAC SDU

RLC RLC SDU

Segmentation

Multiplexing (padding)

Concatenation

PDCP PDCPPDU

RLCPDU

MACPDU

IP TCP Payload

Transport block

The two-layer ARQdesign achieves low

latency and lowoverhead without

sacrificing reliability.Most errors are captured and

corrected by thelightweight HARQ

protocol. Only residual HARQ errors

are detected andresolved by the moreexpensive (in terms

of latency and overhead) ARQretransmissions.



Exemple de LTE : HARQ+ARQ


this message. Consequently, errors or loss of theARQ feedback can be detected and recoveredby sending another RLC status. Upon receptionof the RLC status message, the ARQ transmittertriggers a retransmission of the correspondingRLC PDU(s). The HARQ layer does notattempt to combine the RLC retransmissionwith the previous transmission but treats it asnew data.

The fact that RLC and MAC are terminatedin the same nodes enables a tighter interconnec-tion of the two protocol sublayers. In LTE, theHARQ transmitter can indicate a so-called localNACK to the ARQ transmitter, if it knows orassumes that a HARQ transmission failed. Themost prominent example is that the maximumnumber of HARQ transmission attempts wasreached. This might happen, for example, if thechosen modulation and coding scheme is tooweak for the given channel quality. The mainbenefit of the local NACK is the shorter detec-tion delay, resulting in improved performancecompared to the gap detection at the ARQreceiver.

The two-layer ARQ design achieves lowlatency and low overhead without sacrificing reli-ability. Most errors are captured and correctedby the lightweight HARQ protocol. Only residu-al HARQ errors are detected and resolved bythe more expensive (in terms of latency andoverhead) ARQ retransmissions.

Finally, it should be noted that services thatcan sustain error rates on the order of 10–3 to10–2, while gaining from reduced delays, can bemapped to a radio bearer running the RLC pro-tocol in unacknowledged mode (UM), that is,without the second ARQ layer. In that case,residual errors on the MAC layer are not recov-ered, but packet losses propagate to higher lay-ers. RLC UM generally is assumed to be usedfor VoIP and real-time gaming traffic.

RANDOM ACCESSTo keep transmissions from different UEsorthogonal, uplink transmissions in LTE arealigned with the frame timing at the eNB. When

timing is not aligned yet or alignment was lostdue to a period of inactivity during which timealignment was not maintained by the eNB, arandom access (RA) procedure is performed toacquire time alignment.

The RA procedure establishes uplink-timealignment by means of a four-phase contention-based procedure outlined in the following andshown in Fig. 5:1. RA Preamble — The UE randomly selects

an RA preamble sequence from the set ofsequences available in the cell and trans-mits it on an RA channel. A guard periodis applied to the RA preamble transmissionto avoid creating interference in adjacentsubframes. To minimize non-orthogonaltransmissions and thereby improve resourceefficiency, unsynchronized and unscheduledtransmissions, like the first step in the RAprocedure, do not carry data.

2. RA Response — The eNB detects thepreamble transmission, estimates the uplinktransmission timing of the UE, andresponds with an RA response providingthe UE with the correct timing-advancevalue to be used for subsequent transmis-sions and with a first grant for an uplink

!!

Figure 4 HARQ and ARQ retransmissions on MAC and RLC layer.

Uplink L1

Sliding window ARQUL ARQtransmitterRLC

Stop and wait HARQMAC

RLC STATUSBLER ~10-4-10-3

HARQ ACK/NACKerror rate=10-4-10-3

Transport blockBLER e.g.10-1

RLC STATUSas DL HARQ data

RLC PDUBLER ~10-4-10-3

RLC SDUBLER ~10-6

UL HARQtransmitter

DL HARQreceiver

UL ARQreceiver

DL HARQtransmitter

UL HARQreceiver

Downlink L1

!!

Figure 5. Contention-based random access procedure.

eNB2 4

1 3

RA p

ream

ble

RA m

essa

ge(U

E id

entit

y, B

SR, e

tc.)

Furt

her

uplin

k/do

wnl

ink

tran

smis

sion

s

RA r

espo

nse

(tim

ing

adva

nce,

UL

gran

t, e

tc.)

RA c

onte

ntio

n re

solu

tion

(UL

gran

t, D

L as

sign

men

t)

UE



Exemple de LTE : perfrormances

IEEE Communications Magazine • April 200958

latter group of services as depicted in Table 1.RLC AM bearers employ a two-layer ARQ

functionality intended to provide low delays andvery low residual-error rates while causing rea-sonably low overhead. In this section, we presentsimulation results showing the benefit of the sec-ond ARQ layer in terms of file transfer perfor-mance. We simulate a large number of filetransfers of 100-MB files toward a UE connect-ed to an LTE cell in a-10 MHz deployment withlow load. The simulation settings are according

to the 3GPP case 3 scenario [9], and a simplified2!2 MIMO scheme is used. The theoreticalpeak-bit rate for this case is around 70 Mb/s.The HARQ block error-rate target is set to 10percent. HARQ failures appear if the maximumnumber of five transmission attempts (usedhere) are exceeded or due to NACK-to-ACKerrors. The residual loss rate above the MAClayer is on the order of 10–4. With RLC UM,these errors propagate to higher layers and mustbe handled by TCP; whereas with RLC AM,they are recovered by the RLC protocol.

Figure 6 shows the performance of the object-bit rate (OBR), that is, the file size divided bythe file transfer time, of the download for bothAM and UM radio bearers as a cumulative dis-tribution function (CDF). As expected, the AMradio bearer using RLC ARQ almost alwaysachieves better performance than the UM radiobearer. Whereas the best 10 percent of the filetransfers for RLC UM perform well, the majori-ty suffers significantly from residual HARQ fail-ures that trigger the TCP congestion control andthereby increase the transmission delay. The50th percentile of the OBR decreases by 44 per-cent to 15 Mb/s. The actual performance of afile transfer over RLC UM depends on the num-ber of losses seen by TCP and on the instanta-neous state of the TCP congestion control uponoccurrence of the loss.

The cost for the second ARQ layer ismarginal due to the few residual HARQ errorsrequiring ARQ retransmissions. Also, the costfor regular RLC status reports is negligible inthis case because they are typically multiplexedwith TCP acknowledgments that are transmittedin the reverse direction in any case.

The motivation for offering an unacknowl-edged mode for RLC operation may not be

!!

Table 1. Protocol overhead in LTE assuming IPv4.

Protocol LayerTCP/IP with RLC AM VoIP with RLC

UM AMR-WBcodec 12.65 kb/sTCP segment TCP ACK

Application-, Transport-,and IP Layer 1460 + 40 bytes 40 bytes 33 + 40 bytes

PDCP ROHC 40 bytes to ~8 bytes 40 bytes to ~8 bytes 40 bytes to ~3 bytes

PDCP SDU ~1468 bytes ~8 bytes ~36 bytes

PDCP Header 2 bytes12 bits SN

1 byte7 bits SN

RLC Header4 bytes

12 bits SN and framing sub-headerfor concatenation

1 byte5 bits SN

MAC Header 1 byte 1 byte

L1 CRC 3 bytes 3 bytes

Total OverheadL2 + L1 on Shared Channel 10 bytes 6 bytes

Net overhead reductionincluding ROHC

22 of 1500 bytes(–1.5%)

22 of 40 bytes(–55%)

31 of 73(–42%)

!!

Figure 6. Performance samples of consecutive file downloads with RLC AMand RLC UM.

Object bit rate [Mbps]100

0

50CDF

40

30

20

10

60

70

80

90

100

20 30 40 50 60 70

UM-3gpp-case3AM-3gpp-case3



Documents

Cours 7: Protocoles ARQ/HARQ - ENSEAperso-etis.ensea.fr/andriyanova/documents/cours/cours7-ComNum2.pdf · Cours 7: Protocoles ARQ/HARQ ... carrier concept enables the operation of