reti_cap3_8df4339bb2417bec9bac51f79a305cf9.pdf

Reti (Computer Networks) Capitolo 3 Livello di trasporto: UDP e TCP Docente: Fabrizio Granelli AA 2024/2025 Capitolo 3: Livello di trasporto Obiettivi: r Capire i principi che sono alla r Descrivere i protocolli base dei servizi del livello di del livello di...

Reti (Computer Networks) Capitolo 3 Livello di trasporto: UDP e TCP Docente: Fabrizio Granelli AA 2024/2025 Capitolo 3: Livello di trasporto Obiettivi: r Capire i principi che sono alla r Descrivere i protocolli base dei servizi del livello di del livello di trasporto trasporto: di Internet: m Multiplexing/demultiplexing m UDP: trasporto senza m Trasferimento dati affidabile connessione m Controllo di flusso m TCP: trasporto orientato alla connessione m Controllo di congestione m Controllo di congestione TCP 3-2 Capitolo 3: Livello di trasporto r 3.1 Servizi a livello di trasporto r 3.5 Trasporto orientato alla r 3.2 Multiplexing e connessione: TCP demultiplexing m Struttura dei segmenti m Trasferimento dati affidabile r 3.3 Trasporto senza m Controllo di flusso connessione: UDP m Gestione della connessione r 3.4 Principi del trasferimento dati affidabile r 3.6 Principi del controllo di congestione r 3.7 Controllo di congestione TCP 3-3 Servizi e protocolli di trasporto applicazione trasporto q Forniscono la comunicazione rete data link logica tra processi applicativi di fisico host differenti Tr as q I protocolli di trasporto vengono po rto eseguiti nei sistemi terminali log v Lato invio: scinde i messaggi in ico segmenti e li passa al livello di rete pu nt o- v Lato ricezione: riassembla i pu segmenti in messaggi e nt o li passa al livello di applicazione q Più protocolli di trasporto sono a applicazione trasporto disposizione delle applicazioni rete data link v Internet: TCP e UDP fisico 3-4 Relazione tra livello di trasporto e livello di rete r Livello di rete: Analogia con la posta ordinaria: Comunicazione logica tra 12 studenti a Torino inviano lettere a 12 studenti a Enna host r Processi = studenti r Messaggi delle applicazioni = r Livello di trasporto: Lettere nelle buste Comunicazione logica tra r Host = Abitazioni processi r Protocollo di trasporto = m Si basa sui servizi del livello sorella maggiore Anna e di rete e li potenzia fratello maggiore Andrea r Protocollo del livello di rete = Servizio postale 3-5 Protocolli del livello di trasporto in Internet applicazione trasporto q Affidabile, consegne rete data link nell’ordine originario: TCP fisico Tr v Controllo di congestione as po v Controllo di flusso rto log v Setup della connessione ico pu q Inaffidabile, consegne senza nt o- ordine: UDP pu nt o v Estensione senza fronzoli del servizio di consegna best effort applicazione trasporto q Servizi non disponibili: rete data link fisico v Garanzia su ritardi v Garanzia su ampiezza di banda 3-6 Capitolo 3: Livello di trasporto r 3.1 Servizi a livello di trasporto r 3.5 Trasporto orientato alla r 3.2 Multiplexing e connessione: TCP demultiplexing m Struttura dei segmenti m Trasferimento dati affidabile r 3.3 Trasporto senza m Controllo di flusso connessione: UDP m Gestione della connessione r 3.4 Principi del trasferimento dati affidabile r 3.6 Principi del controllo di congestione r 3.7 Controllo di congestione TCP 3-7 Multiplexing/demultiplexing q Multiplexing al trasmettitore: gestione dati da diverse socket, aggiunta header con PCI del livello transport (ne ha bisogno il ricevitore per il demultiplexing) q Demultiplexing al ricevitore: utilizza le PCI nell’header per consegnare i segmenti ricevuti alle socket giuste applicazione applicazione P1 P2 applicazione socket P3 trasporto P4 processo trasporto rete trasporto rete data link rete data link fisico data link fisico fisico 3-8 Come funziona il demultiplexing q L’host riceve i datagrammi IP 32 bit v Ogni datagramma ha un Num. porta Num. porta indirizzo IP di origine e un sorgente destinazione indirizzo IP di destinazione v Ogni datagramma trasporta 1 Altri campi dell’header segmento a livello di trasporto v Ogni segmento ha un numero di porta di origine e un numero di porta di destinazione Dati dell’applicazione (payload) q L’host usa gli indirizzi IP e i numeri di porta per inviare il segmento alla socket appropriata Struttura di un segmento TCP / UDP 3-9 Porte TCP e UDP q La destinazione finale di un segmento non è un host, ma un processo che gira sull’host q L’interfaccia tra l’applicazione e il livello di trasporto è la “porta” v Identificata da un intero di 16 bit v Mappatura biunivoca tra porta ßà processo v I servizi standard vengono esposti da un server utilizzando numeri di porta standard o “well-known”, con valori < 1024 Esempio: porta 80 per HTTP, porta 25 per SMTP, porta 53 per DNS v I processi non-standard e le connessioni in ingresso a un client usano invece numeri di porta più alti, fino a 65535 (=216-1) 3-10 Porte TCP e UDP q I numeri di porta si possono anche classificare come v Statici (altro nome delle porte “well-known”) Associati con applicazioni standard (email, web, DNS, …) v Dinamici (o “ephemeral”) Assegnati automaticamente dal sistema operativo quando si apre una connessione o si crea una socket q Le porte sorgente e destinazione non sono le stesse (D: perché?) q Concetto di flusso (flow) e connessione v Gruppo di dati che appartengono alla stessa comunicazione logica v Un’applicazione può aprire multiple connessioni e veicolare molteplici flussi 3-11  Demultiplexing senza connessione r Crea le socket con i numeri r Quando l’host riceve il di porta: segmento UDP: r DatagramSocket mySocket1 = new m Controlla il numero della porta di DatagramSocket(12534); destinazione nel segmento r DatagramSocket mySocket2 = new m Invia il segmento UDP alla socket con DatagramSocket(12535); quel numero di porta r La socket UDP è identificata r Datagrammi IP con indirizzi IP da 2 parametri: di origine e/o numeri di porta (indirizzo IP di destinazione, di origine differenti vengono numero della porta di destinazione) inviati alla stessa socket 3-12  Demultiplexing senza connessione (continua) DatagramSocket serverSocket = new DatagramSocket(6428); P2 P1 P1 P3 SP: 6428 SP: 6428 DP: 9157 DP: 5775 SP: 9157 SP: 5775 client DP: 6428 DP: 6428 client server IP: A IP: C IP: B SP = source port DP = destination port SP fornisce “l’indirizzo di ritorno a livello 4” 3-13 Demultiplexing orientato alla connessione r La socket TCP è identificata r Un host server può da 4 parametri: supportare più socket TCP m indirizzo IP di origine contemporanee: m numero di porta di origine m Ogni socket è identificata dai m indirizzo IP di destinazione suoi 4 parametri m numero di porta di destinazione r I server web hanno socket r L’host ricevente usa i differenti per ogni quattro parametri per connessione client inviare il segmento alla m Con HTTP non-persistente si socket appropriata avrà una socket differente per ogni richiesta 3-14 Demultiplexing orientato alla connessione (cont.) P1 P4 P5 P6 P2 P1P3 SP: 5775 DP: 80 S-IP: B D-IP:C SP: 9157 SP: 9157 client DP: 80 DP: 80 client server IP: A S-IP: A IP: C S-IP: B IP: B D-IP: C D-IP: C 3-15 Demultiplexing orientato alla connessione (cont.) P1 P4 P2 P1P3 SP: 5775 DP: 80 S-IP: B D-IP:C SP: 9157 SP: 9157 client DP: 80 DP: 80 client server IP: A S-IP: A IP: C S-IP: B IP: B D-IP: C D-IP: C 3-16 Capitolo 3: Livello di trasporto r 3.1 Servizi a livello di trasporto r 3.5 Trasporto orientato alla r 3.2 Multiplexing e connessione: TCP demultiplexing m struttura dei segmenti m trasferimento dati affidabile r 3.3 Trasporto senza m controllo di flusso connessione: UDP m gestione della connessione r 3.4 Principi del trasferimento dati affidabile r 3.6 Principi del controllo di congestione r 3.7 Controllo di congestione TCP 3-17  UDP: User Datagram Protocol [RFC 768] r Protocollo di trasporto “senza fronzoli” Perché esiste UDP? r Servizio di consegna r Non richiede di stabilire una “a massimo sforzo” connessione (che potrebbe (best effort) aggiungere un ritardo) r I segmenti UDP possono r Semplice: nessuno stato di essere: connessione nel mittente e m Perduti destinatario m Consegnati fuori sequenza all’applicazione r Header di segmento corti r Senza connessione: r Senza controllo di congestione: UDP può inviare raffiche di m No handshaking tra mittente e destinatario UDP pacchetti dati m Ogni segmento UDP è gestito indipendentemente dagli altri 3-18 TCP vs UDP 3-19  UDP: ulteriori informazioni r Utilizzato spesso nelle applicazioni multimediali 32 bit m Tollera piccole perdite Num. porta Num. porta m Sensibile alla frequenza sorgente destinazione r Altri impieghi di UDP Lunghezza in byte del Lunghezza Checksum m DNS segmento UDP, m SNMP incluso l’header r Trasferimento affidabile con Dati dell’applicazione UDP: aggiungere affidabilità al (messaggio) livello di applicazione Struttura del segmento UDP 3-20 Checksum UDP Obiettivo: rilevare gli “errori” (bit alterati) nel segmento trasmesso Mittente: Ricevente: r Tratta il contenuto del r Somma tutte le parole di 16 bit del segmento come una sequenza segmento, incluso il checksum di interi da 16 bit r Controlla se il risultato è una parola di 16 bit tutti uguali a 1 r checksum: somma le parole di m Sì – Nessun errore rilevato. 16 bit nel segmento e calcola il Ma potrebbero esserci errori complemento a 1 della somma nonostante questo? Lo scopriremo più avanti … r Il mittente pone il valore m No – errore rilevato ottenuto nel campo checksum del segmento UDP 3-21 Checksum UDP: esempio Esempio: somma di due parole di 16 bit ciascuna 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Riporto 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 sommato + Somma 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 Checksum 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 (complemento a 1) Nota: quando si sommano i numeri, se c’è un riporto dal bit più significativo, questo deve essere sommato al risultato 3-22 Checksum UDP: al ricevitore Somma 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 + Checksum 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 = (ricevuto) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Sommare la somma delle parole di 16 bit e il complemento a 1 della somma stessa produce una parola di tutti 1 (se non ci sono bit errati nel segmento ricevuto) 3-23 Nota su rilevamento e correzione di errori q Bit di parità: permette di rilevare un numero 0 1 1 0 1 0 1 0 0 0 1 0 0 1 0 1 0 1 dispari di bit errati q Codice a ripetizione: 0 1 1 0 1 0 1 0 permette voti di 0 1 0 0 1 0 1 0 maggioranza, e 0 1 1 0 1 0 1 0 correzione di qualche 0 1 1 0 1 0 1 0 errore 3-24 Capitolo 3: Livello di trasporto r 3.1 Servizi a livello di trasporto r 3.5 Trasporto orientato alla r 3.2 Multiplexing e connessione: TCP demultiplexing m struttura dei segmenti m trasferimento dati affidabile r 3.3 Trasporto senza m controllo di flusso connessione: UDP m gestione della connessione r 3.4 Principi del trasferimento dati affidabile r 3.6 Principi del controllo di congestione r 3.7 Controllo di congestione TCP 3-25 ARQ q Automatic Repeat reQuest v Classe di protocolli che cerca di recuperare le perdite di pacchetti q Usa pacchetti speciali per notificare il trasmettitore di una avvenuta ricezione corretta v Acknowledgments (ACK) q Esempi di protocolli basati su forme di ARQ v Stop-and-Wait v Go-back-N v Selective Repeat v TCP v Il protocollo MAC (livello 2, data link) dei sistemi WiFi 3-26 Stop-and-Wait q Trasmettitore: v Invia una PDU (e mantiene una copia locale) v Imposta un timeout v Attende la ricezione del rispettivo ACK Se non riceve alcun ACK entro il timeout, invia nuovamente la stessa PDU Se riceve l’ACK – Controlla che l’ACK non contenga errori (checksum) – Controlla il numero di sequenza – Se è tutto OK (quindi l’ACK si riferiva alla PDU inviata) procede con l’invio della PDU successiva q Il ricevitore, quando riceve una PDU: v Controlla se ci sono errori (checksum) v Controlla il numero di sequenza Se è corretto e in ordine, invia l’ACK e passa l’SDU ai layer superiori Se il checksum o il numero di sequenza sono errati, cancella la PDU (drop) 3-27 Come funziona Stop-and-Wait Trasmettitore Ricevitore Primo bit del pacchetto trasmesso, t = 0 Ultimo bit trasmesso, t = Ttrans = L / R Primo bit del pacchetto arrivato RTT Ultimo bit arrivato, invia ACK Arriva l’ACK, invia il prossimo pacchetto, t = RTT + L / R = RTT + Ttrans q Assunzione: la durata del messaggio ACK è trascurabile 3-28 Efficienza di Stop-and-Wait q Assumiamo v R = 1 Gbit/s v 15 ms di ritardo di propagazione (RTT = 30 ms) v L = 8000 bit v Ttrans = L/R = 8000 [bit] / 109 [bit/s] = 8 [µs] q Throughput percepito a livello applicazione v L / (Ttrans + RTT) = 8000 [bit] / (30.008 [ms]) = 33 [kByte/s] v Ehi! Ma non avevo pagato per un link da 1 Gbit/s?? L q Efficienza v Ttrans / (Ttrans + RTT) = 0.008 [ms] / 30.008 [ms] = 0.00027 (0.027 %) q I protocolli di trasporto limitano l’uso delle risorse fisiche 3-29  Protocolli con pipelining q Pipelining: il trasmettitore accetta che ci siano diversi pacchetti “in volo”, cioè per i quali non ha ancora ricevuto un ACK v Va tenuta traccia dei numeri di sequenza dei pacchetti “in volo” L’intervallo di numeri di sequenza accettabili si allarga v Bisogna memorizzare i segmenti sia al trasmettitore sia al ricevitore q Due forme di protocolli con pipelining: Go-back-N, selective repeat 3-30  Il pipelining aumenta l’utilizzo di un link Trasmettitore Ricevitore Primo bit del pacchetto trasmesso, t = 0 Ultimo bit trasmesso, t = Ttrans = L / R Primo bit del pacchetto (pkt) 1 arrivato RTT Ultimo bit del pkt 1 arrivato, invia ACK Ultimo bit del pkt 2 arrivato, invia ACK Ultimo bit del pkt 3 arrivato, invia ACK Arriva l’ACK, invia il prossimo pacchetto, t = RTT + L / R Aumento dell’utilizzo di un fattore 3! (D: Perché 3?) q Application layer throughput v 3L / (Ttrans + RTT) = 24000 b / (30.008 ms) = 100 kByte/sec 3-31 Throughput in presenza di pipelining sender receiver q 1 pacchetto inviato (dimensione L) per RTT: v Throughput = L / (RTT + Ttrans) q 3 pacchetti inviati per RTT: v Throughput = 3L / (RTT + Ttrans) ……… q N pacchetti inviati per RTT: v Throughput = N x L / (RTT + Ttrans) v (Sempre che il tempo necessario per trasmettere N pacchetti sia < RTT) q Il valore di N è chiamato “dimensione della finestra” 3-32 Protocolli con pipelining: definizioni q Finestra di trasmissione WT: insieme di PDU che il trasmettitore può trasmettere senza avere ancora ricevuto l’ACK corrispondente v Al massimo tanto grande quanto la memoria allocata dal sistema operativo del trasmettitore v |WT| (cardinalità di WT) indica la dimensione della finestra q Finestra di ricezione WR: insieme di PDU che il ricevitore può accettare e immagazzinare v Al massimo tanto grande quanto la memoria allocata dal sistema operativo del ricevitore q Puntatore low WLOW: puntatore al primo pacchetto nella finestra di trasmissione WT q Puntatore up WUP: puntatore all’ultimo pacchetto già trasmesso v Potrebbe non coincidere con l’ultimo pacchetto di WT 3-33 Finestre di trasmissione e ricezione Pacchetti Pacchetti che Pacchetti Pacchetti che trasmessi possono essere «ACKati» non possono in attesa di ACK trasmessi ancora essere WLOW trasmessi WUP WT n Pacchetti fuori Pacchetti che sequenza: Pacchetti Pacchetti possono essere scartati anche «ACKati» attesi memorizzati se corretti n WR 3-34 Acknowledgements A seconda del protocollo, si possono usare diversi tipi di ACK q ACK individuale v Indica la ricezione corretta di un pacchetto specifico v ACK(n) significa “Ho ricevuto il pacchetto n” q ACK cumulativo v Indica la ricezione corretta di tutti i pacchetti fino a un certo indice v ACK(n) significa ”Ho ricevuto tutto fino al pacchetto n (escluso)” q ACK negativo (NACK) v Richiede la ritrasmissione di un pacchetto singolo v NACK(n) significa “Inviami di nuovo il pacchetto n” q “Piggybacking” v Inserimento di un ACK data in un pacchetto dati 3-35 Protocolli con pipelining: sommario Go-back-N: Selective Repeat: q Il mittente può avere fino a q Il mittente può avere fino a N pacchetti senza ACK in N pacchetti senza ACK in pipeline pipeline q Il ricevente invia solo ACK q Il ricevente dà gli ACK solo cumulativi ai singoli pacchetti v Non dà l’ACK di un pacchetto q Il mittente mantiene un se c’è un gap timer per ciascun pacchetto q Il mittente ha un timer per il che non ha ancora ricevuto più vecchio pacchetto senza ACK ACK v Quando il timer scade, v Se il timer scade, ritrasmette ritrasmette solo i pacchetti tutti i pacchetti senza ACK che non hanno avuto ACK 3-36  Nota: qui l’ACKn cumulativo riscontra i pacchetti fino a n incluso per comodità di spiegazione Go-back-N in action (in rosso i veri ACK cumulativi) Finestra di trasmissione Finestra di ricezione (|WR|=1) (|WT|=4) Trasmettitore Ricevitore (dopo la ricezione) 012345678 Invia pkt0 012345678 Invia pkt1 Invia pkt2 Ricevi pkt0, invia ack0(ack1) 0 1 2 3 4 5 6 7 8 012345678 Invia pkt3 X perdi Ricevi pkt1, invia ack1 (ack2) 0 1 2 3 4 5 6 7 8 012345678 ta (attendi) Ricevi pkt3, scartalo, 012345678 0 1 2 3 4 5 6 7 8 Ricevi ack0, invia pkt4 (re)invia ack1(ack2) 0 1 2 3 4 5 6 7 8 Ricevi ack1, invia pkt5 Ricevi pkt4, e scartalo, (re)invia ack1(ack2) 012345678 Ignora l’ACK duplicato Ricevi pkt5, e scartalo, 012345678 (re)invia ack1(ack2) pkt 2 timeout 012345678 Invia pkt2 012345678 Invia pkt3 012345678 Invia pkt4 Ricevi pkt2, invia ack2(ack3) 012345678 012345678 Invia pkt5 Ricevi pkt3, invia ack3(ack4) 012345678 Ricevi pkt4, invia ack4(ack5) 012345678 Ricevi pkt5, invia ack5(ack6) 012345678 3-37 D: quando vengono consegnati i pacchetti all’applicazione del ricevitore?  Nota: qui gli ACKn si riferiscono a un singolo pacchetto, Selective repeat in action non sono cumulativi Finestra di trasmissione Finestra di ricezione (|WR|=4) (|WT|=4) Trasmettitore Ricevitore (dopo la ricezione) 012345678 Invia pkt0 012345678 Invia pkt1 Invia pkt2 Ricevi pkt0, invia ack0 012345678 012345678 012345678 Invia pkt3 X perdi Ricevi pkt1, invia ack1 012345678 ta (attendi) Ricevi pkt3, mantieni 012345678 0 1 2 3 4 5 6 7 8Ricevi ack0, invia pkt4 in buffer, invia ack3 0 1 2 3 4 5 6 7 8Ricevi ack1, invia pkt5 Ricevi pkt4, mantieni in buffer, invia ack4 012345678 Registra l’arrivo di ack3 Ricevi pkt5, mantieni 012345678 in buffer, invia ack5 pkt 2 timeout 012345678 invia pkt2 012345678 Registra l’arrivo di ack4 012345678 Registra l’arrivo di ack5 Ricevi pkt2, invia ack2 012345678 012345678 D1: quando vengono consegnati i pacchetti all’applicazione del ricevitore? 3-38 D2: cosa succede quando arriva ack2? Relazione tra dimensione delle finestre e numeri di sequenza in selective repeat Finestra di trasmissione Finestra di ricezione 0123012 (dopo la ricezione) q Numero di 0123012 0123012 sequenza 0123012 0123012 di 2 bit X 0123012 X v 0, 1, 2, 3 X q |WT| = |WR| = 3 pkt0 timeout (re)invia pkt0 pkt0 è un duplicato, ma viene erroneamente accettato come pacchetto nuovo! 3-39  Spazio dei numeri di sequenza q Il numero di sequenza è ciclico WR v Con k bit si ha un periodo pari a 2k v Se |WT| = |WR|, serve |WT| ≤ 2k-1 = 2k /2 WT v Regola generale: |WT| + |WR| ≤ 2k 7 0 v Idea di base: se consegno correttamente tutti i segmenti, ma perdo tutti gli ACK, WT e WR devono rimanere al massimo 6 1 contigue, senza mai sovrapporsi q Nell’esempio: v k = 3 à 2k = 8 v |WT| = 3 , |WR| = 1 5 2 v Altrettanto validi: |WT| = 7 , |WR| = 1 |WT| = 3 , |WR| = 5 4 3 D1: nel Go-Back-N vale la stessa cosa? 3-40 Capitolo 3: Livello di trasporto r 3.1 Servizi a livello di trasporto r 3.5 Trasporto orientato alla r 3.2 Multiplexing e connessione: TCP demultiplexing m struttura dei segmenti m trasferimento dati affidabile r 3.3 Trasporto senza m controllo di flusso connessione: UDP m gestione della connessione r 3.4 Principi del trasferimento dati affidabile r 3.6 Principi del controllo di congestione r 3.7 Controllo di congestione TCP 3-41  TCP: Panoramica RFCs: 793, 1122, 1323, 2018, 2581, … q Protocollo punto-punto: q Full duplex: v un mittente, un destinatario v Flusso di dati bidirezionale nella stessa connessione q Flusso di byte affidabile e consegnato in ordine v MSS: dimensione massima di un segmento (maximum segment size) v Nessun “limite di messaggi” q Orientato alla connessione: q Con pipelining: v Setup della connessione tramite v Meccanismi di controllo di flusso e handshaking (scambio di messaggi di di congestione TCP definiscono controllo) la dimensione della finestra v Inizializza lo stato di mittente e v Le dimensioni delle finestre sono destinatario prima dello scambio di dinamiche (sia al mittente sia al dati destinatario) q Flusso controllato: v Usa ACK cumulativi v Il trasmettitore non sovraccaricherà il q Il controllo di congestione evita ricevitore di saturare la rete 3-42  Struttura dei segmenti TCP 32 bit URG: dati urgenti Conteggio per (generalmente non usato) Num. porta sorgente Num. porta destinazione byte di dati Numero di sequenza (non segmenti!) ACK: numero di riscontro valido Numero di ACK Lung. Non PSH: invia i dati adesso header usato U A P R S F Finestra di ricezione (generalmente non usato) Numero di checksum Puntatore ai dati urgenti byte che il RST, SYN, FIN: destinatario Opzioni (lunghezza variabile) comandi per desidera impostare e chiudere accettare la connessione Dati Checksum Internet (lunghezza variabile) (header TCP + dati + pseudoheader IP) 3-43 (Dimensione della) Finestra di ricezione (RWND) q RWND è un campo di 16 bit v Indica il numero di byte che il ricevitore può immagazzinare v Di conseguenza, rappresenta anche la massima quantità di dati in transito durante un RTT v Valore massimo: 216 Byte = 65536 Byte = 64 kByte q Assumiamo RTT = 100 ms v Dipende dalla velocità del link quanti dati possono essere "in volo" (ricordate il bandwidth-delay product!!) Bandwidth Bandwidth-delay product T1 (1.5 Mbps) 18 kB Ethernet (10 Mbps) 122 kB T3 (45 Mbps) 549 kB FastEthernet (100 Mbps) 1.2 MB STS-48 (2.5 Gbps) 29.6 MB v RWND può essere aumentato usando un meccanismo di “scalatura” (ovvero decidendo che il numero non conteggia Byte, ma multipli di Byte) 3-44  Numeri di sequenza e ACK di TCP Numeri di sequenza: Host A Host B m “Numero” del primo byte del segmento nel flusso di byte L’utente Seq=42 digita , ACK= 79, dat ACK: ‘C’ a = ‘C’ L’host m Numero di sequenza del invia ACK per prossimo byte atteso la ricezione ta = ‘C’ dall’altro lato a ACK=43, d di ‘C’ e q=79, m ACK cumulativo Se ritrasmette ‘C’ al mittente D: Come fa il destinatario a gestire L’host invia ACK segmenti fuori sequenza? per la ricezione Seq=43 m R: la specifica TCP non lo della ‘C’ , ACK= 80 dice – dipende reinviata dall’implementazione Una semplice applicazione Telnet tempo (ricordate: Telnet invia un’eco di ogni cosa inviata dal mittente, eccetto le password) 3-45  Setup della connessione TCP q La procedura di setup della connessione TCP si chiama "three-way handshake“ q Host A (il client che inizia la connessione): segmento con flag SYN a 1 v Porta sorgente (= A), Porta destinazione (= B) v Numero di sequenza iniziale (= x) q Host B (server in attesa di connessioni): segmento con flag SYN e ACK a 1 v Porta sorgente (= B), Porta destinazione (= A) v Numero di sequenza iniziale (= y) v Numero di ACK (= x + 1) q Host A: segmento con il flag ACK a 1 v Porta sorgente (= A), Porta destinazione (= B) v Numero di ACK (= y + 1) D: perché l’handshake è proprio a 3 vie? 3-46  ISN = TCP connection setup Initial A B Sequence Number SYN(PortA, PortB, ISN-A = x) SYN | ACK(PortB, PortA, ISN-B = y, ACK = x+1) ACK(PortA, PortB, ACK = y+1) time 3-47 3-48 3-49 Lunghezza massima di un segmento TCP (Maximum Segment Size, MSS) q TCP lavora per byte, ma non manda mai un singolo byte alla volta a meno che non sia forzato a farlo v Cerca invece di inviare segmenti lunghi quanto un MSS q L’MSS dipende da un parametro del livello di rete sottostante (es. IP) che si chiama Maximum Transfer Unit (MTU) v A sua volta, l’MTU del livello di rete dipende dall’MTU del livello data link v I parametri sopra dipendono dai link lungo tutto il percorso in Internet q L’MSS si riferisce alla lunghezza del solo payload! (i dati trasportati dal segmento) q Come scegliere l’MSS? v Non ci sono meccanismi per comunicarlo v "Trial and error": si tenta con MSS sempre più grandi, finché non ci si accorge che qualche segmento viene perso In molti casi si riceve una comunicazione esplicita di incompatibilità, ma in molti altri casi… no q Default: MSS = 1460 Byte (1500: MTU di Ethernet - 40 Byte di header tra TCP e IP) q Minimo: MSS = 536 Byte (IP richiede una minima MTU di 576 Byte = 536 + 40) 3-50 Chiusura (“tear-down”) di una connessione TCP q Le connessioni TCP sono sempre bidirezionali v Bisogna chiuderle in entrambe le direzioni q Procedura “gentile”: inviare un segmento TCP con flag FIN a 1 v Il ricevitore invia un ACK v La connessione è semi-chiusa (“half-closed”) q Si possono ancora mandare dati nella direzione opposta v Gli ACK inviati su una connessione semi-chiusa non costituiscono traffico dati q La chiusura è completa solo quando si invia un FIN e si riceve un ACK anche nell’altra direzione 3-51 Chiusura (“tear-down”) di una connessione TCP A B FIN(PortA, PortB) FIN | ACK(PortB, PortA) DATA() ACK() DATA() ACK() FIN(PortB, PortA) FIN | ACK(PortA, PortB) 3-52 time Chiusura (“tear-down”) di una connessione TCP q Chiusura “brusca”: reset (RST) q RST si usa per resettare connessioni non gestibili o che si trovano in uno stato errato v Esempio: ricevo un ACK per una connessione mai aperta q Uno degli host invia un segmento con flag RST a 1 v Entrambi gli host liberano le risorse allocate dal sistema operativo v D: E se il RST si perde? q I server possono usare il RST per chiudere connessioni B velocemente A RST(PortA, PortB) time 3-53 TCP: tempo di andata e ritorno e Retransmission TimeOut (RTO) D: come impostare il valore D: come stimare RTT? del timeout di TCP? r SampleRTT: tempo misurato r Più grande di RTT dalla trasmissione del segmento m Ma RTT varia fino alla ricezione di ACK m Ignora le ritrasmissioni r Troppo piccolo: timeout prematuro r SampleRTT varia, quindi occorre m Ritrasmissioni non una stima “più livellata” di RTT necessarie m Media di più misure recenti, r Troppo grande: non semplicemente il valore reazione lenta alla perdita dei corrente di SampleRTT segmenti 3-55 TCP: tempo di andata e ritorno e Retransmission TimeOut (RTO) EstimatedRTT = (1 - a)*EstimatedRTT + a*SampleRTT r Media mobile esponenziale ponderata r L’influenza dei vecchi campioni diminuisce esponenzialmente r Valore tipico: a = 0,125 3-56 Esempio di stima di RTT RTT tra gaia.cs.umass.edu e fantasia.eurecom.fr 350 300 RTT (millisecondi) 250 200 150 100 1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106 tempo (secondi) Campione RTT Stime livellate di RTT 3-57 TCP: tempo di andata e ritorno e Retransmission TimeOut (RTO) Impostazione dell’RTO r EstimatedRTT più un “margine di sicurezza” m Grande variazione di EstimatedRTT -> margine di sicurezza maggiore r Stimare innanzitutto di quanto SampleRTT si discosta da EstimatedRTT: DevRTT = (1-b)*DevRTT + b*|SampleRTT - EstimatedRTT| (tipicamente, b = 0.25) Poi impostare l’intervallo di timeout: RTO = EstimatedRTT + 4*DevRTT 3-58 Inizializzazione (RFC 6298) q Retransmission TimeOut (RTO) = 1 secondo v O un qualunque valore maggiore di questo q Quando si ha una sola misura di RTT, si pone: v EstimatedRTT = SampleRTT v DevRTT = RTT / 2 3-59 TCP: controllo di flusso Processo L’applicazione potrebbe dell’applicazione prelevare i dati dal buffer TCP Applicazione più lentamente… TCP socket Sistema Buffer del ricevitore operativo … di quanto il codice che esegue le regole di TCP sia capace di Codice inviarli TCP q Controllo di flusso v Premette al ricevitore di Codice IP controllare la velocità di trasmissione del mittente Dal mittente v Troppi dati, troppo in fretta Pila (“stack”) protocollare al ricevitore 3-60 TCP: controllo di flusso q Il ricevitore comunica quanto spazio libero ha nel proprio All’applicazione buffer di ricezione, includendo il valore della RWND nell’header TCP di ogni segmento che invia RcvBuffer Dati nel buffer al mittente RWND Spazio libero nel buffer q Il mittente limita la quantità di dati “in volo” (ancora non ACKati) al valore di RWND Dati contenuti nei segmenti TCP q Garantisce che il buffer del Buffering al ricevitore ricevitore non vada in overflow (lo costringerebbe a scartare pacchetti corretti per mancanza di spazio) 3-61 Capitolo 3: Livello di trasporto r 3.1 Servizi a livello di trasporto r 3.5 Trasporto orientato alla r 3.2 Multiplexing e connessione: TCP demultiplexing m struttura dei segmenti m trasferimento dati affidabile r 3.3 Trasporto senza m controllo di flusso connessione: UDP m gestione della connessione r 3.4 Principi del trasferimento dati affidabile r 3.6 Principi del controllo di congestione r 3.7 Controllo di congestione TCP 3-62 Principi del controllo di congestione Congestione: q Informalmente: “troppi trasmettitori stanno mandando troppi dati e la rete non riesce a gestire tutto questo traffico” q E’ diverso dal controllo di flusso! q Come si manifesta: v Pacchetti persi (buffer overflow nei router) v Ritardi lunghi (accodamento nei buffer dei router) q Nella top-10 dei problem dell’informatica moderna 3-63 Modelli per sistemi a coda (non materiale d’esame) q Un sistema a coda comprende una “fila d’attesa” e un server v Tasso (frequenza) di arrivo 𝜆: numero medio di pacchetti (o più in generale: di unità di lavoro) che entra nella coda per unità di tempo v Tasso (frequenza) di servizio 𝜇: tempo medio richiesto dal server per trasmettere un pacchetto (in generale: concludere un lavoro) q Arrivi e servizi avvengono secondo una distribuzione statistica ! ! v Es.: M/M/1: Arrivi ~ exp , Tempi servizio ~ exp , 1 server " # v M = “Markovian” à si riferisce alla distribuzione esponenziale 𝜆 𝜇 3-64 Modelli per sistemi a coda ritardo (non materiale d’esame) q Si possono calcolare le proprietà del sistema: lin R/2 v Per un sistema M/M/1: ! Definiamo il carico del server come 𝜌 = " #! La lunghezza media della coda è : 𝐿 = (per 𝜌 < 1) $%# La probabilità che ci siano N pacchetti in coda è : 𝜋𝑁 = (1 − 𝜌)𝜌𝑁 v Es.: 𝜆 = 0.8 pkt/s, 𝜇 = 1 pkt/s (M/M/1: medie di distribuzioni esponenziali) 𝐿 = 3.2 pkt 𝜋0 = 0.2, 𝜋1 = 0.16, 𝜋2 = 0.128, 𝜋3 = 0.1024, … q Ricordate: 𝜆 e 𝜇 sono solo delle medie statistiche, non delle costanti v Qualche volta passa più tempo o meno tempo tra arrivi e tra servizi q Anche se 𝜆 è molto piccolo e 𝜇 molto grande, c’è una probabilità ≠ 0 (magari bassa) che i pacchetti si accodino e magari vengano scartati 3-65 Cause/costi della congestione: Scenario 1 q Due trasmettitori, due ricevitori q Throughput massimo per q Un router, buffer infinito connessione: R/2 q Capacità del link di uscita: R q Ritardi elevati se il tasso di arrivo lin si avvicina a R/2 q No ritrasmissioni R/2 Dati originali: lin throughput: lout lout Host A Buffer condiviso di lin R/2 dimensioni infinite ritardo Host B lin R/2 3-66 Cause/costi della congestione: Scenario 2 q Un router, buffer di dimensione finita q Il mittente ritrasmette i pacchetti finiti in timeout v Tasso di arrivo dall’applicazione al mittente: lin , tasso percepito dall’applicazione del destinatario: lout v Al livello di trasporto, il tasso di arrivo include le ritrasmissioni! l'in > lin lin : dati originali lout l'in: dati originali, più le eventuali ritrasmissioni Host A Buffer condiviso di Host B dimensioni finite 3-67 Cause/costi della congestione: Scenario 2 Caso ideale: conoscenza perfetta della situazione R/2 q Il mittente invia dati solo se il router ha spazio nel buffer lout q Risultato ideale l'in R/2 lin : dati originali lout copia l'in: dati originali, più le eventuali ritrasmissioni Host A Spazio libero nel buffer! Buffer condiviso di Host B dimensioni finite 3-68 Cause/costi della congestione: Scenario 2 Caso realistico: conoscenza limitata della rete R/2 q La congestione causa ritardi R/4 lout q Se al mittente scatta un timeout, il mittente invia una seconda copia dello stesso pacchetto v Vengono consegnate entrambe, dimezzando il throughput l'in R/2 lin copia lout timeout l'in Host A Spazio libero nel buffer! Host B 3-69 Cause/costi della congestione: Scenario 2 Idealizzazione: il mittente reinvia pacchetti solo se è sicuro che si siano persi lungo la strada (ovvero, i timeout sono molto lunghi) lin : dati originali copia lout l'in: dati originali, più le eventuali ritrasmissioni Host A Buffer già pieno! Host B 3-70 Cause/costi della congestione: Scenario 2 Idealizzazione: il mittente reinvia pacchetti solo se è sicuro che si siano persi lungo la strada (ovvero, i timeout sono molto lunghi) q Throughput potenzialmente migliore R/2 v Dipende sempre da perdite e timeout R/3 lout q Take-home message: congestione à ritrasmissioni da gestire accuratamente lin : dati originali l'in R/2 lout l'in: dati originali, più le eventuali ritrasmissioni Host A Spazio libero nel buffer! Host B 3-71 Cause/costi della congestione: Scenario 3 q Rotte multi-salto con perdite v D: che succede a lout quando lin e l’in aumentano senza controllo? v R: quando l’in aumenta, tutti o quasi i pacchetti blu in arrivo alla coda in alto a destra vengono scartati, lout à 0 Host A lin: dati originali lout Host B l'in: dati originali, più le eventuali ritrasmissioni Buffer condiviso di dimensioni finite Host D Host C 3-72 Cause/costi della congestione: Scenario 3 Un altro “costo” della congestione: q Ogni volta che si scarta un pacchetto, tutte le risorse usate per portare il pacchetto fino a quel punto risultano sprecate! R/2 lout l'in R/2 3-73 Cause/costi della congestione: Riassunto q Buffer infiniti delay v No perdite, ma se tasso di arrivo = tasso di servizio… v Costo: ritardi molto elevati q Ritardi dovuti alla congestione: timeout lin R/2 v Costo: spreco di risorse R/2 Ritrasmissioni inutili R/4 lout Nel grafico a destra: 1 ritrasmissione per pacchetto q Pacchetti scartati a causa della congestione v Costi: ritrasmissioni l'in R/2 R/2 v Più lavoro richiesto per ottenere lo stesso throughput percepito a livello applicazione R/3 lout v Tale throughput potrebbe ridursi a zero sprecando gli sforzi fatti l'in R/2 3-74 Capitolo 3: Livello di trasporto r 3.1 Servizi a livello di trasporto r 3.5 Trasporto orientato alla r 3.2 Multiplexing e connessione: TCP demultiplexing m struttura dei segmenti m trasferimento dati affidabile r 3.3 Trasporto senza m controllo di flusso connessione: UDP m gestione della connessione r 3.4 Principi del trasferimento dati affidabile r 3.6 Principi del controllo di congestione r 3.7 Controllo di congestione TCP 3-75 Controllo di congestione in TCP: attenzione! q Non c’è un solo algoritmo in TCP per gestire la congestione q Molte varianti sono state proposte nel tempo, ciascuna per rimuovere una limitazione delle versioni precedenti v TCP Tahoe, Reno, New Reno, Vegas, Westwood, CUBIC, BBR… q L’implementazione di TCP spesso dipende dal sistema operativo q Ora ci concentriamo su una versione specifica descritta nel libro v Anche questa versione non è del tutto completa q In ogni caso, non dite mai a nessuno che “di TCP ce n’è uno solo” q Le implementazioni di TCP ragionano in byte v Per semplicità, noi nel seguito ragioneremo in segmenti quanto più possibile 3-76 Controllo di congestione q E’ una delle caratteristiche più importanti di TCP v Adatta il tasso di trasmissione alle condizioni di rete v Evita di saturare e congestionare la rete q Diversi approcci possibili v Controllo di congestione end-to-end Non coinvolge la rete Si capisce se c’è congestione osservando perdite di pacchetti e ritardi Metodo usato da TCP v Controllo di congestione assistito dalla rete I router forniscono feedback agli host sullo stato della rete Es. un singolo bit per indicare la congestione (SNA, DECbit, TCP/IP Explicit Congestion Notification (ECN), ATM) 3-77 TCP congestion control: Additive Increase Multiplicative Decrease (AIMD) q Approccio: il mittente aumenta il tasso di trasmissione (cioè la dimensione della finestra) cercando di occupare la banda disponibile, finché non si rilevano perdite v Additive increase: aumenta la finestra di 1 MSS ogni RTT finché non ci sono perdite v Multiplicative decrease: riduci la finestra (tipicamente della metà) quando si rileva una perdita Si aumenta linearmente la dimensione della finestra… Dimensione della congestion window del mittente TCP …finché non ci sono perdite (e allora la si riduce di metà) tempo 3-78 Perché usare AIMD? q Per ottenere equità (fairness): se K sessioni TCP si dividono uno stesso link di banda R che fa da “collo di bottiglia”, le sessioni dovrebbero percepire tutte la stessa banda R/K Connessione TCP 1 Router con link “collo di bottiglia” di banda R Connessione TCP 2 3-79 Perché usare AIMD? (cont.) Due sessioni in competizione sullo stesso link di banda R: grafico in cui la banda della connessione 1 è sull’asse x, e la banda della connessione 2 è sull’asse y q Tracciamo sul grafico come cambia la banda delle connessioni nel tempo v Additive increase fa aumentare linearmente la banda di entrambe (pendenza = 1) q Multiplicative decrease reduce il throughput proporzionalmente (cioè, maggior diminuzione per la connessione che stava usando più banda) R Banda perfettamente ripartita a metà Connection 2 throughput Additive increase Perdita: riduci la finestra della metà 3-80 Connection 1 throughput R Perché usare AIMD? (cont.) Due sessioni in competizione sullo stesso link di banda R: grafico in cui la banda della connessione 1 è sull’asse x, e la banda della connessione 2 è sull’asse y q Tracciamo sul grafico come cambia la banda delle connessioni nel tempo v Additive increase fa aumentare linearmente la banda di entrambe (pendenza = 1) q Multiplicative decrease reduce il throughput proporzionalmente (cioè, maggior diminuzione per la connessione che stava usando più banda) R Connection 2 throughput 3-81 Connection 1 throughput R Perché usare AIMD? (cont.) Due sessioni in competizione sullo stesso link di banda R: grafico in cui la banda della connessione 1 è sull’asse x, e la banda della connessione 2 è sull’asse y q Tracciamo sul grafico come cambia la banda delle connessioni nel tempo v Additive increase fa aumentare linearmente la banda di entrambe (pendenza = 1) q Multiplicative decrease reduce il throughput proporzionalmente (cioè, maggior diminuzione per la connessione che stava usando più banda) R Banda perfettamente ripartita a metà Connection 2 throughput Additive increase Perdita: riduci la finestra della metà Additive increase Perdita: riduci la finestra della metà 3-82 Connection 1 throughput R Meccanismi per il controllo di congestione q Il controllo di congestione gestisce l’adattamente della cosiddetta finestra di congestione (congestion window, CWND) v CWND = numero di byte che il trasmettitore può inviare nella rete q In TCP ci sono diversi algoritmi per adattare la CWND q In assenza di perdite v Slow start v Congestion avoidance q Per migliorare l’efficienza di TCP in caso si verifichino perdite: v Fast retransmit v Fast recovery q In ogni caso, |WT| = min(CWND, RWND) = min(CWND, |WR|) 3-83 Ricapitoliamo il significato delle finestre q Finestra: insieme di dati (byte, o segmenti) q Finestra di ricezione, RWND v Insieme di dati che può essere gestito dal ricevitore v La sua dimensione è il limite massimo di dati che il ricevitore può immagazzinare nel buffer di ricezione q Finestra di congestione, CWND v Insieme di dati che si possono inviare nella rete v La sua dimensione si adatta alla quantità massima di dati che il trasmettitore pensa di poter inviare senza sovraccaricare la rete q Finestra di trasmissione v Insieme di dati che si possono inviare senza sovraccaricare la rete e senza saturare il ricevitore v Proprio per questo, |WT| = min(CWND, RWND) = min(CWND, |WR|) v D: da che relazione sono legati i valori |WT| e |WR| ? 3-84 TCP: Slow start e congestion avoidance q Slow start v Per ogni ACK valido ricevuto, aumento CWND di 1 MSS v Così, CWND aumenta esponenzialmente nel tempo Inizio con CWND = 1 MSS Ricevo 1 ACK dopo 1 RTT à CWND = 2 MSS Ricevo 2 ACK dopo 1 RTT à CWND = 4 MSS v Quando CWND raggiunge o supera una soglia (slow start threshold, SSTHRESH) à passa alla modalità congestion avoidance q Congestion avoidance MSS v Per ogni ACK valido ricevuto, aumento la CWND di MSS ∗ CWND 1 O se ragioniamo in segmenti, aumento la CWND di segmenti CWND v In alter parole, per ogni RTT in cui ricevo esattamente tutti gli ACK attesi (in totale CWND ACK), aumento CWND di 1 MSS (1 segmento) v Aumento lineare di CWND nel tempo 3-85  Esempio di slow start A B 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 18 4 CWND 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 18 5 6 8 6 7 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 18... 4 10 2 11 time... RTT 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 18... 18 3-86  Esempio di congestion avoidance A B 5 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 18 6 CWND 7 8 8 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 18 9 6 10 11 4 2 12 13 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 18 time 14 RTT 15 16 3-87 Parametri su cui potete agire q Finestra di congestione (CWND) v Aumentandola, vi fidate della capacità della rete di gestire CWND il traffico q Slow start threshold (SSTHRESH) v Diminuendola, riducete la durata della fase di slow start, SSTHRESH passate più rapidamente a congestion avoidance, e favorite un approccio più prudente q Retransmission timeout (RTO) RTO v Aumentandolo, date più tempo alla rete di consegnare i segmenti e riducete il traffico delle ritrasmissioni q WLOW e WUP WLOW WUP v Potete ritardarne lo spostamento (ad esempio per tenere memoria di pacchetti per i quali non avere ricevuto ACK) 3-88 Algoritmo della fase Slow start q Inizializzazione: v CWND = 1 MSS (o semplicemente 1 segmento) v SSTHRESH = RWND (o RWND/2 a seconda delle implementazioni) q Se ricevo un ACK valido: v CWND = CWND + 1 MSS v Sposto WLOW al primo byte (o segmento) non ACKed v Se CWND ≥ SSTHRESH à passo alla fase Congestion Avoidance v Trasmetto nuovi segmenti come consentito da CWND q Se scatta un timeout: v Abbasso SSTHRESH = MAX(CWND / 2, 2) v Aumento RTO = RTO * 2 (questo passaggio manca nel libro) v Reimposto CWND = 1 v Ritrasmetto il segmento che ha causato il timeout 3-89 Algoritmo della fase Congestion avoidance q Se ricevo un ACK valido: MSS v CWND = CWND + MSS ∗ (ricordate: valori in byte!) CWND v Sposto WLOW al primo segmento non ACKed v Trasmetto nuovi segmenti come consentito da CWND q Se scatta un timeout: v Passo a slow start v Abbasso SSTHRESH = MAX(CWND / 2, 2) v Aumento RTO = RTO * 2 (questo passaggio manca nel libro) v Reimposto CWND = 1 v Ritrasmetto il segmento che ha causato il timeout 3-90  RTO è un buon indicatore di errori? A B 10 q Supponiamo che in questo 11 12 scenario siamo in congestion 13 14 X A11 avoidance A11 DupACK A11 DupACK v CWND = 5, WT = [10, …, 14] 15 A11 DupACK q Dopo il RTO per 11 ignora ignora ignora A11 DupACK v Ritrasmetto 11 v CWND = 1 ignora q Dopo ACK 16 ~ Scade il RTO (timeout) ~ ~ ~ v CWND = 1, WT = Ritrasmetto 11 q Abbiamo ignorato la RTO = RTO*2 A16 sequenza di ACK duplicati Fine recovery v Ci stavano dicendo qualcosa? 16 3-91 Prestazioni di questa versione di TCP 3-92  Fast retransmit … q Gli ACK duplicati, in fondo, ci dicono che la rete funziona q Idea di base del fast recovery: v Diamo fiducia alla rete: se funziona, continuiamo a trasmettere q Alla ricezione del 3o ACK duplicato v Ritrasmetto il segmento indicato dall’ACK (“fast retransmit”) v Entro in una fase di “fast recovery” q Mi ricordo il valore di WUP per sapere quanti segmenti sono “in volo” v RECOVER = WUP v Questo mi permetterà di capire quando la fase è completata 3-93 … e Fast recovery q Alla ricezione del 3o ACK duplicato v Abbasso SSTHRESH = CWND / 2 v Suppongo di aver perso solo quel segmento e imposto CWND = SSTHRESH + 3 MSS Se quindi CWND me lo permette, trasmetto altri segmenti v NON SPOSTO il puntatore WLOW q Se arrivano altri ACK duplicati v CWND = CWND + 1 MSS Se CWND me lo permette, trasmetto altri segmenti v NON SPOSTO il puntatore WLOW q Quando arriva un ACK valido (che include un riscontro per il segmento RECOVER) v CWND = SSTHRESH v Passo alla fase Congestion avoidance v Sposto WLOW al primo segmento non ACKed q Se arriva un ACK parziale (conferma un segmento precedente a RECOVER) v Ritrasmetto il primo segmento per cui non ho un ACK v Riduco CWND = CWND – numero di segmenti ACKed + 1 v Sposto WLOW al primo segmento non ACKed 3-94 Fast recovery: esempio WT = [10, … , 10 A B 14] 11 q Supponiamo ancora che in questo scenario 12 siamo in congestion avoidance 13 X 14 A11 v CWND = 5, WT = [10, …, 14] A11 DupACK 1 q Dopo ACK 11 A11 DupACK 2 WT = [11, … , 15 A11 DupACK 3 v WT = [11, …, 15]: invio 15 15] Dup ACK 1 q Dopo 3 ACK11 duplicati: Fast Recovery Dup ACK 2 v SSTHRESH = CWND / 2 = 2 FR Dup ACK 3 A11 DupACK 4 WT = [11, … , v CWND = SSTHRESH + 3 = 5 15] Ritrasmetto 11 v WT = [11, …, 15] WT = [11, … , 16 A16 q Dopo il 4o ACK 11 duplicato CA 16] Fine recovery A17 v CWND = CWND + 1 WT = [16, 17 v WT = [11, …, 16]: trasmetto 16 17] WT = [17, 18]18 A18 q Dopo ACK 16 WT = [18, 19, 19 v CWND = SSTHRESH = 2 20] 20 A19 v Passo a congestion avoidance … A20 v WT = [16, 17]: trasmetto 17 A21 3-96 TCP fast retransmit e fast recovery 3-97 Macchina a stati dell’algoritmo di controllo di congestione in TCP new ACK duplicate ACK cwnd = cwnd + MSS * (MSS/cwnd) dupACKcount++ new ACK dupACKcount = 0 cwnd = cwnd+MSS transmit new segment(s), as allowed dupACKcount = 0 L transmit new segment(s), as allowed cwnd = 1 MSS ssthresh = 64 KB cwnd > ssthresh dupACKcount = 0 slow L congestion start timeout avoidance ssthresh = cwnd/2 cwnd = 1 MSS duplicate ACK timeout dupACKcount = 0 dupACKcount++ ssthresh = cwnd/2 retransmit missing segment cwnd = 1 MSS dupACKcount = 0 retransmit missing segment timeout ssthresh = cwnd/2 cwnd = 1 New ACK dupACKcount = 0 dupACKcount == 3 retransmit missing segment cwnd = ssthresh dupACKcount == 3 dupACKcount = 0 ssthresh= cwnd/2 ssthresh= cwnd/2 cwnd = ssthresh + 3 cwnd = ssthresh + 3 retransmit missing segment retransmit missing segment fast recovery duplicate ACK cwnd = cwnd + MSS transmit new segment(s), as allowed 3-98 Un’altra macchina a stati TCP Source: S. Jero, et al. "Automated attack discovery in TCP congestion control using a model-guided approach." Proc. of Network and Distributed System Security Symp., San Diego, CA, USA. 2018. 3-99 Formula approssimata per il throughput di TCP q From Mathis et al., “The macroscopic behavior of the TCP congestion avoidance algorithm”, 1997 +,, / vThr 𝑅𝑇𝑇, 𝑝 [Gbit/s] < 4 -.. 0 v p = Probabilità di perdere un pacchetto v MSS = maximum segment size [Byte] v RTT = round-trip time [s] q Es: RTT = 220 ms, MSS = 1460 Byte, p = 10"## à THR = 2.1 Gbit/s 3-100 Problemi di equità (fairness) in TCP Fairness e UDP Fairness con connessioni TCP q Le applicazioni multimediali parallele non usano TCP quasi mai q Le applicazioni possono aprire v Non desiderano ridurre il tasso più connessioni in parallelo tra di trasmissione per via del due host controllo di congestione v I web browser lo fanno q Invece usano UDP: q Es.: link con banda R e v Inviano audio e video a un tasso 9 connessioni TCP esistenti costante v Una nuova applicazione apre v Tollerano o diversamente 1 TCP, ottiene una banda R/10 compensano le perdite di v Una nuova applicazione apre pacchetti 9 TCP, ottiene una banda R/2 3-101 Futuro di TCP q La versione di TCP che abbiamo studiato è loss-based v Ma quando avviene una perdita è già «tardi» per reagire 3- 102 TCP e controllo di congestione q Il controllo della congestione di TCP stabilisce di rallentare la trasmissione basandosi solo sulle indicazioni dei pacchetti persi q Questo ha funzionato bene per molti anni v I piccoli buffer degli switch Internet e dei router erano ben adattati alla bassa larghezza di banda dei collegamenti Internet q Ad oggi abbiamo bisogno di un algoritmo che risponda alla congestione effettiva, piuttosto che alla perdita di pacchetti q Alcune soluzioni: v CUBIC v BBR v QUIC 3-103 CUBIC q Algoritmo di controllo della congestione di rete in TCP q In particolare, fa variare la lunghezza della finestra di congestione secondo una funzione cubica del tempo v Migliora la scalabilità e la stabilità su reti veloci e a lunga distanza q Utilizzato da anni come impostazione predefinita nel kernel Linux v Windows lo ha adottato solo nel 2017 3-104 Principi di CUBIC q Per un migliore utilizzo e stabilità della rete, CUBIC usa entrambi i profili concavo e convesso di una funzione cubica per aumentare la dimensione della finestra di congestione q Dove e, da RFC 8312, 𝐶 = 0.4 e 𝛽 = 0.7 q Dopo una congestione, la finestra è scalata di 𝛽, non di 0.5 v CUBIC bilancia scalabilità e velocità di convergenza q TCP-friendly: non penalizza troppo i flussi TCP standard che condividono lo stesso bottleneck link v https://www.cs.princeton.edu/courses/archive/fall16/cos561/papers/Cubic08.pdf 3-105 Funzione cubica per la CWND in CUBIC 3-106 CUBIC 3- 107 BBR q Bottleneck Bandwidth and Roundtrip propagation time (BBR) q Algoritmo per il controllo della congestione (Google, 2016) q BBR non si basa più sulle perdite ma stima due parametri: v La banda sul link «collo di bottiglia» (bottleneck bandwidth) v L’RTT q Idea: trasmettere pacchetti a una velocità che non «dovrebbe» incontrare accodamenti 3-108 BBR q Progettato per rispondere alla congestione effettiva, piuttosto che alla perdita di pacchetti v BBR modella la rete per inviare alla velocità della larghezza di banda disponibile q Incentrato sul miglioramento delle prestazioni della rete quando la rete non è molto buona q Server-side algorithm! v Non richiede al client di implementare BBR q Concetto di pacing: invece di inserire nella CWND (e inviare) tutti i pacchetti consentiti, li inserisco al ritmo al quale può inviarli il nodo più lento (a monte del bottleneck link) 3-109  Ricerca del punto ottimale (effettuato cambiando il «pacing gain») 3-110 Performance 3-111 Maggiore produttività q Secondo Google, in un server con un collegamento Ethernet a 10 Gigabit che invia dati lungo un percorso con un RTT di 100 ms e tasso di perdita di pacchetti dell’1% si ha come throughput: v 3,3 Mbit/s con CUBIC v 9100 Mbit/s con BBR q Ottimo insieme ad HTTP/2, che usa una singola connessione v Il risultato finale è un traffico più veloce sulle odierne dorsali ad alta velocità e una larghezza di banda notevolmente aumentata e tempi di download ridotti 3-112 Latenza inferiore q BBR consente riduzioni significative della latenza nelle reti dell'ultimo miglio che connettono gli utenti a Internet q Consideriamo un collegamento con 10 Mbps, un tempo di andata e ritorno di 40 ms e un tipico buffer di collo di bottiglia di 1000 pacchetti v CUBIC ha un tempo di andata e ritorno medio di 1090 ms v BBR di solo 43 ms 3-113 BBR: Velocità di trasmissione 3-114  Reno vs CUBIC vs BBR Pacing gain = 1.25 Pacing gain = 1 Pacing gain = 0.75 Figura da: https://blog.apnic.net/2017/05/09/bbr-new-kid-tcp-block/ 3-115  BBR e CUBIC insieme F. Vaccari, «Fairness di algoritmi per il controllo della congestione in protocolli TCP», Tesi UniTN, 2022. 3-116 Per approfondimenti q BBR Congestion-Based Congestion Control (N. Cardwell, Y. Cheng, C. S. Gunn, S. H. Yeganeh, Van Jacobson) ACM Queue, 2016 https://dl.acm.org/doi/pdf/10.1145/3012426.3022184 3-117 QUIC q Inizialmente progettato da Google nel 2012 q Dapprima acronimo di Quick UDP Internet Connections, IETF lo considera semplicemente il nome del protocollo q Due obiettivi v Evitare fenomeni di Head-of-Line blocking Utilizzando di base UDP invece di TCP v Ridurre la latenza rispetto alle connessioni TCP Compattando i messaggi per ridurre l’overhead di connessione q Può essere implementato a livello applicativo anziché nel kernel v Chrome, Firefox, Safari, … q Protocollo di livello trasporto del futuro HTTP/3 3-118 HTTP/2 vs. QUIC 3-119 HTTP/2 (e HoL blocking) vs. QUIC Già passati Bloccati da 4 X X 3-120 Ridurre l’overhead di connessione q Molte connessioni HTTP richiederanno TLS per funzioni di sicurezza (autenticazione, crittografia, …) q QUIC incorpora nel processo di handshake iniziale lo scambio delle chiavi di configurazione e dei protocolli supportati q Quando un client apre una connessione, il pacchetto di risposta include anche i dati per i pacchetti futuri necessari all'uso della crittografia in TLS q Si elimina la necessità di impostare la connessione TCP e poi negoziare il protocollo di sicurezza tramite altri pacchetti q Altri protocolli possono essere serviti nello stesso modo, combinando insieme più passi in una singola richiesta-risposta v Questi dati possono poi essere utilizzati sia per le richieste successive nella configurazione iniziale, sia per le richieste future 3-121 Dialogo «istantaneo» 3-122 UDP o TCP? q TCP è ampiamente adottato e spesso le infrastrutture internet sono «sintonizzate» per TCP e limitano o bloccano UDP v D: perché? q Google ha condotto degli esperimenti esplorativi e ha scoperto che solo un piccolo numero di connessioni sono state bloccate in questo modo q Perciò lo stack di rete di Chromium apre contemporaneamente sia una connessione QUIC sia una connessione TCP v Questo permette un fallback con una latenza trascurabile 3-123 Eventi di cambio rete q Con TCP: v Le socket sono identificate dalla quadrupla (IP sorgente, porta sorgente, IP destinazione, porta destinazione) v Tutte le connessioni vanno in timeout e vengono ristabilite q Invece, QUIC include un ID di connessione al server, che non dipende dalla fonte o dalla rete usata q Si può così ristabilire la connessione inviando nuovamente un pacchetto contenente tale ID v L’ID sarà ancora valido anche se l'indirizzo IP dell'utente cambia 3-124 Capitolo 3: Riassunto r Principi alla base dei servizi del livello di trasporto: m Multiplexing, demultiplexing m Trasferimento dati affidabile m Controllo di flusso m Controllo di congestione Prossimamente: r Implementazione in Internet r Lasciare la “periferia” m UDP della rete (livelli di applicazione e di m TCP trasporto) r Protocolli di trasporto moderni r Entrare nel r CUBIC r BBR “cuore” della rete r QUIC 3- 125