Protocollo di trasferimento dati affidabile

Lezione 16 – Protocollo di
trasferimento dati affidabile
Reti di calcolatori
Modulo 2 - Protocollo di rete TCP/IP
Unità didattica 5 – Tecniche di controllo
Ernesto Damiani
Università di Milano
RDT 3.0: canali con errori e perdite (1)
• Il canale sottostante può anche smarrire i pacchetti
(dati o ACK)
– Somma di controllo, numero di sequenza, ACK e
ritrasmissioni aiuteranno, ma non saranno sufficienti
RDT 3.0: canali con errori e perdite (2)
• Il mittente attende un ACK per un tempo
“ragionevole”
• Se in questo periodo non riceve alcun ACK,
ritrasmette
• Se il pacchetto (o l’ACK) è soltanto in ritardo (non
perso):
– La ritrasmissione sarà duplicata, ma l’uso dei numeri di
sequenza gestisce già questo
– Il destinatario deve specificare il numero di sequenza del
pacchetto da riscontrare
• E’ necessario un contatore (countdown timer)
Rdt 3.0: mittente
Rdt 3.0 in azione (1)
Rdt 3.0 in azione (2)
Rdt 3.0: funzionamento stop-and-wait
Prestazioni di Rdt 3.0 (1)
• Rdt. 3.0 funziona, ma le prestazioni non sono
buone
• Esempio: link da 1 Gbps, ritardo prop. end-toend 15 ms., pacchetto da 1 KB
Prestazioni di Rdt 3.0 (2)
• U mittente: utilizzo: frazione di tempo in cui il
mittente è occupato nell’invio
• Pacchetto di 1KB ogni 30 msec -> throughput 33
kB/sec su link da 1 Gbps
• Il protocollo di rete limita l’uso delle risorse
fisiche
Protocolli con pipeline (1)
• Nei protocolli con pipelining il mittente ammette
più pacchetti in transito, ancora da notificare
– L’intervallo dei numeri di sequenza deve essere
incrementato
– Buffering dei pacchetti presso il mittente e/o ricevente
Protocolli con pipeline (2)
• Due forme generiche di protocolli con pipeline sono
– go-Back-N
– ripetizione selettiva
Pipelining: aumento dell’utilizzo
Il caso TCP (1)
• I dati vengono inviati da TCP in segmenti che
tipicamente hanno una lunghezza pari a 1460 byte
– (1460 + 20 byte per l’intestazione TCP + 20 byte per
l’intestazione IP danno un payload di 1500 byte per i frame
Ethernet)
Il caso TCP (2)
• Se le dimensioni di una finestra possono essere
solo pari a 1 segmento per il mittente, quest’ultimo
trasmette un solo segmento e aspetta una conferma
dal destinatario.
– Se il ritardo di trasmissione tra mittente e destinatario è
lungo, si ha un throughput molto basso (vengono trasferiti
pochissimi segmenti per volta), poiché sia il mittente sia il
destinatario trascorrono la maggior parte del loro tempo
aspettando che i messaggi vengano trasmessi da un lato
del collegamento all’altro
Il caso TCP (3)
• Al fine di migliorare il throughput, il mittente
trasmette più segmenti senza aspettare la conferma
dal mittente
• La finestra TCP è la quantità di dati senza conferme
in transito tra il mittente e il destinatario
• La finestra TCP è una valutazione del numero
massimo di segmenti che è ammissibile in base alla
lunghezza del pipe tra il mittente e il destinatario
Il caso TCP (4)
• Se il pipe è piuttosto grosso e il ritardo di andata e
ritorno è lungo, molti segmenti si adatteranno alla
rete tra il mittente e il destinatario, quindi le
dimensioni della finestra devono essere abbastanza
grandi, ma quanto grandi?
– Dimensioni della finestra = larghezza della banda * ritardo
Il caso TCP (5)
• Per una larghezza di banda di 10 Mbit/s e un
ritardo di andata e ritorno di 0,010 sec, si ha una
finestra di dimensioni pari a circa 12 KB
– (= 9 segmenti di 1460 byte)
Ripetizione selettiva
• Il destinatario conferma singolarmente tutti i
pacchetti correttamente ricevuti
– Il destinatario deve memorizzare i pacchetti per eventuali
consegne in sequenza al livello superiore
• Il mittente rimanda solo i pacchetti per cui non ha
ricevuto conferma
– Il mittente deve tenere un timer per ogni pacchetto di cui
non ha ricevuto conferma
• Finestra del mittente
– N numeri di sequenza consecutivi
– limita ancora i numeri di sequenza dei pacchetti inviati di
cui non ha ricevuto conferma
Ripetizione selettiva: finestre del
mittente e del destinatario (1)
Ripetizione selettiva: finestre del
mittente e del destinatario (2)
Mittente
• Dati dall’alto
– Se il successivo numero di sequenza è disponibile nella
finestra, invia il pacchetto
• Timeout (n)
– Rimanda il pacchetto, riavvia il timer
• ACK(n) in [sendbase, sendbase+N]:
– Marca il pacchetto n come ricevuto
– Se n è il pacchetto più piccolo non confermato, avanza la
base della finestra al successivo numero di sequenza del
pacchetto non confermato
Ripetizione selettiva: finestre del
mittente e del destinatario (3)
Destinatario
• Pacchetto n in [rcvbase, rcvbase+N-1]
– Fuori ordine: memorizza nel buffer
– In ordine: consegna anche i pacchetti memorizzati in
ordine, avanza la finestra al successivo pacchetto non
ancora ricevuto
• Pacchetto n in [rcvbase-N, rcvbase-1]
– ACK(n)
• Altrimenti
– Ignora
Ripetizione selettiva in azione
Ripetizione selettiva: dilemma (1)
Esempio
• Numeri di sequenza: 0, 1, 2, 3
• Dimensioni della finestra = 3
• Il destinatario non nota alcuna differenza tra i due
casi!
• Passa erroneamente i dati duplicati come nuovi in
(a)
Ripetizione selettiva: dilemma (2)
Go-Back-N (1)
Mittente
• Numero di sequenza in k-bit nell’intestazione
del pacchetto
• La “finestra” contiene fino a N pacchetti
consecutivi non confermati
Go-Back-N (2)
• ACK(n): conferma tutti i pacchetti, tra cui quelli
con numero di sequenza n (conferma cumulativa)
– I pacchetti duplicati potrebbero essere scartati (vedere il
destinatario)
• Timer per ogni pacchetto in transito
• timeout(n): ritrasmette il pacchetto n e tutti i
pacchetti con i numeri di sequenza più grandi nella
finestra
Go-Back-N: FSM esteso del mittente
Go-Back-N: FSM esteso del destinatario
(1)
• Solo ACK: invia sempre un ACK per un pacchetto
ricevuto correttamente con il numero di sequenza più
alto in ordine
– Può generare ACK duplicati
– Deve ricordare solo expectedseqnum
• Pacchetto fuori ordine
– Scartato (non è salvato) ⇒ senza buffering del destinatario!
– Rimanda un ACK per il pacchetto con il numero di sequenza
più alto in ordine
Go-Back-N: FSM esteso del destinatario
(2)
Go-Back-N in azione
FINE