TCP è un protocollo stop-and-wait: si aspetta il pacchetto di ack per un certo tempo prima di ritrasmettere il pacchetto.
Come stimare il giusto tempo di timeout? Un timeout troppo breve porterebbe a frequenti ritrasmissioni. Un timeout troppo lungo porterebbe ad una lenta reazione alla perdita dei pacchetti.
L'unica certezza è che
S D
| ----> | -
| | | RTT
| | |
| <---- | -
Quanto maggiore? Inoltre, il RTT cambia continuamente in base a fattori come:
- condizioni del traffico di rete
- cambiamenti delle rotte
Una scelta obsoleta è quella di prendere
RTT - Round Trip Time: tempo tra invio dell'ultimo bit di un pacchetto e ricezione dell'ACK da parte del destinatario.
Tempo di propagazione: tempo per andare dalla sorgente alla destinazione. Idealmente
$\frac{RTT}{2}$ .
Approcci diversi, dai più semplici ai più complessi:
-
$Timeout = \beta \times RTT_{AVG}$ con$\beta=2$ consigliato - Sample RTT: misura il tempo tra invio del segmento e ricezione ACK
- Esitmated RTT (Exp Weighted Mov AVG):
$RTT_{EWMA} = (1-x) \times RTT_{EWMA}(t-1) + x \times SampleRTT(t)$
L'Estimated RTT si adatta più velocemente agli outvalue. Gestisce meglio gli spike.
Ma alcuni valori vengono comunque scartati, ovvero quelli sopra
Come facciamo ad ottenere meno falsi positivi? Possiamo aggiungere un margine di errore:
Un protocollo stop-and-wait è altamente affidabile ma rallenta enormemente il throughput a causa delle latenze della rete.
In quanto trasmetto un pacchetto?
Posso introdurre una strategia di pipelining.
Sussiste la formula di occupazione della rete. L'utilizzazione precedente viene scalata per il numero di di segmenti che riesco ad inviare in parallelo.
Quanti segmenti inviare senza attendere l'ack? Questo fattore è importante e la velocità di trasmissione si governa con questo fattore.
La dimensione massima del segmento è governata dal path MTU.
Meccanismo a finestra scorrevole
La sliding window identifica quale area di memoria, appartenente al buffer, deve essere inviata al destinatario.
La parte che sta dietro, fuori dalla finestra, contiene tutti i segmenti che sono stati inviati e confermati con ACK. La parte in testa contiene i segmenti ancora da inviare.
#Attenzione è diverso rispetto a dire che la coda contiene pacchetti che sono stati inviati ma di cui attendiamo l'ACK. Questo non è sempre possibile perché gli ACK potrebbero arrivare out-of-order. Come descritto sopra si presuppone che alcuni segmenti inclusi nella finestra lo abbiano già ricevuto.
| 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 | 100 |
| window |
^ ^
LAR LSS
- LAR - Last Acknowledgement Received
- LSS - Last Segment Sent
- SWS - Sender Window Size -
A sinistra di LSS (incluso LSS) si trovano i segmenti inviati di cui si attende ACK, mentre alla sua destra si trovano quelli da inviare.
| 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 | 100 |
| window |
^ ^
LSR LAS
- LSR - Last Segment Received
- LAS - Last Acceptable Segment
- RWS - Receive Window Size
Il destinatario accetta solo i segmenti che arrivano all'interno della sliding window.
#Nota se arriva un segmento fuori dalla finestra -> deve essere scartato
Come dimensionarla?
- più è grande RWS più siamo resilienti a reti che consegnano i segmenti fuori ordine.
- più è grande più memoria dobbiamo allocare al processo di ricezione. Inoltre finché i dati non sono contigui non potremo svuotare il buffer allocato dal SO.
Idealmente il buffer del mittente e del destinatario dovrebbero essere uguali. Non ha senso avere buffer grandi in trasmissione per poi droppare la maggior parte dei pacchetti in ricezione.
Inoltre non è detto che la dimensione delle finestre sia dinamica; cercheremo di dimensionare il buffer del mittente con due strategie:
- controllo di flusso - dimensionato in base al buffer del destinatario
- controllo di congestione - dimensionato in base allo stress sulla rete
#Nota questo buffer è ripetuto per ogni connessione TCP instaurata. Il che è diverso da dire: per ogni porta. Si pensi ad un server web.
ACK cumulativi. Ogni ACK conferma la ricezione di tutto il flusso, fino a quel segmento (diverso dalla supposizione fatta finora).
Se ricevo un segmento con SEQ diverso da quello che attendevo, riconfermo l'ultimo ricevuto contiguamente. Eg con Go-Back-N con N=4:
- invio 0, 1, 2, 3
- ricevo 0, confermo 0
- ricevo 1, confermo 1
- ricevo 3, confermo 1
- ricevo 0
- invio 4
- ricevo 1
- invio 5
- mi accorgo del timeout di 2
- reinvio da 2 in poi (alto costo)
Questo approccio semplifica la logica di funzionamento, ma introduce un alto costo, in quando devono essere reinviati dati che magari erano stati ricevuti correttamente. Il mittente gestisce di fatto una finestra grande 1.
#Attenzione l'ACK cumulativo non corrisponde a ritrasmetto un ACK finale dopo una marea di segmenti ricevuti. Quando tutto va bene ACK selettivo e cumulativo hanno il medesimo comportamento.
Si tratta di un ACK stateful.
#Nota nel caso di una perdita di ACK questa tecnica riesce a comunicare al mittente di aver ricevuto il segmento di cui esso non ha ricevuto l'ACK. La ritrasmissione selettiva non gestisce questo caso.
ACK selettivi. Alla ricezione di un segmento si conferma solamente la ricezione di quel segmento. ACK stateless.
Si noti inoltre che con ACK cumulativi in caso di consegna fuori ordine, con ricezione dell'ACK di un segmento "vecchio" successiva alla ricezione di un AKC più nuovo, si evita la ritrasmissione del vecchio (Vecchio fuori timeout, ma nuovo dentro).
Controllo di flusso: evita di spedire più segmenti di quanti il destinatario ne possa ricevere Controllo di congestione: evita di spedire più segmenti di quanti la rete ne riesca a gestire. Si pensi alla congestione di un router.
Come coniugarli? Vogliono influenzare lo stesso parametro. $$ Effective window = min(Flow Window, Congestion Window) $$
Si introduce un concetto di fairness: TCP cerca di non inviare segmenti inutili, che non sarebbero gestibili dal destinatario o dalla rete; l'idea alla alla base della fairness è anche quella di dividere equamente le risorse tra più utenti della stessa rete.
TCP usa un approccio ibrido tra Go-Back-N e Ritrasmissione Selettiva.
#Nota il destinatario ha un controllo diretto su quanti dati deve inviare il mittente
Tramite il campo window size dell'header TCP il destinatario invia al mittente la dimensione libera della sliding window. Più si riempie il buffer il ricezione, meno segmenti il mittente deve inviare.
Nell'ipotesi in cui il destinatario dovesse inviare window size = 0 il mittente dovrebbe smettere di inviare segmenti.
Perché si potrebbe riempire il buffer (allocato dal SO)?
- TCP è un protocollo nativamente asincrono. Se i dati del buffer non vengono consumati, il buffer si satura.
- Il destinatario, senza ricevere nulla, non avrebbe mai l'occasione per poter segnalare che il buffer si è svuotato. Viene introdotta una logica di polling che invia pacchetti con payload fittizi (nullo o ad 1 byte) per avere una risposta dal dst.
#Vedi Advertised Window e Flow Window
Congestione: saturazione della rete (buffer dei router saturi, et similia)
Questo è l'approccio usato da TCP, il controllo è regolato da mittente e destinatario.
- slow start: partiamo piano pessimisticamente.
- AIMD - Additive Increase Multiplicative Decrease. Equilibrio dinamico, non cerca di convergere ad un punto fisso di stabilità.
CW : = 1 # Congestion Window
for each segment ACK:
CW * = 2
until (timeout OR CW > threshold)
L'evento di timeout menzionato può essere dovuto a:
- router che scarta segmento
- destinatario che non risponde
La velocità di trasmissione in questo contesto è misurata in termini di segmenti contenibili nella sliding window.
#Nota nella fase di slow-start non si aumenta addittivamente (per questo differenziata da Additive Increase). Se aumentassi linearmente e non esponenzialmente nella prima fase avrei una trasmissione subefficiente per parecchio tempo.
Il timeout non è l'unico meccanismo per rilevare che qualcosa sta andando storto:
- timeout scaduto
- ACK duplicato presupponendoci in un contesto di ACK cumulativo
Supponendo ACK cumulativo. Se:
- trasmetto 10, 20, 30, 40
- 10 viene ricevuto, conferma di 20
- 20 viene droppato dal router, niente ACK
- 30 viene ricevuto, conferma di 20
- 40 viene ricevuto, conferma di 20
In definitiva viene ricevuto un triplo ACK con SEQ pari a 20. Interpretato come NACK sul segmento 20.
Spesso la ricezione di ACK duplicati viene interpretata con meno severità rispetto alla scadenza di un timeout.
#Vedi algoritmo Reno. Questo algoritmo non riparte da zero, ma da threshold. #vedi algos: Tahoe, Cubic, BIC, New Reno, Proportional Rate Reduction L'algoritmo utilizzato è differente da OS in OS
Un timeout significa che o sto perdendo tutti i pacchetti, oppure che la latenza è davvero alta.
I router inviano informazioni sulla congestione mediante il bit ECN - Explicit Congestion Notification - a livello IP. I router forniscono un feedback esplicito ai nodi terminali.
L'evoluzione degli algoritmi per il controllo di congestione è dovuta sia a un miglior studio delle reti, sia ad una loro evoluzione. Le reti cambiano e così le velocità a cui questi algoritmi devono reagire.
TCP è quindi fair anche per il controllo della congestione. Osservando il comportamento su più macchine si nota che, quando la congestione aumenta, il loro utilizzo diminuisce in contemporanea.
Un uso "illecito" di UDP non è fair, rischia di saturare la banda dedicata agli altri.
Protocolli costruiti ad arte si dicono fair rispetto a TCP se è "amichevole", quindi implementa le sue stesse regole di condivisione della banda mediante controllo della congestione.