5 Protocolli Trasporto Parte2

1

Modulo 7:Protocollo TCP

Parte 5

Protocolli e Architetture di Rete 2009/2010 – Livello Trasporto 5.65

Livello 4 (transport)[ TCP ]

• Protocollo che fornisce un livello di trasporto affidabile ed orientato alla connessione

• Servizi aggiuntivi rispetto a UDP– orientato alla connessione: comprende le fasi di instaurazione,

utilizzo e chiusura della connessione– orientato al flusso di dati: considera il flusso di dati dall’host

mittente fino al destinatario ( considera sia rete sia host terminali)– trasferimento con buffer: i dati sono memorizzati in un buffer e poi

inseriti in un pacchetto quando il buffer è pieno– connessione full duplex (bi-direzionale): una volta instaurata una

connessione, è possibile il trasferimento contemporaneo in entrambe le direzioni della connessione

2


Cosa il TCP non garantisce

• Comunicazioni in tempo reale

• Garanzia di disponibilità di banda tra mittente e destinatario

• Multicast (un mittente, molti destinatari) affidabile


TCP

Transmission Control ProtocolRFC: 793, 1122, 1323, 2018, 2581, 2988

Offre un livello di trasporto affidabile

ed orientato alla connessione su di un

canale inaffidabile

3


Problemi da affrontare a livello TCP• Eterogeneità degli host e dei processi in comunicazione

c’è bisogno di un meccanismo per attivare e concludere una comunicazione in modo esplicito per entrambi

• Eterogeneità dei tempi di trasmissionec’è bisogno di un meccanismo di timeout adattativo

• Possibilità di ritardi molto lunghi nella rete c’è bisogno di gestire il possibile arrivo di pacchetti molto vecchi

• Possibilità di avere un host destinatario con capacità molto diversa dall’host mittente c’è bisogno di gestire capacità dei nodi eterogenee

• Possibilità di avere capacità di rete molto diverse c’è bisogno di gestire possibili congestioni dovute alla rete


Attributi di TCP [RFC 793]

1. Orientato alle connessioni

2. Trasmissione byte-stream

3. Connessione full-duplex

4. Affidabile

5. Trasmissione con buffer

4


1. Orientato alle connessioni• Connection oriented significa che:

– viene creata una connessione tra i due host prima del trasferimento di qualunque dato tra le applicazioni (e quindi in modo trasparente per l’applicazione)

– viene chiusa dopo il completamento del trasferimento dati• 3 fasi

– Instaurazione– Utilizzo– Chiusura

• Il processo applicativo viene avvisato solo se:– non si riesce a stabilire la connessione– la connessione viene interrotta


2. Trasmissione byte stream

• Byte stream significa che la connessione viene trattata come un flusso di byte continuo dal mittente al destinatario

• L’unità di trasmissione nello stream è il byte

1. Il processo applicativo mittente scrive byte2. Il livello TCP, per inviarli, accorpa i byte in un

segmento TCP3. Il livello IP incapsula ogni segmento TCP in un

datagram IP4. Il processo applicativo destinatario legge byte

5


3. Connessioni full duplex

• TCP può effettuare trasferimenti contemporanei in entrambe le direzioni della connessione, nell’ambito della stessa sessione– Full duplex Half duplex

• Ai processi applicativi, questi trasferimenti “appaiono” come due data stream non correlati

• Tuttavia, le ultime versioni del TCP consentono di sovrapporre (piggybacking) comunicazioni di dati e comunicazioni di controllo, con l’invio di informazioni di controllo (es., ACK) insieme ai dati utente


TCP e gli altri layer dello stack

1 2 3 4 5 6 7

TCP TCP

IPNetwork Access

IPNetwork Access

h2n h2n

1 2 3 4 5 6 7

3

4

h2n

IPNet Access

NOTA: I router non gestiscono il livello TCP

6


4. Affidabile• Affidabile significa che TCP gestisce un

trasferimento ordinato di uno stream di dati:acknowledgment + time-out+(ritrasmissione)

– Ogni trasmissione andata a buon fine viene notificata (acknowledged) dall’host ricevente

– Se l’host mittente non riceve un acknowledgement entro un intervallo di tempo predefinito (time-out), il mittente ritrasmette i dati

– Acknowledgment e ritrasmissioni dovute ad eventuali perdite sono gestite in modo trasparente rispetto al processo applicativo


5.a Trasmissione con buffer• Per far fronte a molti dei problemi evidenziati in

precedenza, il layer TCP deve utilizzare necessariamente un buffer. Un buffer consente, infatti, di ovviare a:– asincronia dell’invio dati da parte del processo applicativo– tempi di trasmissione differenti– capacità di invio e di ricezione differenti– segmenti persi o fuori ordine

• Il livello TCP è responsabile della gestione del buffering dei dati e di determinare quando è tempo di inviare uncerto insieme di dati. Alcune scelte:– congestion control: l’host mittente deve diminuire il tasso di

trasmissione dei pacchetti quando la rete è congestionata– flow control: l’host mittente non deve sovraccaricare l’host

ricevente

7


1) Dati inseriti temporaneamente in un buffer del mittente e poiinseriti in un segmento TCP quando il segmento è pieno

Maximum Segment Size (MSS): viene concordato o di default dipendedall’implementazione TCP (es., 1460 byte, 536 byte, 512 byte)

Un’applicazione può anche specificare al protocollo TCP di inviare i datiche ha nel buffer, senza aspettare che il buffer sia pieno

2) Il segmento, a livello logico, viene poi inserito nel buffer deldestinatario (in realtà, viene incapsulato in un datagram IP,spedito via rete e dopo aver attraversato i vari livelli, arriva nelbuffer TCP di destinazione)

5.b Uso del buffer

socketdoor

TCPsend buffer

TCPreceive buffer

socketdoor

segmento

applicazionescrive dati

applicazionelegge dati

Vistalogica

Modulo 8:Segmento TCP

Parte 5

8


Segmento TCP

• L’insieme di dati che il livello TCP chiede di trasferire al livello IP è detto segmento TCP

• Ogni segmento TCP contiene:– Payload: dati del byte stream– Header: informazioni di controllo per identificare i

byte dati


Formato del segmento TCP

DATI. . .

PADDINGTCP OPTIONS

0 4 10 16 24 31SOURCE PORT DESTINATION PORT

SEQUENCE NUMBER

ACKNOWLEDGEMENT NUMBER

HLEN RESERVED CODE BIT WINDOW SIZE

CHECKSUM URGENT POINTER

9



DATI. . .

PADDINGTCP OPTIONS


SEQUENCE NUMBER




• source port (16 bit): numero di porta del mittente

• destination port (16 bit): numero di porta del destinatario

• sequence number (32 bit): numero di sequenza relativo al flusso dibyte che si sta trasmettendo

• acknowledgement number (32 bit): ACK relativo ad un numero disequenza del flusso di byte che si sta ricevendo (poiché il flusso è bi-direzionale, vi è la possibilità di piggybacking si vedrà in seguito)



DATI. . .

PADDINGTCP OPTIONS


SEQUENCE NUMBER



CHECKSUM URGENT POINTER• hlen (4 bit): lunghezza dell’header TCP (in multipli di 32 bit) se non visono opzioni hlen = 20 byte

• reserved (4 bit): per usi futuri

• code bit (6 bit): scopo e contenuto del segmento• URG (urgent): dati segnati come urgenti dal livello applicativo• ACK (acknowledgement): valore del campo acknowledgement è valido• PSH (push): il destinatario deve passare i dati all’applicazione immediatamente• SYN (synchronize), FIN, RST (reset): usati per instaurazione, chiusura ed interruzione della connessione

10



DATI. . .

PADDINGTCP OPTIONS


SEQUENCE NUMBER




– window size (16 bit): dimensione della finestra in ricezione (indica il numero di byte che si è disposti ad accettare in ricezione)– checksum (16 bit): controllo integrità dei dati trasportati nel segmento TCP (del tutto analogo al caso del protocollo UDP)– urgent pointer (16 bit): puntatore al termine dei dati urgenti (utilizzato raramente, nel caso di trasmissione di caratteri speciali)– TCP options: campo opzionale di lunghezza variabile (serve a negoziare la dimensione del segmento massimo scambiato MSS)– zero padding: per header con lunghezza multipla di 32 bit (se opzioni)


Checksum TCPUtilizzato per rilevazione errori nei dati trasportati:calcolato usando un maggior numero di informazioni di quellepresenti nell’header TCP (vi sono anche informazioni IP) definizione di uno pseudo-header TCP

32 bit

indirizzo IP mittente

lunghezza TCP

indirizzo IP destinatario

zero padding protocollo

• zero padding: dimensione dello pseudo-header, multiplo di 32 bit• protocollo: campo protocollo del datagram IP• pseudo-header anteposto al segmento TCP• checksum calcolato su pseudo-header e intero segmento TCP• pseudo-header non è trasmesso dal mittente

11


Dati urgenti(trasmissione fuori banda)

• Servono a trasportare segnali speciali come ^C, ^Z, … in modo che possano essere recapitati immediatamente al processo applicativo

• All’arrivo all’host destinatario, scavalcano lo stream e vengono recapitati immediatamente al processo applicativo

• Il puntatore punta alla fine del blocco dei dati urgenti

• I dati urgenti iniziano all’inizio del segmento


Negoziazione del MSS• Le TCP OPTIONS consentono di negoziare il Maximum

Segment Size (MSS) per– garantire che il segmento entri nei rispettivi buffer– evitare il più possibile la frammentazione al livello h2n– sfruttare al meglio la banda

• MSS troppo piccolo overhead eccessivo dovuto agli header

• MSS troppo grande elevati rischi di frammentazione nell’attraversamento dei livelli dello stack sottostanti IP-h2n

Default MSS = 536 byte

• L’ACK viene mandato a livello del segmento originale. Quindi se un frammento viene perso, tutto il segmento deve essere riinviato

12


Numeri di sequenza e acknowledgmentNumero di sequenza per un segmento TCP è dato da:- primo ISN random- poi offset del primo byte del flusso dati inviati dal mittente(L’Initial Sequence Number è scelto casualmente con l’obiettivo diminimizzare la probabilità che sia presente un segmento identificato con lostesso numero appartenente ad una connessione precedente con identicinumeri di porta)Esempio: Si supponga di trasferire un file di 500000 byte, con MSS=1000byte. I numeri sequenza saranno: X, X+1000, X+2000, …

#seqsegmento 1

#seqsegmento 2

data for500th segment


Numeri sequenza e acknowledgment (2)

Il numero di acknowledgment per un segmento TCP:• TCP è full duplex: l’host A può ricevere dati dall’host B mentre stainviando dati a B sulla stessa connessione

• Segmento da B a A:

- numero di sequenza: numero sequenziale del byte del flusso dati

- numero di acknowledgment: numero di sequenza delsuccessivo byte che A si aspetta di ricevere da B (tutti i byteprecedenti sono stati ricevuti (acknowledgement incrementale)

Esempi

- A ha ricevuto da B i segmenti da 0 a 999 byte e da 1000 a 1999 byte,per cui il numero di acknowledgment nel segmento da A a B 2000

- A ha ricevuto da B i segmenti da 0 a 999 byte e da 2000 a 2999 byte,per cui il numero di acknowledgment nel segmento da A a B 1000

13


Gestione ack

• Nella direzione da host1 a host2 viaggiano i segmenti dati inviati da host1 a host2 e i segmenti di ack inviati da host1 a host2 (in risposta ai segmenti dati inviati da host2 a host1)

• Nella direzione da host2 a host1 viaggiano i segmenti dati inviati da host2 a host1 e i segmenti di ack inviati da host2 a host1 (in risposta ai segmenti dati inviati da host1 a host2);

• Il campo code bit serve a distinguere fra i due tipi di segmenti, dati e di ack, che viaggiano nella stessa direzione


Gestione ack migliorata: piggybacking

• Obiettivo: aspettare e combinare

• Nella direzione, per esempio, da host2 a host1 faccio viaggiare nello stesso segmento:– sia i dati che l’host2 deve inviare a host1– sia gli ack che host2 deve inviare a host1 in risposta ai

segmenti dati inviati da host1 a host2

• Piggybacking “portare sulle spalle”

14

Piggybacking


1 - 2 - 3 a 4 b 5 c 6 d 7 e 8 f ... .

a - b - c 1 d 2 e 3 f 4 g 5 h 6 ... .

Si sfrutta il flusso inverso opposto per portare gli ack dei pacchetti ricevuti

Modulo 9:Instaurare e chiudere una

connessione TCP

Parte 5

15


Instaurazione di una connessione

• Nel TCP il mittente ed il destinatario, prima di iniziare il trasferimento dei segmenti contenenti i dati, instaurano la connessione

• Modello client/server– client: inizia la connessione– server: deve essere già attivo, in attesa, viene

contattato dal client

• Inizializzazione delle variabili del TCP– numeri di sequenza dei segmenti– informazioni necessarie per la gestione del buffer di

trasmissione e ricezione


Instaurazione di una connessione (2)

• Quando un client richiede una connessione, invia un segmento TCP speciale, detto “SYN”segment (SYN sta per synchronize) al server

• Il client deve conoscere a chi spedire la richiesta, per cui nell’header del segmento deve specificare:– La porta del server?– L’indirizzo IP?

• Per accettare la connessione, il server deve essere già in attesa di ricevere connessioni

SINO

16



Il segmento SYN del client include:

• Initial Sequence Number (ISN) del client:– un numero di 32 bit– Il numero è scelto in modo pseudo-casuale tra 0 e 232-1– Se il numero iniziale è 2032 e ci sono da spedire 5000

byte, tutti i byte saranno numerati da 2032 a 7031– La numerazione dei byte in una direzione è indipendente

dalla numerazione dei byte nell’altra direzione– Nell’intestazione di ogni segmento è riportato solo il

numero di sequenza del primo byte dei dati contenuto nel segmento. Gli altri byte del segmento sono numerati di conseguenza



Il segmento SYN del client include anche: • Maximum Receive Window (MRW) del client: il

massimo numero di byte che il client è in grado di ricevere nel suo buffer – necessario per la regolazione del flusso dello stream di byte

• Maximum Segment Size (MSS): la massima dimensione del segmento (informazione non sempre inviata)

• NON HA payload (dati del messaggio), ma solo il TCP header!

17



Il segmento SYN del server include: • Initial Sequence Number (ISN) del server: un

numero pseudo-casuale• ACK del server: client_ISN+1• Maximum Receive Window (MRW) del server• Maximum Segment Size (MSS): la massima

dimensione del segmento (informazione non sempre inviata)

• NON HA payload (dati del messaggio), ma solo il TCP header


Instaurazione di una connessione(Three-way handshaking)

• Il client invia al server un segmento di controllo con SYN=1, e specificanello stesso segmento il proprio numero iniziale di sequenza (client_isn)• Il server riceve il segmento del client con SYN=1• Se accetta, il server invia un segmento di controllo con SYN=1,ACK=client_isn+1, ed il proprio numero iniziale di sequenza (server_isn)• Il client segnala la definitiva apertura della connessione inviando unsegmento di controllo con SYN=0, ACK=server_isn+1, e numero disequenza client_isn +1

18


Three-way handshacking

1. Client: “Hello server, voglio parlare con te, e comincerò con il byte che indicherò con il numero X”

2. Server: “OK, sono disponibile a parlare. Il mio primo byte sarà indicato con il numero Y e so che il tuo prossimo byte sarà indicato con X+1”

3. Client: “D’accordo, so che il prossimo byte che mi invierai sarà indicato con il numero Y+1”


Chiusura (polite) della connessione(esempio lato client)

- Il client invia un segmento dicontrollo con bit FIN=1 al server

- Il server riceve FIN, inviaACK

- Il server chiude la connessione latoclient-server ed invia FIN=1 al client

- Il client riceve il segmento conFIN=1 ed inviaACK

- Il server riceveACK

- Il client attende il timeout dell’ACKinviato; allo scadere anche laconnessione lato server-client vienechiusa

client serverApplicazione

chiude

closed

timed

wai

t

closed

Perché tante “fasi” nella chiusura?

Send FIN

Send FIN

Informaapplicazione

Applicazionechiude

19


Chiusura (polite) della connessione (2)

• Dopo che la connessione TCP è stata chiusa (ovvero è stato inviato l’ultimo ACK dal client), ci potrebbe essere ancora qualcosa da fare. Per esempio:– Se l’ultimo ACK si perde? L’ultimo segmento FIN verrà inviato nuovamente, e dovrà essere notificato con un ACK

– Se segmenti persi o duplicati dovessero raggungere la destinazione dopo un lungo ritardo?

• Quindi, il client TCP attende per un tempo TIME_WAIT (es., 30 secondi) prima di chiudere definitivamente la connessione per poter gestire queste situazioni anomale


Chiusura (reset) della connessioneIn condizioni normali, la connessione viene chiusa in modo “polite” tramite loscambio di segmenti di controllo FIN e ACK, visto in precedenza

• Talvolta, si verificano condizioni che portano ad interrompere laconnessione in modo “brusco”, o dal lato server (tipicamente, per errori osovraccarico) o dal lato client (tipicamente, in seguito a azione dell’utente)• TCP fornisce un meccanismo per la chiusura rapida: reset• L’host che decide il reset pone il campo del segmento RST=1• L’altro nodo chiude immediatamente la connessione• Vengono rilasciate tutte le risorse utilizzate dalla connessione

closing

closed

client server

closing

closed

client server

20


Protocollo TCP: funzionamentoIl trasferimento dati tra host end-to-end avvienein 3 fasi:1. Handshaking: fase di setup (con trasferimento di

3 segmenti) in cui ci si prepara al trasferimento dei dati– Si deve arrivare ad uno stato di setup riconosciuto da

parte di entrambi gli host che devono comunicare2. Trasmissione: fase di trasmissione

(bidirezionale) di uno o più segmenti3. Chiusura connessione

Protocolli e Architetture di Rete 2009/2010 – Livello Trasporto

Ciclo di vita delle connessioni TCP

Ciclo di vita del server TCP

Ciclo di vita del client TCP

NOTAI diagrammi si riferiscono soloall’apertura-chiusura delleconnessioni. Ciò che succededurante la connessione è dentrolo stato “established” 6.103

21


Diagramma delle transizioni di stato del protocollo TCP

(server)

(client)

FASE DIINSTAURAZIONEDI UNACONNESSIONE

FASE DICHIUSURADI UNACONNESSIONE

Modulo 10:Affidabilità del protocollo TCP

Parte 5

22


Meccanismi per l’affidabilità1. Acknowledgment (positivo)2. Time-out3. Ritrasmissione

Meccanismi gestiti dal livello TCP in modo del tutto trasparente rispetto al processo applicativo

Principî:– Ogni trasmissione andata a buon fine viene notificata

(acknowledged) dall’host ricevente– Se l’host mittente non riceve un acknowledgement

entro il time-out, il mittente ritrasmette i dati


Affidabilità del protocollo TCPAffidabilità: uso della tecnica di acknowledgement positivocon ritrasmissione Il destinatario, quando riceve i dati, inviaun acknowledgement (ACK) al mittente, che attende diricevere un ACK prima di inviare il segmento successivo.Esempio

Invia ACK 1

Invia pacchetto 1 Riceve pacchetto 1

Riceve pacchetto 2Invia ACK 2

Riceve ACK 1Invia pacchetto 2

Riceve ACK 2

Mittente Destinatario

tempo

23


Scenari di ritrasmissioneAffidabilità: uso della tecnica di acknowledgement positivocon timeout e ritrasmissione se il mittente non haricevuto ACK di un segmento dopo un certo periodo(timeout), ritrasmette il segmento

ACK 1 dovrebbe essere inviato

Invia pacchetto 1Pacchetto 1 dovrebbe essere arrivato

Riceve pacchetto 1Invia ACK 1

Riceve ACK 1tempo

Pacchetto 1 perso

ACK 1 dovrebbe essere ricevuto

TimeoutInvia pacchetto 1

Mittente Destinatario

Protocolli e Architetture di Rete 2009/2010 – Livello Trasporto

Scenari di ritrasmissione(protocollo stop-and-wait)

Host A

perdita

timeo

ut

time

Ritrasmissione causata dalla perdita dell’ACK

Host B

X

Host A

perdita

timeo

ut

Ritrasmissione causata dalla perdita del segmento

Host B

X

In entrambi i casi, l’ack=100 non arriva.Nel primo caso, c’è una duplicazione. 6.109

24

Come stimare il “time-out”?


Round Trip Time e Timeout

Come stabilire il valore del timeout in trasmissioni TCP?

– Timeout troppo breve: si effettuano ritrasmissioni non necessarie

– Timeout troppo lungo: reazione lenta alla perdita di segmenti

UNICA CERTEZZA: Il timeout deve essere maggiore delRound Trip Time (RTT). Ma di quanto?

RTT

25


RTT varia continuamenteMotivazioni delle differenze del RTT:- fluttuazioni delle condizioni di traffico della rete- possibili cambiamenti di router nel percorso tra mittente e

destinatarioR

TT

Sequenza di datagrammi


Scelta del Timeout (old)

Inizialmente si sceglieva:

Timeout = * RTTmedio

dove la raccomandazione era: = 2

Adesso, si utilizzano stime molto più sofisticate

26


Scelta del Timeout

EstimatedRTT(t) = (1-x)*EstimatedRTT(t-1) + x*SampleRTT(t)

• EstimatedRTT: media pesata per stimare RTT al tempo t

• Exponential Weighted Moving Average (EWMA)

• L’influenza dei campioni passati diminuisce in modo esponenziale

• Il valore di x è compreso tra 0 e 1. Inizialmente, si sceglie tipicamentex=1/(n+1) dove n è il numero di campioni di RTT usati per il calcolo

SampleRTT: misura del tempo trascorso dalla trasmissionedel segmento alla ricezione del suo ACK

- Ignora ritrasmissioni, segmenti con ack cumulativi

- SampleRTT varia dinamicamente si usa una media pesata


Esempio della stima RTT

100

150

200

250

300

350

1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106

Tempo (secondi)

RTT (

mill

iseco

ndi)

RTT campionata

Impossibile v isualizzare l'immagine. La memoria del computer potrebbe essere insufficiente per aprire l'immagine oppure l'immagine potrebbe essere danneggiata. Riavviare il computer e aprire di nuovo il file. Se viene visualizzata di nuovo la x rossa, potrebbe essere necessario eliminare l'immagine e inserirla di nuovo.

RTT stimata

27


Scelta del Timeout (2)

Timeout(t) = EstimatedRTT(t) + 4*Deviation(t)

Deviation(t) = (1-x)*Deviation(t-1) +x*abs[SampleRTT(t)-EstimatedRTT(t)]

Scelta del timeout:

Valore del RTT stimato più un margine dierrore

dove:

Modulo 11:Gestione del buffer TCP

Parte 5

28


Motivazioni per buffering: asincronia

• Il TCP fa parte del Sistema Operativo, non del livello applicativo che gestisce l’invio e la ricezione dei dati

• Deve tener conto di tutti gli eventi che si verificano in modo asincrono:– Il livello TCP del mittente non sa quando il processo

applicativo deciderà di spedire dati– Il livello TCP del destinatario non sa quando il processo

applicativo accetterà (o chiederà) di prendere i dati arrivatiL’unica possibilità è inserire temporaneamente i dati ricevuti

in un buffer, in modo da poterli ricevere/trasmettere dal/al livello applicativo quando vengono inviati/richiesti

CONTROLLO DI FLUSSO (si vedrà in seguito)


Motivazioni per buffering: prestazioni

• Il meccanismo di trasporto stop-and-wait è estremamente affidabile e semplice da implementare

• Tuttavia, utilizza le risorse di rete e degli host in modo non efficiente

Il buffering consente di passare da un protocollo stop-and-wait al pipelining

MOTIVAZIONI

29


Prestazioni (alcune definizioni)

• Round Trip Time (RTT): tempo impiegato dal pacchetto per andare dal mittente al destinatario e ritorno

• Tempo di propagazione: RTT/2• Utilizzazione: percentuale di utilizzo di una risorsa in un

intervallo di tempo

Rate = transmission rate capacità della rete, espressa in: bit/sec (bps), Kbit/sec (Kbps), Mbit/sec (Mbps),Gbit/sec (Gbps)

L(pkt) = lunghezza pacchetto (espressa in byte o bit, e loro multipli)


Prestazioni (alcune definizioni)

• Tempo di trasmissione pacchetto L(pkt) / Rate

[dimensionalmente: (bit) / (bit/sec) = sec ]

• Tempo di trasferimento pacchetto (vista mittente)

[propagazione + trasmissione] + [propagazioneack ]

= [RTTpkt/2 + L(pkt) / Rate] + [RTTack/2 ]

30


Prestazioni protocollo stop-and-wait

Trasmesso primo bit pkt, t=0

MITTENTE DESTINATARIO

RTT*

Trasmesso ultimo bit del pkt, (t = L / Rate)

Arriva il primo bit del pktArriva l’ultimo bit del pkt; il destinatario invia l’ACK

Arriva ACK, invia prossimo pkt; (t = RTT + L / Rate)

RTT*= Round Trip Time ideale (se il destinatario non è rallentato daaltri processi)


Es. prestazioni protocollo stop-and-wait

Esempio• Canale fisico di capacità 1 Gbps (= 10^9 bit/sec)

• Ritardo di propagazione (RTT/2) = 15 msec

• Pacchetto da 1KB (=8 Kb) Rate = transmission rateL(pkt) = lunghezza pacchetto

Ttrasm/pkt = 8Kb10^9 bit/sec =L(pkt)

Rate = 8 ·10^3 bit10^9 bit/sec=

= 0.000008 sec = 0.008 msec8 bit10^6 bit/sec=

Calcolare il tempo di trasmissione pacchetto:

31


Trasmesso primo bit pkt, t=0


RTT*

Trasmesso ultimo bit del pkt, t = 0.008

Arriva il primo bit del pktArriva l’ultimo bit del pkt(t = 15.008)Il destinatario invia l’ACK

Arriva ACK, invia prossimo pkt; t = 30.008

Utilizzazione= L/RRTT + L/R = 0.00027

In pratica, si riesce a trasmettere ~1 KB ogni 30 msec ~264 Kbit ogni secondo, su un link da 1 Gbps!!

= 0.00830 + 0.008

TRTT + T

=(mittente)

Tempo trasm.Tempo totale =

Es. prestazioni protocollo stop-and-wait (2)Uso limitato delle risorse di rete


Come combinare affidabilità e efficienza

SOLUZIONE

Pipelining il mittente invia un numero multiplo disegmenti prima di ricevere un ACK

Dal protocollo stop-and-wait ad un protocollo pipelined

32


Incremento delle prestazioni (es. per 3)

RTT*

Utilizzazione incrementatadi un fattore 3 rispetto a

0.00027


Arriva il primo bit del pkt 1Arriva ultimo bit pkt 1, invia ACKArriva ultimo bit pkt 2, invia ACKArriva ultimo bit pkt 3, invia ACK

Trasmesso primo bit pkt, t = 0Trasmesso ultimo bit del pkt,

t = L / R

Arriva ACK, invia prossimi pkt;t = RTT + L / R

Utilizzazione= 3*L/RRTT + L/R = 0.0008= 0.024

30 + 0.008T

RTT + T=

(mittente)

Tempo trasm.Tempo totale

=


Sintesi: Requisiti per l’implementazione

1. Necessità di un buffer lato mittente– Per mantenere i pacchetti inviati e di cui non ha ancora

ricevuto l’ack2. Necessità di un buffer lato destinatario

– Per mantenere le sequenze di pacchetti dove non tutti i pacchetti sono arrivati o sono arrivati correttamente

3. Necessità di una “finestra a scorrimento” che denota il numero massimo di pacchetti che il mittente può inviare senza aver ricevuto un ACK dal destinatario

33

Modulo 12:Sliding window

Parte 5


Sliding window - mittente• Il mittente assegna a ciascun segmento un numero di

sequenza Num_segm• Si ipotizza che questo numero possa crescere a piacere,

anche se nella realtà il range va da 0 a 231-1

PRINCIPI:- Ad ogni istante, ciascun mittente gestisce una finestra

scorrevole sugli indici dei segmenti, e solo quelli all’interno della finestra possono essere trasmessi(o sono stati spediti o stanno per essere spediti)

- La dimensione della finestra del mittente è controllata prevalentemente dal destinatario

34


Sliding window – mittente (2)

• Per gestire la sliding window (finestra scorrevole), il mittente utilizza tre variabili:– Dimensione della finestra di invio SWS (Sender Window

Size): indica il limite superiore per il numero di segmenti che il mittente può inviare in pipeline senza aver ricevuto un ACK

– Numero di sequenza dell’ultima conferma ricevuta LAR(Last Acknowledgement Received)

– Numero di sequenza dell’ultimo segmento inviato LSS(Last Segment Sent)


Sliding window - mittente (3)

• Le tre variabili del mittente devono soddisfare la seguente relazione:

LSS – LAR SWS

10 20 30 40 50 60 70 80 90 100110120130140150160 … ..

LSSLAR

SWS

SWS: Sender Window SizeLAR: Last Acknowledgement Received LSS: Last Segment Sent

35


Esempio: Sliding window - mittente (4)

10 20 30 40 50 60 70 80 90 100110120130140150160 … ..

LSSLAR[SWS]

Byte inviati econfermati (ack)

Byteinviati

Byte che si stannoper inviare

Byte non inviati che non si possono inviare

• IPOTESI: segment size di 10 byte


Sliding window - mittente (5)• Quando arriva un ACK, il mittente sposta LAR verso destra,

consentendo così l’invio di un altro segmento• Inoltre, il mittente associa un time-out a ciascun segmento

che trasmette, con conseguente ritrasmissione del segmento se il time-out scade prima di aver ricevuto il relativo ACK

10 20 30 40 50 60 70 80 90 100110120130140150160 … ..

10 20 30 40 50 60 70 80 90 100110120130140150160 … ..

Se l’ack del segmento 60 arriva entro il time-out trasmissione di 120

10 20 30 40 50 60 70 80 90 100110120130140150160 … ..

Se l’ack del segmento 60 non arriva entro il time-out ritrasmissione di 60

36


Sliding window - destinatario

• PRINCIPIO: per alcuni algoritmi di gestione (“Ritrasmissione selettiva”, ma non per il “Go-Back-N”), il destinatario può mantenere una finestra scorrevole sugli indici dei segmenti ricevuti

• La dimensione della finestra e le modalità di gestione dipendono dall’algoritmo utilizzato


Sliding window – destinatario (1)

• I destinatari che gestiscono una sliding windowutilizzano tre variabili:– Dimensione della finestra di ricezione RWS (Receive

Windows Size): indica il limite superiore dei segmenti “fuori sequenza” che il destinatario può accettare

– Numero di sequenza del segmento accettabile più elevato LAS (Largest Acceptable Segment)

– Numero di sequenza dell’ultimo segmento ricevuto “in sequenza” LSR (Last Segment Received)

37


Sliding window - destinatario (2)

• Le tre variabili del destinatario devono soddisfare la seguente relazione:

LAS – LSR RWS

10 20 30 40 50 60 70 80 90 100110120130140150160 … ..

LASLSR

RWS

RWS: Receive Window SizeLAS: Largest Acceptable Segment LSR: Last Segment Received


Sliding window - destinatario (3)

• Quando arriva un segmento con numero di sequenza Num_segm, il destinatario agisce come segue:– Se Num_segmLSR oppure Num_segm>LAS, significa

che il segmento si trova al di fuori della finestra utile del destinatario e viene scartato

– Se LSR<Num_segmLAS , il segmento si trova all’interno della finestra del destinatario e viene inserito nel buffer

38


Es.: finestra a scorrimento (size 3)

10 20 30 40 50 60 70 80 90 100110120130140150160 … ..Quando arriva l’ack del segmento 10

Send Pk1

Send Pk2

Send Pk3

Rec. Pk1

Rec. Pk2

Rec. Pk3

Send Ack1

Send Ack2

Send Ack3

Rec. Ack1

Rec. Ack2

Rec. Ack3

In questo modo è possibile sovrapporrele comunicazioni sulcanale di andatae su quello di ritorno

Tutto abbastanza semplice fin quando le “cose vanno bene”: cioè le trasmissioni vanno a buon fine e avvengono in modo ordinato.

Ma cosa succede se qualcosa va male …

MITTENTE

10 20 30 40 50 60 70 80 90 100110120130140150160 … ..


Algoritmi per l’affidabilità del pipelining

“Andar male” =mancato arrivo di un pacchetto ACK entro il timeout

Vi sono due approcci alternativi per affrontare il problema dell’affidabilità della comunicazione nel caso di un protocollo pipelining:

• Go-Back-N

• Ritrasmissione selettiva

NOTA: Sono algoritmi generali, non riferibili in modo specifico al protocollo TCP

39


Algoritmo 1: Go-Back-N

MITTENTEIPOTESI: Finestra (window size) di max N segmenticonsecutivi, inviabili senza ACK

• Timeout per singolo segmento• In caso di timeout(i) il mittente deve ritrasmettere il

segmento i e tutti i segmenti che hanno un numero di sequenza superiore ad i. Perché?


Algoritmo 1: Go-Back-N

DESTINATARIO• “ACK cumulativi” da parte del destinatario ACK(n)

conferma che sono arrivati correttamente i primi nsegmenti

• C’è il buffer di ricezione, ma non c’è necessità di unasliding window gestita dal destinatario

• Segmenti che arrivano fuori sequenza:– Vengono scartati senza essere inseriti nel buffer– Quindi non c’è bisogno di un buffer di ricezione sul lato

destinatario per gestire il pipeling, ma solo per gestire l’asincroniatra l’arrivo dei dati a livello di TCP (sistema operativo) e il loroconsumo da parte del processo applicativo del destinatario

40


Funzionamento algoritmo Go-Back-N

Ipotesi:

Finestra N=4


Algoritmo 2: Ritrasmissione selettiva

• Il destinatario invia ACK relativo a ciascun segmento ricevuto correttamente– Bufferizzazione dei pacchetti, per consegnarli secondo la

sequenza ordinata al processo applicativo

• Il mittente ritrasmette soltanto i segmenti per i quali non ha ricevuto ACK dal destinatario entro il time-out– Gestisce un timeout per ciascun pacchetto

• Sia mittente sia destinatario gestiscono la propria sliding window

41


Finestra mittente e destinatarioIpotesi: finestra di dimensione N =14

Window del mittente

Window del destinatario


Algoritmo di Ritrasmissione selettiva

Dati dall’applicazione:• se c’è un numero di

sequenza disponibile nella finestra, invia segmento

Timeout(i):• ritrasmetti segmento i,

inizializza nuovo timer per iACK(i) nella finestra[send_base, send_base+N]:

• segna segmento i ricevuto• se i è il segmento “base” non

ancora ACK, incrementa la finestra fino al successivo pacchetto non ACK

Segmento i ricevuto in[rcv_base, rcv_base+N-1]

• invia ACK(i)• non ordinato: metti in buffer• ordinato: consegna al

processo applicativo; avanza la finestra al segmento successivo non ancora ricevuto

Segmento i ricevuto in [rcv_base-N, rcv_base-1]

• ACK(i)Altrimenti:• ignora

destinatariomittente

42


Funzionamento Ritrasmissione selettiva


Algoritmo del protocollo TCP

• Sebbene sia stata proposta una modifica al protocollo TCP [RFC 2018] per andare verso un meccanismo di ritrasmissione selettiva pura, attualmente il TCP nonsegue nessuna delle due versioni (Go-Back-N e Ritrasmissione Selettiva) in modo puro, in quanto utilizza:

“ACK cumulativi” da parte del destinatario ACK(n)conferma che sono arrivati correttamente i primi n byte dei segmenti dati inviati (come Go-Back-N)

Segmenti arrivati fuori ordine, vengono salvati nelbuffer di ricezione (come Ritrasmissione Selettiva)

43


Algoritmo del protocollo TCP (2)

• Mittente e destinatario gestiscono due finestre di sequenze di segmenti da inviare e ricevuti

• Il destinatario invia un ACK cumulativo relativo all’ultimo byte dell’ultimo segmento ricevuto senza errori ed “in sequenza”

• Il mittente ritrasmette soltanto i segmenti per i quali non ha ricevuto ACK dal destinatario entro il time-out

• Sia la window del destinatario sia quella del mittente possono avanzare di d posizioni (d1)


Algoritmo del protocollo TCP (es.)• LSR=5, cioè l’ultimo ACK inviato dal destinatario è

relativo al segmento 5• RWS=4 (receiver window size) e quindi LAS=9• Se dovessero arrivare i segmenti 7 e 8, verrebbero

memorizzati nel buffer perché si trovano all’interno della finestra del destinatario, ma poiché non è arrivato ancora il segmento 6, a seconda dell’implementazione del TCP:– non verrebbe inviato alcun ACK oppure– verrebbe inviato nuovamente ACK(5)

• Quando arriva il segmento 6, il destinatario può inviare ACK(8), confermando la ricezione corretta di 6, 7 e 8 (cioè d=3), consentendo quindi di settare LFS=8 e LAS=12

44


Algoritmo del protocollo TCP (conseguenze)

• Si evita la ritrasmissione di segmenti ricevuti correttamente che si verificava nel caso di Go-Back-N

• Si sfruttano tutti gli ACK per comprendere che i segmenti sono stati ricevuti correttamente e, quindi, in caso di trasmissioni corrette, si velocizza l’avanzamento della finestra di spedizione (vedi esempi successivi)

• In caso di time-out, la quantità di dati trasmettibile diminuisce perché il mittente non è in grado di far avanzare la finestra ed il buffer risulta occupato da altri segmenti. Più tempo occorre per accorgersi che un segmento è andato perduto, più si limita la capacità della banda di trasmissione ( necessità di comprendere problemi al più presto)


Scenari di ritrasmissione per ritardi (protocollo pipelining)

Host A

Seq=

92 ti

meo

ut

Host B

Seq=

100

timeo

ut

L’ack=100 arriva, ma oltre il timeout prestabilito.L’host A deve rinviare il segmento. Doppia duplicazione: segmento a host B, ack=120 a host A

Seq=

92 ti

meo

ut

Host A

Seq=

92 ti

meo

ut

Host B

Seq=

100

timeo

ut

Caso molto particolare in cui ack=100non arriva entro il timeout prestabilito, mentre ack=120 arriva addirittura entro il timeout del segmento 92.NON C’E’ RITRASMISSIONE! Perché?

45


Altri due problemi da risolvere nel TCP• Il TCP è il livello che deve evitare di spedire

più segmenti di quanti il destinatario sia in grado di riceverne “Controllo di flusso”

• Il TCP è il livello che deve evitare di spedire più segmenti di quanti la rete tra mittente e destinatario sia in grado di assorbirne “Controllo di congestione”

• Entrambi gli obiettivi vengono raggiunti determinando come adattare dinamicamente la dimensione della sliding window mittente

5 Protocolli Trasporto Parte2

Technology

Transcript of 5 Protocolli Trasporto Parte2