Go-Back-N: finestra scorrevole e riscontri cumulativi

Dallo stop and wait al Go-Back-N

Il trasferimento dati affidabile chiede quattro cose: niente frame fuori sequenza, niente duplicati, niente perdite, e dati consegnati corretti. Ricevere un frame e consegnarlo al livello di rete sono due passi diversi: un frame ricevuto può anche essere scartato. Gli strumenti sono la ritrasmissione, gli ACK, il timer di ritrasmissione (RTO, Retransmission Timeout) e i numeri di sequenza.

Lo stop and wait ha un frame in volo per volta, quindi rende poco quando il prodotto banda-ritardo $C\,\mathrm{RTT}$ è grande rispetto a $L$. Con una pipeline il trasmettitore invia $W$ frame senza aspettare i riscontri, e l'efficienza diventa $W$ volte quella dello stop and wait, fino al 100 %:

$$\eta=\min\left(1,\ \frac{W}{1+C\,\mathrm{RTT}/L}\right)$$

$W$ è la dimensione della finestra. Al 100 % l'ultimo bit dell'ultimo frame della finestra parte subito prima che arrivi l'ACK del frame più vecchio: il collegamento, come un tubo, è sempre pieno. Il protocollo che usa questa finestra è il Go-Back-N.

La finestra scorrevole

Con più frame in volo i numeri di sequenza non sono più solo 0 e 1, quindi il campo dell'intestazione usa più bit.

La finestra è una memoria del trasmettitore A, lunga $W$ frame. Comincia da un numero, la base, e contiene i numeri da base a base $+\,W-1$: quelli che A è autorizzato a inviare. Sono di due tipi:

• numeri di frame già inviati e non ancora riscontrati;
• numeri liberi, che A può usare per frame nuovi, se ne ha.

Se la finestra è piena di frame inviati, A si ferma. Il ricevitore B tiene una variabile, l'expected sequence number (ESN), il numero del prossimo frame atteso: parte da 0 e aumenta di uno a ogni frame accettato. L'ACK porta l'ESN, non il numero del frame appena ricevuto: dopo il frame 0 dice ACK 1. Quando A riceve un ACK, la base diventa il numero scritto nell'ACK e la finestra scorre in avanti (sliding window), liberando posto per un frame nuovo.

Con $W=4$, A invia i frame da 0 a 3 e si ferma. Arriva l'ACK 1: la finestra diventa 1–4 e A invia il 4. Con l'ACK 2 diventa 2–5 e A invia il 5, e così via.

Go-Back-N nel tempo

Caso

Senza erroriFrame 1 persoACK persi

AB012345123456

Una perdita: si torna indietro

Con $W=3$ A invia i frame 0, 1 e 2, e il frame 1 si perde. B accetta lo 0 e risponde con l'ACK 1: la base di A passa a 1. Il frame 2 arriva, ma accettarlo creerebbe un fuori sequenza: B lo scarta e ripete l'ultimo ACK, ACK 1, come a dire «aspetto ancora l'1». La finestra di A non scorre.

Da qui si esce con l'RTO. A tiene un solo timer, per il frame più vecchio non ancora riscontrato della finestra. Quando arriva l'ACK di quel frame, A ferma il timer e ne avvia uno per il nuovo frame più vecchio: all'ACK 1 il timer passa al frame 1. Quando l'RTO scade, A torna indietro e ritrasmette tutti i frame della finestra ancora in attesa di riscontro, qui 1 e 2: da questo il nome Go-Back-N.

Il prezzo dell'efficienza è questo: dopo una perdita si ritrasmettono anche frame già arrivati, come il 2. Per questo la finestra migliore è la minima che dà il 100 %, cioè

$$W_{\min}=\left\lceil1+\frac{C\,\mathrm{RTT}}{L}\right\rceil$$

Una finestra più grande non migliora l'efficienza, che è già al massimo, ma fa ritrasmettere più frame a ogni perdita.

Riscontri cumulativi

Nel Go-Back-N un ACK con numero $k$ significa «ho ricevuto correttamente fino a $k-1$, aspetto $k$». Con $W=4$, A invia i frame da 0 a 3; gli ACK 1, 2 e 3 si perdono e arriva solo l'ACK 4. La base passa subito a 4 e la finestra diventa 4–7: l'ACK 4 garantisce che sono arrivati anche 0, 1 e 2, anche se i loro riscontri non si sono visti.

Frame fuori ordine

Con $W=3$, se il frame 0 è molto in ritardo e i frame 1 e 2 arrivano prima:

1. B scarta 1 e 2, fuori sequenza, e risponde due volte con l'ACK 0, perché il suo ESN è ancora 0;
2. A riceve gli ACK 0 e non fa nulla: la finestra resta 0–2, se l'RTO non è ancora scaduto;
3. arriva il frame 0: B lo accetta, porta l'ESN a 1 e invia l'ACK 1; la finestra di A diventa 1–3 e A può inviare il 3.

I frame 1 e 2, scartati da B, ripartono allo scadere dell'RTO.