Il problema: trasmettitore veloce, ricevitore lento
Immagina di inviare un file a 1 Gbps verso un router che elabora i frame a 100 Mbps. Se il trasmettitore non rallenta, il buffer del ricevitore si riempie e i frame in eccesso vengono semplicemente scartati. Questo fenomeno si chiama buffer overflow.
Il controllo del flusso (flow control) è il meccanismo che impedisce al trasmettitore di inondare il ricevitore. Opera al livello Data Link per gestire il flusso tra due nodi adiacenti; la stessa logica, a livello superiore, è la base del controllo di congestione TCP.
Prima di analizzare le strategie, definiamo un parametro fondamentale: il rapporto tra il tempo di propagazione e il tempo di trasmissione.
Stop-and-Wait (PAR — Positive Acknowledgment with Retransmission)
La strategia più semplice: il trasmettitore invia un frame, poi si ferma e attende che il ricevitore invii un ACK (acknowledgment positivo) prima di inviare il successivo. Se scade il timeout senza ricevere ACK, ritrasmette lo stesso frame.
Efficienza: in Stop-and-Wait, il trasmettitore può occupare il canale solo per il tempo di trasmissione di un frame, poi attende 2×T_prop (round-trip). L’efficienza è:
Su un link transatlantico da 1 Gbps con RTT di 100ms, trasmettendo frame da 1 KB: a = 0.1s / 8μs = 12500. L’efficienza di Stop-and-Wait sarebbe 0.004% — praticamente inutilizzabile. Servono protocolli a finestra scorrevole.
Sliding Window — Il Concetto
L’idea è semplice: invece di attendere l’ACK di ogni frame prima di inviare il successivo, il trasmettitore mantiene aperta una finestra di N frame che possono essere “in volo” sul canale contemporaneamente, senza ACK ricevuto.
ACK
ACK
TX
TX
TX
TX
wait
wait
La finestra “scorre” (slide) man mano che arrivano gli ACK: da qui il nome. I frame sono numerati con k bit di sequenza, quindi i numeri di sequenza vanno da 0 a 2ᵏ−1, poi si riazzerano (arithmetic modulo 2ᵏ).
Go-Back-N (GBN)
In Go-Back-N il trasmettitore può avere fino a N frame in volo. Il ricevitore accetta solo frame in ordine e non ha buffer per i frame fuori sequenza. In caso di errore nel frame i:
Dimensione massima della finestra con k bit di sequenza: N ≤ 2ᵏ − 1. Non si può usare tutta la finestra 2ᵏ per evitare ambiguità tra ACK vecchi e nuovi.
GBN è efficiente quando il tasso di errore è basso: in quel caso raramente si ritrasmette, e la semplicità del ricevitore (nessun buffer) è un vantaggio. Se il canale è rumoroso, le ritrasmissioni a cascata degradano pesantemente le prestazioni.
Selective Repeat (SR)
Selective Repeat risolve il problema di GBN: ritrasmette solo il frame effettivamente errato. Il ricevitore ha un buffer e accetta frame fuori ordine, tenendoli in attesa del frame mancante per consegnarli al livello superiore in ordine.
La dimensione massima della finestra SR con k bit di sequenza è N ≤ 2^(k−1) — metà dello spazio dei numeri di sequenza. Questo vincolo è necessario per evitare che frame “vecchi” e “nuovi” abbiano lo stesso numero di sequenza quando la finestra avanza.
Confronto tra le tre strategie ARQ
| Protocollo | Finestra TX (k bit) | Buffer RX | In caso di errore | Efficienza canale |
|---|---|---|---|---|
| Stop-and-Wait | N = 1 | No | Ritrasmette 1 frame | 1/(1+2a) |
| Go-Back-N | N ≤ 2ᵏ−1 | No | Ritrasmette N frame | N/(1+2a) se N<2a+1 |
| Selective Repeat | N ≤ 2^(k−1) | Sì (finestra) | Ritrasmette 1 frame | N/(1+2a) se N<2a+1 |
Il protocollo TCP usa una sliding window con logica simile a Selective Repeat: il campo Window Size negli header TCP specifica quanti byte il ricevitore può ricevere senza ACK. Ogni ACK TCP usa cumulative acknowledgment (conferma tutti i byte fino a N) con SACK (Selective ACK) come opzione per recuperare i buchi. La finestra TCP varia dinamicamente con il controllo di congestione (slow start, congestion avoidance, fast retransmit).
Numeri di sequenza e gestione del timeout
I numeri di sequenza si ripetono ciclicamente. Con k=3 bit i numeri vanno da 0 a 7. In GBN la finestra max è 7 (non 8), perché se il trasmettitore invia 8 frame consecutivi con numeri 0–7 e tutti gli ACK vengono persi, il ricevitore non può distinguere se il frame 0 successivo è una ritrasmissione o un nuovo frame.
Il timeout deve essere calibrato correttamente: se troppo breve si generano ritrasmissioni inutili, se troppo lungo si perde tempo prezioso. Nei sistemi reali si usa un RTO adattivo (Retransmission Timeout), come fa TCP con l’algoritmo di Jacobson/Karels.
Canale affidabile, basso overhead: Go-Back-N (ricevitore semplice, nessun buffer). Canale rumoroso o satellite: Selective Repeat (evita ritrasmissioni a cascata). Sistemi embedded con poca RAM: Stop-and-Wait (implementazione minima). In generale, Selective Repeat domina nelle reti moderne dove memoria e CPU sono abbondanti.
- Buffer overflow: senza flow control, il ricevitore lento perde frame. ARQ risolve sia gli errori che il flusso con ACK/NAK + timeout.
- Stop-and-Wait: efficienza η = 1/(1+2a). Accettabile solo se a ≪ 1 (link corti e lenti).
- Go-Back-N: finestra N ≤ 2ᵏ−1, nessun buffer al ricevitore. Errore → ritrasmette N frame. Efficiente se errori rari.
- Selective Repeat: finestra N ≤ 2^(k−1), buffer al ricevitore. Errore → ritrasmette solo il frame sbagliato. Più efficiente ma più complesso.
- Il vincolo sulla dimensione massima della finestra evita ambiguità tra numeri di sequenza vecchi e nuovi nello spazio ciclico.
- TCP usa sliding window adattiva con logica SR + cumulative ACK + SACK: è l’evoluzione diretta dei meccanismi visti oggi.