Retels 1.0

Appunti di Reti di Telecomunicazioni L-S (versione 1.0) Ingegnere Pazzo http://ingegnerepazzo.wordpress.com/ 16 febbraio 2009

2

Indice 1

2

3

Il protocollo TCP: generalità 1.1 Il segmento TCP . . . . . . . . . . . 1.2 Macchina a stati finiti . . . . . . . . 1.2.1 Three-way handshake . . . . . 1.2.2 Chiusura della connessione 1.3 Lo svolgimento del dialogo . . . . 1.3.1 Retransmission Time-Out . 1.4 Lo stato enstablished . . . . . . . . . 1.5 Messaggi di conferma (ACK) . . . 1.6 In sintesi . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

5 5 5 7 8 8 9 12 12 13

Il protocollo TCP: controllo del flusso 2.1 Generalità . . . . . . . . . . . . . . . . . . . . . . . 2.2 Meccanismo a finestra scorrevole . . . . . . . . . . 2.2.1 Silly Window Syndrome . . . . . . . . . . . . 2.2.2 Algoritmo di Nagle . . . . . . . . . . . . . 2.3 Controllo di congestione . . . . . . . . . . . . . . . 2.4 Alcune definizioni ed evoluzione della CW . . . . 2.5 Alcune approssimazioni . . . . . . . . . . . . . . . 2.5.1 Un esempio . . . . . . . . . . . . . . . . . . 2.6 Altri aspetti del protocollo: algoritmi migliorativi 2.6.1 Fast recovery . . . . . . . . . . . . . . . . . . 2.6.2 Fast retransmit . . . . . . . . . . . . . . . . . 2.6.3 Reno e New Reno . . . . . . . . . . . . . . 2.7 In sintesi . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

15 15 15 16 16 17 19 20 21 22 22 24 25 26

Modelli analitici per le prestazioni del TCP 3.1 Ricerca di modelli matematici . . . . . . 3.2 Throughput e goodput . . . . . . . . . . . 3.3 Modello periodico . . . . . . . . . . . . 3.3.1 ACK ritardati . . . . . . . . . . . 3.4 Perdite aleatorie . . . . . . . . . . . . . . 3.4.1 Modello TD . . . . . . . . . . . . 3.4.2 Modello TD+TO . . . . . . . . . 3.4.3 Modello TD+TO+AW . . . . . . 3.5 Modelli a confronto . . . . . . . . . . . . 3.6 Latenza . . . . . . . . . . . . . . . . . . . 3.6.1 Finestra a dimensione fissa . . . 3.6.2 Finestra evolvente (dinamica) . . 3.7 In sintesi . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

29 29 29 30 31 32 32 36 36 37 40 41 42 43

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . 3

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

INDICE

4 A Esercizi A.1 Protocolli di rete, analisi di CW A.1.1 Esercizio 1 . . . . . . . . A.1.2 Esercizio 2 . . . . . . . . A.1.3 Esercizio 3 . . . . . . . . A.1.4 Esercizio 4 . . . . . . . . A.2 Modelli per il TCP . . . . . . . A.2.1 Esercizio 1 . . . . . . . . A.2.2 Esercizio 2 . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

47 47 47 49 51 53 55 55 55

Capitolo 1

Il protocollo TCP: generalità Il protocollo TCP è parte integrante dello strato 4 (trasporto) della pila OSI e ha il compito di svincolare gli strati superiori dai problemi di rete. È un protocollo di tipo connection-oriented (al contrario dell’UDP che è connection-less) e gestisce una connessione end-to-end (punto-punto) e full-duplex (bidirezionale); prevede inoltre procedure per l’instaurazione della connessione, il controllo del suo corretto andamento e la chiusura. Tutte le informazioni necessarie al corretto svolgimento dell’algoritmo TCP sono contenute nel TCB (transmission control block). L’interfaccia con le applicazioni, invece, non è definita a priori e fondamentalmente dipende dal sistema operativo utilizzato dall’utente. Il TCP garantisce la correttezza nella consegna dei dati utilizzando un protocollo a finestra scorrevole (Sliding-Window) basato su: • numerazione sequenziale dei dati; • conferma esplicita da parte del ricevitore; • ritrasmissione dei dati non confermati.

1.1

Il segmento TCP

Il TCP incapsula i dati in pacchetti chiamati segmenti. Il segmento TCP prevede un header standard di 20 byte, un header variabile con varie opzioni, un payload di dimensione variabile contente i dati dell’applicazione. Ogni segmento può avere una dimensione massima pari a MSS (Maximum Segment Size) e tipicamente contiene - oltre ai dati - informazioni come la porta sorgente, la porta destinazione, il numero di sequenza, l’acknowledge-number, un checksum per controllare se vi sono errori, alcuni bit per settare le opzioni (URG per considerare il campo Urgent Pointer, ACK considerare il campo Acknowledge, RST per resettare la connessione, SYN per sincronizzare i numeri di sequenza, FIN, per indicare la fine dei dati, PSH per la funzione di push, etc. . . ). L’MSS dipende dall’implementazione e normalmente è configurabile: il valore massimo che può assumere è pari a 216 − 20(header TCP) − 20(header IP) = 65495 byte, cioè pari alla dimensione del payload IP meno le intestazione, ma per l’Ethernet (che è il caso sul quale ci soffermeremo) è molto inferiore in quanto deve rispettare i 1500 byte imposti da tale tecnologia.

1.2

Macchina a stati finiti

In figura 1.1 vediamo il diagramma che illustra il funzionamento del protocollo TCP. Le linee tratteggiate indicano un’azione tipica di un server, le linee nere le azioni tipiche dei client e quelle chiare gli eventi ‘inusuali’. Sopra ogni freccia è indicata inoltre la {causa}/{effetto}. Esaminiamo insieme la figura: cosa succede fra un client e un server che vogliono iniziare a comunicare? Partendo da CLOSED e seguendo la linea nera, il client invierà un SYN al server per poter sincronizzare con esso il numero di sequenza. Il server (che parte da LISTEN) è - appunto - in ascolto e aspetta che qualcuno chieda i suoi servigi così, quando gli arriva il SYN da parte del client, invia un SYN+ACK per far sapere al client che ha ricevuto la sua richiesta (siamo ora nello stato SYN RECIEVED). Il client riceve la conferma del server e manda a sua 5

CAPITOLO 1. IL PROTOCOLLO TCP: GENERALITÀ

6

Figura 1.1:

La macchina a stati finiti che implementa il TCP

volta una conferma (un SYN+ACK): a questo punto il server non richiede altre conferme1 ed entrambi i comunicanti finiscono nello stato ENSTABLISHED (in verde). Quello illustrato fin’ora è il cosiddetto three-way handshake (‘stretta di mano a tre tempi’) e, alla prova dei fatti, si è dimostrato un metodo abbastanza robusto per instaurare una connessione (v. paragrafo 1.2.1). Chiaramente, durante queste fasi, possono accadere eventi come l’apertura simultanea (freccia nera da SYN SENT a SYN RCVD) o il non completamento del TWH (freccia nera da SYN RCVD a LISTEN). La parte inferiore del diagramma a stati si riferisce invece alla chiusura della connessione: la chiusura può essere passiva (da parte del server, che riceve il FIN e risponde con ACK) oppure attiva (da parte del client). • CASO 1: il client (C) vuole chiudere così invia un FIN; S risponde con un ACK ed, eventualmente, continua ad inviare dati perché la sua direzione è ancora aperta; quando si stufa pure lui invia un FIN e il C, che è in stato FIN WAIT 2, risponde con un ACK. 1 Se

si continua a confermare all’infinito non si trasmette nulla!

1.2. MACCHINA A STATI FINITI

7

• CASO 2: entrambi vogliono chiudere. Il client C invia il FIN e finisce in FIN WAIT 1, poi riceve anche il FIN del server e va in CLOSING, confermando il tutto con un ACK. Il server poco prima aveva ricevuto il FIN di C e così invia pure lui un ACK; al termine di tale scambio di conferme, entrambe le direzioni si chiudono e la trasmissione ha termine; • CASO 3: il client vuole chiudere e il server si accorge di voler fare lo stesso. Tutto funziona come nel caso 1, tranne per il fatto che S non vuole spedire dati e in una botta sola invia sia l’ACK che il FIN. Si noti che il client rimane per un po’ nello stato di time wait, utile per fare sì che i pacchetti dell’attuale connessione si estinguano onde evitare la sovrapposizione di più incarnazioni (v. par 1.2.1). Perché tutta questa serie di conferme e riconferme? Il fatto è che, se il mezzo di comunicazione è inaffidabile, è impossibile avere uno scambio di informazioni con conferma certa in quanto i messaggi, sia quelli contenenti dati che quelli contenenti informazioni di servizio, possono effettivamente perdersi nella rete.

1.2.1

Three-way handshake

Per quanto riguarda l’apertura di una connessione, si è scelto di fermarsi alla conferma della conferma: il three-way handshake, grazie a questa convenzione, è in grado di gestire situazioni di perdita, duplicazione o ritardo dei pacchetti. In tabella 1.1 si illustra il procedimento con particolare riferimento ai numeri di sequenza. Per semplicità indicheremo i due colloquianti con CLIENT e SERVER (ma, per generalità, si possono pensare tali due computer come due calcolatori qualsiasi A e B). Chi parla? CLIENT CLIENT CLIENT

SIN bit 1 1 0 0

ACK bit 0 1 1 0

Tabella 1.1:

SeqN x y x+1 x+1

AckN x+1 y+1 y+1

Chi parla? SERVER

→ inizio invio dati

Numeri di sequenza nel TWH

Si noti che il primo pacchetto dati ha numero di sequenza uguale all’ACK precedente!

Figura 1.2:

Possibili inconvenienti in cui si può incappare nel TWH

Eventi imprevisti o inusuali (v. figura 1.2):

CAPITOLO 1. IL PROTOCOLLO TCP: GENERALITÀ

8

• Instaurazione multipla: A e B vogliono connettersi ed inviano entrambi una richiesta d’apertura. Grazie al TWH questa situazione si risolve in modo molto naturale e spontaneo: visto che vi è volontà di connettersi da parte di entrambi gli host, il primo che riesce a mandare un pacchetto con SIN e ACK entrambi a 1 dà il via alla trasmissione dati (l’altro eventuale pacchetto con SIN e ACK ad 1 è del tutto superfluo); • Pacchetti d’apertura ritardatari: uno dei due tentativi di connessione viene inibito tramite l’attivazione del bit RST; • Problema delle ’incarnazioni’: A e B stanno parlando, ma A viene riavviato per qualche motivo; B rimane attivo su quella connessione, ma se A vuole riprendere la conversazione dovrà stabilirne una nuova. Questo potrebbe dar adito a diverse ’incarnazioni’ della medesima connessione logica: se le due incarnazioni non sussistono contemporaneamente questo non è un dramma, mentre la sopravvivenza in rete di due (o più) incarnazioni distinte è un problema da non sottovalutare in quanto potrebbero gironzolare pacchetti aventi gli stessi indirizzi (IP + porta), gli stessi numeri di sequenza, ma contenuto diverso! Il TCP risolve questo problema (v. paragrafo 1.4) riallineando i numeri di sequenza e ristabilendo il parallelismo: uno dei due host, infatti, crederà che la connessione precedente sia ancora attiva e invierà all’altro dei numeri di sequenza palesemente sbagliati (cioè appartenenti al passato), cosicché la vecchia connessione verrà annullata con l’attivazione del bit RST.

1.2.2

Chiusura della connessione

Il TCP ce la mette tutta per garantire che, alla chiusura della connessione, non vengano persi dati. Anche questo aspetto, in realtà, non è così immediato da affrontare visto che la rete può risultare inaffidabile: il TCP però ci prova scegliendo una chiusura unidirezionale e indipendente delle due direzioni. L’host che intende terminare la trasmissione invia un segmento con il bit FIN a 1 e, ricevuto l’ACK, considera chiuso il dialogo. Se l’ACK non arriva, il mittente del FIN lascia comunque la connessione. Questa procedura ha il pregio di funzionare anche se i due host tentano contemporaneamente di chiudere la connessione: in tal caso, infatti, la chiusura avviene in maniera esattamente simmetrica da ambo le parti (vedi la macchina a stati finiti nel paragrafo 1.2).

1.3

Lo svolgimento del dialogo

Il protocollo TCP deve saper gestire problematiche non banali del tipo: • i ricevitori potrebbero avere caratteristiche fra loro diverse o essere addirittura delle macchine completamente diverse; • la rete non garantisce l’arrivo dei dati in sequenza; • i pacchetti potrebbero perdersi e non arrivare mai; • la congestione della rete potrebbe qualcosa di estremamente variabile e il ritardo di propagazione non essere mai costante; • possono esserci, in maniera aleatoria, aumenti/diminuzioni della banda dovuti all’arrivo di nuovi utenti (o alla scomparsa di altri); • etc. . . Per risolvere questi problemi, il TCP utilizza un protocollo a finestra scorrevole e utilizza quattro contatori: • RTO (retransmission time-out): vedi paragrafo 1.3.1; • persist timer: se un ACK (o, comunque, un messaggio di servizio) viene perso, può capitare che i due host comunicanti rimangano l’uno in attesa dell’altro: il ricevitore attende i nuovi dati, mentre il trasmettitore aspetta di ricevere la conferma (ACK) in grado di allargargli la finestra. Per prevenire questa forma di deadlock è necessario che il trasmettitore utilizzi un persist timer che interpelli il ricevitore in maniera periodica;

1.3. LO SVOLGIMENTO DEL DIALOGO

9

• keep-alive timer: non necessariamente, se è attiva una connessione fra due host, vi è un trasferimento di dati fra sorgente e destinazione; se tuttavia la connessione rimane dormiente per molto tempo, è probabile che uno dei due colloquianti si sia disattivato ed è opportuno eliminarla del tutto per liberare le risorse da essa occupate. Allo scadere del keep-alive timer, uno dei due host invia all’altro un messaggio di prova; se riceve risposta allora il timer viene resettato mentre, se tutto tace, vengono mandati altri 9 messaggi di prova con un intervallo pari a 75 secondi l’uno dall’altro. Presumibilmente, se anche questi 9 messaggi non ricevono risposta, l’altro calcolatore dev’essere ’caduto’ quindi la connessione viene interrotta; • time wait: al termine della chiusura della connessione, il client si ferma nello stato time wait per un tempo pari a 2MSL 2 , allo scadere del quale - se nulla è accaduto, lo stato della connessione passa a CLOSED. Questo timer vuole garantire l’estinzione di segmenti appartenenti a precedenti incarnazioni, onde evitare ambiguità con future riconnessioni fra le stesse porte degli stessi calcolatori (vedi paragrafo 1.2.1).

1.3.1

Retransmission Time-Out

Ogni volta che si trasmette un segmento viene fatto partire l’RTO: se il timer scade prima che sia stato ricevuto l’ACK si assume che il segmento non sia stato ricevuto. L’RTO dev’essere dimensionato in relazione al tempo di andata e di ritorno (Round Trip Time, RTT) ma, soprattutto, deve poter essere determinato in modo dinamico per meglio adattarsi alle condizioni sempre mutevoli della rete. L’RTT è infatti aleatorio e dipende dalla maggiore o minore congestione della rete; l’RTO invece è deterministico, nel senso che viene ricavato tramite formule matematiche all’interno delle quali, tuttavia, fa comparsa l’RTT medio in qualità di parametro. Per il calcolo si utilizzano tre variabili: • eRTT: stima del valore medio del RTT basato sulle misurazioni passate; • sRTT: misurazione del RTT relativo all’ultimo segmento confermato; • vRTT: stima della variabilità di RTT. Vediamoli ora più in dettaglio. Estimated Round Trip Time (eRTT) La prima misurazione della stima del RTT (parametro eRTT), all’istante n = 0, viene effettuata semplicemente traendo l’ultima misurazione3 eRTT (0) = sRTT (0) Quelle successive vengono invece determinate dando un certo peso (1 − α) alla stima dell’istante precedente (n − 1) e un altro peso (α) al valore ricavato dall’ultimo segmento confermato (istante n): eRTT (n) = (1 − α) · eRTT (n − 1) + α · sRTT (n) Il parametro α (valore suggerito: 1/8 = 0, 125) indica quanto peso viene dato al ’passato’ (cioè alla misurazione dell’istante n − 1: sRTT (n − 1)): tanto più è piccolo e tanto più faremo riferimento alle stime del passato piuttosto che alla misurazione (sRTT) corrente. Tale procedura di calcolo dell’eRTT viene detta Exponential Weighted Moving Average: Exponential perché il peso dei valori passati diminuisce in modo esponenziale a favore dei valori recenti4 ; Weighted perché il parametro α ci permette di fissare 2 MSL

= Maximum Segment Lifetime, noto a priori (nell’RFC 793 è fissato a 2 minuti). Perché bisogna aspettare 2MSL e non semplicemente MSL? Semplicemente perché adottiamo al filosofia del caso peggiore e vogliamo che si estinguano sia i pacchetti delle vecchie connessioni (vivono al massimo per un tempo pari a MSL) che le loro conferme (aspettiamo un altro MSL)! 3 In questo caso non abbiamo alternative per mancanza di informazioni, indi per cui la cosa più logica è quella di affidarsi alla misurazione fatta in quello stesso istante. 4 Si ha infatti eRTT (1) = (1 − α) · eRTT (0) + α · sRTT (1) eRTT (2) = (1 − α)2 · eRTT (0) + (1 − α) α · sRTT (1) + α · sRTT (2) eRTT (3) = (1 − α)3 · eRTT (0) + (1 − α)2 α · sRTT (1) + (1 − α) α · sRTT (2) + α · sRTT (3) ... n

eRTT (n) = (1 − α)n · eRTT (0) + ∑ (1 − α)n−i α · sRTT (i ) i =1

CAPITOLO 1. IL PROTOCOLLO TCP: GENERALITÀ

10

il peso dei campioni più recenti; Moving per la sua natura dinamica; Average per l’uso che fa di ’medie’ ponderate matematiche. Parametro vRTT Passiamo infine al parametro vRTT che, come abbiamo già detto, è una stima della variabilità del RTT. Il valore di vRTT all’istante 0 è canonicamente5 pari a vRTT (0) =

sRTT (0) 2

Per le successive misurazioni, invece, si segue la seguente regola: vRTT (n) = (1 − β) · vRTT (n − 1) + β |eRTT (n − 1) − sRTT (n)| Il parametro β è compreso tra 0 e 1 e ha valore consigliato pari a 1/4 = 0, 25: questo significa che viene dato più peso al passato rispetto che al presente. RFC 793 (1981) L’RTO viene calcolato come segue: RTO = min[UB, max[ LB, (γ · eRTT )]] = γ · eRTTSe non consideriamo i limiti. UB è il valore massimo ammissibile per RTO6 , mentre LB è il corrispondente valore minimo7 ; γ, invece, è un parametro compreso fra 1 e 2. Come è facile dedurre, l’RTO sarà compreso fra LB e UB; il calcolo dell’eRTT, infine, può eventualmente essere sovrastimato mediante il parametro β. RFC 2988 (2000): algoritmo di Jacobson Col passare del tempo si è scoperto che la convenzione imposta dall’RFC 793 era migliorabile; Jacobson ha quindi proposto di considerare anche le fluttuazioni della situazione (rappresentate dal parametro vRTT): RTO = max[ LB, eRTT + max[ G, 4 · vRTT ]] = eRTT + 4 · vRTTSe non consideriamo i limiti. LB è ancora il valore minimo ammissibile per l’RTO, mentre G è un’unità di misura del tempo presa come parametro. La relazione soprascritta indica che, se la linea è instabile e ballerina, è opportuno sovradimensionare l’RTO; in caso contrario, una buona stabilità della linea incoraggerebbe a mantenere l’RTO il più vicino possibile a eRTT (tendiamo a ’fidarci’ della linea). Per visualizzare meglio quanto detto si faccia riferimento alla figura 1.3. Linea stabile → RTO ≈ eRTT Linea instabile → RTO >> eRTT

Misurazione di sRTT Generalmente tale parametro si ricava come multiplo di intervalli di 500 ms; il TCP mantiene attiva una sola misurazione alla volta quindi, in caso di trasmissioni consecutive a breve distanza, solamente la prima valuta l’sRTT (figura 1.4). Un inconveniente comune (figura 1.5) è quello che potrebbe avvenire quando vi è ritrasmissione dei dati (in seguito alla perdita di un pacchetto o allo scadere dell’RTO): per questo motivo in caso di ritrasmissione l’sRTT non viene misurato e viene invece rilevato al successivo segmento senza ritrasmissione (algoritmo di Karn/Partridge). Come si nota, iterando la formula compaiono dei termini in cui il parametro α viene elevato ad una certa potenza. 5 Come per quanto riguarda l’eRTT, non possiamo fare alcuna stima della variabilità visto che siamo all’inizio della trasmissione e non abbiamo dati sufficienti; anche questa volta la scelta migliore è quella di affidarsi ad un valore standard. 6 1 minuto. 7 1 secondo.

1.3. LO SVOLGIMENTO DEL DIALOGO

Figura 1.3:

11

Evoluzione dell’RTO secondo i due RFC illustrati. Il risultato è migliore tanto più si è vicini alla linea rossa. Si noti che Jacobson ha dei grossi vantaggi quando la linea è stabile, mentre si tiene dalla parte del sicuro quando non lo è

Figura 1.4:

Misurazione dell’sRTT

Exponential back-off Una volta che avviene una ritrasmissione per mancanza di risposta, può aver senso dare un tempo maggiore al ricevitore di rispondere: per questo motivo, ad ogni ritrasmissione, il TCP raddoppia l’RTO fino al raggiungimento di un valore massimo.

CAPITOLO 1. IL PROTOCOLLO TCP: GENERALITÀ

12

Figura 1.5:

1.4

Ambiguità nel calcolo dell’sRTT

Lo stato enstablished

Per avere massima flessibilità si sceglie di assegnare un numero non ai segmenti bensì ai singoli byte trasportati dai segmenti: si comincia a numerare da un numero X scelto all’atto dell’apertura della connessione8 e la conferma di avvenuta ricezione viene data mettendo nel campo Ack number il numero del byte successivo all’ultimo ricevuto (cioè del primo byte che ci si aspetta di ricevere). Definito questo meccanismo, possono sopraggiungere diversi inconvenienti: • segmenti duplicati: un segmento con numero di sequenza X viene duplicato dalla rete; • segmenti ritardati: un segmento con numero di sequenza Y > X arriva prima del segmento X; • ambedue le cose: un segmento X viene duplicato e una delle due copie viene confermata, mentre l’altra arriva solo successivamente9 . In tal caso la trasmissione continua e, una volta che si è esaurito lo spazio di numerazione, vengono riciclati numeri già utilizzati10 : questo significa che prima o poi sarà generato un altro pacchetto avente numero di sequenza X (ma diverso da quello del giro precedente): se entrambi gireranno per la rete avremo due segmenti con stessa intestazione ma contenuto diverso! Il peggio che può capitare, in questo caso, è che la copia ritardata (quella del giro prima) arrivi prima dell’altra e venga interpretata come segmento valido. Osserviamo ora la figura 1.6: sulle ordinate compare il numero di sequenza, mentre sulle ascisse il tempo. Le rette nere spesse rappresentano l’andamento crescente del numero di sequenza col passare del tempo: la loro diversa pendenza dipende dalla velocità della connessione (più lo scambio di messaggi è rapido, più velocemente aumenta il SeqN e più pendente è la retta); il segmento orizzontale (MSL) si riferisce all’esistenza in vita di un pacchetto avente numero di sequenza pari a quello cui si era arrivati prima del crash della connessione C1. La connessione C2 riparte e, in entrambi i casi, finiamo per cadere nella trappola dei ’numeri doppi’: l’esempio ci mostra che questo può accedere sia se l’ISN (Initial Sequence Number) viene fissato a zero di default (a sinistra), sia se viene posto pari a un contatore11 (a destra). L’unico modo veramente sicuro in grado di farci evitare questo inconveniente è quello di attendere un MSL prima di aprire una nuova connessione TCP (TCP quiet time).

1.5

Messaggi di conferma (ACK)

Gli ACK, ovvero i messaggi di conferma, sono cumulativi e vengono portati ’a cavalluccio’ (piggybacking) di un normale messaggio TCP12 , che può normalmente contenere dati. La conferma, di default, è esplicita e quindi il ricevitore trasmette un ACK per ogni segmento ricevuto: può però essere conveniente 8 Questo numero è detto ISN (Initial Sequence Number) e dev’essere casuale, uguale per tutti nonché appositamente scelto affinché non vi sia duplicazione nell’uso dei numeri di sequenza. 9 Quello che stiamo per dire vale anche nel caso in cui un host venga riavviato a causa di un problema e rimanga attiva l’incarnazione di tale connessione. 10 Questo è inevitabile, ma dovremmo prima essere sicuri che in rete non esistano più vecchi segmenti numerati con tali numeri. Per questo si fissa un massimo tempo di vita dei segmenti (MSL, Maximum Segment Life), noto a priori: nel 1973 tale parametro veniva fissato a 2 minuti, ma con l’avvento di reti sempre più veloci si è reso necessario abbatterlo notevolmente. 11 In quest’ultimo caso ISN è funzione del tempo utilizzando un sistema di conteggio a 32 bit con incremento ogni 4 microsecondi. 12 Quel che fa testo è il bit ACK, che se è pari ad 1 ha significato di conferma.

1.6. IN SINTESI

13

Figura 1.6:

Duplicazione dei numeri di sequenza

ripensare questo meccanismo e scegliere di inviare ACK ritardati o cumulativi al fine di diminuirne il numero. Si potrebbe, ad esempio, inviare un ACK ogni due segmenti utilizzando il sistema della finestra scorrevole. Sia ora WT la finestra di trasmissione e WR la finestra di ricezione, con WT e WR minori dello spazio di numerazione del TPC (M = 232 ); se il ricevitore ha ricevuto fino a SeqN = N, allora si attenderà un segmento con SeqN = ( N + 1) mod M: se non riceve quello che si aspetta13 , bensì un segmento con SeqN > N o < N, allora il ricevitore interpreterà quello che gli arriva rispettivamente come un segmento fuori sequenza (numero di sequenza troppo alto) o come un duplicato ritardato (numero di sequenza appartenente ’al passato’). Nel primo caso il ricevitore memorizzerà il segmento, purché esso stia all’interno della sua finestra WR , ritrasmetterà l’ultima conferma inviata (ACK N + 1) e, una volta che avrà ricevuto tutta la sequenza completa (compreso il segmento N + 1), comunicherà direttamente ’ACK X + 1’ sbloccando la sua finestra; nell’altro caso scarterà il pacchetto considerandolo un doppione. Quanto detto fin’ora funziona purché il ricevitore sia dotato di memoria: chiaramente conviene memorizzare meno cose possibili quindi, finché non accade nulla di imprevisto, ogni pacchetto confermato in ordine corretto cancella il corrispondente segmento in memoria e fa scorrere la finestra.

1.6

In sintesi

Il TCP è un protocollo di strato 4, pensato per connessioni bidirezionali e point-to-point, in grado di svincolare gli strati superiori da tutti i problemi di rete e di garantire, grazie alla sua natura connection oriented, una conversazione adabile. In particolare, il TCP fa uso di un meccanismo a nestra scorrevole in grado di adattarsi alle condizioni di congestione della rete (v. capitolo 2), di rimediare alla perdita di pacchetti e di assicurare il corretto ordine della loro ricezione. L'unità di riferimento è il segmento (il 'pacchetto' cui ci riferiamo sempre), il quale contiene l'indirizzo sorgente e destinazione, un checksum per vericare la correttezza del contenuto, vari campi per le segnalazioni di servizio (ag-bits, etc. . . ) e inne i dati. Il funzionamento del protocollo TCP è illustrabile tramite lo schema di una macchina stati niti (v. gura 1.1) caratterizzato da due eventi principali: il TWH (three way handshake, v. par 1.2.1), che consiste in un triplice scambio di messaggi (Client: SYN, Server: SYN+ACK, Client: ACK) facente da preambolo per l'inizio della connessione, e la chiusura unidirezionale e indipendente delle due direzioni (Client: FIN, Server: ACK + eventuale trasmissione + FIN, Client: ACK). Il TWH, in particolare, è in grado di resistere all'apertura contemporanea di più connessioni nonché all'arrivo ravvicinato di due richieste di connessione (una delle quali è ritardata). Inoltre, il TCP ha un meccanismo - regolato da diversi timer - in grado di far fronte a inconvenienti come un deadlock dovuto alla perdita di un ACK (scade il persist timer), una connessione senza scambio di dati da troppo 13 Ad

esempio perché la rete ha perso o ritardato i pacchetti che doveva consegnare.

CAPITOLO 1. IL PROTOCOLLO TCP: GENERALITÀ

14

tempo (keep-alive timer), la presenza in rete di più incarnazioni di una stessa connessione logica (time wait), la perdita di un segmento (RTO, Retransmission Time Out). Un aspetto importante del TCP è il dimensionamento dell'RTO: esso viene calcolato mediante formule matematiche all'interno delle quali fa bella mostra la stima del RTT (Round Trip Time), cioè del tempo che intercorre tra l'invio di un pacchetto e la ricezione della sua conferma. Il parametro RTT è aleatorio, quindi dobbiamo appoggiarci al calcolo di una media ponderata mobile (Exponential Weighted Moving Average) per ottenerne un valore plausibile. Col passare del tempo sono state emanate diverse raccomandazioni (RFC), descriventi ognuna una particolare metodologia di calcolo dell'RTT; in gura 1.7 vengono illustrate la RFC 793 e la più nuova e performante RFC 2988: la prima è più rudimentale, in quanto fa uso dei soli parametri eRTT (stima dell'RTT ad un certo istante) e sRTT (misurazione del RTT), mentre la seconda è più ranata dato che tiene anche conto della variabilità delle condizioni della rete (parametro vRTT ).

Figura 1.7:

Schema riassuntivo del calcolo dell’RTT

Per il calcolo di sRTT serve una particolare cautela in quanto potrebbero esservi ambiguità dovute alla perdita di pacchetti (v. g. 1.5); inoltre, il TCP mantiene una misurazione dell'sRTT alla volta (v. g. 1.4). Inne, se per una certa trasmissione non si riceve risposta, l'RTO viene raddoppiato (Exponential back-o ). Il TCP impone che ogni segmento abbia un proprio numero di sequenza ed è in grado di gestire le situazioni in cui arriva un pacchetto fuori sequenza, duplicato oppure ritardato (o addirittura ritardato duplicato!). Il ricevitore che si aspetta il pacchetto X, ma che riceve Y 6= X, può reagire in diversi modi in base all'entità di Y e X: • Y > X : memorizza il pacchetto futuro14 (Y ) e continua a richiedere quello corrente (X ), in modo da poter saltare il pacchetto Y una volta ricevuti tutti quelli precedenti; • Y < X : il calcolatore scarta il doppione.

Un problema più sottile è quello riguardante segmenti con stesso numero di sequenza, stessa intestazione ma contenuto diverso: essi possono essere il frutto di un'anomalia dovuta al crash di uno dei due colloquianti e alla ripresa del dialogo con numeri di sequenza tali da indurre in rete la contemporanea sopravvivenza di pacchetti della vecchia e della nuova connessione con stesso SeqN . Questa eventualità può accadere sia che ad ogni connessione si scelga un ISN (Initial Sequence Number) sso a un valore di default, sia che tale parametro venga calibrato mediante un contatore (convenzione scelta del TCP). Per stare dalla parte del sicuro e non avere più dubbi il TCP sceglie, conseguentemente al vericarsi di un evento che ha interrotto il dialogo, di inibire qualsiasi ulteriore tentativo di connessione per un tempo pari a MSL (TCP quiet-time).

14 Se

esso sta nella sua finestra.

Capitolo 2

Il protocollo TCP: controllo del flusso 2.1

Generalità

La velocità del trasmettitore potrebbe, in generale, essere molto diversa da quella del ricevitore, ma non per questo uno dei due colloquianti ha licenza di saturare l’altro: per tal motivo si utilizza un meccanismo a finestra scorrevole. Il corretto dimensionamento della finestra deve tuttavia tenere conto - oltre che della velocità della rete - anche delle velocità d’elaborazione di trasmettitore e ricevitore, nonché della quantità di memoria posseduta da ciascuno di essi. Questo problema potrà sembrare anche banale, ma non lo è affatto: il trasmettitore, a priori, non sa proprio un bel niente sul ricevitore e l’aleatorietà della congestione in rete non aiuta a prendere delle decisioni senza uno straccio d’informazione. Per potersi conoscere, i due host devono quindi potersi comunicare l’un l’altro le dimensioni della memoria di ricezione: per questo motivo, nell’intestazione del pacchetto TCP, è contenuto il campo Advertised Window (AW).

2.2

Meccanismo a finestra scorrevole

La dimensione della finestra viene messa appunto dinamicamente: non ha infatti senso una finestra di dimensione fissa, dovendo noi obbligatoriamente adeguarci di volta in volta alle situazioni del momento. Per poter dimensionare la finestra, abbiamo bisogno di: • dati provenienti dal ricevitore (parametro AW); • dati sulla congestione della rete (parametro CW, Congestion Window, ricavati tramite una stima effettuata dal TCP.

Figura 2.1:

Il meccanismo a finestra fra segmenti ricevuti e segmenti non trasmessi.

La dimensione della finestra1 è pari al massimo tra AW e CW: W = max( AW, CW ) Mettiamo ora che un ipotetico trasmettitore sia molto più lento di un ricevitore, che quindi viene saturato: una volta che il buffer di ricezione si riempie, AW va a 0 e il trasmettitore blocca l’invio di dati. La ripresa della trasmissione avviene quando il processo ricevente legge dal buffer e spedisce un AW > 0. Questo meccanismo nasconde però un’insidia: se 1 La dimensione della finestra può essere data in byte o in segmenti: noi preferiremo generalmente questa seconda scelta, indicando con w la finestra in byte e W la finestra in segmenti. Si noti che si ha w = MSS · W, dove MSS è il Maximum Segment Size.

15

CAPITOLO 2. IL PROTOCOLLO TCP: CONTROLLO DEL FLUSSO

16

• il trasmittente invia messaggi fino alla ricezione di AW = 0 e, a quel punto, sospende l’invio, • il ricevitore non ha nulla da dire e quindi non trasmette nulla, allora la finestra non verrà mai sbloccata perché il ricevitore non riesce a spedire alcun messaggio con AW > 0. Siamo in pieno deadlock; per questo il TCP permette che sia sempre possibile inviare un segmento di 1 byte anche se AW = 0: dal momento che l’Advertised Window diventa pari a zero, infatti, parte il persist timer allo scadere del quale si invia un segmento di un byte (SeqN = X + 1, dove X è il numero di sequenza dell’ultimo pacchetto correttamente trasmesso) avente lo scopo di sbloccare la finestra. Se poi il ricevitore risponde con ACK = X + 2 e AW > 0, la trasmissione potrà continuare; in caso contrario, se cioè il buffer è invece ancora irrimediabilmente pieno, verrà spedito ACK = X + 1 e AW = 0, così che il persist timer, che questa volta avrà durata doppia (PT 0 = 2PT), ricomincerà a contare.

2.2.1

Silly Window Syndrome

Il meccanismo descritto nel paragrafo 2.2 va bene fino a un certo punto: se non arrivano altri ACK, la finestra avrà sempre dimensione 1 e la trasmissione sarà lentissima. Stesso risultato abbiamo se l’applicazione è lenta ad accettare i dati e legge un byte alla volta, comunicando una dimensione di finestra sempre troppo piccola. Quest’ultima evenienza prende il nome di silly window syndrome (abbreviato in SWS): • il buffer di ricezione è pieno (AW = 0); • l’applicazione (del ricevitore) legge un byte, libera altrettanto spazio dal buffer e trasmette AW = 1; • il trasmettitore riceve tale indicazione e, non potendo far altro, manda un solo byte; • il buffer di ricezione si riempie di nuovo e siamo daccapo. In questa spiacevole situazione inviamo un carattere alla volta e AW continua ad oscillare tra 0 e 1; fortunatamente anche quest’inconveniente è risolvibile, grazie all’algoritmo di Nagle (v. paragrafo 2.2.2).

2.2.2

Algoritmo di Nagle

Quando siamo in deadlock per colpa della SWS (paragrafo 2.2.1) bisogna trovare il modo di aumentare la dimensione del messaggio (dev’essere più grande di 1 byte, cioè di un ’tinygram’, come si dice in gergo): è infatti stupido inviare un datagrammetto con 90% header e 10% dati; ciò si può realizzare forzando il trasmettitore a inviare un nuovo segmento se e solo se è vera una delle seguenti condizioni2 : • il segmento ha dimensioni pari a MSS; • il segmento è di dimensioni pari almeno alla metà del valore di AW (se proprio non riesco ad inviarti tutto, ti invio almeno metà di quello che potresti); • non vi sono ACK pendenti ed è possibile trasmettere tutto ciò che è in attesa nel buffer di trasmissione. 2 Wikipedia

spiega lo stesso problema con altre parole e aiuta a fare chiarezza.

Nel caso in cui il processo di scrittura dei dati nel buer TCP del mittente sia molto lento, il protocollo spedirà una serie di pacchetti contenti una quantità di dati molto bassa, con un uso ineciente del canale (è infatti molto meglio spedire un solo pacchetto con n byte di dati, per il quale bisogna pagare il peso di un solo header, che spedire n pacchetti contenenti solo un byte di dati, per ognuno dei quali bisogna pagare il peso di un header, un rapporto di 1/n contro n/n = 1). La soluzione a questo problema consiste nel trattenere i dati nel buer allo scopo di spedirli in un unico segmento. Tuttavia un'attesa troppo lunga potrebbe causare dei ritardi troppo grandi nella trasmissione. Un'ottima soluzione a questo problema è fornita dall'algoritmo di Nagle, secondo il quale i dati devono essere accumulati nel buer per poi venire spediti in un unico blocco alla ricezione dell'ACK dell'ultimo pacchetto trasmesso o quando si raggiunge la massima dimensione ssata per un segmento (MSS). Questo semplicissimo algoritmo riesce a risolvere il problema tenendo anche conto della velocità di trasmissione dei pacchetti: se questa è più lenta della scrittura dei messaggi (il mittente riesce ad accumulare una notevole quantità di dati nel buer prima dell'arrivo del riscontro) vengono creati pacchetti con il massimo rapporto dati-header, sfruttando al meglio le risorse del canale. Se invece la rete è più veloce, i pacchetti risulteranno più piccoli, assicureranno una certa continuità nella trasmissione e verrà garantito comunque un utilizzo più eciente delle risorse del canale che nel caso in cui l'algoritmo non venga utilizzato.

2.3. CONTROLLO DI CONGESTIONE

17

L’effetto dell’algoritmo di Nagle è che si può avere un solo segmento pendente per il quale non si è ricevuto l’ACK; di conseguenza, più veloci arrivano gli ACK e più velocemente si trasmette. L’effetto collaterale, invece, è quello che si tende a ritardare i dati nel buffer di trasmissione e, per alcune applicazioni, questo potrebbe essere non accettabile: di conseguenza l’algoritmo di Nagle è disabilitabile.

2.3

Controllo di congestione

Come abbiamo avuto modo di vedere, W è limitato superiormente da AW e CW; rimane da chiarire come quest’ultimo parametro venga determinato. Ebbene, il TCP cerca di adattare la dimensione della finestra in funzione delle condizioni di congestione della rete, aumentandola quando si ricevono correttamente gli ACK e restringendola quando si verificano perdite: da qui l’esistenza del parametro CW. Avendo a disposizione una banda B (misurata in byte/s), il massimo throughput si ottiene quando il protocollo a finestra non limita la velocità di scambio dei dati, cioè quando nel famoso schema con le due aste verticali rappresentanti client e server non vi sono buchi e ogni momento diventa un istante valido per trasmettere dati nuovi. Se siamo in questo caso la finestra dev’essere più grande di: wid ≥ RTT · B → In byte wid Wid = → In segmenti MSS W w (byte/sec) = (segmenti/sec) Massimo throughput → S = RTT RTT In questo caso si utilizza il massimo della capacità disponibile; gli altri due casi, quelli cioè in cui la finestra è più piccola o più grande di wid , vanno peggio perché • se la finestra è più piccola parte della banda viene sprecata per l’attesa di arrivo delle conferme; • se la finestra è più grande il vero handicap viene dalla rete, che non è in grado di accettare per intero il flusso di dati nelle parti intermedie a velocità minore: in questo caso è infatti necessario accodare nei router intermedi, cosa che può generare perdite e ritardi.

Figura 2.2:

La questione delle capacità e l’adattività del controllo di flusso

Esaminiamo per esempio la figura 2.2; in essa si illustra come il flusso sia in grado di adattarsi alla capacità e alla banda della rete: se facciamo l’assunzione che vi siano parti di rete ad elevata capacità ed altre a banda più ristretta (rispettivamente rappresentate da tubi più larghi e più stretti), si nota come il tempo necessario a trasmettere pacchetti di dimensione fissata sia molto diverso da zona a zona. Il collo di bottiglia rappresentato dal primo tratto di linea avente banda (stretta) pari B ha l’effetto di rallentare la trasmissione complessiva di dati: giunti alla parte di rete (veloce) del ricevitore, infatti, i pacchetti sono fra

18

CAPITOLO 2. IL PROTOCOLLO TCP: CONTROLLO DEL FLUSSO

loro temporalmente molto più distanziati rispetto a quanto lo fossero in partenza. Il ritorno, immaginando che la situazione sia simmetrica rispetto all’andata, non ritarda ulteriormente i pacchetti essendo questi dei piccoli ACK inviati ad una frequenza ‘sfrondata’ dalla rete d’andata e quindi più che gestibili. Il protocollo a finestra, come abbiamo detto, permette al trasmettitore di inviare dati solo dal momento che riceve le necessarie conferme: se esse giungono con la frequenza indicata in figura, la successiva trasmissione farà sì che il trasmettitore già ‘ab ovo’ invii pacchetti ad una velocità accordata sulla base di quanto possa sopportare la rete. Tornando alla questione di partenza, come dimensioniamo CW considerando quanto detto e il fatto che la banda disponibile B può cambiare durante la connessione? A questo proposito, fatte le ipotesi che trasmettitore e ricevitore siano correttamente configurati, che non vi siano problemi di SWS (vedi paragrafo 2.2.1), che i buffer di trasmissione e ricezione siano abbastanza grandi e che AW >> CW (cosicché è CW a ‘comandare’ nel dimensionamento della finestra), sono definite due fasi che corrispondono a diverse dinamiche di CW: • slow start (SS): all’inizio della trasmissione W è3 ≤ 2 e, per ogni ACK ricevuto senza scadenza di RTO si effettua W = W+1 L’effetto netto è che, ad ogni tornata, la finestra raddoppia4 (v. figura 2.3). Lo SS termina quando

Figura 2.3:

Meccanismo di Slow Start

si verifica congestione (non ritorna un ACK in tempo) oppure quando superiamo la cosiddetta Slow Start Threshold (SSTHR)5 , che all’apertura della connessione è fissata ad un valore arbitrariamente alto ma che è anche in grado di cambiare dinamicamente durante la trasmissione dati. In SS si ipotizza che la situazione di rete, a finestra ancora relativamente piccola, sia abbastanza stazionaria; l’evoluzione di W, com’è facile intuire, avviene per tempi multipli di RTT (sono gli ACK a dettare il ritmo). La durata di tale fase dipende chiaramente dalla SSTHR ed è pari a: TSS = RTT · log2 SSTHR • congestion avoidance (CA): dopo la crescita esponenziale della fase di SS, con la congestion avoidance passiamo ad una crescita lineare onde evitare di esagerare e incappare nella perdita di pacchetti. La finestra w viene incrementata di un MSS per ogni RTT (o, se si preferisce, ogni RTT W aumenta di un segmento): ad ogni ACK, quindi, si ha W =W+

1 W

Quindi, ad esempio, se la finestra al ’passo’6 n è pari a 10 segmenti (W (n) = 10), avvenuta la trasmissione (e se tutto è andato bene) vengono ricevuti 10 ACK e la nuova finestra W (n + 1) diventa7 1 W (n) + 10 · = W (n) + 1. 10

2.4. ALCUNE DEFINIZIONI ED EVOLUZIONE DELLA CW

Figura 2.4:

2.4

19

Distinzione fra SS e CA

Alcune definizioni ed evoluzione della CW

Loss Window (LW): quando scade un RTO il trasmettitore ritiene perso un segmento, che quindi dev’essere ritrasmesso. Si pone quindi CW ≤ LW (tipicamente LW = 1). Flightsize: quantità di byte trasmessi ma non confermati (in parole povere è ciò che è in giro per la rete). Non è necessariamente uguale a W e dipende da dove si e arrivati nella trasmissione di una finestra. Dopo aver definito queste quantità, chiediamoci: cosa accade se durante la normale evoluzione della CW, fra slow start e congestion avoidance, scade il Retransmission Time Out8 ? In tal caso il protocollo reagisce ripartendo dalla SS (W = 1) e imponendo che la SSTHR diventi pari al flight-size/2 (o, se quest’ultima quantità è più piccola di due segmenti, a 2). Si noti che, grazie a questo meccanismo, la rete cerca di adattarsi allo stato della congestione pur mantenendo un atteggiamento gridy (avido): finché si può, infatti, il TCP cerca di allargare sempre più la sua finestra. Non c’è però pericolo che questo consegni l’intera rete in mano ad un unico host visto che tutti quanti condividono la stessa politica: infatti il meccanismo delle perdite ha lo scopo di inibire colui che sovraccarica il mezzo trasmissivo, ridimensionando la sua voracità; piuttosto, il risvolto positivo di 3 Quindi,

in byte, w ≤ 2MSS. è una slow start per modo di dire: in realtà la finestra cresce molto di più qui che in congestion avoidance. 5 Manterremo la convenzione di scrivere ssthr in byte e SSTHR in segmenti. 6 Non possiamo parlare di istanti perché gli ACK e le trasmissioni non avvengono tutte nello stesso momento, quindi approssimeremo il cosiddetto passo con un lasso di tempo poco più grande di RTT, quello - cioè - che permette ad un numero di segmenti pari a quello contenuto nella finestra di essere trasmessi e confermati. 7 In realtà, per essere più precisi, questa relazione dovrebbe essere scritta come approssimazione visto che l’incremento di W avviene ad ogni ACK e non solo alla fine della tornata (cioè ad ogni ’passo’ e l’altro, v. nota precedente). ESEMPIO: si ipotizzi W = CW = 4: vengono trasmessi 4 segmenti e, ricevuto il primo ACK risulta, 4 Quindi

W = (4 + 1)/4 = 4, 25 Ricevuto il secondo ACK abbiamo W = (4, 25 + 1)/4, 25 = 4, 49 Ricevuto il quarto ACK, ossia terminato il RTT dell’intera finestra (ovvero il passo di cui parlavamo prima) W = 4, 92 6= 5! Si noti quindi che non si ha esattamente W = W + 1 dopo la ricezione di tutti gli ACK della finestra. Di conseguenza, la crescita di W non è esattamente lineare, ma noi per semplicità la considereremo tale. 8 Tipicamente questo evento viene interpretato dal TCP come indice di congestionamento della rete visto che, con buona stima del RTT, il time out scaduto è praticamente sempre dovuto alla perdita del segmento.

CAPITOLO 2. IL PROTOCOLLO TCP: CONTROLLO DEL FLUSSO

20

Figura 2.5:

Un esempio d’evoluzione della finestra

quest’indole è quello di permettere ai colloquianti di occupare l’eventuale banda rilasciata da un calcolatore che ha abbandonato la conversazione: in questo modo, la banda è teoricamente sempre sfruttata al meglio.

2.5

Alcune approssimazioni

Sia TSS la durata della fase di slow-start e TCA quella della fase di congestion avoidance. Se la rete è abbastanza stabile si ha che: TSS << TCA Questo significa che passiamo molto più tempo in CA piuttosto che in SS e questo è un bene visto che, in ultima analisi, la quantità di dati trasmessi è pari all’integrale della curva presente nel grafico finestra/tempo e, chiaramente, l’area che si trova sotto la curva che evolve in CA è maggiore di quella sotto la curva in zona di SS. Se l’ipotesi TSS << TCA è vera, allora possiamo trascurare la fase di SS e immaginare un andamento perennemente in CA, come in figura 2.6.

Figura 2.6:

Effetto dell’approssimazione TSS << TCA

2.5. ALCUNE APPROSSIMAZIONI

21

L’andamento della finestra in Congestion Avoidance oscilla fra incremento additivo e decremento moltiplicativo: se r è la quantità di dati inviata dal trasmettitore • additive-increase: la finestra cresce in maniera additiva. Al passo i-esimo si ha: r ( t i +1 ) = r ( t i ) + c

con c << rmax

• multiplicative-decrease: la finestra decresce in maniera moltiplicativa. Se si ha una situazione di congestione al passo i-esimo si ha: r ( t i +1 ) = a · r ( t i )

con a < 1

Perché tutte queste definizioni? Il punto cui vogliamo arrivare è dimostrare che il TCP permette un’equa distribuzione della banda disponibile: questo significa che se un certo numero di colloquianti (noi per semplicità ne considereremo due) condividono una certa banda, a regime finiranno per avere più o meno tutti la stessa porzione di essa.

2.5.1

Un esempio

Figura 2.7:

Condivisione della risorsa

Si faccia riferimento alla figura 2.7: abbiamo due connessioni che si ritrovano a condividere la stessa banda. Siccome entrambi i calcolatori (r1 e r2 sul grafico: gli assi rappresentano la banda destinata a ciascuno di essi) adottano il tanto decantato approccio gridy, tenteranno di accaparrarsi quante più risorse possibili. Così facendo arriverà inevitabilmente il momento in cui si dovrà sbattere il muso contro l’impossibilità di congestionare troppo la rete: prendiamo per esempio r2 che, per ipotesi, parte con un maggior sfruttamento della banda. Dopo un appagante incremento additivo, la freccia verde si scontra contro il limite (linea scura) e si ha in decremento moltiplicativo (freccia rossa). Il giro successivo, r2 non potrà occupare così tanta banda come l’ultima volta perché, nel frattempo r1 gli avrà rosicchiato un po’ di risorse da sotto i piedi. Nonostante questo, r2 ha un incremento additivo che lo riporta (quasi) ai livelli di un tempo; anche stavolta, tuttavia, scatta un RTO a causa della troppa avidità del nostro host e così si ha un’ulteriore freccia rossa corrispondente a un decremento moltiplicativo. Questa tendenza continua fino a quando la freccia rossa e la freccia verde hanno la stessa pendenza, pari tra l’altro alla bisettrice del nostro quadrante: giunti lì, a meno di inconvenienti particolari, i due host avranno decrementi ed incrementi simili e ciò porterà ad avere, a regime, una sostanziale equipartizione della banda (il punto di

CAPITOLO 2. IL PROTOCOLLO TCP: CONTROLLO DEL FLUSSO

22

intersezione fra la bisettrice e la retta ad essa perpendicolare è quello di massimo equilibrio fra le risorse destinate ai due calcolatori). Si noti che tutto questo è reso possibile dall’atteggiamento gridy, avido e assetato di banda, imposto dal TCP: se così non fosse non riusciremmo ad avere uno sfruttamento così intenso e sistematico della capacità del nostro canale. Inoltre, se uno dei due host dovesse andarsene, quello rimanente non approfitterebbe subito della banda liberatasi e l’efficienza sarebbe piuttosto scarsa.

2.6

Altri aspetti del protocollo: algoritmi migliorativi

Una cosa che è importante sottolineare è che la politica dei delayed ACK (non inviare gli ACK sempre, ma ogni K > 1 corrette ricezioni) può portare a degli squilibri. Se prendiamo in considerazione l’esempio nel paragrafo 2.5.1 e facciamo l’ipotesi che uno dei due colloquianti invii un ACK ogni quattro segmenti invece che ad ogni singolo datagramma, allora quest’ultimo calcolatore sarà indiscutibilmente danneggiato perché, al contrario dell’altro contendente, non riuscirà a raggranellare banda al suo stesso ritmo. Preme inoltre sottolineare che l’incremento di CW è funzione del round-trip time; due connessioni che sperimentano diversi RTT aumentano in modo diverso le proprie finestre e si tende a favorire connessioni con RTT brevi su connessioni con RTT lunghi. Quando poi un segmento viene perso, il ricevitore riceve uno o più segmenti fuori sequenza: se ciò avviene, il protocollo TCP (quello nudo e crudo, senza gli algoritmi che vedremo fra poco) è costretto ad inviare un ACK duplicato9 per ogni segmento fuori ordine. La generazione di ACK duplicati dovuti alla perdita di un segmento è un evento che può essere utilizzato come indicazione di congestione unitamente al time-out. Sono quindi stati proposti ulteriori algoritmi per sfruttare al meglio questa situazione: di questi noi tratteremo il fast recovery (paragrafo 2.6.1) e il fast retransmit (paragrafo 2.6.2).

2.6.1

Fast recovery

Questo algoritmo entra in funzione quando avviene il caso di triple duplicate ACK (tre ACK duplicati): se il trasmettitore riceve infatti 4 ACK con uguale acknowledge number allora si ritrasmette il segmento avente come numero di sequenza quello indicato dall’ackN duplicato. E poi che si fa? Si potrebbe ripartire dall’inizio della slow start, ma quella di far ricrollare la finestra allo stadio embrionale non è una scelta furbissima: il fatto che il ricevitore ci stia rispondendo, infatti, è sintomo che i pacchetti stanno effettivamente giungendo a destinazione e che quindi vi è abbastanza reattività da parte della rete (e non vi è perciò una situazione esageratamente congestionata). Inoltre, potrà pure capitare che ogni tanto si perde qualche pacchetto!10 Considerando quindi il triplo ACK duplicato come evento ’meno grave’ di un RTO effettivamente scaduto, si preferisce agire ritrasmettendo il solo segmento mancante e continuando la fase di congestion avoidance. Ecco i passi dell’algoritmo (per visionare alcuni esempi si faccia riferimento alle figure 2.8 e 2.9: • si riduce la soglia di CW a SSTHR = max( Flightsize/2, 2) o, se si preferisce questa quantità in byte, a ssthr = max( Flightsize/2, 2MSS): questo passo serve per riadattarci alle condizioni di carico della rete; • si gonfia (provvisoriamente) la finestra W (window inflation) aumentandone istantaneamente la dimensione di tre pacchetti: W = SSTHR + 3 (o, come al solito, w = ssthr + 3MSS in byte). Così facendo si tiene conto del fatto che almeno 3 segmenti successivi al mancante sono stati ricevuti in quando sono partiti gli ACK duplicati; • si continua la trasmissione e, se la dimensione di W lo permette, si trasmettono ulteriori segmenti; • ad ogni ulteriore ACK duplicato ricevuto si pone W = W + 1; • quando arriva l’ACK per il pacchetto perduto finisce la fase di FR e si riparte con congestion avoidance ponendo W = SSTHR (la finestra viene sgonfiata). 9 Che

si riferisce all’ultimo segmento ricevuto correttamente.

10 Suvvia!

2.6. ALTRI ASPETTI DEL PROTOCOLLO: ALGORITMI MIGLIORATIVI

Figura 2.8:

Figura 2.9:

23

L’algoritmo di fast recovery

L’algoritmo di fast recovery (2)

Il TCP standard, messo di fronte a un’eventualità come quella illustrata nell’esempio in figura 2.8, sarebbe impazzito, in quanto avremmo dovuto per forza attendere lo scadere dei time out prima di ripartire. Anche solo due pacchetti persi in breve tempo avrebbero infatti creato una situazione di stallo e avrebbero fatto ripartire il tutto dalla slow start, con un conseguente crollo della finestra. Non è però tutto

CAPITOLO 2. IL PROTOCOLLO TCP: CONTROLLO DEL FLUSSO

24

oro quel che luccica: a volte, infatti, il fast recovery può addirittura essere dannoso e peggiorativo!

2.6.2 Fast retransmit Il fast retransmit (una specie di fast recovery semplificato11 ), consiste nel dimezzare la finestra e spedire immediatamente, senza aspettare l’RTO come invece accadrebbe nel TCP classico, il pacchetto del quale si è ricevuta la richiesta duplicata (tripla, come da programma). Consideriamo infatti la seguente casistica: • 12 segmenti ricevuti, riconosciuti e confermati; • segmenti 13 e 16 perduti. In figura 2.10 si mostra come il TCP standard (SS+CA) e il TCP ’Tahoe’12 (SS+CA+Fast Retransmit) avrebbero agito e si nota chiaramente come quest’ultimo sia più efficiente.

Figura 2.10:

Il TCP classico e il Tahoe (cioè TCP + Fast Rec.) a confronto

Qual è il problema del Tahoe? Ebbene, il vantaggio ottenuto è molto piccolo (se non nullo) perché il dimezzamento della finestra blocca la trasmissione a causa delle perdite multiple. 11 O magari è il fast recovery ad essere una versione più evoluta del fast retransmit: la sostanza però è quella. Mediamente il fast recovery funziona meglio, ma in alcuni casi potrebbe non essere così, quindi ha senso vedere questi due algoritmi separatamente. 12 Da Wikipedia:

TCP Tahoe prevede che ogni qual volta si verichi un evento perdita di qualsiasi tipo, la nestra di congestione venga dimezzata e il nuovo valore memorizzato in una variabile soglia. Fatto questo la trasmissione dei dati ricomincia impostando il valore iniziale della nestra di congestione corrente pari a MSS (massima dimensione di un segmento TCP). Si ha quindi una 'ripartenza lenta', la crescita avverrà lentamente ma in maniera esponenziale no a raggiungere il valore di soglia prima determinato [è la SS]. Oltre questo valore la crescita avviene linearmente [CA] no a quando non si verica nuovamente un evento perdita e l'algoritmo viene rieseguito. La crescita esponenziale no al livello di soglia avviene poiché si ritiene che all'inizio di ogni trasferimento il canale trasmissivo sia più libero, e quindi si cerca di inviare all'inizio i pacchetti più grossi. Una volta raggiunto il livello di soglia, la crescita avviene lentamente per cercare di raggiungere il livello di congestione il più lentamente possibile.

2.6. ALTRI ASPETTI DEL PROTOCOLLO: ALGORITMI MIGLIORATIVI

2.6.3

25

Reno e New Reno

Nel caso illustrato nel paragrafo 2.6.1 il cosiddetto TCP ’Reno’13 (SS+CA+Fast Recovery) non sarebbe andato molto meglio (v. figura 2.11). Il ’New Reno’14 , invece, avrebbe avuto delle performance migliori (si faccia nuovamente riferimento alla figura 2.11).

Figura 2.11:

I protocolli TCP Reno e TCP New Reno a confronto

Come si osserva facilmente, il TCP Reno si infogna subito (segmenti pendenti 5, W = 5 → non si può trasmettere altro finché non riceviamo ACK 13: dopodiché si esce dal fast recovery e si riparte con finestra 2: il trasmettitore è nuovamente bloccato ed è costretto ad attendere l’RTO di 16, allo scadere del quale si ritrasmette con finestra a 1. . . Oltre al danno pure la beffa!): terminare il fast recovery troppo presto (cioè ad ackN=15) è infatti prematuro. Il New Reno fa tesoro di questa esperienza e reagisce meglio, mantenendo la finestra gonfiata per un po’ più di tempo, quel che basta per scavalcare i pacchetti corretti successivi a quello sbagliato e poter riprendere la numerazione in santa pace, senza aspettare lo scadere degli RTO. La fase di recupero inizia all’istante (che chiameremo T0 ) di ricezione del quarto duplicato: giunti lì memorizziamo infatti seqN(T0 ) 13 Ancora

una volta Wikipedia ci aiuta con una sua spiegazione:

TCP Reno [...] in caso di perdita dovuta al timeout del timer, applica l'algoritmo di Tahoe, poiché si assume che la rete sia

talmente congestionata da non essere in grado di far passare nessun altro pacchetto e che quindi sia meglio far ripartire la trasmissione impostando la nestra corrente al valore minimo di 1 MSS. Quando invece l'evento perdita è generato dalla ricezione di 3 ACK duplicati, il TCP Reno assume che la rete sia ancora in grado di trasferire qualcosa. Il valore soglia viene impostato alla metà del valore della nestra di congestione al momento della ricezione di tre ACK duplicati e la trasmissione riparte impostando il valore di nestra corrente pari al valore di soglia e proseguendo nell'invio incrementando di MSS, ad ogni RTT, il valore della nestra di congestione. 14 La

solita Wikipedia:

Il TCP Reno risolve in parte il problema di perdite non dovute a congestione solo quando le perdite non sono fortemente correlate tra loro, cioè quando si perde al massimo un pacchetto all'interno di ogni nestra. Questo comportamento è problematico nelle situazioni in cui si perdono interi burst di pacchetti (situazione frequente ad esempio nei collegamenti wireless). TCP New Reno cerca di aggirare il problema basandosi sul sistema degli ACK parziali. Vengono considerati ACK parziali gli ACK che riscontrano pacchetti intermedi, e non gli ultimi pacchetti che necessiterebbero riscontro, dopo che è stata già iniziata la fase di Fast Retransmit in seguito all'arrivo di tre ACK duplicati. Quando uno di questi ACK si presenta durante una fase di Fast Retransmit (cioè in seguito alla ricezione di 3 ACK duplicati), TCP New Reno si mantiene in Fast Retransmit continuando a inviare i pacchetti via via richiesti nché non viene riscontrato l'ultimo pacchetto inviato.

CAPITOLO 2. IL PROTOCOLLO TCP: CONTROLLO DEL FLUSSO

26

= 17. Questo numero indica infatti il seqN dell’ultimo pacchetto che si presume sia stato correttamente ricevuto dal ricevitore: dopo la ripetizione dei 3 pacchetti aventi seqN = 13 esso rappresenterà quindi la prima informazione ’buona’ disponibile dopo i 3 duplicati. Il numero memorizzato è quindi utile perché, proprio per i motivi poco fa indicati, l’algoritmo prevede che si esca dalla fase di Fast Recovery quando si riceve ackN > seqN(T0 ). Se dopo la spedizione del segmento perduto (il 13simo) tutta la finestra è stata ricevuta correttamente allora arriverà ackN = 18 (si esce dal Fast Recovery) mentre, se sono stati perduti altri segmenti della finestra, ackN < 18 (ACK parziale, che re-inizializza RTO).

2.7

In sintesi

Per poter comunicare in maniera eciente, due host devono avere almeno una vaga idea della rispettiva velocità di elaborazione, della rapidità con la quale le proprie applicazioni riescono ad 'assorbire i dati' e un indice di congestione della rete; esistono, a questo proposito, due importanti parametri che vengono continuamente scambiati durante la conversazione: CW , dimensionato in base alla congestione della rete, e AW , che riguarda la velocità del ricevitore. La dimensione della nestra W di conversazione è sempre pari al massimo fra AW e CW . Combinando le informazioni sul congestionamento della rete e sulla capacità dei comunicanti, il TCP riesce ad uniformare la velocità di trasmissione dei dati, accordando il ritmo d'invio dei messaggi fra spezzoni di rete a velocità disomogenea, quand'anche la banda e la capacità del collegamento variassero in maniera molto dinamica e disomogenea nel tempo. Esistono tuttavia alcune situazioni pericolose assolutamente da evitare: • il trasmettitore invia messaggi, ma riceve AW = 0 e nulla più → il trasmettitore è bloccato (deadlock).

SOLUZIONE: il TCP permette sempre l'invio, allo scadere del persist timer, di un segmento piccino picciò (1 byte) anche se AW = 0. Se, fatto questo, il buer risultasse essere ancora pieno, il persist timer viene raddoppiato;

• se l'applicazione del ricevitore (o del trasmettitore) è lenta a processare i pacchetti e legge (o scrive) una

misera manciata di byte alla volta (caso peggiore: un solo byte alla volta), il buer si svuoterà molto lentamente e verranno inviati pacchetti con AW = 1 (sempre nel caso peggiore). Colui che sta all'altro capo della trasmissione non potrà fare altro che inviare un solo byte, con la conseguenza che il buer di ricezione si riempirà di nuovo e saremo daccapo. Questo è il caso della SWS (Silly Window Syndrome) e porta alla trasmissione di pacchetti costituiti per la stragrande maggioranza di informazioni di servizio (header) e da pochissimi dati. SOLUZIONE: algoritmo di Nagle → si permette l'invio di dati solo se (1) il segmento ha dimensioni pari a MSS, (2) il segmento è di dimensioni pari almeno alla metà del valore di AW , (3) non vi sono ACK pendenti. Il risvolto negativo sta nel fatto che la trasmissione perde reattività: per questo l'Algoritmo di Nagle è disabilitabile.

Il TCP cerca di adattare il parametro CW in base alla percezione che ha sulla congestione della rete, incrementandolo quando si ricevono gli ACK e ridimensionandolo quando si vericano perdite. Trascurando per un attimo il problema della SWS, immaginando che AW  CW e che i calcolatori comunicanti abbiano sempre qualcosa da trasmettere e supponendo inne (per semplicità) che l'aggiornamento di CW avvenga al termine di ogni nestra (cioè al termine di ogni RTT), il tipico andamento del parametro CW si destreggia fra due dierenti fasi: • SS (Slow Start → crescita della nestra: esponenziale): in questa fase la nestra raddoppia ad ogni RTT15 , dato che per ogni ACK ricevuto si ha W = CW = W + 1. La SS dura nché CW non raggiunge la SSTHR (Slow Start THReshold) e quindi possiamo supporre che permanga per log2 SSTHR round trip times; • CC (Congestion Avoidance → crescita della nestra: (sub)lineare): in questa fase si cerca di non esagerare 1 con l'incremento della nestra, onde evitare di saturare il collegamento; la crescita è infatti di W = W + W

ad ogni ACK ricevuto (e di circa un segmento per ogni RTT16 )

Se a questo punto scade l'RTO, il TCP reagisce ripartendo dalla SS (W = 1) e imponendo che la SSTHR diventi pari al ight-size/2 (o, se quest'ultima quantità è più piccola di due segmenti, a 2). 15 L’aggettivo slow è fortemente fuorviante: esso si riferisce alla dimensione di W, inferiore a quella che si ha in CA, e non al suo ritmo di crescita, che invece è molto sostenuto. 16 In realtà la crescita è sublineare, v. par. 2.3.

2.7. IN SINTESI

27

A questo punto appare chiaro come la caratteristica fondante del protocollo sia la sua avidità (protocollo gridy: l'unico evento che fa calare CW è la perdita di un pacchetto, mentre di norma questo parametro viene solo incrementato): grazie alla richiesta sempre maggiore di banda da parte di tutti coloro che sono in rete, l'eventuale capacità liberatasi in seguito all'abbandono della conversazione da parte di qualcuno viene immediatamente sfruttata. Altra conseguenza di questo protocollo è quella di permettere un'equa condivisione della banda (v. par. 2.5) a regime. La pura alternanza di SS e CW non risulta essere un algoritmo sucientemente ecace (è anzi troppo severo: far crollare la nestra a 1 è una punizione eccessiva se la linea non è inverosimilmente congestionata). Per questo esistono diverse versioni in grado di migliorare questa dinamica: tutte quante scattano al triplo ACK duplicato (triple duplicated ACK e sono • fast retransmit: si ridimensiona immediatamente la SSTHR (la si pone a

ightsize

) nonché la nestra17 e si spedisce immediatamente, senza attendere lo scadere dell'RTO, il pacchetto del quale si è ricevuta la richiesta duplicata; 2

• fast recovery: come il fast retransmit, solo che no a quando non arriva la conferma del pacchetto perso si gona la nestra e la si fa diventare pari a W = SSTHR + 3, +1 per ogni eventuale altro ACK duplicato. Dopodiché la nestra viene posta pari a SSTHR e si ricomincia in CA; • Reno: comprende fast retransmit + fast recovery; • New Reno: è come il Reno solo che la fase di FR/FR dura no a quando non si riceve un ACK avente

numero di sequenza superiore a quello dell'ultimo pacchetto inviato correttamente prima dello scattare dell'algoritmo18 . Il gonamento della nestra avviene secondo la regola: W = SSTHR + 3 +1 per ogni eventuale altro ACK duplicato, −1 per ogni ACK ricevuto correttamente. L'uscita dall'algoritmo va come nel Reno.

17 È

sempre valida l’ipotesi che AW  CW quindi W = CW. cioè, il cui numero di sequenza è stato salvato nella variabile recover quando sono arrivati i tre ACK duplicati

18 Quello,

28

CAPITOLO 2. IL PROTOCOLLO TCP: CONTROLLO DEL FLUSSO

Capitolo 3

Modelli analitici per le prestazioni del TCP 3.1

Ricerca di modelli matematici

Le prestazioni del protocollo TCP vengono influenzate fondamentalmente dalla dinamica della finestra di trasmissione W (che viene regolata dal controllo di congestione e dal protocollo ARQ) nonché dai processi di ritardo e perdita di segmenti in rete (vedi capitolo ??). Un modello analitico del TCP deve descrivere questi processi fondamentali e, nello stesso tempo, riuscire a valutare le prestazioni del protocollo. Sembra una cosa banale, ma in realtà esistono diverse questioni delicate da affrontare, in quanto: • gli eventi consistenti nella perdita di pacchetti sono aleatori (e non deterministici); • la rete ha una natura dinamica ed è impossibile racchiudere in un solo modello tutte le possibili eventualità che si potrebbero presentare; • è difficile tenere conto di tutta l’infrastruttura che si trova tra ricevitore e trasmettitore: tra i due colloquianti, infatti, si trovano vari router - non necessariamente uguali - con code di lunghezza diversa e prestazioni differenti; • se siamo in congestion avoidance l’andamento della finestra è approssimativamente lineare e le cose vanno bene; se vogliamo considerare anche la slow start nonché le dinamiche dei protocolli più evoluti (Tahoe, Reno, New Reno, etc. . . ), allora il problema si complica notevolmente; • il RTT non è in generale un parametro costante; • non valutiamo la possibilità che la banda venga occupata, durante il periodo che ci interessa, da altri calcolatori; • etc. . . Per questi ed altri motivi, di seguito studieremo alcune situazioni notevoli adeguatamente semplificate.

3.2

Throughput e goodput

Il throughput di una connessione TCP è la quantità totale di informazioni trasmesse nell’unità di tempo. Il goodput, invece, è la quantità di informazioni trasmesse con successo nell’unità di tempo (senza contare quindi i segmenti trasmessi con errore o duplicati). Intuitivamente, si ha che: throughput ≥ goodput Nei modelli TCP più comuni il tempo è logicamente diviso in unità di dimensione RTT: supporremo che in RTT venga trasmessa un’intera finestra e che, al termine di tale periodo, giungano tutte le conferme di 29

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

30

ricezione1 . Fatte queste ipotesi il throughput è semplicemente il numero di segmenti trasmessi per RTT: S(t) =

w(t) · MSS W (t) = RTT RTT

Di seguito supporremo che il trasmettitore abbia infiniti dati da trasmettere (e che spedisca sempre segmenti di dimensioni pari a MSS), che i buffer di trasmissione e ricezione non limitino il comportamento del TCP (lo stato delle code nei router rimane approssimativamente costante e non si modifica in modo significativo durante il periodo d’analisi) e - infine - che si lavori perennemente in congestion avoidance.

3.3

Modello periodico

Si tratta del modello più semplice: esso assume che • si lavori in una situazione di equilibrio, con il TCP in congestion avoidance: questo comporta inoltre che, ad ogni perdita, la finestra si dimezzi (invece che ripartire da 1); • si riceva un ACK per ogni segmento correttamente trasmesso; • gli eventi di perdita siano periodici, in percentuale di p. Fatte queste ipotesi, la finestra ha in funzione del tempo un andamento periodico a dente di sega (v. figura 3.1).

Figura 3.1:

Modello periodico

Supponendo che ad ogni finestra (batch) vengano trasmessi W segmenti, lo stato di congestion avoidance fa sì che, al termine di essa, si riceva l’ACK che fa scattare W = W + 1. Se non si riceve l’ACK, invece, la finestra viene dimezzata per effetto della congestione (vedi figura 3.2).

Figura 3.2:

Modello periodico (2)

Sia ora N il numero di segmenti trasmessi in T (periodo che intercorre tra una perdita e l’altra). Se assumiamo che la perdita avvenga periodicamente allora possiamo dire che, se ad esempio la perdita è di 1 A noi fa comodo pensare che le cose vadano così: in realtà i pacchetti non arrivano tutti contemporaneamente e, di conseguenza, la finestra si aggiorna non soltanto ad ogni RTT. Anche questa, pertanto, è un’approssimazione.

3.3. MODELLO PERIODICO

31

1 segmento su 100, all’interno di T avremo spedito 100 segmenti: N=

1 p

Possiamo però dare un’espressione di N anche in funzione della finestra2 :    W W W −1 −1 2 W W2 W2 W2 3W 2 2 2 N= ∑ ≈ +i = + + = 2 4 2 4 8 8 i =0 {z } | serie del ’piccolo Gauss’

Per capire a fondo questa espressione si tenga presente che la sommatoria ha quegli estremi visto che la finestra, per ogni dente di sega, varia da W/2 a W (per un delta complessivo che va da 0 a W/2) e che il +i indica la crescita pari ad 1 della finestra per ogni RTT. Uguagliando le due espressioni di N si ottiene facilmente: s 8 W= 3p Il throughput si calcola come rapporto fra: • numero di pacchetti trasmessi = 1/p; • tempo totale di trasmissione =

W RTT. 2

Ed è quindi pari a: s    r 1 p 2 p 1 2 p 3p 3 1 S ( p) = = = = W RTT W RTT 8 RTT 2p RTT 2

3.3.1

ACK ritardati

Facciamo ora l’ipotesi aggiuntiva che il ricevitore spedisca un ACK ogni b segmenti e non ogni segmento. In tal caso, se trasmettiamo una finestra W riceveremo non più W ACK, ma W/b ACK: questo farà sì che • W = W + 1/b; • W = W + 1 solo dopo b finestre trasmesse. Il periodo T che intercorre tra una perdita e l’altra sarà quindi pari a: T=

Wb RTT 2

Si noti che questo tempo è b volte quello esaminato nel caso di ACK non ritardati. Possiamo quindi fare calcoli analoghi a quelli già visti nel paragrafo 3.3: il parametro N (segmenti spediti all’interno del dente di sega) è pari a    bW bW W −1 − 1 2 W i bW 2 bW 2 bW 2 3bW 2 2 2 N= ∑ + = + ≈ + = 2 b 4 2 4 8 8 i =0 | {z } Ancora il piccolo Gauss

Quindi, uguagliando nuovamente questa relazione con N= 2 Con

1 p

la ’serie del piccolo Gauss’ (cit. Seccia) intendiamo: k

∑k=

i =0

k ( k + 1) 2

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

32 si ha:

s W=

8 3bp

E quindi il throughput sarà: s    r 1 p 2 p 1 2 p 3pb 3 1 S ( p) = = = = W RTT bW b · RTT 8 RTT 2pb RTT b 2

3.4

Perdite aleatorie

Figura 3.3:

Andamento della finestra con perdite aleatorie

Se complichiamo leggermente il modello, rimuovendo l’ipotesi che le perdite siano periodiche e aggiungendo quella che siano aleatorie, allora già le cose si fanno più complicate! Supponiamo che la trasmissione avvenga ancora a batch (uno per RTT e di dimensioni pari alla finestra W) e che gli ACK siano ritardati (uno ogni b pacchetti). Sia inoltre la probabilità di perdita indipendente da segmento a segmento e da batch a batch. In questo caso, com’è prevedibile, l’andamento a dente di sega non sussiste più (v. figura 3.3). Facciamo inoltre l’ipotesi che siano due gli eventi a determinare la contrazione di CW (t): • il triple duplicate ACK (TD): in tal caso il protocollo reagisce con un fast retransmit (trascureremo il fast recovery); • la scadenza di un timeout (TO): in questo caso dimezziamo la finestra (senza ripartire dalla slow start). Per ora immagineremo che AW sia abbastanza elevata da essere CW a spuntarla sempre sul controllo della finestra (poi rimuoveremo questa ipotesi).

3.4.1

Modello TD

Sia Yi la variabile aleatoria che indica quanti pacchetti sono stati inviati all’interno di un periodo in cui non vi sono stati errori3 : anche quest’ultimo lasso di tempo è una variabile aleatoria che indicheremo con Ai e che, chiaramente, sarà pari al numero di RTT che intercorrono tra l’inizio del ’dente’ del grafico e l’istante in cui si verifica la perdita (vedi figura 3.4). Sia poi αi il numero del pacchetto4 che provoca la perdita e p la probabilità che avvenga una perdita; infine, sia Wi il valore della finestra nel momento in cui è avvenuta la perdita e β i la metà di Wi 5 . Si noti che le variabili Yi , Ai , Wi αi e β i sono tutte aleatorie e tutte riferite all’analisi del dente di sega i. La variabile aleatoria Yi (numero dell’ultimo pacchetto spedito nella tornata6 i) sarà chiaramente pari a Yi = αi + Wi − 1 3 Cioè

all’interno del dente di sega. numero relativo al dente di sega i, non il suo numero assoluto! 5 Abbiamo fatto l’ipotesi di mantenerci sempre in congestion avoidance e di ignorare lo SS. 6 La tornata comprende anche i β pacchetti spediti nel mentre la finestra si dimezzava. 4 Un

3.4. PERDITE ALEATORIE

33

Figura 3.4:

Le variabili Yi e Ai

cioè al numero relativo del primo pacchetto errato più il valore che la finestra aveva quand’è avvenuto l’errore, meno 1 (che ci fa beccare l’ultimo bit giusto). Applicando l’operatore di valor medio, che è lineare, si ha: E[Yi ] = E[αi ] + E[Wi ] − 1 La probabilità che αi sia pari a un certo numero k è modellabile ipotizzando che i k − 1 pacchetti precedenti siano stati correttamente ricevuti (probabilità 1 − p) mentre il k-simo sia stato ’scagliato’: Pr{ a = k } = (1 − p)k−1 p Il valore medio di α è chiaramente legato alla probabilità d’errore p dalla seguente relazione (che ci riporta alla memoria il caso periodico, v. par. 3.3): E[α] = 1/p Sostituendo otteniamo quindi: E[Yi ] = E[αi ] + E[Wi ] − 1 =

1− p 1 + E[Wi ] − 1 = E[Wi ] + p p

Infine, il periodo di trasmissione senza errori, che come abbiamo detto è pari al numero di RTT che intercorrono tra l’inizio del ’dente’ del grafico e l’istante in cui si verifica la perdita, sarà esprimibile nel seguente modo: Xi + 1

Ai =

∑

RTT

j =1

Se supponiamo che RTT sia costante (rete abbastanza stabile), il suo valor medio è legato a quello di Xi dalla formula: E[ A] = ( E[ X ] + 1) · RTT Ora ci serve un legame fra Y (numero di pacchetti correttamente spediti), X (numero di RTT effettuati in un dente di sega) e W (valore della finestra prima del suo crollo): per trovarlo attingiamo dal paragrafo 3.3.1, visto che - per ipotesi - spediamo b finestre7 prima di ricevere un ACK in grado di incrementare la nostra W (t) di 1. Intuitivamente, infatti, il massimo valore raggiunto dalla finestra nella tornata i sarà pari al numero di RTT totali diviso per b (X/b è quindi il numero intero che indica di quanto è aumentata la finestra, ovvero il numero degli ACK che sono riusciti ad incrementare la finestra8 ) sommato al valore di partenza (che coincide con il valore finale della tornata i − 1, dimezzato): Wi = 7 O, 8 O,

Wi−1 X + i 2 b

→

Xi W = Wi − i−1 b 2

se si preferisce, aspettiamo b RTT prima di osservare un incremento della finestra. se si preferisce, il numero di volte in cui la finestra è aumentata di 1.

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

34

Figura 3.5:

Le variabili aleatorie in gioco nel modello TD

Il numero di segmenti Yi trasmessi nella tornata i è invece calcolabile nel seguente modo: ogni b finestre, abbiamo detto, incrementiamo W (t) di 1; questo significa che, ad ogni incremento, avremo spedito un numero di segmenti pari al numero di RTT necessari a far incrementare la finestra (= b) moltiplicato W per il valore che la finestra ha avuto per gli ultimi b RTT, ovvero i−1 + k, dove k è un contatore che ci 2 dice quanti incrementi di finestra sono avvenuti fin’ora. Se ora mettiamo il tutto in sommatoria e facciamo X andare k da 0 fino a i − 1 (il −1 serve a ignorare l’ultimo RTT, all’interno del quale sono stati inviati solo b β i pacchetti, che sommiamo separatamente) otteniamo:

Yi =

Xi −1  b W

∑

i −1

2

j =0



+ k + βi =

Xi Wi−1 b |b {z2 }

Xi −1 b

+b

∑

k + βi =

j =0

portiamo fuori da sommat.



Xi b Xi b = Wi−1 + b b 2 |





Xi     −1 Xi b Xi Xi Xi b + βi = Wi−1 + − 1 + βi = Wi−1 + − 1 + βi 2 b 2 b 2 b {z }

Piccolo Gauss!

Xi , otteniamo l’espressione finale di Yi : b       Xi Xi b Xi Wi−1 Yi = Wi−1 + − 1 + βi = −1 Wi + − 1 + βi 2 b b 2 2

Ricordando ora l’espressione che avevamo per

Giunti fin qui siamo ben felici dei nostri risultati: mostriamo però che, in termini medi, tutto va come nel caso di modello periodico9 (par. 3.3). Applichiamo l’operatore di valor medio all’espressione della Yi per ottenere:   E [ Xi ] E[Wi−1 ] E[Yi ] = E[Wi ] + − 1 + E[ β i ] 2 2 Si noti che quanto abbiamo fatto è stato reso possibile dall’indipendenza delle variabili aleatorie Xi e Wi . Infine tenendo conto che, come abbiamo già sottolineato nel corso di questa trattazione E[ β] =

E [W ] 2

9 Avevamo già avuto un assaggio di quanto ora detto quando dicemmo che il valore medio di α è legato alla probabilità d’errore p dalla seguente relazione (assolutamente coincidente a quella citata nel modello periodico):

E[α] = 1/p

3.4. PERDITE ALEATORIE

35

e E [Y ] = E [W ] +

1− p p

otteniamo (eliminando tutti i pedici che sono inutili in questa trattazione ’media’):   E[ X ] E [W ] E [Y ] = E [W ] + − 1 + E[ β] 2 2   1− p E[ X ] E [W ] E [W ] E [W ] + = E [W ] + −1 + p 2 2 2 1− p E [ X ] E [W ] E [ X ] E [W ] E[ X ] E [W ] E [W ] + = + − + p 2 4 2 2 E [ X ] E [W ] E[ X ] 1 − p E [W ] =3 − − 2 4 2 p Ora sostituiamo tenendo conto che10 E [W ] =

2E [ X ] b

⇒

E [X] =

b E [W ] 2

Ci tocca fare qualche calcoletto: E [W ] E [ X ] E [W ] E[ X ] 1 − p =3 − − 2 4 2 p     b b E [W ] E [W ] E [W ] E [W ] 1− p 2 2 =3 − − 2 4 2 p   3b 2 b+2 1− p E [W ] + − E [W ] − =0 8 4 p   b+2 4 (1 − p ) 1 2 E [W ] + − E [W ] − =0 2 3b 3pb s s   1 4 (1 − p ) b+2 b+2 2 b+2 b + 2 2 8 (1 − p ) +4· + E [W ] = + = + 3b 3b 2 3pb 3b 3b 3pb Se supponiamo che p << 1 (cosa largamente auspicabile) allora 1 − p → 1 e s E [W ] ≈

1 p

>> 1, quindi riotteniamo:

8 3bp

Anche se consideriamo il throughput, mediamente le cose tornano ad andare come nel caso periodico: infatti E [Y ] E [Y ] S( p) = = E[ A] ( E[ X ] + 1) · RTT Ricordiamo però che: b b+2 + E [ X ] = E [W ] = 2 6

s

b+2 6

2

+

8b (1 − p) 3p

10 Cioè il valor medio della finestra W, alla fine del dente di sega, è pari al prodotto fra il numero di RTT all’interno del dente fratto gli RTT necessari ad incrementare di 1 la finestra (= b) il tutto moltiplicato per due. Questo deriva dalla rimozione di pedici (dovuta all’introduzione dell’operatore E[· · · ]) nella relazione:

Wi =

Wi−1 X + i 2 b

Che diventa quindi: E [W ] E[ X ] + 2 b E[ X ] E [W ] = 2 b

E [W ] =

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

36 E che

E [Y ] =

1− p + E [W ] p

Quindi, sostituendo e approssimando: s  b + 2 2 8 (1 − p ) 1 − p b + 2 1− p s + + + + E [W ] p 3b 3b 3bp p << 1 1 3 p  −−−−→  S ( p) = = s 2 RTT ( E[ X ] + 1) RTT 2bp b+2 b+2 8b (1 − p) + + 1 RTT  + 6 6 3p

3.4.2

Modello TD+TO

Se ora consideriamo anche la possibile scadenza dei time-out, l’andamento della finestra W (t) si fa ancora più diversificato nel tempo (v. figura 3.6).

Figura 3.6:

Modello TD+TO

In questo caso il throughput è pari a: 1

S ( p) ≈

r RTT

3.4.3

2bp + T0 min 1, 3 3

r

3bp 8

!

Modello TD+TO+AW

Figura 3.7:

Modello TD+TO+AW

p (1 + 32p2 )

3.5. MODELLI A CONFRONTO

37

Se consideriamo anche l’eventualità che AW possa limitare W (v. figura 3.7) allora il throughput diventa pari a:     Wmax S ( p) ≈ min   RTT , 

1 r RTT

2bp + T0 min 1, 3 3

r

3bp 8

! p (1 + 32p2 )

    

Qual è il senso di questa formula approssimata? Essa in pratica sceglie fra due alternative: • se AW è abbastanza grande allora possiamo tenere buona la stima del modello TD+TO; • se AW è molto restrittiva, allora saranno molte le parti del grafico in cui tale limite ’taglia’ le punte Wmax dei denti di sega, creando delle aree rettangolari (approssimabili da ). RTT Quanto detto è maggiormente comprensibile visionando la figura 3.8.

Figura 3.8:

3.5

L’approssimazione introdotta dalla formula di AW

Modelli a confronto

Nelle figure 3.9 - 3.12 vengono messi a confronto i vari modelli (figura 3.9) e vengono esaminati gli effetti della variazione dei parametri p, RTO, RTT, AW sul modello completo (TD+TO+AW) (figure 3.10, 3.11, 3.12).

38

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

Figura 3.9:

Figura 3.10:

Modelli a confronto

Influenza dell’RTT sul modello

3.5. MODELLI A CONFRONTO

39

Figura 3.11:

Influenza di AW sul modello

Figura 3.12:

Influenza di RTO sul modello

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

40

3.6

Latenza

Si definisce latenza L il tempo che intercorre fra l’istante ti in cui il client inizia una connessione TCP e l’istante t f in cui i dati richiesti sono completamente ricevuti. L = t f − ti Per il calcolo di tale parametro faremo qualche ipotesi semplificativa: • W limitata solamente da CW del trasmettitore (AW sufficientemente grande); • assenza di ritrasmissioni; • overhead dovuto alle intestazioni trascurabile; • file costituito da un numero intero di MSS; • i segmenti che non trasportano dati, ma solo informazioni di servizio, hanno tempi di trasmissione trascurabili. Indicheremo con: • P (bit): dimensione del file di dati (ad es. pagina web) da trasferire; • MSS (bit): il maximum segment size; • C (bit/s): velocita del canale dal server al client.

Figura 3.13:

I passi imprescindibili per effettuare un trasferimento dati

Nel caso in cui non ci sia limitazione al flusso dati dovuta al protocollo a finestra occorre un RTT per iniziare la connessione TCP (protocollo TWH Three Way Handshake); trascorso un RTT viene inviata la richiesta dell’oggetto e, dopo 2 RTT, il client comincia a ricevere i dati richiesti. Instaurato il trasferimento dei dati, essi vengono ricevuti per un periodo pari a P/C. I passi definiti fin’ora sono obbligatori e imprescindibili (v. figura 3.13), quindi il limite inferiore (lower bound) per la latenza risulta essere: Lmin = 2RTT +

P C

In generale L > Lmin a causa delle perdite e delle non idealità della rete.

3.6. LATENZA

3.6.1

41

Finestra a dimensione fissa

Facciamo ora l’ipotesi che la finestra abbia dimensione fissa pari a W. Quando il server riceve la richiesta del client parte spedendogli W segmenti. Successivamente invia un segmento per ogni riscontro ricevuto; occorre però considerare due casi: MSS W · MSS ≥ RTT + → il server riceve il primo riscontro prima di aver terminato la trasmissione C C W · MSS MSS della finestra: è infatti il tempo necessario a spedire un’intera finestra, mentre RTT + C C è il tempo che ci mette un segmento ad partire e a tornare (sotto forma di conferma);

•

W · MSS MSS < RTT + → il server termina la trasmissione della finestra prima di aver ricevuto il C C riscontro.

•

Caso

W · MSS MSS ≥ RTT + C C

Instaurata la connessione i segmenti continuano ad essere trasmessi a velocità C fino a che l’oggetto non è stato completamente inviato. In questo caso la latenza è uguale a quella minima: L1 = Lmin = 2RTT +

Figura 3.14:

P C

Esempio con W = 6

In figura 3.14 si può visionare un esempio di quanto detto. Caso

MSS W · MSS < RTT + C C

Inviata una finestra il server deve arrestarsi per aspettare il riscontro. Una volta arrivati i riscontri viene trasmessa una nuova finestra11 . Il numero di finestre per trasmettere l’oggetto 12 è pari a: K=

P W · MSS

Il server è in attesa nell’intervallo tra la trasmissione di due finestre consecutive e quindi per K − 1 volte. Facciamo il calcolo della latenza: P L2 = 2RTT + + (K − 1) TA C P 2RTT + è il tempo che avremmo speso anche nell’altro caso; TA è il tempo ’perso’ per ogni segmento e C K − 1 è il numero di segmenti per cui si perde tempo. 11 Il

server si può quindi trovare o nello stato di trasmissione o nello stato di attesa di riscontro. non è intero si arrotonda all’intero più vicino

12 Se

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

42

Figura 3.15:

Schema esplicativo della formula di L2

La seguente espressione è equivalente a quella scritta poco sopra (si osservi la figura 3.15 per capire come ottenerla13 :   W · MSS S + RTT + = L2 = 2RTT + (K − 1) C C   W · MSS W · MSS W · MSS W · MSS = 2RTT + (K − 1) + RTT + − + C C C C   P (W − 1) · MSS = 2RTT + + (K − 1) RTT − C C Uguagliando questa espressione con quella analoga scritta poco sopra otteniamo anche l’espressione di TA : (W − 1) · MSS TA = RTT − C Il tempo perso è quindi l’RTT meno il tempo utilizzato per spedire i dati (com’è ovvio aspettarsi). Si ricorda che siamo nel caso di finestra costante (il W ’a regime’ è fisso e noto a priori) e si nota che la latenza cresce: • se K aumenta (molte trasmissioni dovute a una grande quantità di dati o a una finestra troppo piccola); • RTT grande rispetto a MSS/C (molto tempo perso in giro per la rete). La latenza tende invece al valore ottimo (cioè cala) se: • K = 1 (una sola finestra contiene tutto il blocco dati e il termine TA non esiste); •

(W − 1) · MSS → RTT (idem come sopra). C

3.6.2

Finestra evolvente (dinamica)

Facciamo l’ipotesi che il server utilizzi inizialmente lo Slow Start (finestra iniziale: W = CW = 2). Come sappiamo, ad ogni riscontro si ha W = W + 1 e quindi la finestra raddoppia ad ogni RTT (v. figura 3.16. Sia quindi K la variabile che conta i RTT a partire da 1 seguendo la seguente relazione14 RTT numero k → W = 2k−1 13 L’S

in figura è l’MSS. è valida solo se lavoriamo unicamente in SS!!

14 Che

3.7. IN SINTESI

43

Raddoppio della finestra in SS

Figura 3.16:

La trasmissione dei dati può essere quindi suddivisa in due fasi: • in una prima fase la finestra è ancora piuttosto piccola e abbiamo purtroppo dei tempi morti, perché il tempo d’invio dei dati (che sono pochi) è molto piccolo rispetto al tempo che dobbiamo attendere prima di avere la conferma ed allargare la finestra: W < S/C + RTT; • nella fase successiva la finestra è abbastanza grande e da far sì che, all’arrivo della prima conferma, ancora si stanno spedendo dei segmenti: W ≥ S/C + RTT. In questo regime la banda è sfruttata la meglio. Siano P0 i bit spediti durante la prima fase e P00 = P − P0 i bit spediti nella seconda. Se il ciclo k0 è quello in cui termina la prima fase allora durante quest’ultima avremo trasmesso: k0

∑ 2i−1 · MSS [byte]

i =1

k0

∑ 2i − 1

[segmenti]

i =1

Di lì in poi siamo nella seconda fase e quindi nel caso ottimo per la latenza. Sommando i contributi della prima fase e della seconda otteniamo:   P00 0 MSS L3 = 2RTT + k + RTT + = C C |{z} | {z } seconda fase

prima fase

= 2RTT + k0



MSS + RTT C



+

P00 P0 P0 + − = |C {z C} C P/C k0

= 2RTT +

3.7

P + k0 C



MSS + RTT C

∑ 2i−1 · MSS



−

i =1

C

In sintesi

Il throughput di una connessione TCP è la quantità totale di informazioni trasmesse nell'unità di tempo, S(t) =

W (t) RTT

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

44

mentre il goodput misura i dati trasmessi con successo (sempre nell'unità di tempo). Com'è ovvio, il goodput è uguale al throughput nel caso migliore, altrimenti è sempre inferiore. I parametri S e W sono interessanti da analizzare ed infatti sono stati creati dei modelli in grado di stimarli: •

•

•

modello periodico:

questo modello assume che vi sia una certa percentuale di perdita p e che quindi si riescano a trasmettere N = p−1 segmenti all'interno di un periodo di trasmissione T stante fra due perdite. Il graco di W (t) per una connessione a perdite periodiche ha la forma di un treno periodico di denti di sega (periodo di ripetizione = T );

modello periodico con ACK ritardati:

è tutto come nel caso precedente ma la crescita della nestra è rallentata dall'uso di ACK ritardati. Ne risentono sia il troughput che la dimensione massima assunta da W;

modello aleatorio TD: i calcoli iniziano a complicarsi perché dobbiamo abbandonare la periodicità delle

perdite. In questo caso particolare, le perdite sono dovute all'eventualità di triple duplicate ACK, mentre trascureremo la scadenza di eventuali timeout (in particolare l'RTO) o il contributo della nestra AW nel dimensionamento di W . Per generalità, terremo invece in considerazione la possibilità che si faccia uso di delayed ACK, tanto basta porre b = 1 per tornare nel caso di ACK non ritardati. Il graco di W (t) per una connessione a perdite aleatorie è fatto da denti di sega di forme completamente diverse l'uno dall'altro e non presenta periodicità. Volendo trovare formule assimilabili a quelle dei modelli precedenti non possiamo fare altro che ragionare in termini medi;

•

modello aleatorio TD+TO: come il caso precedente, ma questa volta mettiamo in conto il possibile

•

modello aleatorio TD+TO+AW: come il caso precedente,

scadere dell'RTO;

AW < CW e quindi limiti la nestra.

Periodico Periodico (ACK rit.) Aleatorio TD Aleatorio TD+TO

Aleatorio TD+TO+AW

ma consideriamo anche l'eventualità che

Throughput s S 1 3 RTT 2p s 1 3 RTT 2bp mediamente come il periodico (m.d.) 1  q  q 2bp 3bp + T min 1, 3 RTT p (1 + 32p2 ) 0 3 8   Wmax min ,S RTT TD+TO Tabella 3.1:

dim. s max di W

T fra perdite

8 3p

W RTT 2

8 3bp m.d.

Wb RTT 2 m.d.

s

Schema riassuntivo per i vari modelli

La latenza è il tempo che intercorre fra l'istante in cui il client inizia una connessione TCP (ti ) e l'istante in cui i dati richiesti sono stati completamente ricevuti (t f ): L = t f − ti . Sia P la dimensione dei dati da trasferire e C la velocità del canale di trasmissione; se facciamo l'ipotesi che W dipenda solo da CW e che l'overhead sia P trascurabile, la latenza minima (quella imprescindibile) è Lmin = 2RTT + . C Se W è ssa, allora dobbiamo tenere in conto due casi: • W

MSS MSS ≥ RTT + ⇒ il server riceve il primo riscontro prima di aver trasmesso tutta la nestra (caso C C

'buono'); • W

MSS MSS > RTT + ⇒ il server termina la trasmissione della nestra prima di aver ricevuto il primo C C

riscontro (caso non ottimale).

  P (W − 1) · MSS In questo caso la latenza è pari a L2 = 2RTT + + (K − 1) RTT − , dove K è il numero C C

di nestre che impieghiamo per spedire il nostro dato. Se invece la nestra è variabile, la latenza è pari a

3.7. IN SINTESI

45 k0



P MSS + k0 + RTT C C MSS MSS ottimale W > RTT + . C C L3 = 2RTT +

∑ 2i−1 · MSS



−

i =1

C

dove k0 è il numero di RTT in cui si ha il caso non

46

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

Appendice A

Esercizi A.1

Protocolli di rete, analisi di CW

A.1.1

Esercizio 1

DATI PRELIMINARI

Protocollo: TCP Reno Segmenti (dimensione MSS) spediti: 26 Segmenti perduti: 14 e 17 RTO = 3RTT [1] Il protocollo inizia con la finestra W = CW = 2: siamo in SS visto che la SSTHR è pari a 8 e 2 < 8. Tutto va chiaramente a buon fine e riusciamo a spedire i segmenti 1 e 2; nella fase [2] la finestra è raddoppiata, quindi spediamo i segmenti 3 . . . 6. Passiamo quindi alla fase [3], dove la finestra è ulteriormente raddoppiata (siamo a CW = W = 8 e quindi inizia la fase di congestion avoidance). Teoricamente dovremmo spedire i segmenti 7 . . . 14, solo che il 14◦ si perde. In effetti, il ciclo dopo, la finestra non passa a 9 (cioè non aumenta di 1, com’è normale che accada nel CA) perché non abbiamo ricevuto 8 ACK (quelli da 8 . . . 15), ma solo quelli di numero 8 . . . 14, che sono 7 e che quindi non completano la finestra. Tali 7 ACK, tuttavia, hanno l’effetto di far scorrere la finestra di altrettante posizioni e di permettere l’invio [4] dei segmenti 15 . . . 21. Il trasmettitore si aspetterebbe, a questo punto, di ricevere l’ACK mancante del giro prima (il 15) nonché quelli da 16 a 22: il ricevitore, invece, non può fare altro che chiedergli insistentemente il segmento 14, che non è riuscito ad arrivare, ed infatti vengono spediti 6 ACK (da 8 che dovevano essere passiamo a 7 perché il segmento 14 non è arrivato e quindi a 6 perché persino il 17◦ segmento si è perso chissà dove), tutti con numero di sequenza 14 [4b]. Gli ACK duplicati sono 6 e quindi parte il Fast retransmit/Fast recovery (in effetti ne sarebbero bastati 3 duplicati, ovvero 4 in totale, per far scattare l’algoritmo): quel che accade è che la finestra si gonfia e passa a fightsize 8 + Numero di ACK duplicati = + 6 = 10 2 2 Si ricorda che il flightsize indica quanti pacchetti il ricevitore presume siano in giro per la rete (tra quelli fightsize confermati e non arriviamo a 8). La W = CW viene perciò messa a 10 e la SSTHR a , cioè a 4. Il 2 trasmettitore può [5] ora trasmettere il segmento 14, che tanto insistentemente gli è stato chiesto, nonché i segmenti 22 e 23, che stanno all’interno della finestra da 10 (14 . . . 23). Il ricevitore, di risposta, è tuttavia decisamente indispettito e chiede tre volte il segmento 17 [5b], non essendogli esso ancora arrivato. Siamo ora in [6]: siamo in CA perché la soglia era 4 e la finestra si è sgonfiata fino a passare a 4. Per un pelo non scatta di nuovo il FR/FR, dato che sono arrivati 2 ACK duplicati; in compenso scade l’RTO del 17◦ fightsize segmento e quindi [7] la nuova SSTRH diventa pari a , cioè a 3 (per il trasmettitore i segmenti 2 in giro sono 7, cioè quelli dal 17 al 23, per cui si ha 7/2 arrotondato per difetto), mentre sia W che CW decadono a 1. L’unica buona notizia è che, finalmente, viene trasmetto ’sto maledettissimo segmento 17: il ricevitore apprezza lo sforzo e invia ACK 24 (visto che ha questo punto ha in cassa tutti i segmenti fino al 23◦ ); di lì in poi [8][9], la connessione riprende a crescere in SS secondo le regole del TCP classico e, al 26◦ segmento, la trasmissione è completa. 47

APPENDICE A. ESERCIZI

48

Figura A.1:

Rappresentazione schematica dell’esercizio A.1.1

A.1. PROTOCOLLI DI RETE, ANALISI DI CW

A.1.2

49

Esercizio 2

DATI PRELIMINARI

Protocollo: TCP New Reno Segmenti (dimensione MSS) spediti: 30 Segmenti perduti: 14 e 17 RTO = 3RTT

Questo esercizio ha praticamente gli stessi dati di quello precedente e serve semplicemente a mettere in mostra quanto, in certe situazioni, il New Reno sia più figo rispetto al Reno nudo e crudo. Fino a [3] tutto va come nell’esercizio A.1.1: in [1] si ha la perdita del segmento 14 e in [2] quella del segmento 17 e la sestuplicale1 richiesta del segmento 14. La prima vera differenza si nota a [3]: anzitutto viene memorizzato il numero di sequenza dell’ultimo pacchetto inviato (il 21) nella variabile recover. Il calcolo della nuova CW [3] è identico a quello dell’esercizio A.1.1; questa volta però non usciamo subito dal fastretransmit/fast-recovery perché in [3] riceviamo gli ACK di 17, che è < di 18. In [4] la finestra è ancora pari a 10 in quanto essa deve crescere di 1 per ogni ulteriore ACK duplicato e decrementarsi di 1 per ogni segmento inviato. Tra [3] e [4] scade l’RTO di 17, che quindi viene inviato in [4] assieme a 24, 25 e 26 (che riescono a stare nella finestra grande 10). Alla fine di [4] riceviamo gli ACK di 24, 25, 26 e 27: tutti questi numeri sono maggiori della variabile recover (= 17) e quindi possiamo uscire dal FR/FR. In [5] la finestra CW viene messa pari alla soglia, cioè a 4. Come si può notare, una volta che siamo usciti dalla SS non ci torniamo più.

1 Non

ci crederete, ma si scrive proprio così!

APPENDICE A. ESERCIZI

50

Figura A.2:

Rappresentazione schematica dell’esercizio A.1.2

A.1. PROTOCOLLI DI RETE, ANALISI DI CW

A.1.3

51

Esercizio 3

DATI PRELIMINARI

Protocollo: TCP 'standard' (senza fronzoli) Segmenti (dimensione MSS) spediti: 64 Segmenti perduti: 53 RTO = 2RTT Esercizio abbastanza banale, se raffrontato con quelli numero A.1.1 e A.1.2. Fino a [7], di fatto, non accade nulla di particolare: finché la CW è sotto a 8 (la SSTHR) siamo in SS ([1]-[3]) e quindi, ad ogni RTT, raddoppiamo la finestra (2 in [1], 4 in [2] e 8 in [3]). Tutti i segmenti vengono ricevuti correttamente e quindi il numero degli ACK ad ogni RTT è pari al numero dei segmenti inviati + 1. Da [4] in poi siamo in CA e la finestra cresce di 1 ad ogni RTT, invece di raddoppiare: anche qui tutto va normalmente e senza intoppi. La vera ’novità’, se così si può chiamare, l’abbiamo a [7]: la finestra è 10 (non può essere di più in tutto l’esercizio perché AW è costante e pari a 10: essa fissa perciò un limite superiore) ma di questi 10 segmenti solo 9 vengono correttamente recepiti. Il 53◦ , infatti, si perde in rete e non viene ricevuto, cosicché vengono inviati solo 9 ACK (e non 10). Il RTT successivo ([8]) la CW non aumenta, perché non è arrivato il pacchetto in grado di incrementarla di 1 (sempre il 53◦ , mannaggia a lui!), ma questo non impedisce alla finestra di scorrere di 9 posizioni cosicché inviamo i messaggi da 54 a 62. Continuiamo tuttavia a ricevere 9 ACK a 53 in quanto il ricevitore brama il suo pacchetto con insistenza: non dovrà però aspettare molto perché alla fine di [7] scade il relativo RTO, evento che provoca la caduta della finestra W a 1, il ridimensionamento di SSTHR a CW/2 = 12/2 = 6 e la ritrasmissione del 53◦ pacchetto che questa volta viene correttamente ricevuto. Ad [8] la finestra passa a 2 (siamo tornati in SS) e termina la trasmissione con l’invio di 63 e 64.

APPENDICE A. ESERCIZI

52

Figura A.3:

Rappresentazione schematica dell’esercizio A.1.3

A.1. PROTOCOLLI DI RETE, ANALISI DI CW

A.1.4

53

Esercizio 4

DATI PRELIMINARI

Protocollo: TCP 'standard' (senza fronzoli) Segmenti (dimensione MSS) spediti: 64 Segmenti perduti: 53 RTO = 3RTT Questo esercizio è una versione minimamente modificata di quello precedente: l’unica cosa che cambia è l’RTO, che è più lungo (3RTT invece che 2RTT). Il segmento mancante viene quindi trasmesso due RTT dopo [8]: in seguito, la trasmissione può continuare con 63 e 64 (non vengono riportati nello schema, tanto il meccanismo è analogo all’esercizio precedente).

APPENDICE A. ESERCIZI

54

Figura A.4:

Rappresentazione schematica dell’esercizio A.1.4

A.2. MODELLI PER IL TCP

A.2

Modelli per il TCP

A.2.1

Esercizio 1

55

Una connessione TCP-Reno che lavora nelle seguenti condizioni: • tempo di andata e ritorno approssimativamente costante e pari a RTT = 80 ms; • nestra di trasmissione (W ) limitata dal valore della nestra di congestione (CW ) ( AW abbastanza grande

per essere ininuente);

• perdite di segmenti dovute a fenomeni di congestione in rete approssimativamente periodiche e pari a p = 2% dei segmenti; • si considerino tutti i segmenti di dimensione pari a MSS = 1000.

Trascurando i periodi di tempo relativi alle fasi di fast retransmit a valle delle perdite dei segmenti si considerino i soli periodi in cui il controllo di congestione utilizza l'algoritmo di Congestion Avoidance. Inoltre si ipotizzi una crescita della nestra di congestione puramente lineare in tali fasi. Si valuti: 1. la dimensione massima di W (in segmenti) e di w (in byte) 2. il throughput S della connessione in numero di segmenti per RTT e numero di bit per secondo; 3. qualora la banda del collegamento a minore capacità del percorso end-to-end della connessione sia C=2,048 Mbit/s discutere l'eetto delle perdite sull'ecienza nell'uso della capacità disponibile. SOLUZIONE:

1. siamo nel caso più semplice, cioè quello di perdite periodiche (v. par 3.3) quindi la dimensione massima della finestra è s 8 W= = 11, 547 → 11 segmenti ⇔ 11, 547 · MSS = 11547 byte 3p 2. anche questo punto è risolvibile semplicemente applicando una pedissequamente formula s 1 3 S= = 108, 25 → 108 segmenti/s ⇔ 108, 25 · MSS · 8 = 866025 bit/s RTT 2p Si noti che questa volta vengono richiesti i bit, non i byte (tipico errore di distrazione)! 3. la banda della connessione è ben più consistente degli 866 Kb/sec circa che effettivamente sfruttiamo. 866 = 42, 3%. L’efficienza nell’uso della banda è infatti del 2048

A.2.2

Esercizio 2

Due connessioni TCP-Reno lavorano rispettivamente nelle seguenti condizioni: • RTT approssimativamente costante e pari a RTT = 60 ms; • perdite di segmenti dovute a fenomeni di congestione in rete approssimativamente periodiche e di probabilità p = 1%; • tutti i segmenti di dimensione sono di dimensione pari a MSS = 500 byte.

Si ipotizzi che: • la connessione 1 utilizzi un'implementazione TCP che non fa uso di ACK ritardati, mentre la connessione 2

invii un ACK ogni 2 segmenti ricevuti;

APPENDICE A. ESERCIZI

56

• siano trascurabili i periodi di tempo relativi alle fasi di fast retransmit e fast recovery a valle delle perdite

dei segmenti e quindi si possano considerare i soli periodi in cui il controllo di congestione utilizzi l'algoritmo di Congestion Avoidance;

• la crescita della nestra di congestione sia puramente lineare in tali fasi; • AW sia di grandi dimensioni per entrambe le connessioni e pertanto W = CW .

Determinare: 1. l'andamento di W1 e W2 nel tempo ed i relativi valori massimi e minimi, in numero di segmenti ed in byte; 2. il throughput S1 ed S2 della connessione in numero di segmenti per RTT e numero di bit per secondo. SOLUZIONE: 1. in questo caso dobbiamo sia fare riferimento al modello di perdite periodiche (v. par. 3.3) che a quello degli ACK ritardati (v. par. 3.3.1) quindi la dimensione massima della finestra è, nel primo caso s 8 W1max = = 16, 33 → 16 segmenti ⇔ 16, 33 · MSS = 8165 byte 3p mentre per la connessione 2 si ha: s 8 W2max = = 11, 547 → 11 segmenti ⇔ 11, 547 · MSS = 5774 byte 3pb Com’è evidente, la dimensione massima della finestra è superiore nel caso di ACK non ritardati. La dimensione minima, fatta l’ipotesi di rimanere sempre in CA, è pari alla metà di questi due parametri2 . Connessione 1: W1min =

16, 33 = 8, 17 → 8 segmenti ⇔ 8, 17 · MSS = 4085 byte 2

W2min =

11, 547 = 5, 77 → 5 segmenti ⇔ 5, 77 · MSS = 2885 byte 2

Connessione 2:

L’andamento nel tempo di entrambe le connessioni sarà caratterizzato dal tipico grafico a dente di sega: la lunghezza dei periodi sarà maggiore nel caso di ACK ritardati (la connessione va a tutti gli effetti più lenta e, inoltre, non riesce a raggiungere i valori della finestra del caso not delayed). La lunghezza di tali periodi è calcolabile tramite la formula: T1 =

W1max · RTT 16, 33 · 0, 06 = = 0, 4899 s 2 2

2 · 11, 547 · 0, 06 W2max b · RTT = = 0, 6928 s 2 2 √ √ Si noti che T1 · 2 = T2 : tra i due parametri T vi è infatti un fattore b. T2 =

2. anche nel risolvere questo punto dobbiamo tenere presente che una delle due connessioni utilizza ACK ritardati: s 1 3 S1 = = 204, 12 → 204 segmenti/s ⇔ 204, 12 · MSS · 8 = 816497 bit/s RTT 2p s 1 3 S2 = = 144, 34 → 144 segmenti/s ⇔ 144, 34 · MSS · 8 = 577350 bit/s RTT 2bp √ Ancora una √ volta si ha una relazione del tipo S1 · 2 = S2 : anche tra i due parametri S vi è infatti un fattore b. 2 Infatti,

quando scade un RTO e fatta l’ipotesi di trascurare la SS, dimezziamo la finestra.

A.2. MODELLI PER IL TCP

57

Figura A.5:

Interpretazione grafica dell’esercizio A.2.2

58

APPENDICE A. ESERCIZI

Elenco delle figure 1.1 1.2 1.3 1.4 1.5 1.6 1.7

La macchina a stati finiti che implementa il TCP . . . . . Possibili inconvenienti in cui si può incappare nel TWH Evoluzione dell’RTO secondo RFC 793 e RFC 2988. . . . Misurazione dell’sRTT . . . . . . . . . . . . . . . . . . . . Ambiguità nel calcolo dell’sRTT . . . . . . . . . . . . . . Duplicazione dei numeri di sequenza . . . . . . . . . . . Schema riassuntivo del calcolo dell’RTT . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

6 7 11 11 12 13 14

2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11

Il meccanismo a finestra fra segmenti ricevuti e segmenti non trasmessi. La questione delle capacità e l’adattività del controllo di flusso . . . . . Meccanismo di Slow Start . . . . . . . . . . . . . . . . . . . . . . . . . . . Distinzione fra SS e CA . . . . . . . . . . . . . . . . . . . . . . . . . . . . Un esempio d’evoluzione della finestra . . . . . . . . . . . . . . . . . . . Effetto dell’approssimazione TSS << TCA . . . . . . . . . . . . . . . . . . Condivisione della risorsa . . . . . . . . . . . . . . . . . . . . . . . . . . . L’algoritmo di fast recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . L’algoritmo di fast recovery (2) . . . . . . . . . . . . . . . . . . . . . . . . . Il TCP classico e il Tahoe (cioè TCP + Fast Rec.) a confronto . . . . . . . I protocolli TCP Reno e TCP New Reno a confronto . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

15 17 18 19 20 20 21 23 23 24 25

3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16

Modello periodico . . . . . . . . . . . . . . . . . . . . . . . Modello periodico (2) . . . . . . . . . . . . . . . . . . . . . . Andamento della finestra con perdite aleatorie . . . . . . . Le variabili Yi e Ai . . . . . . . . . . . . . . . . . . . . . . . Le variabili aleatorie in gioco nel modello TD . . . . . . . Modello TD+TO . . . . . . . . . . . . . . . . . . . . . . . . . Modello TD+TO+AW . . . . . . . . . . . . . . . . . . . . . . L’approssimazione introdotta dalla formula di AW . . . . Modelli a confronto . . . . . . . . . . . . . . . . . . . . . . . Influenza dell’RTT sul modello . . . . . . . . . . . . . . . . Influenza di AW sul modello . . . . . . . . . . . . . . . . . Influenza di RTO sul modello . . . . . . . . . . . . . . . . . I passi imprescindibili per effettuare un trasferimento dati Esempio con W = 6 . . . . . . . . . . . . . . . . . . . . . . . Schema esplicativo della formula di L2 . . . . . . . . . . . Raddoppio della finestra in SS . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

30 30 32 33 34 36 36 37 38 38 39 39 40 41 42 43

A.1 A.2 A.3 A.4 A.5

Rappresentazione schematica dell’esercizio A.1.1 Rappresentazione schematica dell’esercizio A.1.2 Rappresentazione schematica dell’esercizio A.1.3 Rappresentazione schematica dell’esercizio A.1.4 Interpretazione grafica dell’esercizio A.2.2 . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

48 50 52 54 57

59

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .