TCP
Università
di Palermo
TCP
1
LA
Transport Control Protocol
Protocollo di trasporto usato più largamente nel mondo
La RFC 793 recita:
TCP is a connection-oriented, end-to-end reliable protocol designed to fit into
a layered hierarchy of protocols which support multi-network applications.
The TCP provides for reliable inter-process communication between pairs of
processes in host computers attached to distinct but interconnected computer
communication networks.
Very few assumptions are made as to the reliability of the communication
protocols below the TCP layer.
Università
di Palermo
TCP
2
LA
Evoluzione del TCP
Formalizzato nel Sep 1981
RFC 793 – Transmission Control Protocol
TCP fu definito formalmente in RFC 793 anche se successivamente furono
scoperti vari errori e inconsistenze che vennero corrette con la pubblicazione
di nuove RFC (Cfr. RFC 813, RFC 1122, RFC 1323)
In breve tempo è divenuto così popolare che l’ISO
derivò da esso uno standard, il TP-4
Università
di Palermo
TCP
3
LA
Evoluzione del TCP
(cont)
A partire dalla nascita evoluzione continua
RFC 813 – Delayed ACK
RFC 1072 – TCP Extension for Long-Delay Paths
RFC 1122 – Requirements for Internet Hosts
RFC 1185 – TCP Extension for High-Speed Paths
RFC 1323 - TCP Extensions for High Performance
RFC 2001 – TCP Slow start, Congestion avoidance, Fast retransmit and …….
RFC 2581 – TCP Congestion Control
RFC 2988 – TCP’s computing retransmission timer
..........................................
Università
di Palermo
TCP
4
LA
Protocol Architecture
TCP sopra IP (un layer connection-less e con poche funzioni)
Upper
Layers
Upper
Layers
Ampio range di richieste in un ambiente dinamico
End-to-End communication
TCP
TCP
IP
IP
IP
IP
Data Link
Data Link
Data Link
Data Link
Physical
Physical
Physical
Physical
S.net_1
Università
di Palermo
TCP
S.net_2
S.net_3
5
LA
Overview
TCP non risiede nei router
IP non fornisce sequenziamento
TCP deve fornire sequenziamento
IP non fornisce traffic acknowledgment
TCP deve fornire reliability
IP è connectionless
TCP deve fornire flow control
TCP deve fornire multiplexing
Università
di Palermo
TCP
6
LA
Major Features of TCP
Servizi all’ULP:
Connection oriented data management
Reliable data transfer
Resequencing
Go-back n protocol
Flow control (sliding window / credits)
Multiplexing
Full-duplex transmission
Precedence and security
Graceful close
Stream oriented data transfer
Push function
Università
di Palermo
TCP
7
LA
Stream Data Transfer
L’applicazione consegna quantità arbitrarie di dati al TCP come
un un flusso (stream) senza confini di record; il TCP non garantisce
che i dati verranno ricevuti negli stessi blocchi come trasmessi
Il TCP spezza questi dati in segmenti, ciascuno
dei quali si adatta ad un datagram IP
Lo stream originario è numerato per byte
Il segmento, formato da un numero intero di bytes, contiene il numero
di sequenza dei byte di dati
Università
di Palermo
TCP
8
LA
TCP connection
Process X
…
Process Y
port N
TCP
…
…
reliable
TCP connection
IP
port M
…
connections
sockets
TCP
IP
IP addresses
unreliable
host A
Università
di Palermo
TCP
IP datagrams
host B
9
LA
Transport address
Conosciamo Physical, Data Link e Network adddresses
In uno stesso host possibili più applicazioni contemporanee
Insufficienza degli address degli strati inferiori
Servono indirizzi per gli strati di trasporto e applicazione
In OSI
T-SAP
In TCP/IP
Protocol ID, Port, Socket
Università
di Palermo
TCP
10
LA
Layer’s addresses
Sending computer
Receiving computer
User Application
User Application
Internet Application
Internet Application
Protocol ID
Transport
Transport
Protocol ID
IP address
Network
Network
IP address
SAPs
EtherType
LLC
LLC
SAPs
EtherType
MAC address
MAC
MAC
MAC address
Physical
Physical
User
names
Ports
Università
di Palermo
TCP
User
names
Ports
11
LA
Port & Socket
Numeri di Port
255 per porte usate frequentemente (Well Known)
23
Telnet
25
SMTP
137
NETBIOS-NS
Socket = Port + IP Address
Una coppia di socket identifica una connessione
Università
di Palermo
TCP
12
LA
TCP Flow Control
TCP use a credit scheme to perform the flow control
This feature decouples acknowledgement from flow control
Each transmitted segment have to include in its header
three fields required for this flow control type:
Sequence Number
(SN)
Acknowledgement Number (AN)
Window
Università
di Palermo
TCP
(W)
13
LA
TCP Segments
Source Port
Destination Port
Sequence Number (SN)
Acknowledgment Number (AN)
Data
Offset
Reserved
Window
Flags
Checksum
Urgent pointer
Options + Padding
Data
Università
di Palermo
TCP
14
LA
Sequence Number
Rappresenta (a parte un valore iniziale) il numero del primo
byte di dati nel segmento
Si tratta di un numero di 32 bit , quindi può avere come valore
massimo 2 32-1
Tutti i calcoli riguardanti i sequence numbers devono essere modulo 2 32
Università
di Palermo
TCP
15
LA
Data Offset/Reserved bits
Data Offset (4 bits)
Il numero di word da 32 bit presenti nell’ header TCP
Indica il punto di inizio del campo data
Reserved bits (6 bits)
Reserved for future use
Must be zero
Università
di Palermo
TCP
16
LA
Flags
6 control bits
URG: Urgent Pointer field significant
ACK: Acknowledgment field significant
PSH: Push Function
RST: Reset the connection
SYN: Synchronize sequence numbers
FIN: No more data from sender
Università
di Palermo
TCP
17
LA
Window/Urgent Pointer
Window
TCP è un protocollo sliding window
Il numero di Bytes di dati, ad iniziare da quello indicato nel campo
Acknowledgement che il sender del segmento è disposto ad accettare
Urgent Pointer
Questo valore, sommato al sequence number del segmento, fornisce
il sequence number dell’ultimo ottetto in una sequenza di dati urgenti
Il ricevitore viene a conoscere la quantità di dati urgenti
Università
di Palermo
TCP
18
LA
Pseudo Header
32
Source IP Address
Destination IP Address
zero
Protocol
8
8
Università
di Palermo
TCP
TCP Length
16
19
LA
Options
In origine solo tre options:
Oggi molte altre
Università
di Palermo
TCP
Kind
Length
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
19
4
3
2
N
6
6
10
2
3
Option
End of option list
No operation
Maximum segment size
Window scale factor
SACK Permitted
SACK
Echo (obsoleted by option 8)
Echo Reply (obsoleted by option 8)
Timestamp
Partial Order Connection Permitted
Partial Order Service Profile
CC
CC.NEW
3
N
18
CC.ECHO
TCP Alternate Checksum Request
TCP Alternate Checksum Data
MD5 Signature
20
LA
Window Scale Option
Definita nella RFC 1323
Con TCP normale la SEG.WND definita tramite un campo da 16 bit
16
Dimensione massima della finestra = 2
1 = 65535 Bytes
Dimensione troppo piccola nel caso delle LFT (elephan)
Con Window Scale Option finestra definita con 32 bit
Per compatibilità SEG.WND espressa sempre con 16 bit
Nella option è trasmesso uno shift.cnt che fornisce lo shift per
passare dall’una all’altra finestra
Entambi i sistemi devono accettare la option, altrimenti non si applica
L’option è negoziata soltanto nell’handshake iniziale (SYN)
Università
di Palermo
TCP
21
LA
Port Assignmet
Host A
Host B
Host C
3
2
1
Source Port = 400
Destination Port = 25
+ IP Address
Source Port = 400
Destination Port = 25
+ IP Address
Source Port = 401
Destination Port = 25
Università
di Palermo
TCP
+ IP Address
22
LA
Passive and Active Opens
Instaurazione di connessione:
Controllo dell’esistenza del corrispondente
Negoziazione dei parametri opzionali
Allocazione delle risorse
Due tipologie:
Passive-open
Active-open
Università
di Palermo
TCP
23
LA
Transmission Control Block
Insieme di variabili che identifica la connessione ed il suo stato
Local and remote socket numbers
Pointers to send and receive buffers
Pointers to the retransmit queue
Security and precedence value for the connection
Current segment
Variables associated with send and receive sequence numbers
ISS
Initial send sequence number
SND.UP
Sequence number of last octet of urgent data
RCV.NXT Sequence number of next octet to be received
Università
di Palermo
TCP
RCV.IRS
Initial receive sequence number
…………
………………………………………………
24
LA
Retransmission Operation
TCP non usa NAK
In assenza di ACK, ritrasmissione
A
B
SN = 3
(300 bytes sent)
1
AN = 303
2
SN = 303
(300 bytes sent)
AN = 303
3
4
SN = 603
(300 bytes sent)
5
AN = 303
6
7
{
8
Università
di Palermo
TCP
SN = 303
(300 bytes sent)
SN = 603
(300 bytes sent)
AN = 903
25
LA
User Interfaces
Service Request
Primitives
Service Response
Primitives
UNSPECIFIED-PASSIVE
OPEN-ID
OPEN
OPEN-FAILURE
FULL-PASSIVE-OPEN
OPEN-SUCCESS
ACTIVE-OPEN
DELIVER
ACTIVE-OPEN-WITH-DATA
CLOSING
SEND
TERMINATE
RECEIVE
STATUS-RESPONSE
ALLOCATE
ERROR
CLOSE
ABORT
STATUS
Università
di Palermo
TCP
26
LA
Items Passed to IP
Il TCP passa alcuni parametri al sottostante modulo IP
Precedence
Normal/Low Delay
Normal/High Throughput
Normal/High Reliability
Security
Università
di Palermo
TCP
27
LA
Connection Establishment
Process A
Process B
Active OPEN
Passive OPEN,
waits for active request
SYN = 1; SN = k
SYN = 1; ACK = k+1; SN = j
ACK = j+1
Università
di Palermo
TCP
28
LA
Initial Sequence Numbers (ISN)
Possibili diverse istanze (incarnazioni) della stessa connessione
Problema:
Come evitare confusioni con i segmenti duplicati delle incarnazioni precedenti?
Bisogna evitare che i segmenti di una incarnazione utilizzino gli stessi SN dei
segmenti di una precedente incarnazione che possono ancora trovarsi in rete
Alla creazione di una connessione, uso di generatore di ISN legato al tempo
Scatto di un bit ogni
4 µs
Riciclo dopo 2^32 * 4*10^-6
4,55 h
Tempo di riciclo > MSL
Università
di Palermo
TCP
29
LA
Connection Management
CLOSED
Passive OPEN
Create TCB
rcv SYN
snd SYN, ACK
CLOSE
Delete TCB
CLOSE
Delete TCB
LISTEN
rcv SYN, snd ACK
SYN RCVD
rcv ACK of SYN
CLOSE
snd FIN
ESTAB
rcv FIN
Snd ACK
SYN SENT
rcv SYN, ACK
snd ACK
rcv FIN
snd ACK
Closed
Snd FIN
FIN WAIT-1
Active OPEN
Create TCB
Send SYN
CLOSE WAIT
CLOSE
snd FIN
CLOSING
LAST-ACK
rcv ACK of FIN
rcv ACK of FIN
rcv FIN
snd ACK
FIN WAIT-2
Università
di Palermo
TCP
TIME WAIT
rcv ACK of FIN
Time=2 MSL
del TCB
CLOSED
30
LA
Retransmission Timer
Problema: Stima del timer per Ritrasmissione
Send Delay (SD)
A
B
Processing
Time (PT)
Receive Delay (RD)
RTT = SD + RD + PT
Università
di Palermo
TCP
31
LA
Early Version
Media semplice
k
ARTT( k ) =
ARTT( k ) =
i =1
RTT( i )
k
k 1
RTT( k )
ARTT( k 1) +
k
k
k>1
Valori descrescenti
Valori crescenti
20
15
15
10
Osservazione
Media semplice
10
5
5
0
0
0
5
Università
di Palermo
10
TCP
15
20
25
30
0
5
10
15
20
25
32
30
LA
Smoothed Round-Trip Time
SRTT( k ) =
0
RTT( k ) +
1
RTT( k 1) +
2
RTT( k 2) + . . . +
cost
Per congruenza:
i
cost =
i =0
=
Università
di Palermo
cost
= RTT
i=0
<1
1
TCP
i =1
i
1
SRTT( k ) =
RTT(1)
i
SRTT( ) = RTT
Da cui
k 1
k
i =1
k i
(1
) RTT( i )
33
LA
Smoothed Round-Trip Time
) RTT( k ) +
SRTT( k ) = (1
SRTT( k ) = (1
k 1
k 1 i
(1
k 1
k i
i =1
) RTT( k ) +
k 1
(1
k 1 i
i =1
(2)
) RTT( i )
(1
) RTT( i )
) RTT( i ) = SRTT( k 1)
i =1
In conclusione relazione ricorsiva:
SRTT( k ) = (1
Università
di Palermo
TCP
) RTT( k ) +
SRTT( k 1)
34
LA
Smoothed and Simple Average
Valori decrescenti
Valori crescenti
12
25
10
20
8
Osserv .
15
Med. semplice
6
Med. sm.d a=0,5
4
Med. sm.d a=0,875
10
2
5
0
0
0
5
10
15
20
25
30
0
5
10
15
20
25
30
12
10
8
Osserv.
Med. semplice
6
Med. sm.d a=0,5
Med. sm.d a=0,875
4
2
Università 0
di Palermo
0
TCP
5
10
15
20
25
30
35
LA
Retransmission Timeout
IL Value for Timeout (VT) non può essere uguale a
VT = SRTT +
Logica migliore
RFC 793 presenta
Logica scorretta
VT =
SRTT
TCP
( > 1)
as an illustration la relazione
VT = min[Ubound, max(Lbound,
Università
di Palermo
SRTT
SRTT)]
= 0,8 ÷ 0 ,9
= 1,3 ÷ 2
Ubound = 60 s
Lbound = 1 s
36
LA
Round Trip Time variance
SRTT( k ) = (1
) RTT( k ) +
SRTT( k ) = SRTT( k 1) + (1
SRTT( k 1)
) [RTT( k )
SRTT( k 1)]
Lo standard originale non funziona bene con varianza elevata
3 problemi:
Con bit rate basso stima dipendente fortemente dai dati
Brusche ed imprevedibili variazioni di RTT provocata dal traffico internet
Possibile assenza di un riscontro immediato dei singoli segmenti
Università
di Palermo
TCP
37
LA
Round Trip Time Variance
(2)
RFC 793 tiene conto della variabilità di RTT con il fattore costante
Procedura migliore: basarsi sulla varianza di RTT
mdev
mean deviation
mdev ( X ) = E[ X
mdev ( X ) =
Università
di Palermo
TCP
n
i =1
E[X ] ]
xi E[ X ] pi
38
LA
Round Trip Time Variance
(3)
Nel caso presente
1
mdev ( X ) = n
1
mdev ( X ) = 2
n
2
n
i =1
n
i =1
xi E [ X ]
2
2
xi E [ X ]
1
(X ) =
n
n
i =1
(xi
2
E[ X ])
X n^2
n
i =1
Università
di Palermo
2
xi E [ X ]
TCP
n
n
i =1
(xi
2
E[ X ])
39
LA
Round Trip Time Variance
(4)
Per distribuzione gaussiana
mdev 2 ( X ) =
2
2
(X)
mdev approssimazione della varianza
Si vuole stimare
mdev
Si definiscono
ARRT( i ) = round -trip time stimato
AERR( i ) = RTT ( i )
Università
di Palermo
TCP
ARTT( i 1)
= errore di stima
40
LA
Round Trip Time Variance
(5)
Si può esprimere la mean deviation calcolata su k samples come
1
mdev k =
k
k
i =1
RTT( i ) E[ X ]
Si sostituisce ad E[X] il valor medio stimato su i -1 samples ARTT(i -1)
Si ottiene un valore stimato ADEV della mean deviation
1
ADEV( k ) =
k
k
i =1
RTT ( i ) ARTT( i 1)
1
ADEV( k ) =
k
Università
di Palermo
TCP
k
i =1
AERR( i )
41
LA
Round Trip Time variance
ADEV( k ) =
(6)
k 1
1
ADEV( k 1) +
AERR(k)
k
k
Valore di ADEV ottenuto con media semplice
Opportunità di pesare in modo differente i samples
Procedura di Van jacobson
Uso della media esponenziale
Espressione di SRTT
SRTT( k ) = (1
Università
di Palermo
TCP
) RTT( k ) +
SRTT( k 1)
42
LA
Round Trip Time Variance
(7)
1-g
SRTT( k ) = (1 g ) SRTT( k 1) + g RTT( k )
In analogia a:
AERR(k) = RTT(k) - ARTT(k-1)
Errore per media smoothed
SERR(k) = RTT(k) - SRTT(k-1)
Università
di Palermo
TCP
43
LA
Round Trip Time Variance
(8)
In analogia alla media smoothed di RTT media smoothed della deviation
SDEV(k) = (1-h)·SDEV(k-1) + h·|SERR(k)|
Ora più correttamente:
RTO(k) = SRTT(k) + f·SDEV(k)
Van Jacobson ha proposto:
g = 0,125
(
= 0,875)
h = 0,25
f = 2
Università
di Palermo
TCP
f = 4
44
LA
Round Trip Time Variance
Valori crescenti
(9)
Valori decrescenti
40
25
35
20
30
Osserv .
15
25
SDEV
10
RTO
f=2
RTO
f=4
20
15
10
5
5
0
0
0
5
Università
di Palermo
10
15
TCP
20
25
30
0
5
10
15
20
25
30
45
LA
Window Management
TCP self-clocking
Pr
Pb
Receiver
Sender
Ab
As
Università
di Palermo
TCP
Ar
46
LA
Window Management
•
(2)
Congestion Window
Congestion Window fissata dal sender
Allowed_Window =
min (receiver_advertisement, congestion_window)
Strategy:
Multiplicative Decrease Congestion Avoidance: Upon loss of a segment, reduce the
congestion window by half (down to a minimum of at least one segment).
For those segments that remain in the allowed window,
backoff the transmission timer exponentially.
Università
di Palermo
TCP
47
LA
Window Management
(3)
Segment Sequence Number [KB]
• Slow-start
Università
di Palermo
Send Time [s]
TCP
48
LA
Window Management
(4)
Con RFC 2001 introduzione di una partenza graduale
Avvio con finestra da un segmento e incremento fino al massimo
Slow Start (additive) Recovery
Whenever starting traffic on a new connection or increasing traffic
after a period of congestion, start the congestion window at the
size of a single segment and increase the congestion window by
one segment each time an acknowledgement arrives.
Università
di Palermo
TCP
49
LA
Window Management
(5)
Congestion window
increases exponentially
RTT
Increase by 1
segment per ACK
Time
Topening (W ) = RTT log 2 W
Sender
Università
di Palermo
TCP
Receiver
50
LA
Backoff esponenziale dell’RTO
RTO = Round trip Time Out
Siccome il timeout è dovuto probabilmente ad una congestione (pacchetto perduto
o round trip lungo), il mantenimento di RTO non è una buona idea
RTO viene incrementato ogni volta che un segmento è ritrasmesso
RTO =
*RTO
Normalmente
=2
Binary exponential backoff
Università
di Palermo
TCP
51
LA
Delayed ACK - SWS
• Silly Window Syndrome ( SWS)
RFC 793 asserisce genericamente che i dati devono essere
promptly acknowledged
Il receiver invia al sender la offered window
Il sender in base alla offered window calcola la usable window
Usable Window = Offered Window – Unacknowledged Data
Esempio:
Ricevitore
1000 bytes
Sender invia 5 segmenti da 200
Dopo il primo segmento il receiver invia un ACK
Al ricevitore nuovamente disponibile spazio per 1000
Università
di Palermo TCP
52
LA
Silly Window Syndrome
Il sender ricalcola la Usable Window = 1000 – 800 = 200
Il sender ha 50 bytes da inviare fino all’arrivo di un “push” point
Il sender invia un segmento da 50 bytes
Il sender invia un segmento da 150 bytes
Il receiver riceve il segmento da 50 bytes e comunica una
offered window di 1000 bytes
Nuova usable window di 50 bytes
Il sender invia un segmento da 50 bytes (anche in presenza di molti bytes)
Università
di Palermo
TCP
53
LA
Silly Window Syndrome
(2)
Occasionalmente, a causa di confini naturali, la finestra viene spezzata in due
La finestra non viene riunita naturalmente
Continuo invio di piccoli segmenti
Silly Window Syndrome
Per evitarla: Improved Window Algorithm
# Quando il receiver dispone di una piccola quantità di dati, riduce la O_w
Il sender non può inviare altri dati
Quando il receiver ha ricevuto abbastanza dati incremento la O_w
Università
di Palermo
TCP
54
LA
Silly Window Syndrome
(3)
Quando si deve riaprire la finestra ?
Troppo presto
SWS
Troppo tardi
Ritardo
Rule of thumb Reduce the offered window until the reduction
constitutes one half of the available space
Altro algoritmo:
Il sender calcola una U_w,
La confronta con la O_w,
Si ferma finchè la U_w non è maggiore di una frazione della O_w
Tipicamente 25 %
Università
di Palermo
TCP
55
LA
RTT Measurement
RTT calcolato partendo dalla differenza tra l’istante di trasmissione
e quello di arrivo ACK
Problema: Gli ACK non portano informazione circa il pacchetto a cui si riferiscono
Ambiguità dell’Acknowledgement
Scelta dell’istante della prima trasmissione
Scelta dell’istante di ritrasmissione
Università
di Palermo
TCP
Sovrastima di RTT
Sottostima di RTT
56
LA
Karn Algorithm
Risoluzione del problema della ambiguità con:
Echo option (Oct. 1988)
Algoritmo di Karn (Nov. 1991)
In caso di segmenti ritrasmessi il sender non misura RTT ( e non aggiorna RTO)
In caso di ritrasmissione calcolo di RTO non in base a RTT ma con la formula di backoff
RTO = 2 RTO
Uso ripetuto procedura di backoff fino a trasmissione singola
Università
di Palermo
TCP
57
LA