ARQ e stop and wait

L'obiettivo dell'ARQ

Il servizio sottostante introduce errori e perdite, ma chi lo usa vuole le PDU consegnate in ordine, senza errori, duplicazioni o mancanze. Le procedure ARQ (Automatic Repeat Request, richiesta di ripetizione automatica) usano tre strumenti: un codice che rivela gli errori, i riscontri, positivi o negativi, e un timeout. Sono tre procedure; la più semplice è lo stop and wait.

La procedura vale fra entità di collegamento adiacenti, con unità dette trame (frame), e da estremo a estremo, per esempio nel trasporto. Qui si guarda il collegamento.

Trame e riscontri

Il pacchetto dello strato superiore diventa una trama con un'intestazione e, in coda, un CRC. Chi riceve risponde con una trama di controllo, di solito senza dati, con intestazione e CRC: anche l'informazione di controllo viaggia su un canale con errori, quindi va protetta.

Riscontro e timeout

Il trasmettitore A manda una trama e aspetta. Il ricevitore B ne controlla il CRC e, se è corretta, risponde con un ACK (acknowledgement): A manda la trama successiva. Se la trama non arriva o è errata, non c'è ACK e A resterebbe bloccato.

Per sbloccarlo A avvia un temporizzatore a ogni trama trasmessa. Se allo scadere, il timeout, l'ACK non è arrivato, A ritrasmette la trama.

Duplicati e numero di sequenza

Il timeout da solo crea un'ambiguità. Se la trama arriva ma l'ACK si perde, A ritrasmette e B riceve due volte la stessa trama, identica: non può sapere se la seconda è nuova.

Si aggiunge un campo all'intestazione, il numero di sequenza $S_{\text{last}}$, che numera le trame. B riconosce la copia e la scarta, ma risponde con un nuovo ACK, perché A, che non ha ricevuto il precedente, è bloccato.

ACK numerati

Se un ACK arriva in ritardo, o il timeout scade troppo presto, A ritrasmette la trama 1 mentre il suo ACK è ancora in viaggio. Arriva il primo ACK, A manda la 2 e arriva il secondo ACK, quello della copia della 1: A ha trasmesso due trame e ricevuto due ACK, quindi crede che tutto sia regolare. Se la 2 si è persa, sbaglia: il secondo ACK riguarda ancora la 1.

Si numera anche l'ACK. Il suo numero $R_{\text{next}}$ è quello della prossima trama che B si aspetta: dopo la 1 scrive ACK 2, e lo ripete se la 1 arriva di nuovo. Così A vede che B non ha ancora ricevuto la 2.

Bastano due numeri

Con lo stop and wait c'è una sola trama in attesa di riscontro, quindi basta un bit: $S_{\text{last}}$ e $R_{\text{next}}$ alternano 0 e 1. A numera le trame 0, 1, 0, 1, … e B risponde con il numero della trama che attende: ACK 1 dopo la 0, ACK 0 dopo la 1. Una copia porta il numero dell'ultima trama accettata, non quello atteso.

B:

• trama corretta con il numero atteso: la accetta, passa il pacchetto allo strato superiore, aggiorna $R_{\text{next}}$ e invia l'ACK $R_{\text{next}}$;
• trama corretta con un altro numero, una copia: la scarta e invia di nuovo l'ACK $R_{\text{next}}$;
• trama errata: la scarta senza rispondere.

A:

• ACK con $R_{\text{next}}=S_{\text{last}}+1$ (modulo 2): passa alla trama successiva;
• altro ACK: lo ignora;
• timeout: ritrasmette la trama e riavvia il temporizzatore.

Tre casi dello stop and wait

Caso

Trama persaACK persoACK in ritardo

AB0ACK 111ACK 0timeout

Macchina a stati

Il funzionamento regolare si descrive con lo stato $(S_{\text{last}},R_{\text{next}})$: il numero della trama corrente di A e quello atteso da B. Da $(0,0)$, senza errori, lo stato percorre un ciclo:

• $(0,0)\to(0,1)$: la trama 0 arriva a B, che ora attende la 1;
• $(0,1)\to(1,1)$: l'ACK 1 arriva ad A, che passa alla trama 1;
• $(1,1)\to(1,0)$: la trama 1 arriva a B, che ora attende la 0;
• $(1,0)\to(0,0)$: l'ACK 0 arriva ad A, che passa alla trama 0.

Il ciclo di una trama

Senza errori ogni trama occupa il collegamento per un ciclo: trasmissione della trama, propagazione fino a B, elaborazione in B (il CRC), trasmissione dell'ACK, propagazione di ritorno ed elaborazione in A (il CRC dell'ACK). Con $R$ il bit rate, $n_f$ i bit della trama e $n_a$ quelli dell'ACK, i tempi di trasmissione sono

$$\begin{gathered} t_f=\frac{n_f}{R}\\ t_{\text{ack}}=\frac{n_a}{R} \end{gathered}$$

e il ciclo dura

$$t_0=t_f+2t_{\text{prop}}+t_{\text{ack}}+2t_{\text{proc}}$$

dove $t_{\text{prop}}$ è il ritardo di propagazione e $t_{\text{proc}}$ il tempo di elaborazione a ciascun estremo, spesso trascurabile.

Efficienza

L'efficienza $\eta_0$ è il rapporto fra il bit rate utile e il bit rate $R$ dell'interfaccia. In ogni ciclo si consegnano $n_f-n_o$ bit utili, perché $n_o$ bit della trama sono l'intestazione:

$$\begin{aligned} \eta_0&=\frac{n_f-n_o}{R\,t_0}\\ &=\frac{n_f-n_o}{n_f+n_a+2R(t_{\text{prop}}+t_{\text{proc}})} \end{aligned}$$

Trascurando intestazione, ACK ed elaborazione resta

$$\eta_0\simeq\frac{1}{1+\dfrac{2t_{\text{prop}} R}{n_f}}$$

Il termine $2t_{\text{prop}} R$, in bit, è il prodotto banda-ritardo, un parametro chiave di tutti questi protocolli: $\eta_0$ è vicina a 1 solo se è piccolo rispetto a $n_f$.

Se $t_{\text{prop}}$ cresce, il ciclo si allunga e $\eta_0$ cala. Se $R$ cresce, $t_f$ si accorcia ma l'attesa del ritorno no, quindi $\eta_0$ cala anche così. Con $R$ minore la trasmissione pesa di più sul ciclo e $\eta_0$ sale.

Il ciclo di una trama e l'efficienza

Un ciclo trama-ACK

AB$t_f$$t_0$

• trama
• ACK

Efficienza

${\eta }_0$$2t_{\text{prop}}R$ (kbit)

• ${\eta }_0$ al variare di $2t_{\text{prop}}R$

$t_{\text{prop}}$ (ms)

5

$R$ (Mbit/s)

1

Un esempio numerico

Una trama è di 1250 byte, cioè $n_f=10\,000$ bit, con intestazione e ACK di 25 byte, cioè $n_o=n_a=200$ bit, su un collegamento da $R=1$ Mbit/s. Con $t_{\text{prop}}=5$ ms è $2t_{\text{prop}} R=10\,000$ bit e $\eta_0\approx49\,\%$, il punto da cui parte la figura.

Con un ritardo di andata e ritorno $2t_{\text{prop}}$ di 1 ms, 10 ms, 100 ms e 1 s il prodotto banda-ritardo vale $10^3$, $10^4$, $10^5$ e $10^6$ bit e l'efficienza è 88 %, 49 %, 9 % e 1 %. Con $R=1$ Gbit/s il prodotto è mille volte più grande e l'efficienza è 1 %, 0,1 %, 0,01 % e 0,001 %.

Lo stop and wait è semplice e garantisce una trasmissione corretta, ma rende poco quando il prodotto banda-ritardo è alto: a bit rate elevati o su collegamenti lunghi, come quelli via satellite.