Tecniche ARQ e loro prestazioni

Premessa: le ipotesi di lavoro (pacchetti di $L$ bit, probabilità $p$, coda sempre piena, $t_P$, $t_A$, $\tau_P$, $t_{RTT}$, timeout stringente, ACK sempre corretti, ritrasmissioni illimitate) sono nella nota Livello di collegamento - LLC, MAC e ipotesi di lavoroIl livello di collegamento vede un canale fisico con errori residui e deve offrire ai livelli superiori un canale affidabile; ha due sottolivelli: LLC (correzione residua, ARQ con ACK/NACK) e MAC (chi trasmette, perché con più trasmettitori il rapporto giusto è la SINR e non l'SNR e la capacità cala). Per analizzarlo si usano ipotesi standard: pacchetti di $L$ bit, probabilità $p$ di pacchetto errato (i.i.d., $p=1-(1-P_{bit})^L\simeq LP_{bit}$), coda sempre piena (heavy traffic), tempo di pacchetto $t_P=L/R_b$, $t_{RTT}=t_P+t_A+2\tau_P$, timeout stringente, ACK/NACK senza errori, ritrasmissioni illimitate ($E[#tx]=1/(1-p)$). Le metriche sono throughput (frazione di tempo d'aria) e ritardo (fino alla ricezione corretta). Una collisione è la sovrapposizione, anche minima, di due pacchetti.Livello di collegamento - LLC, MAC e ipotesi di lavoro →. Qui si definiscono i tre protocolli e si calcolano throughput, ritardo e condizione di stabilità.

Vedi anche le trattazioni equivalenti Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective RepeatARQ (Automatic Repeat reQuest) rende affidabile un collegamento che sbaglia: il ricevitore conferma (ACK) i frame ricevuti bene, il trasmettitore ritrasmette allo scadere del timeout. Servono timeout (contro il deadlock) e numeri di sequenza (contro i duplicati). Con $t_G=t_F+2\tau_p+t_A$ e probabilità di errore $p$: Stop-and-Wait $\rho=\frac{t_F(1-p)}{t_G}$; Go-Back-N con finestra $N\ge t_G/t_F$ $\rho=\frac{1-p}{1+(N-1)p}$; Selective Repeat $\rho=1-p$. Efficienza $\eta=\rho,I/F$. La finestra ottima è la capacità del tubo in pacchetti. In Selective Repeat esiste anche una lunghezza ottima del frame: con overhead $o$ e probabilità di errore sul bit $P_b$, $x_{ott}\simeq\frac o2+\sqrt{o/P_b}$ (frame più corti se il canale sbaglia di più).Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective Repeat → (Internet, con timeout, finestre e numeri di sequenza) e Tecniche ARQ - stop-and-wait, go-back-N e selective repeatL'ARQ (automatic repeat request) usa un codice che rivela gli errori e fa ritrasmettere i pacchetti sbagliati, con conferme ACK/NACK. Con $p=1-(1-P_{bit})^L$ la probabilità che un pacchetto sia errato, $t_P$ il tempo di pacchetto, $t_A$ quello dell'ACK e $\tau_P$ il ritardo di propagazione: stop-and-wait $S=\frac{t_P(1-p)}{t_P+t_A+2\tau_P}$; go-back-N $S=\frac{(1-p),t_P}{1+(N-1)p}$ con $N-1=\left\lceil\frac{2\tau_P}{t_P+t_A}\right\rceil$; selective repeat $S=(1-p)\frac{t_P}{t_P+t_A}$. Il numero medio di trasmissioni di un pacchetto è $\frac1{1-p}$.Tecniche ARQ - stop-and-wait, go-back-N e selective repeat → (Ing. Elettronica).

ARQ e FEC

Il controllo d'errore si può fare in due modi (Codici a blocco - distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza in modo mirato: $k$ bit di informazione diventano una parola di codice di $n>k$ bit scelta tra $2^k$ parole ammesse. Se la parola ricevuta non è una parola di codice l'errore è rivelato (e si può chiedere la ritrasmissione, ARQ) oppure corretto (FEC). La qualità dipende dalla distanza minima di Hamming $d_{min}$: si rivelano fino a $d_{min}-1$ errori e se ne correggono $t<d_{min}/2$, ma non contemporaneamente. Per un BSC con $P_{bit}<1/2$ la decisione ottima ML coincide con quella a distanza minima. Limite di Hamming: $k/n\le1-\frac1n\log_2\sum_{r=0}^t\binom nr$.Codici a blocco - distanza minima, rivelazione e correzione →):

• FEC (Forward Error Correction): codici che riparano i pacchetti; a livello 2 il throughput è $1-p$ e il ritardo $t_P+\tau_P$ (nessuna interruzione del flusso);
• ARQ (Automatic Repeat reQuest): rivelazione d'errore (parità, CRC: Codici di Hamming e CRCIl codice di Hamming $(2^h-1,,2^h-h-1)$ ha come matrice di controllo $H$ che ha per colonne tutte le sequenze non nulle di $h$ bit: colonne distinte e non nulle danno $d_{min}=3$, la sindrome di un errore singolo è la colonna corrispondente, quindi corregge 1 errore (o rivela 2) ed è un codice perfetto ($2^{n-k}=1+n$). Per $(7,4)$ e BSC: errore non rivelato $\simeq7P^3(1-P)^4$, parola sbagliata dopo correzione $\simeq\binom72P^2(1-P)^5$. Il CRC è un codice lineare ciclico usato per sola rivelazione: la parola è $m(x)x^r$ più il resto della divisione per il polinomio generatore $g(x)$ di grado $r$ (modulo 2); rivela ogni errore a burst di lunghezza $\le r$.Codici di Hamming e CRC →) e richiesta di ritrasmissione dei pacchetti errati.

Spesso si combinano nell'Hybrid ARQ (HARQ = ARQ + FEC): pochi errori li corregge il codice, se sono troppi si rivela e si ritrasmette (come nel 5G).

Modello generale

Il trasmettitore invia pacchetti di dimensione uguale, con un identificatore univoco, in ordine, attraverso un canale rumoroso. L'asse dei tempi si discretizza spesso in slot: unità di tempo = tempo per trasmettere un pacchetto ($t_P$). A ogni pacchetto il ricevitore risponde con:

• ACK se il pacchetto è corretto;
• NACK se è errato.

ACK e NACK sono pacchetti brevi inviati su un canale di ritorno separato. Il tempo tra la trasmissione di un pacchetto e la ricezione del suo ACK/NACK è il round-trip time: comprende il tempo di trasmissione del pacchetto e dell'ACK, il doppio del tempo di elaborazione e il doppio del ritardo di propagazione (con elaborazione trascurabile $t_{RTT}=t_P+t_A+2\tau_P$). Il trasmettitore "sa" l'esito solo a $t_{RTT}$ dall'inizio della trasmissione.

Ipotesi (ripetute perché essenziali): traffico pesante (il trasmettitore ha sempre qualcosa da trasmettere), ACK/NACK senza errori, timeout stringente (la mancata ricezione equivale a un NACK), errori i.i.d. con probabilità $p$ per pacchetto. Con la teoria delle code: il throughput è la frazione di tempo d'aria $S=t_P/m_{t_T}$, dove $m_{t_T}$ è il tempo medio totale speso per un pacchetto.

Stop-and-Wait (SW)

È la tecnica più semplice: dopo ogni pacchetto si aspetta l'esito. Un ACK fa avanzare l'identificatore, un NACK no (si rimanda lo stesso pacchetto).

Il tempo dedicato a un pacchetto è $t_{RTT}\times\#\text{trasmissioni}$ (ogni tentativo, riuscito o no, occupa un round-trip intero). Con $E[\#tx]=\frac1{1-p}$ (vedi la nota sulle ipotesi): $$m_{t_T}=\frac{t_{RTT}}{1-p},\qquad\boxed{S_{SW}=\frac{t_P}{m_{t_T}}=\frac{t_P(1-p)}{t_{RTT}}=\frac{t_P(1-p)}{t_P+t_A+2\tau_P}}.$$ Si noti che anche per $p\to0$ il throughput non tende a $1$: resta $t_P/t_{RTT}<1$, perché il trasmettitore sta fermo ad aspettare l'ACK.

Esempio. $R_b=1$ Mbit/s, $L=10$ kbit ($t_P=10$ ms), $t_A\simeq0$, $\tau_P=25$ ms: $t_{RTT}=60$ ms. Senza errori $S=10/60=0{,}167$; con $p=0{,}1$: $m_{t_T}=60/0{,}9=66{,}7$ ms e $S=10/66{,}7=0{,}15$.

Ritardo. Per SW il ritardo medio è facile: il tempo della trasmissione riuscita più la propagazione, più ogni ritrasmissione che costa un $t_{RTT}$ (cioè si consuma un round-trip per scoprire il fallimento): $$m_{delay}=t_P+\tau_P+E[\#retx]\,t_{RTT}=t_P+\tau_P+\frac p{1-p}\,(t_P+t_A+2\tau_P).$$ Esempio: con i dati sopra, $p=0{,}1$: $m_{delay}=10+25+\frac{0{,}1}{0{,}9}\cdot60=41{,}7$ ms.

Go-Back-N (GBN)

Se il round-trip equivale a $N$ pacchetti, $N=t_{RTT}/t_P$, GBN trasmette in continuazione (occupazione del canale più alta) senza aspettare l'ACK. Dopo un NACK ritrasmette tutto l'ultimo round-trip: il pacchetto errato e quelli che lo seguono (già spediti) vengono rimandati, anche se erano corretti. Esempio con $N=3$ (dalle slide): si trasmettono $1,2,3$; il NACK sul pacchetto $2$ arriva quando il $4$ è già in volo; si riparte da $2$ ($2,3,4$), anche se il $3$ e il $4$ erano arrivati bene.

Per ogni esito cattivo si consuma un $t_{RTT}$ (si aggiunge, non si sostituisce, perché il canale era comunque occupato dal flusso continuo); quando l'esito è finalmente buono si spende solo $t_P$: $$t_T=\#retx\cdot t_{RTT}+t_P,\qquad t_{RTT}=Nt_P.$$ Il tempo medio per pacchetto con $E[\#retx]=\frac p{1-p}$ è $$m_{t_T}=\frac p{1-p}\,Nt_P+t_P=\frac{Np+1-p}{1-p}\,t_P,\qquad\boxed{S_{GBN}=\frac{t_P}{m_{t_T}}=\frac{1-p}{(N-1)p+1}}.$$ (Controllo: $\frac{Np+1-p}{1-p}=\frac{(N-1)p+1}{1-p}$.) Per $p\to0$ il throughput tende al $100\,\%$, a differenza di SW; per $N=1$ coincide con $1-p$.

Esempio. Con $N=t_{RTT}/t_P=6$ e $p=0{,}1$: $S_{GBN}=\frac{0{,}9}{5\cdot0{,}1+1}=0{,}6$. Il costo di ogni errore è $N=6$ pacchetti (invece di $1$): al crescere di $N$ GBN degrada: con $p=0{,}1$ e $N=25$: $S=0{,}9/3{,}4=0{,}26$.

Selective Repeat (SR)

Migliora GBN permettendo ritrasmissioni selettive dei soli pacchetti errati. Richiede di riordinare i pacchetti arrivati fuori sequenza (buffer al ricevitore) e di richiamare pacchetti anche vecchi (buffer al trasmettitore). Il tempo dedicato a un pacchetto è di nuovo $t_P$ per ogni trasmissione, buona o cattiva: $t_T=\#tx\cdot t_P$, da cui $$m_{t_T}=\frac{t_P}{1-p},\qquad\boxed{S_{SR}=\frac{t_P}{m_{t_T}}=1-p}.$$ Significa che se si trasmette sempre (il $100\,\%$ del tempo) una frazione $p$ della trasmissione è persa. È il massimo ottenibile con ritrasmissioni.

Confronto e scelta

• Il throughput ordinato è $S_{SW}\ll S_{GBN}\le S_{SR}$ quando $t_{RTT}\gg t_P$ ($N$ grande); con $N\simeq1$ (collegamento breve, cioè $\tau_P$ e $t_A$ piccoli) le differenze si riducono: SW $\simeq1-p$, e GBN peggiora al crescere di $p$.
• SR richiede buffer di riordino al ricevitore e di riserva al trasmettitore; se GBN va già bene, la complessità aggiuntiva di SR può essere ingiustificata. Il numero $N$ conta: un errore isolato fa perdere 1 pacchetto in SR e tutto il round-trip ($N$ pacchetti) in GBN.
• Efficienza. Dei bit trasmessi solo il payload $L_D$ è "utile": $\eta=S\cdot\frac{L_D}{L}$ (con $L=L_D+L_O$), come nelle curve del corso, in funzione di $P_{bit}$ con $p=1-(1-P_{bit})^L$.

Il grafico mostra $\eta$ in funzione di $P_{bit}$ con parametri nostri ($L=300$ bit, $L_D/L=0{,}93$): in alto con round-trip lungo ($N=25$), SW è bassissimo e GBN crolla già a $P_{bit}\sim10^{-4}$; SR regge fino a $\sim10^{-3}$. Con round-trip corto ($N=1{,}07$) le curve sono molto vicine; GBN è la peggiore perché ritrasmette comunque più del necessario.

Attenzione: i valori sono solo massimi, serve la stabilità

Tutte le formule precedenti valgono sotto traffico pesante (coda sempre piena): sono il massimo throughput raggiungibile. Se il traffico offerto è basso, il sistema semplicemente fa passare ciò che arriva. Quindi prima di usarle bisogna controllare la stabilità della coda ARQ: il throughput vale $\min(\lambda,\mu)$, dove $\lambda$ è il tasso di arrivo e $\mu$ la velocità di servizio effettiva. Se $\lambda<\mu$ la coda è stabile e $\text{throughput}=\lambda$ (tutto ciò che entra, esce); se $\lambda>\mu$ è instabile e il throughput è quello massimo di prima (con $S<1$).

Servizio per pacchetto $y$ (tempo che il pacchetto occupa il trasmettitore, ritrasmissioni incluse), con $m_y=E[y]$ e $\mu=1/m_y$:

• SW: $y=t_{RTT}(1+i)$, $i=\#retx$: $m_y=\dfrac{t_{RTT}}{P_{success}}=\dfrac{t_{RTT}}{1-p}$, $\mu_{SW}=\dfrac{1-p}{t_{RTT}}$.
• GBN: $y=t_P$ con probabilità $P_{success}$, $y=t_{RTT}+y'$ con probabilità $1-P_{success}$ (si riparte da capo, con $y'$ distribuita come $y$): $m_y=t_PP_{success}+p\,(t_{RTT}+m_y)$, quindi $m_y=t_P+t_{RTT}\dfrac p{1-p}$ ($=m_{t_T}$ di prima) e $\mu_{GBN}=1/m_y$.
• SR: con un trucco ispirato all'ALOHA: il tasso totale di pacchetti trasmessi è $\lambda_T=\lambda+\lambda p+\lambda p^2+\dots=\dfrac{\lambda}{1-p}$, e la "velocità di servizio" è la velocità totale del canale, $1/t_P$: stabile se $\dfrac{\lambda}{1-p}<\dfrac1{t_P}$, cioè $\lambda<\dfrac{1-p}{t_P}=\mu_{SR}$.

Ricordare anche che il ritardo non è $m_y$: è $t_{RTT}$ per ogni ritrasmissione più $t_P+\tau_P$ per la trasmissione che riesce, come visto sopra (per SR e GBN a coda vuota, ogni ritrasmissione costa $t_{RTT}$: $m_{delay}=t_P+\tau_P+\frac p{1-p}t_{RTT}$).

Esempio completo (esercizio del corso, Esercizio - Throughput di SR-ARQ e stabilità della coda ARQ): canale a $2$ Mbit/s, $P_{bit}=10^{-6}$, payload $4096$ bit più intestazione di $12$ byte ($L=4192$). $p=1-(1-10^{-6})^{4192}=0{,}418\,\%$, $t_P=L/R_b=2{,}096$ ms, e la velocità di servizio SR è $\mu\simeq(1-p)/t_P=475$ pkt/s ($1/t_P=477$ pkt/s al lordo degli errori). Con $\lambda=100$ pkt/s: stabile, throughput $=\lambda=419{,}2$ kbit/s. Con $\lambda=1000$ pkt/s: instabile ($\lambda>\mu$): il throughput è $S=1-p=0{,}99582$, cioè $1{,}991$ Mbit/s (il traffico offerto sarebbe $4{,}192$ Mbit/s).

Errori comuni

• Applicare $S_{SR}=1-p$ senza controllare $\lambda<\mu$.
• Dire che per $p\to0$ il throughput di Stop-and-Wait tende a $1$: tende a $t_P/t_{RTT}$.
• Dimenticare che in GBN ogni errore costa un round-trip intero ($N$ pacchetti), non un solo pacchetto.
• Confondere il throughput (frazione di tempo d'aria) con l'efficienza $\eta$ (solo payload) e con il ritardo (non è $m_y$).
• Usare $t_{RTT}=2\tau_P$ dimenticando $t_P$ e $t_A$.

Collegamenti

Per i codici che rendono possibile la rivelazione: Codici di Hamming e CRCIl codice di Hamming $(2^h-1,,2^h-h-1)$ ha come matrice di controllo $H$ che ha per colonne tutte le sequenze non nulle di $h$ bit: colonne distinte e non nulle danno $d_{min}=3$, la sindrome di un errore singolo è la colonna corrispondente, quindi corregge 1 errore (o rivela 2) ed è un codice perfetto ($2^{n-k}=1+n$). Per $(7,4)$ e BSC: errore non rivelato $\simeq7P^3(1-P)^4$, parola sbagliata dopo correzione $\simeq\binom72P^2(1-P)^5$. Il CRC è un codice lineare ciclico usato per sola rivelazione: la parola è $m(x)x^r$ più il resto della divisione per il polinomio generatore $g(x)$ di grado $r$ (modulo 2); rivela ogni errore a burst di lunghezza $\le r$.Codici di Hamming e CRC →. Per l'accesso condiviso, dove le ritrasmissioni nascono dalle collisioni: Accesso al mezzo - ALOHA, CSMA e protocolli deterministiciQuando più nodi condividono il canale serve un protocollo di accesso (MAC): deterministico (TDMA, FDMA, SDMA, CDMA), a richiesta (polling, token) o casuale (ALOHA, CSMA). Con $N_u$ utenti, arrivi di Poisson $\lambda$ ciascuno e pacchetti da $t_P=L/R_b$: TDMA stabile se $N_u\lambda t_P<1$, $m_{delay}=\frac{N_ut_P}{2(1-\rho)}+t_P+\tau_P$; FDMA ha ritardo maggiore di $t_P(N_u/2-1)$. ALOHA puro: intervallo di vulnerabilità $2t_P$, $S=Ge^{-2G}$, $S_{max}=1/(2e)\simeq0{,}18$ per $G=1/2$; slotted ALOHA: vulnerabilità $t_P$, $S=Ge^{-G}$, $S_{max}=1/e\simeq0{,}37$. ALOHA è intrinsecamente instabile (oltre il massimo il throughput va a $0$). Il carrier sense riduce la vulnerabilità a $\tau_P$ (CSMA), CD interrompe le collisioni, CA (RTS/CTS) è per il wireless; la persistenza (1-, non-, $p$-persistente) può portare il throughput verso il $100,%$.Accesso al mezzo - ALOHA, CSMA e protocolli deterministici →. Altri esercizi: Esercizio - Pacchetti su BSC, stabilità e traffico offerto.