Trasporto affidabile (principi)• Di fondamentale importanza negli strati applicativi, di

trasporto e di collegamento!

• Le caratteristiche del canale determinano la complessità del protocollo di trasporto affidabile – reliable data transfer (rdt)

Trasferimento affidabile (generalità)

Mittente(sender)

Ricevente(receiver)

rdt_send(): chiamata da “sopra”, (es. app.). Dati da inviare

udt_send(): chiamata da rdt per trasferire i dati sul canale non affidabile

rdt_rcv(): chiamata quando un pacchetto arriva al lato ricezione del canale

deliver_data(): invocata da rdt per consegnare i

dati

Generalità (2)Sviluppo incrementale dei lati mittente e

ricevente del protocollo affidabile (rdt)• Flusso unidirezionale dei dati (per

semplicità)– Flusso di controllo in entrambe le direzioni!

• Macchina a stati finiti (FSM) per modellare mittente e ricevente

Stato1

Stato2

Evento che causa una transizioneAzioni corrispondenti

Stato: se in questo “stato”, lo stato successivo è determinato solo da evento

EventoAzioni

Rdt1.0: canale affidabile

• ASSUNZIONE: Canale affidabile– Nessun errore sui bit trasmessi– Nessuna perdita di pacchetti

• FSM distinte per mittente e ricevente:– Mittente invia dati nel canale– Ricevente legge dati dal canale

Rdt2.0: canale con errori sui bit (no perdita pacchetti)

• Il canale non affidabile può “invertire” bit– Si ricordi: checksum UDP serve a individuare errori sui bit

• Domanda: come reagire agli errori (scoperti):– Acknowledgement (ACK): il ricevente comunica esplicitamente che pacchetto OK– Negative acknowledgement (NAK): il ricevente comunica esplicitamente che

pacchetto ha avuto errori – Il mittente ritrasmette un pacchetto se riceve NAK

• Nuovi meccanismi in rdt2.0 (oltre rdt1.0):– Individuazione di errori– Riscontro del ricevente: messaggi di controllo (ACK,NAK) ricevente->mittente

(ARQ)

rdt2.0: specifica della FSM

FSM mittente FSM ricevente

rdt2.0 in azione (no errori)

sender FSM receiver FSM

rdt2.0 in azione (errori)

sender FSM receiver FSM

rdt2.0 ha un difetto (flaw) fatale!

Cosa succede se ACK/NAK corrotti?

• Il mittente non sa cosa è successo al ricevente!

Cosa fare?• Mittente riscontra ACK/NAK

del ricevente. Cosa succede se questi ACK/NAK persi?

• La ritrasmissione potrebbe causare il reinvio di un pacchetto correttamente consegnato!

Gestione duplicati: • Il mittente aggiunge numero di

sequenza (sequence number) a ciascun pacchetto

• Mittente ritrasmette pacchetto se ACK/NAK con errori

• Il ricevente distrugge (non consegna) pacchetti duplicati

Il mittente invia un pacchetto e aspetta larisposta

stop and wait

rdt2.1:(mittente): gestione errori negli ACK/NAK

rdt2.1 (ricevente): gestione errori negli ACK/NAK

rdt2.1: osservazioni

Mittente:• # seq per ogni pacchetto• Due # seq. (0,1 – 1 bit)

sono sufficienti. Perché?• Controllo: ACK/NAK

ricevuto è corrotto? • Numero doppio di stati

– Lo stato deve “memorizzare” se il pacchetto “corrente” ha # seq. 0 o 1

Ricevente:• Necessità di verificare se un

pacchetto ricevuto è duplicato– Lo stato indica se il # seq.

atteso sia 0 o 1 – Ritrasmissione: stesso numero

di sequenza in due pacchetti successivi

– Altrimenti numero di sequenza diverso

– Nota: il ricevente non sa se l’ultimo ACK/NAK spedito sia stato ricevuto senza errori dal mittente

rdt2.2: protocollo privo di NAK (NAK-free)

• Stesse funzionalità di rdt2.1, ma solo ACK

• Invece di un NAK, il ricevente invia ACK per l’ultimo pacchetto ricevuto correttamente

• Il ricevente deve esplicitamente includere nell’ACK # seq del pacchetto confermato

• ACK duplicato al mittente ha lo stesso significato di un NAK: ritrasmetti il pacchetto corrente

FSM mittente

!

rdt3.0: canale con errori e perdita

Nuova assunzione: il canale può perdere pacchetti (dati o ACK)– checksum, # seq., ACK,

ritrasmissioni non bastano

D: come trattare la perdita?– Il mittente aspetta fino ad

essere certo che il pacchetto sia andato perso, poi ritrasmette

– Svantaggi?

Approccio: il mittente attende per un intervallo “ragionevole” l’arrivo di un ACK

• Ritrasmette se un ACK non è ricevuto entro l’intervallo

• Se il pacchetto (o ACK) solo ritardato (non perso):

– La ritrasmissione sarà un duplicato, ma l’uso di # seq gestisce ciò

– Il ricevente deve indicare il # seq del pacchetto riscontrato

• È necessario un timer

rdt3.0 mittenteNota: le ritrasmissioniavvengono allafrequenza del timer

rdt3.0 in azione

rdt3.0 in azione (cont.)

Prestazioni di rdt3.0

• rdt3.0 funziona, ma le prestazioni non sono buone• Esempio: link da 1 Gbps, ritardo prop. end-to-end 15 ms, pacchetto

da 1KB:

T trasm =8Kb/pkt10^9 b/sec

= 8 microsec

Fatt. Uso = U = =8 microsec

30.016 msec% di tempo mitt. occupato (busy)

= 0.00015

– Pacchetto da 1KB ogni 30 msec -> throughput 33kB/sec su link da 1 Gbps!!!!

– Il protocollo limita l’ uso delle risorse fisiche!

Protocolli con pipeline (pipelined)Pipelining: il mittente invia più pacchetti, senza

attendere l’acknowledgement dei pacchetti precedenti

• L’intervallo dei numeri di sequenza va aumentato– Buffering dei pacchetti al mittente e/o ricevente

• Sliding window: Go-Back-N, Selective Repeat

Go-Back-NMittente:• Numero di sequenza a k-bit nell’ header del pacchetto• “Finestra” (window) di (max.) N, pacchetti consecutivi non confermati

• ACK(n): conferma tutti i pacchetti, fino a (e incluso) quello con numero di sequenza n - “ACK cumulativo”

• Timer unico per il blocco di pacchetti non confermati (“in-flight”)• timeout(n): ritrasmetti il pacchetto n e tutti quelli con numero di sequenza più alto nella finestra

GBN: FSM estesa (mittente)

Nota: timer associato alla variabile base

GBN: FSM estesa (ricevente)

Ricevente semplice:• Solo ACK: si invia sempre l’ACK per il pacchetto con numero di

sequenza più alto (mod N) tra quelli correttamente ricevuti• Si possono avere ACK duplicati

– È sufficiente memorizzare expectedseqnum al lato ricevente

• Pacchetti non in ordine (out-of-order): – Getta (discard), nessun buffering al lato ricezione!– ACK per il pacchetto con numero di sequenza più alto tra quelli

ricevuti in ordine

GBN inazione

Selective Repeat

• Il ricevente conferma singolarmente tutti i pacchetti correttamente ricevuti– Memorizza i pacchetti ricevuti per l’invio in ordine verso gli

strati superiori

• Il mittente ritrasmette solamente i pacchetti per cui non ha ricevuto acknowledgement– Il mittente ha un timer per ogni pacchetto non confermato

• Finestra del mittente– N numeri di sequenza consecutivi– Come con Go-Back-N si limita il numero di pacchetti

trasmessi e non confermati

Selective repeat: finestre sender, receiver

Selective repeat (cont.)

Dati dall’alto :• Se prossimo # seq. disponibile

cade nella finestra invia pacchetto

timeout(n):• Rimanda pacchetto n, riavvia

timer pacchetto n

ACK(n) in [sendbase,sendbase+N]:

• Marca (mark) pacchetto n come ricevuto

• Se n = sendbase, avanza (slide) la base della finestra fino al più piccolo pacchetto non confermato

Mittenten in [rcvbase, rcvbase+N-1]

• invia ACK(n)• out-of-order: memorizza

(buffer)• in-order: consegna tutti I

pacchetti in ordine, avanza rcvbase fino al prossimo pacchetto previsto

• n in [rcvbase-N,rcvbase-1]:

ACK(n)

Altrimenti: • Ignora

Ricevente

Selective repeat in azione

Selective repeat: dilemma

Esempio: • # seq.: 0, 1, 2, 3• Dim. Finestra (window

size)=3• Il ricevente non nota

differenze tra i due casi!• Erroneamente

considera il pacchettoduplicato come nuovo (a)

Q: che relazione tra intervallo # seq. e dimensione finestra?

TCP: generalità RFCs: 793, 1122, 1323, 2018, 2581

• Full duplex:– Flusso dati bi-direzionale

sulla stessa connessione

– MSS: Maximum Segment Size

• Connection-oriented: – handshaking (scambio di

msg di controllo) inizializza gli stati di mitt. e ricev. prima dello scambio dei dati

• Controllo di flusso (flow control):– Il mittente non “inonda”

(flood) il ricevente

• Punto-punto:– Un sender, un receiver

• Affidabile, stream di byte in ordine (in order):– no “message boundaries”

• Pipelining:– Dim. finestra dipende dal

controllo di flusso e congestione di TCP

• Buffer invio & ricezione

socketdoor

T C Psend buffer

T C Preceive buffer

socketdoor

segm ent

applicationwrites data

applicationreads data

Struttura dei segmenti TCP

source port # dest port #

32 bit

Dati (lunghezza variabile)

sequence number

acknowledgement numberrcvr window size

ptr urgent datachecksum

FSRPAUheadlen

notused

Opzioni (lunghezza variabile)

URG: dati urgnti (di solito non usato)

ACK: # ACKvalido

PSH: push data now(di solito non usato)

RST, SYN, FIN:Controllo conness.(comandi di inst., abbattimento)

# byte rcvr dispostoad accettare

Si contano i byte di dati (non i segmenti!)

Internetchecksum(come in UDP)

# seq. e ACK in TCP Numeri di sequenza:

– Numero del primo byte presente nel segmento

ACK:

– # seq del prossimo byte atteso dal lato remoto

– ACK cumulativi– D.: come il ricevente

tratta segmenti fuori ordine

– R.: TCP non specifica, dipende dall’implementazione

Host A Host B

Seq=42, ACK=79, data = ‘C’

Seq=79, ACK=43, data = ‘C’

Seq=43, ACK=80

L’utentedigita

‘C’

host dàACK di

ricezione

host dàACK di

ricezione,trasmette

‘C’

TempoSemplice scenario telnet

TCP: trasferimento affidabile

Versione semplificata del sender, assumendo:

waitfor

event

Attesaevento

evento: dati da applicazione

evento: timeout per il segmento con # seq y

evento: ricevuto ACK,con # ACK y

Crea, invia segmento

Ritrasmetti il segmento

Processamento ACK

•Trasferimento uni-direzionale•Nessun controllo di flusso e congestione

TCP – generazione degli ACK [RFC 1122, RFC 2581]

Evento

Arrivo segmento in ordine, nessun buco, tutti i segmenti precedeni confermati

Arrivo segmento in ordine, nessun buco, un ACK ritardatoin attesa

Arrivo segmento fuori ordine,# seq maggiore di quello atteso,individuato buco

Arrivo segmento che riempie unbuco parzialmente o totalmente

Azione del ricevente

ACK ritardato. Attendi il prossimo segmento per al più 500ms. Se non arriva invia ACK

Manda subito un ACK cumulativo

Manda ACK duplicato, con numerosequenza del prossimo byte atteso

ACK immediato se il segmentoinizia all’estremità inferiore delbuco

TCP: possibili casi di ritrasmissione

Host A

Seq=92, 8 bytes data

ACK=100

loss

tim

eout

TempoScenario 1: ACK perso

Host B

X

Seq=92, 8 bytes data

ACK=100

Host A

Seq=100, 20 bytes data

ACK=100

Seq=

92

tim

eout

TempoScenario2: timeout prematuro, ACK cumulativi

Host B

Seq=92, 8 bytes data

ACK=120

Seq=92, 8 bytes data

Seq=

10

0 t

imeou

t

ACK=120

TCP: Controllo del flussoRicevente: informa

esplicitamente il mitt. circa lo spazio ancora disponibile nei buffer – Campo RcvWindow

nel segmento TCP

Mittente: mantiene la quantità di dati trasmessi e non ancora confermati (unACKed), al di sotto del valore RcvWindow più recente

Mitt. non riempie i buffer del ricevente inviando troppi dati troppo velocemente

Controllo di flusso

Buffering in ricezione

RcvBuffer = dim. del buffer di ricezione TCP

RcvWindow = spazio disponibile (spare) nel Buffer

TCP: Round Trip Time e Timeout

D: come stabilire il valore di timeout?

• Almeno RTT– nota: RTT può

variare• Troppo breve:

timeout prematuro– Ritrasmissioni

superflue• Troppo lungo:

reazione lenta a perdita di segmenti

D: come stimare il RTT?• SampleRTT: tempo misurato tra

invio di un segmento e arrivo dell’ACK corrispondente– Si ignorano le ritrasmissioni e i

segmenti confermati da ACK cumulativi

– SampleRTT varia rapidamente, si vuole una stima più “costante”

– Si usa l’ insieme delle stime più recenti e non solo l’ultimo valore di SampleRTT (EstimatedRTT)

Generalità sul Controllo della Congestione

Congestione:• Informalmente: “troppe sorgenti mandano dati troppo

velocemente perché la rete possa smaltirle”• Controllo di congestione diverso dal controllo di flusso!• Sintomi:

– Pacchetti persi (overflow nei buffer dei router)– Lunghi ritardi (accodamento nei buffer dei router)

• Un problema di primaria importanza!

Cause/costi della congestione:

scenario 1 • Due mittenti,

due riceventi• Un router, buffer

infiniti• Nessuna

ritrasmissione• Grandi ritardi se

congestione• Throughput (ritmo

di trasm.) massimo ottenibile

Cause/costi della congestione: scenario 2

• Un router, buffer finiti• Il mittente ritrasmette i pacchetti

persi

Cause/costi della congestione:

scenario 2 • Senza perdita: (goodput)

• Ritrasmissione “perfetta” solo in caso di perdita:

• La ritrasmissione dei pacchetti ritardati (non persi) rende più

grande di nel caso perfetto

in

out

=

in

out

>

in

out

“Costi” della congestione: • Più lavoro (ritrasmissioni) per un determinato rate effettivo• Ritrasmissioni superflue: il link trasporta copie multiple del pacchetto

Cause/costi congestione: scenario 3 • Quattro mittenti• Cammini con più hop (salti)• Timeout/ritrasmissione

D: che succede se il traffico offerto da B cresce a dismisura?

Cause/costi congestione: scenario 3 (cont.)

Un altro “costo” della congestione: • Quando un pacchetto è scartato, tutta la banda

usata per consegnarlo è stata sprecata

Controllo della congestione in TCP

• Controllo end-to-end• Ritmo di trasmissione limitato da una finestra di congestione,

Congwin, sul numero di segmenti:

• w segmenti, ciascuno con MSS byte inviati in un RTT:

throughput = w * MSS

RTT Byte/sec

Congwin

Controllo della congestione in TCP (2)

• Due “fasi”– Slow start (avvio lento)– congestion avoidance

(evitare la congestione)

• Variabili importanti:– Congwin– threshold: definisce la

soglia di passaggio da una fase di slow start a quella di controllo di congestione successiva

• “Stima” della banda disponibile: – Idealmente: trasmissione

al massimo ritmo possibile (Congwin max. possibile) senza perdita

– Aumenta Congwin fino alla perdita (congestione)

– Perdita: decrementa Congwin, poi inizia nuovamente la stima (aumento)

TCP: Slow start

• Aumento esponenziale della dim. finestra (per RTT)

• Perdita: timeout (Tahoe TCP) e/o tre ACK duplicati (Reno TCP)

Iniz.: Congwin = 1for (each segment ACKed) Congwin=Congwin++until (loss event OR CongWin > threshold)

Algoritmo SlowstartHost A

Un segmento

RTT

Host B

Tempo

Due segmenti

Quattro segmenti

TCP: controllo della congestione

/* slowstart is over */ /* Congwin > threshold */Until (loss event) { every w segments ACKed: Congwin++ }threshold = Congwin/2Congwin = 1perform slowstart

Controllo congestione

1

1: TCP Reno non fa slowstart dopoRicezione di tre ACK duplicati

perché TCP è equo?Due sessioni contemporanee:• Aumento additivo dà pendenza 1, quando il throughput cresce

• Decremento moltiplicativo diminuisce il throughput in modo

proporzionale

R

R

Suddivisione equa della banda

Throughput connessione 1Th

roughput

connes s

i on

e 2

Controllo congestione: incremento additivo

Perdita: decr. Finestra di un fattore 2Controllo congestione: incremento

additivo

Perdita: decr. Finestra di un fattore 2