Reti di calcolatori e Sicurezza

(1)

Reti di calcolatori e Sicurezza

-- Transport Layer ^---

Part of these slides are adapted from the slides of the book:

Computer Networking: A Top Down Approach Featuring the Internet, 2nd edition.

Jim Kurose, Keith Ross Addison-Wesley, July 2002.

(2)

Chapter 3: Transport Layer

Our goals:

 understand principles behind transport

layer services:



multiplexing/demultipl exing



reliable data transfer



flow control



congestion control

 learn about transport layer protocols in the Internet:



UDP: connectionless transport



TCP: connection-oriented transport



TCP congestion control

(3)

Chapter 3 outline

 3.1 Transport-layer services

 3.2 Multiplexing and demultiplexing

 3.3 Connectionless transport: UDP

 3.4 Principles of

reliable data transfer

 3.5 Connection-oriented transport: TCP



segment structure



reliable data transfer



flow control



connection management

 3.6 Principles of congestion control

 3.7 TCP congestion

control

(4)

Transport services and protocols



provide logical communication between app processes

running on different hosts



transport protocols run in end systems



send side: breaks app messages into segments, passes to network layer



rcv side: reassembles segments into messages, passes to app layer



more than one transport protocol available to apps

Internet: TCP and UDP

application transport

network data link

physical

network data link

physical network

data link physical

network data link physical network

data link physical network data link physical network

data link physical

logica

l end-e

nd tran sport

(5)

Transport vs. network layer

 network layer: logical communication

between hosts

 transport layer: logical communication

between processes



relies on, enhances, network layer services

Household analogy:

12 kids sending letters to 12 kids

 processes = kids

 app messages = letters in envelopes

 hosts = houses

 transport protocol = Ann and Bill

 network-layer protocol

= postal service

(6)

Internet transport-layer protocols

 reliable, in-order delivery (TCP)



congestion control



flow control



connection setup

 unreliable, unordered delivery: UDP



no-frills extension of

“best-effort” IP

 services not available:



delay guarantees



bandwidth guarantees

network data link

physical

network data link

physical network

data link physical

network data link physical network

data link physical network data link physical network

data link physical

logica

l end-e

nd tran sport

(7)

Chapter 3 outline

 3.1 Transport-layer services

 3.2 Multiplexing and demultiplexing

 3.3 Connectionless transport: UDP

 3.4 Principles of

reliable data transfer

 3.5 Connection-oriented transport: TCP



segment structure



reliable data transfer



flow control



connection management

 3.6 Principles of congestion control

 3.7 TCP congestion

control

(8)

Un primo servizio

 Network = trasferimento di dati tra host della rete



Host identificato in modo univoco da un indirizzo IP

 Come si fa a traferire i dati ricevuti ai processi che li hanno richiesti?



Multiplexing -- demultiplexing

(9)

Porte e processi

 Porta identifica in modo univoco un processo in esecuzione su di un host



Porte di “sistema”: 0 – 1023



FTP – 21, HTTP – 80,



RFC 1700

 Applicazioni di rete



Porte maggiori di 1024

(10)

network

M P2

network

Multiplexing/demultiplexing

segment – unità di

trasferimento di dati delle entità coinvolte al livello del trasporto

TPDU: transport protocol

data unit

_receiver

Ht Hn

Demultiplexing: invio dei

segmenti ricevuti ai processi

segment

segment _M application transport

network

P1

M

M M

P3 P4

segment header

application-layer data

(11)

Multiplexing/demultiplexing

application transport network link

physical

P1 application

transport network link physical application

transport network

link physical

P3 P1 P2 P4

host 1 host 2 host 3

= process

= socket

Inviare i msg ricevuti al socket corretto

Demultiplexing (host recezione):

Raccogliere i dati, Inviarli in rete

con l’indirizzo corretto

Multiplexing (host invio):

(12)

Demultiplexing: modalità di funzionamento

 host riceve un msg IP (datagrams)

 Ogni datagram è caratterizzato da una coppia di indirizzi IP (mittente, destinatario)

 ogni datagram come paylod ha un msg di trasporto

 Msg del trasporto ha le informazioni dulle porte del mittente e del

destinatario

 Indirizzi IP & porte sono utilizzate per inviare il msg al socket corretto

source port # dest port # 32 bits

application data (message)

other header fields

TCP/UDP segment format

(13)

Connectionless demultiplexing

 Creazione del socket (in un qualche modo)

 Socket UDP sono identificati da:

(

dest IP address, dest port number)

 Alla recezione del segmento UDP:



Si contralla la porta di destinazione



Invia il segmento al socket in ascolto su quella porta

 datagrams con IP e porta del mittente diverse

possono essere inviati

allo stesso socket.

(14)

Connectionless demux

DatagramSocket serverSocket = new DatagramSocket(6428);

Client

IP:B P3

client IP: A

P3 P1P1

server IP: C

SP: 6428 DP: 9157 SP: 9157

DP: 6428

SP: 6428 DP: 5775

SP: 5775 DP: 6428

(15)

Connection-oriented demux

 TCP socket sono identificati



source IP address



source port number



dest IP address



dest port number

 Host in recezione

utilizza queste quattro informazioni per inviare il msg a destinazione

 Server puo’ operare in modalità multithreading (pertanto sono attivi

diversi socket)



Ogni socket attivo è

identificato in modo

univoco da quadrupla di

valori

(16)

Connection-oriented demux (cont)

Client

IP:B P3

client IP: A

P1P1 P3

server IP: C

SP: 80 DP: 9157 SP: 9157

DP: 80

SP: 80 DP: 5775

SP: 5775 DP: 80 P4

(17)

Multiplexing/demultiplexing

host A

source port: x

server B

dest. port: 23

source port:23 dest. port: x

telnet app

Web client host A

server B Web Web client

host C

Source IP: C Dest IP: B source port: x

dest. port: 80 Source IP: C

Dest IP: B source port: y dest. port: 80

Web server

Source IP: A Dest IP: B source port: x dest. port: 80

(18)

Chapter 3 outline

 3.1 Transport-layer services

 3.2 Multiplexing and demultiplexing

 3.3 Connectionless transport: UDP

 3.4 Principles of

reliable data transfer

 3.5 Connection-oriented transport: TCP



segment structure



reliable data transfer



flow control



connection management

 3.6 Principles of congestion control

 3.7 TCP congestion

control

(19)

UDP: User Datagram Protocol ^{[RFC 768]}



Protocollo di trasporto essenziale



Servizio di tipo “best effort”



Segmenti UDP :



perdere



senza ordine



connectionless:



no handshaking



Ogni segmento UDP è gestito in modo

totalmente independente dagli altri segmenti

Quando è necessario utilizzare UDP?



Non c’è la necessità di stabilire una connessione



Applicazioni semplici: non abbiamo bisogno di

informazioni di stato



Header dei segmenti piccoli



Nessun controllo per

evitare i problemi di

congestione

(20)

UDP



Multimedia



Possono permettersi una perdita di

informazione

 Chi utilizza UDP



DNS



Aggiungere un meccanismo di affidabilità ad UDP



error recover al livello delle applicazioni

source port # dest port # 32 bits

Application data (message)

UDP segment format

length checksum

Length, in bytes of UDP segment, including header

(21)

UDP checksum

Sender:



Segmenti sono visti come sequenze di interi di 16- bit



checksum: complemento ad 1 della somma di tutti gli interi che compongono il segmento



Checksum-value viene inserito nel campo del segmento denominato checksum

Receiver:

 Calcola il valore di checksum del segmento

 Controlla se il valore calcolato corrisponde al valore

memorizzato nel campo checksum del segmento:

 NO - error detected

 YES - no error detected.

 Potrebbero essere presenti altri errori

Obiettivo: scoprire eventuali errori di trasmissione

(22)

Chapter 3 outline

 3.1 Transport-layer services

 3.2 Multiplexing and demultiplexing

 3.3 Connectionless transport: UDP

 3.4 Principles of

reliable data transfer

 3.5 Connection-oriented transport: TCP



segment structure



reliable data transfer



flow control



connection management

 3.6 Principles of congestion control

 3.7 TCP congestion

control

(23)

Trasferimento affidabilke



Punto importante nei livelli app., transport, link.



Una delle problematiche piu’ importanti del networking

(24)

Reliable data transfer: RDT

send side receive

side

rdt_send(): invocata dal livello delle applicazioni

udt_send(): trasferire pacchetti su di un canale non

affidabile rdt_rcv(): chiamata al momento

della recezione dei pacchetti deliver_data(): invia i

dati ai livelli superiori

(25)

Automi e trasferimento affidabile

 Trasferimento di dati (unidirezionale)



Ma con meccanismi di controllo del flusso.

 Sender e receiver sono specificati da automi a stati finiti.

state

1 state

2

event causing state transition actions taken on state transition state: when in this

“state” next state uniquely determined by next event

event actions

(26)

Rdt1.0: reliable transfer over a reliable channel

 Il canale di trasmissione è affidabile



no bit erros



no loss of packets

 Sender e receiver (fanno le ovvie cose!!)

Wait for call from

above packet = make_pkt(data) udt_send(packet)

rdt_send(data)

extract (packet,data) deliver_data(data) Wait for

call from below

rdt_rcv(packet)

sender receiver

(27)

Rdt2.0: channel with bit errors



Il canale puo’ modificare il valore dei bit presenti nei pacchetti

 UDP checksum



Come vengono determinati questi errori di trasmissione :

 acknowledgements (ACKs): receiver invia al sender un messaggio di recezione (senza errori) del pacchetto

 negative acknowledgements (NAKs): receiver invia al sender un messaggio di errore

 Sender trasmette nuovamente il pacchetto quando riceve un messaggio NAK



Novità (protocolli ARQ)

 error detection

 receiver feedback (ACK,NAK)

 Ritrasmissione

(28)

rdt2.0: la specifica (FSM)

Wait for call from

above

snkpkt = make_pkt(data, checksum) udt_send(sndpkt)

extract(rcvpkt,data) deliver_data(data) rdt_rcv(rcvpkt) &&

notcorrupt(rcvpkt) rdt_rcv(rcvpkt) && isACK(rcvpkt)

udt_send(sndpkt) rdt_rcv(rcvpkt) &&

isNAK(rcvpkt)

udt_send(NAK) rdt_rcv(rcvpkt) &&

corrupt(rcvpkt) Wait for

ACK or NAK

Wait for call from

below

sender

receiver

rdt_send(data)



(29)

rdt2.0: assenza di errori

Wait for call from

above

extract(rcvpkt,data) deliver_data(data) udt_send(ACK) rdt_rcv(rcvpkt) &&

isNAK(rcvpkt)

ACK or NAK

Wait for call from

below rdt_send(data)



(30)

rdt2.0: Scenario con errore

Wait for call from

above

extract(rcvpkt,data) deliver_data(data) rdt_rcv(rcvpkt) &&

isNAK(rcvpkt)

ACK or NAK

Wait for call from

below rdt_send(data)



Anche detti protocolli Stop-and-Wait

(31)

rdt2.0 ha un fatal flaw!

Cosa succede quando I messaggi ACK/NAK sono corrotti?



sender non è in grado di sapere cosa è successo al receiver



Si possono duplicare i messaggi trasmessi

Come rimediare?



sender ACKs/NAKs e

receiver’s ACK/NAK? Cosa accade in caso di perdita del sender ACK/NAK?

Gestione dei messaggi duplicati:



sender aggiunge ad ogni pacchetto il sequence number



receiver non trasmette alle applicazioni i pacchetti

duplicati

Sender sends one packet, then waits for receiver response

stop and wait

(32)

rdt2.1: sender, handles garbled ACK/NAKs

Wait for call 0 from

above

sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt)

rdt_send(data)

Wait for ACK or

NAK 0 udt_send(sndpkt) rdt_rcv(rcvpkt) &&

( corrupt(rcvpkt) ||

isNAK(rcvpkt) )

rdt_send(data)

rdt_rcv(rcvpkt)

&& notcorrupt(rcvpkt)

&& isACK(rcvpkt)

isNAK(rcvpkt) ) rdt_rcv(rcvpkt)

&& isACK(rcvpkt)

above Wait for

ACK or NAK 1

 

(33)

rdt2.1: receiver, handles garbled ACK/NAKs

Wait for 0 from

below

sndpkt = make_pkt(NAK, chksum) udt_send(sndpkt)

rdt_rcv(rcvpkt) &&

not corrupt(rcvpkt) &&

has_seq0(rcvpkt)

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt)

extract(rcvpkt,data) deliver_data(data)

sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt)

Wait for 1 from

below

extract(rcvpkt,data) deliver_data(data)

rdt_rcv(rcvpkt) &&

(corrupt(rcvpkt)

rdt_rcv(rcvpkt) &&

not corrupt(rcvpkt) &&

has_seq1(rcvpkt) rdt_rcv(rcvpkt) &&

(corrupt(rcvpkt)

sndpkt = make_pkt(NAK, chksum) udt_send(sndpkt)

Duplicato!!!!

(34)

rdt2.1

Sender:

 Pacchetti con numero di sequenza (basta un solo bit di

informazione)

 Stati:



In ogni stato si deve ricordare il numero di sequenz (0 o 1)

Receiver:

 Deve controllare se il pacchetto è duplicato



Ogni stato mantiene

informazione su quale

numero di sequenza si

attende

(35)

rdt2.2: Protocollo NAK-free



Come rdt 2.1 ma ...



Invece di inviare un msg NAK, il receiver invia un msg di ACK per l’ultimo pacchetto ricevuto correttamente

 Informazioni di stato

 “receiver must explicitly include seq # of pkt being ACKed”



ACK duplicato (lato sender) = NAK: ristrasmissione del pkt

corrente

(36)

rdt2.2: sender e receiver (in pillole)

above

rdt_send(data)

udt_send(sndpkt) rdt_rcv(rcvpkt) &&

isACK(rcvpkt,1) )

rdt_rcv(rcvpkt)

&& isACK(rcvpkt,0)

Wait for ACK

sender FSM

0

fragment

Wait for 0 from

below

extract(rcvpkt,data) rdt_rcv(rcvpkt) &&

(corrupt(rcvpkt) ||

has_seq1(rcvpkt))

sndpkt = make_pkt(ACK1, chksum)

udt_send(sndpkt)

receiver FSM fragment



(37)

rdt3.0: Canali con errori e perdita di pacchetti

Ipotesi aggiuntive: Il canale di trasmissione puo’ perdere pacchetti (dati o ACK)

 checksum, seq. #, ACK, sono sufficienti?

Come si gestisce la perdita di pacchetti?

 sender attende un certo periodo di tempo prima di trasmettere nuovamente l’informazione

Una possibile soluzione: sender rimane in attesa per un

periodo di tempo ragionevole

 I pkt vengono trasmessi

nuovamente se non viene ricevuto un ACK in questo periodo di

tempo

 Se la consegna del pkt (ACK) è solo ritardata (non avviene perdita)

 Duplicazione: gestita tramite il # di sequenza

 receiver specifica il # di sequenza del pkt ricevuto

 countdown timer

(38)

rdt3.0 sender

start_timer rdt_send(data)

Wait for ACK0

rdt_rcv(rcvpkt) &&

isACK(rcvpkt,1) )

above

start_timer rdt_send(data)

rdt_rcv(rcvpkt)

&& isACK(rcvpkt,0)

rdt_rcv(rcvpkt) &&

rdt_rcv(rcvpkt)

&& isACK(rcvpkt,1)

stop_timer stop_timer

udt_send(sndpkt) start_timer

timeout

udt_send(sndpkt) start_timer

timeout

rdt_rcv(rcvpkt)

Wait for call 0from

above

Wait for ACK1



rdt_rcv(rcvpkt)



(39)

rdt3.0: esempio

(40)

rdt3.0: esempio

(41)

rdt3.0



rdt3.0 funziona correttamente ma esibisce dei problemi di

efficienza relativi all’uso della banda di trasmissione

(42)

rdt3.0: stop-and-wait

first packet bit transmitted, t = 0

sender receiver

RTT last packet bit transmitted, t = L / R

first packet bit arrives

last packet bit arrives, send ACK

ACK arrives, send next packet, t = RTT + L / R

U

_sender

= .

008

30.008

=

^0.00027

microsec

L / R

RTT + L / R =

(43)

Pipeline

Pipelining: il mittente invia un certo numero di pacchetti senza attendere il relativo ACK



Operare correttamente con i # di sequenza



Buffer (mittente e destinatario)

 Due tipi di protocolli: go-Back-N, selective repeat

(44)

Pipelining: increased utilization

first packet bit transmitted, t = 0

sender receiver

RTT last bit transmitted, t = L / R

first packet bit arrives

last packet bit arrives, send ACK

ACK arrives, send next packet, t = RTT + L / R

last bit of 2^nd packet arrives, send ACK last bit of 3^rd packet arrives, send ACK

U

sender

= .

024

30.008

=

^0.0008

microsecon

3 * L / R RTT + L / R =

Increase utilization

by a factor of 3!

(45)

Protocolli “sliding window”

(46)

Go-Back-N

Sender:

 Header; k-bit per memorizzare i numeri di sequenza dei pkt.

 Si permette di avere una “finestra fino ad N”, di pkt consecutivi in cui non è stato ricevuto il relativo ack

 ACK(n): ACK cumulativo dei pkt con # minore di n

 timer per i pkt in trasmissione

 timeout(n): trasmettere il pkt n e tutti i pkt nella parte superiore della finestra di trasmissione

(47)

GBN: lato sender

Wait start_timer

udt_send(sndpkt[base]) udt_send(sndpkt[base+1])

…

udt_send(sndpkt[nextseqnum- 1])

timeout rdt_send(data)

if (nextseqnum < base+N) {

sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum) udt_send(sndpkt[nextseqnum])

if (base == nextseqnum) start_timer

nextseqnum++

} else

refuse_data(data)

base = getacknum(rcvpkt)+1 If (base == nextseqnum) stop_timer

else

rdt_rcv(rcvpkt) &&

notcorrupt(rcvpkt) base=1

nextseqnum=1

rdt_rcv(rcvpkt) && corrupt(rcvpkt)



(48)

GBN: lato receiver

ACK viene inviato per i pkt corretti aventi il piu’ slto numero seq #



ACK duplicati



Variabile di stato: expectedseqnum

 out-of-order pkt:



discard -> no buffering!

Wait

udt_send(sndpkt) default

rdt_rcv(rcvpkt)

&& notcurrupt(rcvpkt)

&& hasseqnum(rcvpkt,expectedseqnum) extract(rcvpkt,data)

deliver_data(data)

sndpkt = make_pkt(expectedseqnum,ACK,chksum) udt_send(sndpkt)

expectedseqnum++

expectedseqnum=1 sndpkt =

make_pkt(expectedseqnum,ACK,chksum)



(49)

GBN in

action

(50)

Selective Repeat

 receiver invia ACK di tutti i pkt ricevuti correttamente.



Buffer per gestire l’ordine dei pacchetti



Sender invia nuovamente i pkt senza ACK



Sender attiva timer per ogni pkt senza ACK

 La finestra del sender:



N # di sequenza consecutivi



Limite superiore alla dimensione della finestra

(51)

Selective repeat: sender, receiver windows

(52)

Selective repeat

data from above :



if next available seq # in window, send pkt

timeout(n):



resend pkt n, restart timer

ACK(n) in

[sendbase,sendbase+N]:



mark pkt n as received



if n smallest unACKed pkt, advance window base to next unACKed seq #

sender

pkt n in

[rcvbase, rcvbase+N-1]



send ACK(n)



out-of-order: buffer



in-order: deliver (also

deliver buffered, in-order pkts), advance window to next not-yet-received pkt

pkt n in

[rcvbase-N,rcvbase-1]



ACK(n)

otherwise:



ignore

receiver

(53)

Selective repeat

(54)

Selective repeat



seq #’s: 0, 1, 2, 3



window size=3



receiver non riesce a discriminare i due comportamenti



Window di dimensione

inferiore allo spazio

dei numeri di sequenza

(55)

Chapter 3 outline

 3.1 Transport-layer services

 3.2 Multiplexing and demultiplexing

 3.3 Connectionless transport: UDP

 3.4 Principles of

reliable data transfer

 3.5 Connection-oriented transport: TCP



segment structure



reliable data transfer



flow control



connection management

 3.6 Principles of congestion control

 3.7 TCP congestion

control

(56)

TCP: Overview RFCs: 793, 1122, 1323, 2018, 2581

 full duplex data:



bi-directional data flow in same connection



MSS: maximum segment size

 connection-oriented:



handshaking (exchange of control msgs) init’s sender, receiver state before data exchange

 flow controlled:



sender will not

 point-to-point:



one sender, one receiver

 reliable, in-order byte stream:



no “message boundaries”

 pipelined:



TCP congestion and flow control set window size

 send & receive buffers

s o c k e t s o c k e t

a p p l i c a t io n

w r i t e s d a t a a p p l ic a t io n

r e a d s d a t a

(57)

TCP segment structure

source port # dest port #

32 bits

application data

(variable length) sequence number

acknowledgement number

Receive window Urg data pnter checksum

F S P R A

head U

len not used

Options (variable length)

URG: urgent data (generally not used) ACK: ACK #

valid PSH: push data now (generally not used) RST, SYN, FIN:

connection estab (setup, teardown commands)

# bytes rcvr willing to accept counting by bytes of data

(not segments!)

Internet checksum (as in UDP)

(58)

Il segment TCP



Connessione:

 (SrcPort, SrcIPAddr, DsrPort, DstIPAddr)



window + flow control

 acknowledgment, SequenceNum, RcvdWinow



Flags

 SYN, FIN, RESET, PUSH, URG, ACK



Checksum

 pseudo header + TCP header + data

Sender

Data (SequenceNum)

Acknowledgment + RcvdWindow

Receiver

(59)

TCP seq. #’s and ACKs

Seq. #’s:

 byte stream “number”

of first byte in segment’s data ACKs:

 seq # of next byte expected from other side

 cumulative ACK Q: how receiver handles

out-of-order segments

 A: TCP spec doesn’t say, - up to

implementor

Host A Host B

Seq=42, AC

K=79, data = ‘C’

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

Seq=43, ACK=80

typesUser

‘C’

host ACKs receipt of echoed

‘C’

host ACKs receipt of

‘C’, echoes back ‘C’

simple telnet scenario time

(60)

TCP Round Trip Time and Timeout

Q: how to set TCP timeout value?



longer than RTT

 but RTT varies



too short: premature timeout



unnecessary retransmissions



too long: slow reaction to segment loss

Q: how to estimate RTT?



SampleRTT: measured time from segment transmission until ACK receipt



ignore retransmissions



SampleRTT will vary, want estimated RTT “smoother”



average several recent

measurements, not just

current SampleRTT

(61)

TCP Round Trip Time and Timeout

**EstimatedRTT = (1- )EstimatedRTT + SampleRTT**



Exponential weighted moving average



influence of past sample decreases exponentially fast



typical value:  = 0.125

(62)

Example RTT estimation:

(63)

TCP Round Trip Time and Timeout

Setting the timeout

 EstimtedRTT plus “safety margin”

 large variation in EstimatedRTT -> larger safety margin

 first estimate of how much SampleRTT deviates from EstimatedRTT:

**TimeoutInterval = EstimatedRTT + 4DevRTT DevRTT = (1-)DevRTT +**

***|SampleRTT-EstimatedRTT|**

(typically,  = 0.25)

Then set timeout interval:

(64)

Chapter 3 outline

 3.1 Transport-layer services

 3.2 Multiplexing and demultiplexing

 3.3 Connectionless transport: UDP

 3.4 Principles of

reliable data transfer

 3.5 Connection-oriented transport: TCP



segment structure



reliable data transfer



flow control



connection management

 3.6 Principles of congestion control

 3.7 TCP congestion

control

(65)

TCP:

Sender

00 sendbase = initial_sequence number 01 nextseqnum = initial_sequence number 02

03 loop (forever) { 04 switch(event)

05 event: data received from application above

06 create TCP segment with sequence number nextseqnum 07 start timer for segment nextseqnum

08 pass segment to IP

09 nextseqnum = nextseqnum + length(data)

10 event: timer timeout for segment with sequence number y 11 retransmit segment with sequence number y

12 compute new timeout interval for segment y 13 restart timer for sequence number y

14 event: ACK received, with ACK field value of y

15 if (y > sendbase) { /* cumulative ACK of all data up to y */

16 cancel all timers for segments with sequence numbers < y 17 sendbase = y

18 }

19 else { /* a duplicate ACK for already ACKed segment */

20 increment number of duplicate ACKs received for y 21 if (number of duplicate ACKS received for y == 3) { 22 /* TCP fast retransmit */

23 resend segment with sequence number y 24 restart timer for segment y

25 }

26 } /* end of loop forever */

Pseudo Codice

(66)

TCP reliable data transfer

 TCP creates rdt

service on top of IP’s unreliable service

 Pipelined segments

 Cumulative acks

 TCP uses single

retransmission timer

 Retransmissions are triggered by:



timeout events



duplicate acks

 Initially consider

simplified TCP sender:



ignore duplicate acks



ignore flow control,

congestion control

(67)

TCP sender events:

data rcvd from app:

 Create segment with seq #

 seq # is byte-stream number of first data byte in segment

 start timer if not

already running (think of timer as for oldest unacked segment)

 expiration interval:

TimeOutInterval

timeout:

 retransmit segment that caused timeout

 restart timer Ack rcvd:

 If acknowledges previously unacked segments



update what is known to be acked



start timer if there are outstanding segments

Se scade un timer, lo rifaccio ripartire con valore di time-out doppio.

Se ok, risettato al valore ottenuto con

estimatedRTT e devRTT

(68)

TCP sender

(simplified)

NextSeqNum = InitialSeqNum SendBase = InitialSeqNum loop (forever) {

switch(event)

event: data received from application above

create TCP segment with sequence number NextSeqNum if (timer currently not running)

start timer

pass segment to IP

NextSeqNum = NextSeqNum + length(data) event: timer timeout

retransmit not-yet-acknowledged segment with smallest sequence number

start timer

event: ACK received, with ACK field value of y if (y > SendBase) {

SendBase = y

if (there are currently not-yet-acknowledged segments) start timer

Comment:

• SendBase-1: last cumulatively

ack’ed byte Example:

• SendBase-1 = 71;

y= 73, so the rcvr wants 73+ ;

y > SendBase, so that new data is acked

(69)

TCP: retransmission scenarios

Host A

Seq=100, 20 bytes data ACK=100

time premature timeout

Host B

Seq=92, 8 bytes data ACK=120 Seq=92, 8 bytes data

Seq=92 timeout

ACK=120

Host A

Seq=92, 8 bytes data

ACK=100

timeout loss

Host B

X

time

Seq=92 timeout

SendBase

= 100

SendBase

= 120

SendBase

= 120 Sendbase

= 100

(70)

TCP retransmission scenarios (more)

Host A

timeout loss

Host B

X

Seq=100, 2

0 bytes data

ACK=120

time

SendBase

= 120

(71)

TCP ACK generation [RFC 1122, RFC 2581]

Event at Receiver

Arrival of in-order segment with expected seq #. All data up to expected seq # already ACKed Arrival of in-order segment with expected seq #. One other segment has ACK pending Arrival of out-of-order segment higher-than-expect seq. # . Gap detected

Arrival of segment that

partially or completely fills gap

TCP Receiver action

Delayed ACK. Wait up to 500ms

for next segment. If no next segment, send ACK

Immediately send single cumulative ACK, ACKing both in-order segments

Immediately send duplicate ACK,

indicating seq. # of next expected byte

Immediate send ACK, provided that segment startsat lower end of gap

(72)

Fast Retransmit

 Time-out period often relatively long:



long delay before resending lost packet

 Detect lost segments via duplicate ACKs.



Sender often sends

many segments back-to- back



If segment is lost,

there will likely be many duplicate ACKs.

 If sender receives 3 ACKs for the same data, it supposes that segment after ACKed data was lost:



fast retransmit: resend

segment before timer

expires

(73)

event: ACK received, with ACK field value of y if (y > SendBase) {

SendBase = y

if (there are currently not-yet-acknowledged segments) start timer

} else {

increment count of dup ACKs received for y if (count of dup ACKs received for y = 3) { resend segment with sequence number y }

Fast retransmit algorithm:

a duplicate ACK for

already ACKed segment fast retransmit

(74)

Commenti

 ACK comulativi

 Sender



Sendbase = piu’ piccolo numero di sequenza dei segmenti trasmessi ma di cui non si è ancora ricevuto ACK



Nextseqnum = numero di sequenza del prossimo

dato da inviare

(75)

TCP vs GBN

 Sender invia i segmenti 1, 2, …, N.

Assumiamo che i segmenti arrivino correttamente al destinatario.

 ACK(n) viene perduto (unico ACK perduto)

 GBN trasmette nuovamente i segmenti ??

 TCP trasmette nuovamente i segmenti ??

(76)

TCP vs GBN

 Sender invia i segmenti 1, 2, …, N.

Assumiamo che i segmenti arrivino correttamente al destinatario.

 ACK(n) viene perduto (unico ACK perduto)

 GBN trasmette nuovamente i segmenti n, n+1 , …, N

 TCP trasmette nuovamente al piu’ il

segmento n (se il timeout di n scatta prima

dell’arrivo di ACK(n+1))

(77)

Chapter 3 outline

 3.1 Transport-layer services

 3.2 Multiplexing and demultiplexing

 3.3 Connectionless transport: UDP

 3.4 Principles of

reliable data transfer

 3.5 Connection-oriented transport: TCP



segment structure



reliable data transfer



flow control



connection management

 3.6 Principles of congestion control

 3.7 TCP congestion

control

(78)

TCP Flow Control

 receive side of TCP connection has a

receive buffer:

 speed-matching

service: matching the send rate to the

receiving app’s drain

 app process may be rate slow at reading from buffer

sender won’t overflow receiver’s buffer by

transmitting too much,

too fast

flow control

(79)

TCP Flow control: how it works

(Suppose TCP receiver discards out-of-order segments)

 spare room in buffer

= RcvWindow

= RcvBuffer-[LastByteRcvd - LastByteRead]

 Rcvr advertises spare room by including value of RcvWindow in

segments

 Sender limits unACKed data to RcvWindow



guarantees receive

buffer doesn’t overflow

(80)

Sliding Window

 Sending side



LastByteAcked < = LastByteSent



LastByteSent < = LastByteWritten



buffer bytes between LastByteAcked and LastByteWritten

Sending application

LastByteWritten TCP

LastByteSent LastByteAcked

Receiving application

LastByteRead TCP

LastByteRcvd NextByteExpected

 Receiving side



LastByteRead <

NextByteExpected



NextByteExpected < = LastByteRcvd +1



buffer bytes between

NextByteRead and

(81)

TCP Flow Control: variabili di stato

 Send buffer size: MaxSendBuffer

 Receive buffer size: MaxRcvBuffer

 Receiving side

 LastByteRcvd - LastByteRead < = MaxRcvBuffer

 AdvertisedWindow = MaxRcvBuffer - (NextByteExpected - NextByteRead)

 Sending side

 LastByteSent - LastByteAcked < = AdvertisedWindow

 EffectiveWindow = AdvertisedWindow - (LastByteSent - LastByteAcked)

 LastByteWritten - LastByteAcked < = MaxSendBuffer



block sender if (LastByteWritten - LastByteAcked) + y >

MaxSenderBuffer

(82)

TCP Controllo del flusso: azioni

 Inviare ACK all’arrivo di segmenti

 Se ho finito di spedire e ho AdvertisedWindow = 0?



Problema: il ricevente non sapra’ mai se ho di nuovo spazio nel buffer



 il ricevente se ha AdvertisedWindow = 0 continua a spedire ack fino a che si libera il

buffer

(83)

Chapter 3 outline

 3.1 Transport-layer services

 3.2 Multiplexing and demultiplexing

 3.3 Connectionless transport: UDP

 3.4 Principles of

reliable data transfer

 3.5 Connection-oriented transport: TCP



segment structure



reliable data transfer



flow control



connection management

 3.6 Principles of congestion control

 3.7 TCP congestion

control

(84)

TCP Connection Management

Recall: TCP sender, receiver establish “connection” before exchanging data segments



initialize TCP variables:



seq. #s



buffers, flow control info (e.g. RcvWindow)



client: connection initiator

Socket clientSocket = new Socket("hostname","port number");



server: contacted by client

Socket connectionSocket = welcomeSocket.accept();

Three way handshake:

Step 1:

client host sends TCP SYN segment to server



specifies initial seq #



no data

Step 2:

server host receives SYN, replies with SYNACK segment



server allocates buffers



specifies server initial seq.

#

Step 3: client receives SYNACK,

replies with ACK segment,

which may contain data

(85)

TCP Connection Management (cont.)

Closing a connection:

client closes socket:

clientSocket.close();

Step 1:

client end system sends TCP FIN control segment to server

Step 2:

server receives FIN, replies with ACK. Closes connection, sends FIN.

client

FIN

server

ACK

ACK FIN

close

closedtimed wait

(86)

TCP Connection Management (cont.)

Step 3:

client receives FIN, replies with ACK.

 Enters “timed wait” - will respond with ACK to

received FINs

Step 4:

server, receives ACK.

Connection closed.

Note:

with small modification, can handle simultaneous FINs.

client

FIN

server

ACK

ACK FIN

closing

closedtimed wait

closed

(87)

TCP Connection Management (cont)

TCP client lifecycle

TCP server

lifecycle

(88)

Chapter 3 outline

 3.1 Transport-layer services

 3.2 Multiplexing and demultiplexing

 3.3 Connectionless transport: UDP

 3.4 Principles of

reliable data transfer

 3.5 Connection-oriented transport: TCP



segment structure



reliable data transfer



flow control



connection management

 3.6 Principles of congestion control

 3.7 TCP congestion

control

(89)

Principles of Congestion Control

Congestion:

 informally: “too many sources sending too much data too fast for network to handle”

 different from flow control!

 manifestations:



lost packets (buffer overflow at routers)



long delays (queueing in router buffers)

 a top-10 problem!

(90)

Le caratteristiche del problema

 Risorse allocate per evitare la congestione

 Controllo della congestione se (e quando) si manifesta

 Implementazione

 Host (protocolli del livello di trasporto)

 Router (politiche per la gestione delle code)

 Quale modello di servizio

 best-effort (Internet)

 QoS quality of service (Futuro)

Destination 1.5-Mbps T1 link

Router

Source 2 Source

1

100-Mbps FDDI 10-Mbp

s Ethernet

(91)

Contesto



Sequenze di pacchetti che viaggiono nella rete



Router hanno poca informazione sullo stato della rete

Router

Source 2 Source

1

Source 3

Router

Destination 2 Destination

1

(92)

Causes/costs of congestion: scenario 1

 two senders, two receivers

 one router,

infinite buffers

 no retransmission

 large delays

when congested

 maximum achievable

unlimited shared output link buffers Host A

_in: original data

Host B

_out

(93)

Troughput per la connessione

 Throughput per la connessione = numero di byte al secondo al receiver in funzione della velocità di spedizione

 Grandi ritardi quando la velocità dei

pacchetti in arrivo è prossima alla capacità

del router

(94)

Causes/costs of congestion: scenario 2

 one router, finite buffers

 sender retransmission of lost packet

finite shared output link buffers Host A _

in : original data

Host B

_out

'_in: original data, plus retransmitted data

(95)

Congestione

 La velocità del sender è uguale al carico offerto dalla rete

 Sender deve ristramettere pacchetti per compensare le perdite

Costo della congestione:



Maggiore carico per la trasmissione dei pacchetti

(96)

Cause della Congestione



Quattro sender



multihop



Timeout + ritrasmissione

Cosa succede quando aumenta il carico offerto dalle rete?

Quando il carico offerto a B è elevato

il troughput della connessione A-C

risulta zero:

il buffer in R2 è sempre pieno

(97)

Costo della Congestione

 Quando un pacchetto è perso lungo un

percorso la capacità di trasmissione dei

router lungo il percorso è sprecata!!

(98)

Causes/costs of congestion: scenario 3

Another “cost” of congestion:

 when packet dropped, any “upstream transmission capacity used for that packet was wasted!

H o s t A

H o s t B



o u t

(99)

Politiche di gestione delle code

 First-In-First-Out (FIFO)



Non abbiamo alcuna politica di gestione che dipende dalle caratteristiche dei pacchetti

 Fair Queuing (FQ)



Meccanismi di strutturazione del flusso dei pacchetti



Un pacchetto non puo’ mai superare la capacità del router



Code con priorità (WFQ)

Flow 1

Flow 2

Flow 3

Flow 4

Round-robin service

(100)

Approaches towards congestion control

End-end congestion control:



no explicit feedback from network



congestion inferred from end-system observed loss, delay



approach taken by TCP

Network-assisted congestion control:



routers provide feedback to end systems



single bit indicating congestion (SNA,

DECbit, TCP/IP ECN, ATM)



explicit rate sender should send at

Two broad approaches towards congestion control:

(101)

Chapter 3 outline

 3.1 Transport-layer services

 3.2 Multiplexing and demultiplexing

 3.3 Connectionless transport: UDP

 3.4 Principles of

reliable data transfer

 3.5 Connection-oriented transport: TCP



segment structure



reliable data transfer



flow control



connection management

 3.6 Principles of congestion control

 3.7 TCP congestion

control

(102)

TCP: Controllo della Congestione

 Idea di base: si controlla la velocità di trasmissione controllando il numero dei segmenti trasmessi ma di cui non si è ancora ricevuto ACK: W

 Maggiore è il valore di W maggiore è il throughput della connessione.

 Quando si verifica una perdita di segmento

allora si diminuisce il valore W

(103)

TCP Controllo della congestione

 Due fasi



slow start (partenza lenta)



congestion avoidance (annullamento della congestione)

 Valori da considerare:



Congwin



threshold: soglia che segnala il passaggio tra

le due fasi

(104)

Reti di calcolatori e Sicurezza