Stop and wait con errori e Go-Back-N

Stop and wait: il timeout

Nello stop and wait A numera la trama con $S_{\text{last}}$, poi calcola il CRC, che copre anche il numero, trasmette e aspetta l'ACK $R_{\text{next}}$, il numero della prossima trama attesa da B. A va avanti solo con $R_{\text{next}}=S_{\text{last}}+1$. Se l'ACK è errato o non arriva, lo sblocca solo il timeout, e A ritrasmette con lo stesso numero.

Il timeout deve lasciare all'ACK il tempo di tornare. Contato dalla fine della trasmissione della trama,

$$T_{\text{out}}\ge 2t_{\text{prop}}+t_{\text{ack}}$$

con l'elaborazione trascurata; contato dall'inizio, $T_{\text{out}}\ge t_0$. Il valore ideale è proprio il minimo: più breve, A ritrasmette trame il cui ACK sta arrivando; molto più lungo, il protocollo funziona, ma dopo una perdita A aspetta più del necessario.

Canale con errori

Sia $P_f$ la probabilità che una trama arrivi con errori, indipendente da trama a trama. Ogni tentativo riesce con probabilità $1-P_f$, quindi una trama richiede in media

$$\frac{1}{1-P_f}$$

trasmissioni, la prima compresa. Con il timeout minimo ogni tentativo occupa un ciclo $t_0$: il tempo medio per trama è $t_0/(1-P_f)$ e l'efficienza diventa

$$\eta_{\text{SW}}=(1-P_f)\,\eta_0$$

Se ogni bit è errato con probabilità $p$ (il tasso d'errore sul bit, BER), una trama di $n_f$ bit è corretta con probabilità $1-P_f=(1-p)^{n_f}\simeq e^{-n_f p}$. Con trame di 10 000 bit, 200 bit di intestazione e ACK, $R=1$ Mbit/s e $2t_{\text{prop}}=1$ ms, senza errori $\eta_0=87{,}5\,\%$:

$p$	$0$	$10^{-6}$	$10^{-5}$	$10^{-4}$
$1-P_f$	$1$	$0{,}990$	$0{,}905$	$0{,}368$
$\eta_{\text{SW}}$	$87{,}5\,\%$	$86{,}6\,\%$	$79{,}2\,\%$	$32{,}2\,\%$

Gli errori pesano quando $n_f\,p$ si avvicina a 1. Lo stop and wait è semplice, ma conviene poco con un prodotto banda-ritardo alto o con molti errori, come nei collegamenti senza fili disturbati da interferenze.

Go-Back-N: la finestra

Nel Go-Back-N A invia fino a $W_s$ trame di seguito senza aspettare i riscontri. $W_s$ è la finestra di trasmissione. Gli ACK portano ancora $R_{\text{next}}$: quando A riceve l'ACK $R_{\text{next}}$, la finestra scorre e va da $R_{\text{next}}$ a $R_{\text{next}}+W_s-1$, sempre lunga $W_s$ (sliding window). A invia le trame della finestra che non ha ancora inviato. Lo stop and wait è il caso $W_s=1$.

Se la finestra copre il ciclo, A trasmette senza pause e il canale è sempre occupato: l'efficienza, come rapporto fra tempo di trasmissione e tempo totale, vale 1.

Go-Back-N con $W_s=3$

Caso

Senza erroriTrama 2 persa

AB123456234567

Perdite: si torna indietro

A tiene $S_{\text{last}}$, la trama più vecchia non ancora riscontrata, e può avere inviato le trame da $S_{\text{last}}$ a $S_{\text{last}}+W_s-1$. Avvia un timeout per ogni trama. Quando arriva un ACK con $R_{\text{next}}$ maggiore, pone $S_{\text{last}}=R_{\text{next}}$. Se scade il timeout di $S_{\text{last}}$, torna indietro e ritrasmette tutte le trame inviate da $S_{\text{last}}$ in poi: da qui il nome.

B ha una finestra di ricezione $W_r=1$: accetta solo la trama corretta con numero $R_{\text{next}}$ e scarta le trame errate e quelle fuori sequenza. Nella figura, con la trama 2 persa, A invia ancora 3 e 4, che la finestra 2–4 consente; B le riceve corrette ma le scarta, perché manca la 2. Scade il timeout della 2 e A ritrasmette 2, 3 e 4, che ora B accetta in ordine. La sequenza resta corretta; il prezzo è ritrasmettere trame già arrivate bene.

Riscontro cumulativo

L'ACK $R_{\text{next}}$ conferma tutte le trame fino a $R_{\text{next}}-1$, perché B accetta solo in sequenza: è un riscontro cumulativo. Così un ACK perso non costa nulla, se il successivo arriva prima del timeout. Con $W_s=4$, A invia le trame da 1 a 4 e l'ACK 2 si perde; arriva l'ACK 3, prima che scada il timeout della 1. La finestra scatta da 1–4 a 3–6, la trama più vecchia non riscontrata: A ha già inviato 3 e 4, quindi invia la 5. Se l'ACK 3 arrivasse dopo il timeout, A ritrasmetterebbe la finestra dalla 1.

Piggybacking e controllo di flusso

Quando A e B si scambiano dati nei due versi, ognuno mette nelle proprie trame di dati anche il riscontro per l'altro: è il piggybacking. Il riscontro vale per ciò che è arrivato quando la trama viene formata. Con trame di B molto più lunghe di quelle di A, $W_s=4$, timeout molto lungo e nessun errore:

Trama di B	Ricevute da B	$R_{\text{next}}$	Finestra di A	A invia
prima	nessuna	1	1–4	niente
seconda	1	2	2–5	5
terza	1, 2, 3, 4	5	5–8	6, 7, 8

All'inizio A ha già inviato le trame da 1 a 4, quindi il primo riscontro non lo fa avanzare; il terzo conferma tre trame in un colpo, e A procede a singhiozzo, al ritmo dei riscontri.

Se B ritarda i riscontri, la finestra di A scorre più lentamente e A rallenta. Il ricevitore regola così la velocità del trasmettitore: è il controllo di flusso, che il protocollo fa da sé, purché i riscontri arrivino prima dei timeout.

Quanto grande la finestra

A non si ferma se le trame della finestra coprono il ciclo $t_0$ della prima, cioè se $W_s\,t_f\ge t_0$:

$$W_s\ge\left\lceil\frac{t_{\text{ack}}+2t_{\text{prop}}}{t_f}\right\rceil+1$$

con l'elaborazione trascurata. Allora, senza errori, l'ultima di $n$ trame parte a $(n-1)\,t_f$ e il suo ACK torna $t_0$ dopo: $T_{\text{tot}}=(n-1)\,t_f+t_0$.

Con una finestra più piccola A esaurisce le trame prima che torni il primo ACK e resta fermo. Con una molto più grande il canale resta occupato, ma ogni errore costa una finestra intera. Se ogni trama sbagliata fa ripetere $W_s$ trame, il tempo medio per trama e l'efficienza sono

$$\begin{gathered} t_{\text{GBN}}=t_f+P_f\,\frac{W_s\,t_f}{1-P_f}\\ \eta_{\text{GBN}}=\frac{1-n_o/n_f}{1+(W_s-1)\,P_f}\,(1-P_f) \end{gathered}$$

per una finestra non minore della minima: più grande è $W_s$, più pesa ogni errore.

Efficienza e dimensione della finestra

finestra minima$W_s$

• senza errori
• ${\eta }_{\text{GBN}}$ con errori, senza intestazione

$2t_{\text{prop}}/t_f$

5

$P_f$

0,02

Con $2t_{\text{prop}}=5\,t_f$ e ACK trascurabile la finestra minima è 6; con $P_f=0{,}02$ l'efficienza è $0{,}98/1{,}1\approx0{,}89$ con $W_s=6$ e scende a circa $0{,}62$ con $W_s=30$.

Esempio: un collegamento via satellite

Un canale via satellite va a 1 Mbit/s, con ritardo di propagazione di 250 ms e trame di 2000 bit; ACK trascurabili, nessun errore. Una trama dura $t_f=2$ ms e il ciclo $t_0=t_f+2t_{\text{prop}}=502$ ms. La finestra minima del Go-Back-N è

$$W_s=\left\lceil\frac{500}{2}\right\rceil+1=251$$

Con 100 trame A resterebbe fermo per 302 ms a ogni ciclo; con 600 il canale resterebbe occupato, ma ogni errore farebbe ritrasmettere molte più trame. Con lo stop and wait, una trama per ciclo:

$$\eta_0=\frac{t_f}{t_f+2t_{\text{prop}}}=\frac{2}{502}=\frac{1}{251}\approx0{,}004$$

cioè lo 0,4 %.

Oltre il Go-Back-N

Il Selective Repeat evita di ripetere le trame già arrivate bene: B conserva le trame corrette fuori sequenza e A ritrasmette solo quelle mancanti. Nella figura con la trama 2 persa, B terrebbe 3 e 4 e A ritrasmetterebbe solo la 2.