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à)
rdt_send(): chiamata da
deliver_data(): invocata
“sopra”, (es. app.). Dati da inviare
da rdt per consegnare i dati
Mittente
(sender)
udt_send(): chiamata da
rdt per trasferire i dati sul
canale non affidabile
Ricevente
(receiver)
rdt_rcv(): chiamata quando un
pacchetto arriva al lato ricezione
del canale
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 Evento che causa una transizione
Azioni corrispondenti
Stato: se in questo
“stato”, lo stato
successivo è
determinato solo da
evento
Stato
1
Evento
Azioni
Stato
2
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
stop and wait
Il mittente invia un
pacchetto e aspetta la
risposta
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 Approccio: il mittente attende per
un intervallo “ragionevole”
può perdere pacchetti
l’arrivo di un ACK
(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?
•
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 mittente
Nota: le ritrasmissioni
avvengono alla
frequenza 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
Fatt. Uso = U =
=
8Kb/pkt
= 8 microsec
10^9 b/sec
% di tempo mitt.
occupato (busy)
8 microsec
=
= 0.00015
30.016 msec
– 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-N
Mittente:
• 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 in
azione
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.)
Mittente
Dati dall’alto :
Ricevente
n in [rcvbase, rcvbase+N-1]
• Se prossimo # seq. disponibile
cade nella finestra invia
pacchetto
• invia ACK(n)
• out-of-order: memorizza
(buffer)
• in-order: consegna tutti I
pacchetti in ordine, avanza
rcvbase fino al prossimo
pacchetto previsto
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
• n in [rcvbase-N,rcvbase-1]:
ACK(n)
Altrimenti:
• Ignora
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
• Punto-punto:
• Full duplex:
– Flusso dati bi-direzionale
sulla stessa connessione
– MSS: Maximum Segment
Size
– Un sender, un receiver
• Affidabile, stream di byte
in ordine (in order):
– no “message boundaries”
• Connection-oriented:
– handshaking (scambio di
msg di controllo) inizializza
gli stati di mitt. e ricev. prima
dello scambio dei dati
• Pipelining:
– Dim. finestra dipende dal
controllo di flusso e
congestione di TCP
• Buffer invio & ricezione
socket
door
application
writes data
application
reads data
TCP
send buffer
TCP
receive buffer
segment
• Controllo di flusso (flow
control):
socket
door
– Il mittente non “inonda”
(flood) il ricevente
Struttura dei segmenti TCP
URG: dati urgnti
(di solito non usato)
ACK: # ACK
valido
PSH: push data now
(di solito non usato)
RST, SYN, FIN:
Controllo conness.
(comandi di inst.,
abbattimento)
Internet
checksum
(come in UDP)
32 bit
source port #
dest port #
sequence number
acknowledgement number
head not
UA P R S F
len used
checksum
rcvr window size
ptr urgent data
Opzioni (lunghezza variabile)
Dati
(lunghezza variabile)
Si contano i byte
di dati (non i
segmenti!)
# byte
rcvr disposto
ad accettare
# 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
L’utente
digita
‘C’
Host B
host dà
ACK di
ricezione,
trasmette
‘C’
host dà
ACK di
ricezione
Semplice scenario telnet
Tempo
TCP: trasferimento affidabile
evento: dati da
applicazione
Crea, invia segmento
wait
Attesa
for
evento
event
Versione semplificata del
sender, assumendo:
evento: timeout per il
segmento con # seq y
Ritrasmetti il segmento
evento: ricevuto ACK,
con # ACK y
Processamento ACK
•Trasferimento unidirezionale
•Nessun controllo di flusso e
congestione
TCP – generazione degli ACK [RFC
1122, RFC 2581]
Evento
Azione del ricevente
Arrivo segmento in ordine,
nessun buco, tutti i segmenti
precedeni confermati
ACK ritardato. Attendi il prossimo
segmento per al più 500ms.
Se non arriva invia ACK
Arrivo segmento in ordine,
nessun buco, un ACK ritardato
in attesa
Manda subito un ACK cumulativo
Arrivo segmento fuori ordine,
# seq maggiore di quello atteso,
individuato buco
Manda ACK duplicato, con numero
sequenza del prossimo byte atteso
Arrivo segmento che riempie un
buco parzialmente o totalmente
ACK immediato se il segmento
inizia all’estremità inferiore del
buco
TCP: possibili casi di
ritrasmissione
Host A
Host B
X
loss
Tempo Scenario 1: ACK perso
Host B
Seq=100 timeout
Seq=92 timeout
timeout
Host A
Tempo
Scenario2: timeout
prematuro, ACK cumulativi
TCP: Controllo del flusso
Controllo di flusso
Mitt. non riempie i
buffer del ricevente
inviando troppi dati
troppo velocemente
RcvBuffer = dim. del buffer di ricezione TCP
RcvWindow = spazio disponibile (spare) nel Buffer
Buffering in ricezione
Ricevente: 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
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
= l (goodput)
out
in
• Ritrasmissione “perfetta” solo in caso di perdita:
• Senza perdita:
l
l > lout
in
• La ritrasmissione dei pacchetti ritardati (non persi) rende
grande di
lout
nel caso perfetto
“Costi” della congestione:
• Più lavoro (ritrasmissioni) per un determinato rate effettivo
• Ritrasmissioni superflue: il link trasporta copie multiple del
pacchetto
l
più
in
Cause/costi congestione: scenario 3
• Quattro mittenti
D: che succede se il
• Cammini con più hop (salti)
traffico offerto da B
• Timeout/ritrasmissione
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:
Congwin
• w segmenti, ciascuno con MSS byte inviati in
un RTT:
w * MSS
throughput =
RTT
Byte/sec
Controllo della congestione in
TCP (2)
• “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)
• 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
TCP: Slow start
Host A
Iniz.: Congwin = 1
for (each segment ACKed)
Congwin=Congwin++
until (loss event OR
CongWin > threshold)
• Aumento esponenziale
della dim. finestra (per
RTT)
• Perdita: timeout (Tahoe
TCP) e/o tre ACK
duplicati (Reno TCP)
RTT
Algoritmo Slowstart
Host B
Tempo
TCP: controllo della
congestione
Controllo congestione
/* slowstart is over
*/
/* Congwin > threshold */
Until (loss event) {
every w segments ACKed:
Congwin++
}
threshold = Congwin/2
Congwin = 1
1
perform slowstart
1: TCP Reno non fa slowstart dopo
Ricezione 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
Suddivisione equa della banda
Perdita: decr. Finestra di un fattore 2
Controllo congestione: incremento additivo
Perdita: decr. Finestra di un fattore 2
Controllo congestione: incremento additivo
Throughput connessione 1 R