Transport Control Protocol: Outline
Transport Control Protocol: Outline
Transport Control Protocol: Outline
Outline
TCP objectives revisited
TCP basics
New algorithms for RTO calculation
CS 640 1
TCP Overview
• TCP is the most widely used Internet protocol
– Web, Peer-to-peer, FTP, telnet, …
• A two way, reliable, byte stream oriented end-to-end
protocol
– Includes flow and congestion control
• Closely tied to the Internet Protocol (IP)
• A focus of intense study for many years
– Our goal is to understand the RENO version of TCP
• RENO is most widely used TCP today
• RFC 2001 (now expired)
• RENO mainly specifies mechanisms for dealing with congestion
CS 640 2
TCP Features
• Connection-oriented • Full duplex
• Byte-stream • Flow control: keep sender from
overrunning receiver
– app writes bytes
• Congestion control: keep sender
– TCP sends segments
from overrunning network
– app reads bytes
• Reliable data transfer
Write Read
bytes bytes
…
…
TCP TCP
Send buffer Receive buffer
…
Segment Segment Segment
Transmit segments
CS 640 3
Segment Format
0 4 10 16 31
SrcPort DstPort
SequenceNum
Acknowledgment
Checksum UrgPtr
Options (variable)
Data
CS 640 4
Segment Format (cont)
• Each connection identified with 4-tuple:
– (SrcPort, SrcIPAddr, DsrPort, DstIPAddr)
• Sliding window + flow control
– acknowledgment, SequenceNum, AdvertisedWinow
Data(SequenceNum)
Sender Receiver
• Flags Acknowledgment +
AdvertisedWindow
– SYN, FIN, RESET, PUSH, URG, ACK
• Checksum is the same as UDP
– pseudo header + TCP header + data
CS 640 5
Sequence Numbers
• 32 bit sequence numbers
– Wrap around supported
• TCP breaks byte stream from application into packets
(limited by Max. Segment Size)
• Each byte in the data stream is considered
• Each packet has a sequence number
– Initial number selected at connection time
– Subsequent numbers indicate first data byte number in packet
• ACK’s indicate next byte expected
CS 640 6
Sequence Number Wrap Around
CS 640 7
Connection Establishment
Active participant Passive participant
(client) (server)
SYN,
Sequ
enceN
um =
x
um = y,
uenceN
, S e q = x +1
K t
SY N
+ AC
wled gmen
k no
Ac
ACK,
Ackno
wledg
men t=y+
1
CS 640 8
Connection Termination
Active participant Passive participant
(server) (client)
FIN, S
equen
ceNu
m=
x
n t = x+1
l ed gme
Ackn
ow u m = y
N
eq u ence
S
FIN,
Ackno
wledg
ment
=y + 1
CS 640 9
State Transition Diagram
CLOSED
Active open/SYN
Passive open Close
Close
LISTEN
Close/FIN ESTABLISHED
Close/FIN FIN/ACK
FIN_WAIT_1 CLOSE_WAIT
AC FIN/ACK
ACK K Close/FIN
+
FI
FIN_WAIT_2 N/
AC CLOSING LAST_ACK
K
ACK Timeout after two ACK
segment lifetimes
FIN/ACK
TIME_WAIT CLOSED
CS 640 10
Reliability in TCP
• Checksum used to detect bit level errors
• Sequence numbers used to detect sequencing errors
– Duplicates are ignored
– Reordered packets are reordered (or dropped)
– Lost packets are retransmitted
• Timeouts used to detect lost packets
– Requires RTO calculation
– Requires sender to maintain data until it is ACKed
CS 640 11
Sliding Window Revisited
Sending application Receiving application
TCP TCP
LastByteWritten LastByteRead
• Sending side
– LastByteAcked < =
• Receiving side
LastByteSent – LastByteRead <
– LastByteSent < = NextByteExpected
LastByteWritten – NextByteExpected < =
LastByteRcvd +1
– buffer bytes between
LastByteAcked and – buffer bytes between
LastByteWritten NextByteRead and
LastByteRcvd
CS 640 12
Flow Control in TCP
• Send buffer size: MaxSendBuffer
• Receive buffer size: MaxRcvBuffer
• Receiving side
– LastByteRcvd - LastByteRead < = MaxRcvBuffer
– AdvertisedWindow = MaxRcvBuffer - (LastByteRcvd - LastByteRead)
• Sending side
– LastByteSent - LastByteAcked < = AdvertisedWindow
– EffectiveWindow = AdvertisedWindow - (LastByteSent -
LastByteAcked)
– LastByteWritten - LastByteAcked < = MaxSendBuffer
– block sender if (LastByteWritten - LastByteAcked) + y > MaxSenderBuffer
• Always send ACK in response to arriving data segment
• Persist sending one byte seg. when AdvertisedWindow = 0
CS 640 13
Keeping the Pipe Full
• 16-bit AdvertisedWindow controls amount of pipelining
• Assume RTT of 100ms
• Add scaling factor extension to header to enable larger windows
CS 640 14
Making TCP More Efficient
• Delayed acknowledgements
– Delay for about 200ms
– Try to piggyback ACKs with data
• Acknowledge every other packet
– Many instances in transmission sequence which require
an ACK
• Don’t forget Nagle’s algorithm
– Can be switched off
CS 640 15
Karn/Partridge Algorithm for RTO
Sender Receiver Sender Receiver
Orig Orig
in al tra in al tra
nsm nsm
issio is sion
n
SampleR TT
SampleR TT
Retr
ans miss AC K
ion
Retr
ans m
issio
n
ACK
CS 640 16
Jacobson/ Karels Algorithm
• In late ’80s, Internet was suffering from congestion collapse
• New Calculations for average RTT – Jacobson ’88
• Variance is not considered when setting timeout value
– If variance is small, we could set RTO = EstRTT
– If variance is large, we may need to set RTO > 2 x EstRTT
• New algorithm calculates both variance and mean for RTT
• Diff = sampleRTT - EstRTT
• EstRTT = EstRTT + ( d x Diff)
• Dev = Dev + d ( |Diff| - Dev)
– Initially settings for EstRTT and Dev will be given to you
– where d is a factor between 0 and 1
– typical value is 0.125
CS 640 17
Jacobson/ Karels contd.
• TimeOut = x EstRTT + x Dev
– where = 1 and = 4
• When variance is small, TimeOut is close to EstRTT
• When variance is large Dev dominates the calculation
• Another benefit of this mechanism is that it is very efficient
to implement in code (does not require floating point)
• Notes
– algorithm only as good as granularity of clock (500ms on Unix)
– accurate timeout mechanism important to congestion control (later)
• These issues have been studied and dealt with in new RFC’s
for RTO calculation.
• TCP RENO uses Jacobson/Karels
CS 640 18