La Parte III comincia esattamente dove il capitolo 1 si era interrotto. I router di Internet formano una rete di code, la presenza di code nei nodi è la causa principale della variabilità del ritardo, e un accumulo di pacchetti in coda può influire sulle prestazioni: è la congestione.
I capitoli da 3 a 7 hanno quantificato quel fenomeno dall'interno del nodo. Adesso lo si guarda dal punto di vista opposto: quello della sorgente, che è l'unico soggetto in grado di fare qualcosa. Il capitolo 6 ci ha lasciato con una conclusione precisa e scomoda: in un M/M/1/L con A0 > 1 non è possibile dimensionare L per ottenere una probabilità di blocco piccola a piacere. Aggiungere memoria non crea capacità.
Con buffer infiniti, il throughput satura e il ritardo cresce senza limite. Con buffer finiti, quando la congestione diventa significativa alcuni pacchetti vengono scartati per buffer overflow; questo ha spesso come effetto la ritrasmissione dei pacchetti persi, e quindi si rischia di causare un ulteriore aumento del carico se non si interviene in qualche modo. Quel modo è il congestion control, e la Parte III racconta come il TCP lo realizza.
La domanda generale è: come possiamo garantire un corretto scambio di dati tra sorgente e destinazione? Le slide la scompongono in quattro aspetti critici, ciascuno con la propria famiglia di soluzioni. Vale la pena impararli in quest'ordine, perché è l'ordine in cui verranno affrontati.
La distinzione fra il terzo e il quarto punto è quella su cui si gioca tutta la Parte III, e va fissata subito con le parole delle slide:
| Controllo | Regolare la velocità della sorgente per evitare di sovraccaricare… |
|---|---|
| di flusso | … la destinazione |
| di congestione | … la rete |
Due meccanismi diversi, due colli di bottiglia diversi, due finestre diverse. Il capitolo 12 li vedrà convivere nella singola relazione W = min{AW, CW}.
Il controllo d'errore consiste nell'aggiunta di bit di ridondanza per rilevare o correggere eventuali bit ricevuti errati. Il caso più semplice è il bit di parità; nella pratica si usano codici a blocco, codici convoluzionali, CRC, l'Internet Checksum e altri.
Le due strategie possibili si distinguono per quanta ridondanza aggiungono e per che cosa ci si fa:
Forward Error Correction. Richiede maggiore ridondanza, perché i bit aggiuntivi devono bastare non solo ad accorgersi dell'errore ma a ricostruire il dato corretto. È utile nel caso di comunicazioni soggette a molti errori, e il suo utilizzo principale è nelle comunicazioni wireless. Il vantaggio è che non serve alcuna ritrasmissione, quindi nessun round-trip aggiuntivo.
Rivelazione di errore. Richiede minore ridondanza ed è utile nel caso di comunicazioni soggette a pochi errori. Ha però un costo: rende necessaria la ritrasmissione dei dati errati. È la strategia usata anche nei protocolli di livello superiore al 2, e in particolare dal TCP con il suo checksum a 16 bit.
La scelta è un compromesso economico: la FEC paga sempre un sovrapprezzo in banda, anche quando non serve; la rivelazione paga solo quando serve, ma paga in latenza, che è la valuta più cara nelle reti geografiche. Per questo il wireless, dove gli errori sono frequenti, usa FEC, mentre le reti cablate, dove sono rari, si limitano a rivelare e ritrasmettere.
Un protocollo ARQ gestisce la ritrasmissione dei dati ricevuti errati, ma anche di quelli mai ricevuti — ad esempio perché scartati da nodi intermedi — e la gestione dei dati ricevuti fuori sequenza. La precisazione non è pedante: in una rete a pacchetto la causa dominante di ritrasmissione non è l'errore sui bit, è la perdita per buffer overflow di cui parla il capitolo 1.
Ogni soluzione ARQ poggia su tre ingredienti:
Gli acknowledgement possono essere di tre tipi, e li ritroveremo tutti nel TCP:
| Tipo di ACK | Significato |
|---|---|
| esplicito | una conferma per ciascun blocco di dati |
| implicito o cumulativo | una conferma per più blocchi di dati |
| piggybacking | conferma inviata assieme ai dati trasmessi in direzione opposta |
Le due famiglie di protocolli ARQ sono Stop-and-Wait e Sliding Window.
Nel protocollo Stop-and-Wait il trasmettitore invia un blocco dati e aspetta l'ACK dal ricevitore prima di trasmettere il blocco successivo. Se non riceve l'ACK entro un certo time-out, ritrasmette l'ultimo blocco già inviato. È necessaria la gestione dei duplicati nel ricevitore, perché un ACK perso porta a una ritrasmissione di un blocco che era invece arrivato.
Il vantaggio è la semplicità estrema: consente una numerazione a singolo bit, perché in volo c'è al massimo un blocco e basta distinguerlo dal precedente. Lo svantaggio è dichiarato senza mezzi termini: scarsa efficienza quando il round-trip time è maggiore dei tempi di trasmissione.
Il problema dello Stop-and-Wait non è la banda del collegamento: è il prodotto banda × ritardo. Su un collegamento veloce e lungo il trasmettitore passa quasi tutto il tempo ad aspettare, e la capacità disponibile resta inutilizzata. È esattamente lo stesso ragionamento che nel capitolo 12 porterà alla nozione di «finestra ideale».
Nel protocollo Sliding Window più blocchi di dati sono trasmessi prima di ricevere l'ACK. Trasmettitore e ricevitore concordano la dimensione della finestra di trasmissione W, cioè il numero massimo di blocchi che è possibile inviare senza aver ricevuto conferma. Con una numerazione a n bit i numeri di sequenza si riusano modulo M = 2n.
WT + WR ≤ M serve proprio a garantire che due blocchi con lo stesso numero non possano mai coesistere in rete.Il beneficio dichiarato è che il meccanismo migliora l'efficienza quando il RTT non è trascurabile. Con W = 1 si ricade nello Stop-and-Wait; già con W = 3 il trasmettitore riesce a tenere occupata la linea per una frazione di tempo molto maggiore.
La finestra scorrevole risolve l'efficienza, ma apre un problema nuovo: che cosa fare quando uno dei blocchi in volo si perde, mentre i successivi sono già in viaggio? Le due risposte classiche si distinguono per dove mettono la complessità.
Il ricevitore scarta i dati successivi, anche se ricevuti correttamente, per evitare che siano fuori sequenza. Scatta il time-out quando il trasmettitore non riceve un ACK, e il trasmettitore ritrasmette tutti i dati a partire dal blocco non confermato.
| Pro | Contro |
|---|---|
| operazioni semplici da implementare; buffer limitato al ricevitore | inefficienza a causa della ritrasmissione di dati già ricevuti correttamente |
Il ricevitore scarta solo il blocco errato e notifica al trasmettitore il blocco mancante con un Negative ACK, dopo aver ricevuto il blocco successivo. Il trasmettitore ritrasmette solo il blocco mancante. Il ricevitore mantiene in un buffer i blocchi successivi corretti e, quando riceve il mancante, ricostruisce la sequenza giusta e invia un ACK cumulativo.
| Pro | Contro |
|---|---|
| migliore efficienza | ricevitore più complesso |
Il TCP sta in mezzo. Gli ACK sono cumulativi e la procedura di default è Go-Back-N, «anche se molte implementazioni mantengono in memoria i segmenti ricevuti correttamente ma fuori sequenza» — e in più si può negoziare una modalità di tipo Selective Repeat, il SACK. È un punto ricorrente: alla domanda «TCP è Go-Back-N o Selective Repeat?» la risposta corretta non è nessuna delle due da sola.
Il controllo di flusso risponde al terzo aspetto critico: la sorgente deve adattare la velocità con cui trasmette i dati alla capacità di elaborazione della destinazione. Le due famiglie di soluzioni sono:
| Meccanismo | Come funziona | Quando si usa |
|---|---|---|
| Rate based | alla sorgente viene specificata una frequenza di trasmissione R adatta alla capacità della destinazione; la sorgente invia un blocco dati ogni 1/R secondi |
adatto alle modalità di trasmissione multicast/broadcast |
| Window (o credit) based | la destinazione comunica esplicitamente la dimensione massima della finestra di trasmissione in base alla propria capacità (advertised window, AW); la sorgente imposta di conseguenza il valore di W, che può variare nel tempo | adatto alle comunicazioni verso una singola destinazione |
La differenza sostanziale è chi tiene il volante. Nel rate based la destinazione dice «non più di tanto al secondo» e poi tace; nel window based la destinazione emette crediti a ogni ACK, e la sorgente non può spendere più di quanto ha ricevuto. Il secondo è auto-regolante: se la destinazione smette di consumare, smette anche di emettere crediti, e la sorgente si ferma da sola.
Il meccanismo si integra naturalmente con lo sliding window ARQ: la destinazione modifica il valore di AW dentro gli ACK che già stava inviando, e il trasmettitore riduce o allarga W di conseguenza. È esattamente ciò che fa il TCP con il campo Window dell'intestazione, come vedremo nel capitolo 9.
Il controllo di congestione risponde al quarto aspetto critico: la sorgente deve adattare la velocità con cui trasmette i dati alla capacità di smaltimento della rete, che può variare nel tempo a causa di eventi aleatori di congestione. È la differenza cruciale rispetto al controllo di flusso: la capacità della destinazione è una proprietà nota e stabile, quella della rete no.
La sorgente adatta dinamicamente la velocità con cui trasmette i dati in base allo stato corrente della rete. È un metodo reattivo: prima si osserva un sintomo, poi si corregge. È la scelta di Internet e del TCP.
La sorgente fornisce una descrizione del suo profilo di traffico all'atto della creazione della connessione; la rete riserva le risorse necessarie a soddisfare quel profilo, se disponibili; la sorgente trasmette in base al profilo indicato. È un metodo proattivo, tipico delle reti a commutazione di circuito e delle architetture con garanzie di qualità del servizio.
Scelto l'approccio closed-loop, restano due scelte progettuali indipendenti, e ciascuna è un compromesso dichiarato.
| Dimensione | Alternative | Compromesso |
|---|---|---|
| Modalità di retroazione | esplicita: informazioni sull'eventuale congestione inviate tramite messaggi di controllo dalla rete o dalla destinazione implicita: la sorgente si accorge della congestione osservando le tempistiche e il comportamento dei dati scambiati e degli ACK ricevuti |
esplicita = controllo più accurato, ma maggiore overhead implicita = controllo meno accurato, ma minore overhead |
| Livello di controllo | end-to-end: solo fra sorgente e destinazione hop-by-hop: fra coppie di nodi intermedi |
end-to-end = dipendenza forte dal RTT hop-by-hop = reazione più rapida perché non dipende dal RTT, ma operazioni più complesse nei router |
Il TCP sceglie implicito ed end-to-end, cioè la combinazione con il minor costo per la rete e il maggior costo in termini di prontezza. Non è un caso: è la stessa scelta architetturale della pila di Internet, che tiene i router semplici e mette l'intelligenza ai bordi. Il prezzo, come vedremo nel capitolo 12, è che due connessioni con RTT diverso reagiscono con velocità diverse, e la rete finisce per favorire le connessioni con RTT breve.
Il controllo si realizza in pratica con l'adattamento dinamico della finestra di trasmissione dell'ARQ sliding window, che serve così a entrambi gli scopi. Le slide riassumono l'effetto della dimensione della finestra in due righe che è utile tenere insieme:
Tutto il capitolo 12 è la storia di come il TCP cerca, senza mai trovarlo del tutto, il punto di equilibrio fra queste due frasi.
Il capitolo si chiude collocando il TCP nella tassonomia appena costruita. Il protocollo di trasporto affidabile di Internet, che vive solo nei due host terminali, è caratterizzato da tre scelte:
ARQ sliding window con numerazione dei BYTE trasmessi
controllo di flusso window based
controllo di congestione implicito ed end-to-endQueste tre righe sono la carta d'identità del TCP e vanno sapute a memoria, perché ciascuna apre un capitolo. La numerazione a byte invece che a pacchetti è la particolarità del TCP rispetto ai protocolli ARQ classici visti qui, e la sua ragione è che il TCP tratta i dati applicativi come un flusso continuo, non come una sequenza di messaggi.
Da qui in poi si scende nel dettaglio: il capitolo 9 apre il segmento e ne guarda i campi, il 10 studia l'apertura e la chiusura della connessione, l'11 il time-out di ritrasmissione e il controllo di flusso, il 12 il controllo di congestione e il 13 i modelli per stimarne le prestazioni.
1) Verifica della correttezza dei dati ricevuti, con codici a rivelazione o correzione di errore. 2) Verifica della completezza e della corretta sequenza, con protocolli ARQ. 3) Regolazione della velocità della sorgente per non sovraccaricare la destinazione: controllo di flusso. 4) Regolazione della velocità della sorgente per non sovraccaricare la rete: controllo di congestione. Le soluzioni si applicano fra nodi intermedi (layer 2/3) oppure end-to-end (layer 4).
La Forward Error Correction richiede maggiore ridondanza ma corregge senza ritrasmettere: è utile dove gli errori sono molti, e il suo utilizzo principale è nelle comunicazioni wireless. La rivelazione richiede minore ridondanza ma rende necessaria la ritrasmissione: è utile dove gli errori sono pochi, ed è usata anche nei protocolli di livello superiore al 2, come il checksum del TCP.
Esplicito: una conferma per ciascun blocco di dati. Implicito o cumulativo: una conferma per più blocchi. Piggybacking: conferma inviata assieme ai dati trasmessi in direzione opposta. Il TCP li usa tutti e tre: gli ACK sono cumulativi e viaggiano in piggybacking quando c'è traffico nella direzione opposta.
Perché il trasmettitore invia un blocco e poi si ferma ad aspettare l'ACK. È tanto più inefficiente quanto più il round-trip time è maggiore del tempo di trasmissione di un blocco: su un collegamento veloce e lungo la linea resta inattiva per quasi tutto il tempo. Il vantaggio è che consente una numerazione a singolo bit.
Il numero massimo di blocchi che è possibile inviare senza aver ricevuto l'ACK. Trasmettitore e ricevitore la concordano. Con numerazione a n bit i numeri di sequenza si riusano modulo M = 2n, e le dimensioni delle finestre di trasmissione e ricezione devono rispettare WT + WR ≤ M per evitare conflitti fra numeri di sequenza.
Go-Back-N: il ricevitore scarta tutti i dati successivi al blocco perso, anche se corretti; allo scadere del time-out il trasmettitore ritrasmette tutto a partire dal blocco non confermato. Pro: semplice, buffer limitato al ricevitore. Contro: inefficiente, ritrasmette dati già arrivati bene. Selective Repeat: il ricevitore scarta solo il blocco errato, lo segnala con un NACK, bufferizza i successivi e invia un ACK cumulativo quando la sequenza si ricompone; il trasmettitore ritrasmette solo il mancante. Pro: più efficiente. Contro: ricevitore più complesso.
Entrambi, in un certo senso. Gli ACK sono cumulativi e la procedura di default è di tipo Go-Back-N, anche se molte implementazioni mantengono comunque in memoria i segmenti ricevuti correttamente ma fuori sequenza. Si può inoltre negoziare all'apertura della connessione una modalità di tipo selective repeat, il SACK, che permette di ritrasmettere solo i segmenti effettivamente perduti.
Rate based: alla sorgente viene specificata una frequenza R e la sorgente invia un blocco ogni 1/R secondi; è adatto a multicast e broadcast. Window based (o credit based): la destinazione comunica esplicitamente la advertised window in base alla propria capacità, e la sorgente imposta W di conseguenza; è adatto alle comunicazioni verso una singola destinazione ed è auto-regolante, perché i crediti si esauriscono se la destinazione smette di consumare.
Il controllo di flusso adatta la velocità della sorgente alla capacità di elaborazione della destinazione, che è una proprietà nota e sostanzialmente stabile. Il controllo di congestione la adatta alla capacità di smaltimento della rete, che varia nel tempo a causa di eventi aleatori. Sono due meccanismi distinti, con due colli di bottiglia diversi, e nel TCP convivono nella relazione W = min{AW, CW}.
Closed-loop (reattivo): la sorgente adatta dinamicamente la velocità in base allo stato corrente della rete; è la scelta di Internet. Open-loop (proattivo): la sorgente descrive il proprio profilo di traffico alla creazione della connessione, la rete riserva le risorse necessarie se disponibili, e la sorgente trasmette secondo quel profilo.
Esplicita: messaggi di controllo dalla rete o dalla destinazione, controllo più accurato ma maggiore overhead. Implicita: la sorgente deduce la congestione osservando tempistiche e ACK, controllo meno accurato ma minore overhead. End-to-end: solo fra sorgente e destinazione, con forte dipendenza dal RTT. Hop-by-hop: fra coppie di nodi intermedi, reazione più rapida perché non dipende dal RTT, ma operazioni più complesse nei router. Il TCP sceglie implicito ed end-to-end.
W piccolo riduce il carico nella rete e quindi la possibilità di generare congestione. W grande migliora l'efficienza e il tempo di completamento della connessione. Il controllo di congestione consiste appunto nell'adattare dinamicamente W per stare il più vicino possibile al punto in cui le due esigenze si bilanciano.
ARQ sliding window con numerazione dei byte trasmessi; controllo di flusso window based; controllo di congestione implicito ed end-to-end. La numerazione a byte invece che a pacchetti è la particolarità rispetto ai protocolli ARQ classici, e discende dal fatto che il TCP tratta i dati applicativi come un flusso continuo.