09 coms 525 tcpip - tcp 2

1
Transmission Control Protocol
K. PALANIVEL
Systems Analyst, Computer Centre
Pondicherry University, Puducherry – 605014.
LECTURE 8
COMS 525: TCPIP
COURSE
TOPIC
Part - II

What is Flow/Congestion/Error Control ?
• Flow Control: Algorithms to prevent that the sender
overruns the receiver with information
• Error Control: Algorithms to recover or conceal the
effects from packet losses
• Congestion Control: Algorithms to prevent that the
sender overloads the network
• The goal of each of the control mechanisms are
different.
• In TCP, the implementation of these algorithms is
combined

Acknowledgements in TCP
• TCP receivers use acknowledgments (ACKs) to confirm
the receipt of data to the sender
• Acknowledgment can be added (“piggybacked”) to a data
segment that carries data in the opposite direction
• ACK information is included in the the TCP header
• Acknowledgements are used for flow control, error
control, and congestion control
Data for B
A BData for A ACK
ACK

Sequence Numbers and Acknowledgments in TCP
• TCP uses sequence numbers to keep track of transmitted and
acknowledged data
• Each transmitted byte of payload data is associated with a
sequence number
• Sequence numbers count bytes and not segments
• Sequence number of first byte in payload is written in SeqNo
field
• Sequence numbers wrap when they reach 232-1
• The sequence number of the first sequence number (Initial
sequence number) is negotiated during connection setup
Sequence number (SeqNo) (32 bits)
Source Port Number Destination Port Number
Acknowledgement number (AckNo)(32 bits)
window size
header
length
0 Flags
TCP checksum urgent pointer 4

Sequence Numbers and Acknowledgments in TCP
• An acknowledgment is a confirmation of delivery of data
• When a TCP receiver wants to acknowledge data, it
– writes a sequence number in the AckNo field, and
– sets the ACK flag
IMPORTANT: An acknowledgment confirms receipt for all
unacknowledged data that has a smaller sequence number
than given in the AckNo field
Example: AckNo=5 confirms delivery for 1,2,3,4 (but not 5).
Sequence number (SeqNo) (32 bits)
Source Port Number Destination Port Number
Acknowledgement number (AckNo)(32 bits)
window size
header
length
0 Flags
TCP checksum urgent pointer
5

Cumulative Acknowledgements
• TCP has cumulative acknowledgements:
An acknowledgment confirms the receipt of all
unacknowledged data with a smaller sequence number
6
A
B

Cumulative Acknowledgements
• With cumulative ACKs, the receiver can only
acknowledge a segment if all previous segments
have been received
• With cumulative ACKs, receiver cannot
selectively acknowledge blocks of segments:
e.g., ACK for S0-S3 and S5-S7 (but not for S4)
• Note: The use of cumulative ACKs imposes
constraints on the retransmission schemes:
– In case of an error, the sender may need to retransmit
all data that has not been acknowledged
7

Rules for sending Acknowledgments
• TCP has rules that influence the transmission of
acknowledgments
• Rule 1: Delayed Acknowledgments
– Goal: Avoid sending ACK segments that do not carry data
– Implementation: Delay the transmission of (some) ACKs
• Rule 2: Nagle’s rule
– Goal: Reduce transmission of small segments
– Implementation: A sender cannot send multiple segments
with a 1-byte payload (i.e., it must wait for an ACK)
8

Observing Delayed Acknowledgements
9
• Remote terminal applications (e.g., Telnet) send characters to a
server. The server interprets the character and sends the output at
the server to the client.
• For each character typed, you see three packets:
1. Client  Server: Send typed character
2. Server  Client: Echo of character (or user output) and
acknowledgement for first packet
3. Client  Server: Acknowledgement for second packet

Observing Delayed Acknowledgements
• This is the output of typing 3 (three) characters :
Time 44.062449: Argon  Neon: Push, SeqNo 0:1(1), AckNo 1
Time 44.063317: Neon  Argon: Push, SeqNo 1:2(1), AckNo 1
Time 44.182705: Argon  Neon: No Data, AckNo 2
Time 48.946471: Argon  Neon: Push, SeqNo 1:2(1), AckNo 2
Time 48.947326: Neon  Argon: Push, SeqNo 2:3(1), AckNo 2
Time 55.116581: Argon  Neon: Push, SeqNo 2:3(1) AckNo 3
Time 55.117497: Neon  Argon: Push, SeqNo 3:4(1) AckNo 3
10
Argon Neon
Telnet session
from Argon
to Neon

Why 3 segments per character?
• We would expect four
segments per character:
• But we only see three
segments per character:
• This is due to delayed
acknowledgements
11
character
ACK of character
ACK of echoed character
echo of character
character
ACK and echo of character
ACK of echoed character

Delayed Acknowledgement
• TCP delays transmission of ACKs for up to 200ms
• Goal: Avoid to send ACK packets that do not carry data.
– The hope is that, within the delay, the receiver will have data
ready to be sent to the receiver. Then, the ACK can be
piggybacked with a data segment
In Example:
– Delayed ACK explains why the “ACK of character” and the
“echo of character” are sent in the same segment
– The duration of delayed ACKs can be observed in the example
when Argon sends ACKs
Exceptions:
• ACK should be sent for every second full sized segment
• Delayed ACK is not used when packets arrive out of order
12

• Because of delayed ACKs, an ACK is often
observed for every other segment
13
Delayed Acknowledgement
A
B
Max. Delay
for an ACK

Observing Nagle’s Rule
• This is the output of typing 7 characters :
Time 16.401963: Argon  Tenet: Push, SeqNo 1:2(1), AckNo 2
Time 16.481929: Tenet  Argon: Push, SeqNo 2:3(1) , AckNo 2
Time 16.482154: Argon  Tenet: Push, SeqNo 2:3(1) , AckNo 3
Time 16.559447: Tenet  Argon: Push, SeqNo 3:4(1), AckNo 3
Time 16.559684: Argon  Tenet: Push, SeqNo 3:4(1), AckNo 4
Time 16.640508: Tenet  Argon: Push, SeqNo 4:5(1) AckNo 4
Time 16.640761: Argon  Tenet: Push, SeqNo 4:8(4) AckNo 5
Time 16.728402: Tenet  Argon: Push, SeqNo 5:9(4) AckNo 8
argon.cs.virginia.edu
3000
miles
tenet.cs.berkeley.edu
Telnet session
between argon.cs.virginia.edu
and
tenet.cs.berkeley.edu

• Observation: Transmission
of segments follows a
different pattern, i.e., there
are only two segments per
character typed
• Delayed acknowledgment
does not kick in at Argon
• The reason is that there is
always data at Argon ready
to sent when the ACK arrives
• Why is Argon not sending
the data (typed character) as
soon as it is available?
15
char1
ACK of char 1 + echo of char1
ACK + char2
ACK + echo of char2
ACK + char3
ACK + echo of char3
ACK + char4-7
ACK + echo of char3

• Observations:
– Argon never has multiple unacknowledged segments
outstanding
– There are fewer transmissions than there are characters.
This is due to Nagle’s Rule:
– Each TCP connection can have only one small (1-byte)
segment outstanding that has not been acknowledged
• Implementation: Send one byte and buffer all subsequent
bytes until acknowledgement is received.Then send all
buffered bytes in a single segment. (Only enforced if byte is
arriving from application one byte at a time)
• Goal of Nagle’s Rule: Reduce the amount of small segments.
• The algorithm can be disabled.
16

• Only one 1-byte segment can be in transmission (Here: Since no
data is sent from B to A, we also see delayed ACKs)
17
A
B
Nagle’s Rule
Typed
characters
Delayed ACKDelayed ACK Delayed ACK

TCP Flow Control
• TCP uses a version of the sliding window flow
control, where
• Sending acknowledgements is separated from
setting the window size at sender
• Acknowledgements do not automatically
increase the window size
• During connection establishment, both ends of a TCP
connection set the initial size of the sliding window
19

Window Management in TCP
• The receiver is returning two parameters to the sender
• The interpretation is:
• I am ready to receive new data with
SeqNo= AckNo, AckNo+1, …., AckNo+Win-1
• Receiver can acknowledge data without opening the
window
• Receiver can change the window size without
acknowledging data
20
AckNo
window size
(win)
32 bits 16 bits

Sliding Window Flow Control
1 2 3 4 5 6 7 8 9 10 11
Advertised window
sent but not
acknowledged can be sent
USABLE
WINDOW
sent and
acknowledged
can't sent
21
• Sliding Window Protocol is performed at the byte level:
• Here: Sender can transmit sequence numbers 6,7,8.

Sliding Window: “Window Closes”
1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10 11
Transmit Byte 6
1 2 3 4 5 6 7 8 9 10 11
AckNo = 5, Win = 4
is received
22
• Transmission of a single byte (with SeqNo = 6) and
acknowledgement is received (AckNo = 5, Win=4):

Sliding Window: “Window Opens”
1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10 11
AckNo = 5, Win = 6
is received
23
• Acknowledgement is received that enlarges the window to the
right (AckNo = 5, Win=6):
• A receiver opens a window when TCP buffer empties (meaning
that data is delivered to the application).

Sliding Window: “Window Shrinks”
1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10 11
AckNo = 5, Win = 3
is received
24
• Acknowledgement is received that reduces the window from
the right (AckNo = 5, Win=3):
• Shrinking a window should not be used

Sliding Window: Example
3K
2K SeqNo=0
Receiver
Buffer
0 4K
Sender
sends 2K
of data
2K
AckNo=2048 Win=2048
Sender
sends 2K
of data 2K SeqNo=2048
4K
AckNo=4096 Win=0
AckNo=4096 Win=1024
Senderblocked

26
Back to TCP
TCP Error Control

Error Control in TCP
• TCP maintains a Retransmission Timer for each
connection:
– The timer is started during a transmission. A
timeout causes a retransmission
• TCP couples error control and congestion control
(i.e., it assumes that errors are caused by congestion)
– Retransmission mechanism is part of congestion
control algorithm
• Here: How to set the timeout value of the
retransmission timer?

TCP Retransmission Timer
• Retransmission Timer:
– The setting of the retransmission timer is crucial for
efficiency
– Timeout value too small  results in unnecessary
retransmissions
– Timeout value too large  long waiting time before
a retransmission can be issued
– A problem is that the delays in the network are not
fixed
– Therefore, the retransmission timers must be adaptive
28

Round-Trip Time Measurements
• The retransmission mechanism of TCP is adaptive
• The retransmission timers are set based on round-
trip time (RTT) measurements that TCP performs
29
Segment 1
Segment 4
ACK for Segment 1
Segment 2
Segment 3
ACK for Segment 2 + 3
Segment 5
ACK for Segment 4
ACK for Segment 5
RTT#1RTT#2RTT#3
The RTT is based on time
difference between segment
transmission and ACK
But:
TCP does not ACK each
segment
Each connection has only one
timer

Round-Trip Time Measurements
• Retransmission timer is set to a Retransmission
Timeout (RTO) value.
• RTO is calculated based on the RTT measurements.
• The RTT measurements are smoothed by the following
estimators srtt and rttvar:
srttn+1 = a RTT + (1- a ) srttn
rttvarn+1 = b ( | RTT - srttn+1 | ) + (1- b )
rttvarn
RTOn+1 = srttn+1 + 4 rttvarn+1
• The gains are set to a =1/4 and b =1/8
• srtt0 = 0 sec, rttvar0 = 3 sec, Also: RTO1 = srtt1 + 2
rttvar1
30

Karn’s Algorithm
• If an ACK for a retransmitted
segment is received, the sender
cannot tell if the ACK belongs
to the original or the
retransmission.
31
segment
ACK
retransmissionof segment
Timeout !
RTT?
RTT?
Karn’s Algorithm:
Don’t update srtt on any segments that have been
retransmitted.
Each time when TCP retransmits, it sets:
RTOn+1 = max ( 2 RTOn, 64) (exponential backoff)

Measuring TCP Retransmission Timers
32
ellington.cs.virginia.edu satchmo.cs.virginia.edu
ftp session
from ellington
to satchmo
•Transfer file from ellington to satchmo
• Unplug Ethernet cable in the middle of file transfer

Exponential Backoff
• Scenario: File transfer
between two machines.
Disconnect cable.
• The interval between
retransmission attempts in
seconds is:
1.03, 3, 6, 12, 24, 48, 64, 64,
64, 64, 64, 64, 64.
• Time between retrans-
missions is doubled each
time (Exponential Backoff
Algorithm)
• Timer is not increased
beyond 64 seconds
• TCP gives up after 13th
attempt and 9 minutes.
0
100
200
300
400
500
600
Seconds
0 2 4 6 8 10 12
Transmission Attempts
33

34
Back to TCP
TCP Congestion Control

• TCP has a mechanism for congestion control. The
mechanism is implemented at the sender
• The window size at the sender is set as follows:
Send Window = MIN (flow control window,
congestion window)
where
– flow control window is advertised by the receiver
– congestion window is adjusted based on feedback
from the network
35

• TCP congestion control is governed by two
parameters:
– Congestion Window (cwnd)
Slow-start threshhold Value (ssthresh)
Initial value is 216-1
• Congestion control works in two modes:
– slow start (cwnd < ssthresh)
– congestion avoidance (cwnd ≥ ssthresh
36

Slow Start
• Initial value: Set cwnd = 1
» Note: Unit is a segment size. TCP actually is based on bytes
and increments by 1 MSS (maximum segment size)
• The receiver sends an acknowledgement (ACK) for each Segment
» Note: Generally, a TCP receiver sends an ACK for every
other segment.
• Each time an ACK is received by the sender, the congestion window is
increased by 1 segment:
cwnd = cwnd + 1
» If an ACK acknowledges two segments, cwnd is still
increased by only 1 segment.
» Even if ACK acknowledges a segment that is smaller than
MSS bytes long, cwnd is increased by 1.
• Does Slow Start increment slowly? Not really.
In fact, the increase of cwnd is exponential
37

Slow Start Example
• The congestion
window size grows
very rapidly
– For every ACK,
we increase cwnd
by 1 irrespective
of the number of
segments ACK’ed
• TCP slows down
the increase of
cwnd when
cwnd > ssthresh
38
segment 1
ACK for segment 1
cwnd = 1
cwnd = 2 segment 2
segment 3
ACK for segments 2
cwnd = 4 segment 4
segment 5
segment 6
ACK for segments 4
cwnd = 7
ACK for segments 3
ACK for segments 5
ACK for segments 6

Congestion Avoidance
• Congestion avoidance phase is started if cwnd has
reached the slow-start threshold value
• If cwnd ≥ ssthresh then each time an ACK is
received, increment cwnd as follows:
• cwnd = cwnd + 1/ cwnd
• So cwnd is increased by one only if all cwnd
segments have been acknowledged.
39

Example of
Slow Start/Congestion Avoidance
Assume that ssthresh = 8
40
cwnd = 1
cwnd = 2
cwnd = 4
cwnd = 8
cwnd = 9
cwnd = 10
0
2
4
6
8
10
12
14
t=0
t=2
t=4
t=6
Roundtrip times
Cwnd(insegments)
ssthresh

Responses to Congestion
• So, TCP assumes there is congestion if it detects a packet loss
• A TCP sender can detect lost packets via:
• Timeout of a retransmission timer
• Receipt of a duplicate ACK
• TCP interprets a Timeout as a binary congestion signal. When
a timeout occurs, the sender performs:
– cwnd is reset to one:
cwnd = 1
– ssthresh is set to half the current size of the congestion
window:
ssthressh = cwnd / 2
– and slow-start is entered
41

Summary of TCP congestion control
Initially:
cwnd = 1;
ssthresh =
advertised window size;
New Ack received:
if (cwnd < ssthresh)
/* Slow Start*/
cwnd = cwnd + 1;
else
/* Congestion Avoidance */
cwnd = cwnd + 1/cwnd;
Timeout:
/* Multiplicative decrease */
ssthresh = cwnd/2;
cwnd = 1;
42

Slow Start / Congestion Avoidance
• A typical plot of cwnd for a TCP connection (MSS
= 1500 bytes) with TCP Tahoe:
43

Acknowledgments in TCP
• Receiver sends ACK to sender
– ACK is used for flow control,
error control, and congestion
control
• ACK number sent is the next
sequence number expected
• Delayed ACK: TCP receiver normally
delays transmission of an ACK (for
about 200ms)
• ACKs are not delayed when packets
are received out of sequence
– Why?
1K SeqNo=0
AckNo=1024
1K SeqNo=1024
AckNo=2048
SeqNo=2048
SeqNo=3072
AckNo=2048
1K
1K
44
Lost segment

Acknowledgments in TCP
• Receiver sends ACK to sender
– ACK is used for flow control,
error control, and congestion
control
• ACK number sent is the next
sequence number expected
• Delayed ACK: TCP receiver
normally delays transmission of an
ACK (for about 200ms)
– Why?
• ACKs are not delayed when
packets are received out of
sequence
– Why?
1K SeqNo=0
AckNo=1024
1K SeqNo=1024
AckNo=2048
SeqNo=3072
AckNo=2048
SeqNo=2048 1K1K
45
Out-of-order arrivals

Fast Retransmit
• If three or more duplicate ACKs
are received in a row, the TCP
sender believes that a segment
has been lost.
• Then TCP performs a
retransmission of what seems to
be the missing segment, without
waiting for a timeout to happen.
• Enter slow start:
ssthresh = cwnd/2
cwnd = 1
1K SeqNo=0
AckNo=1024
AckNo=1024
1K SeqNo=1024
SeqNo=2048
1K
AckNo=1024
SeqNo=3072
1K
SeqNo=4096
1K
1. duplicate
2. duplicate
AckNo=1024
SeqNo=1024
1K
SeqNo=5120
1K
3. duplicate
46

Fast Recovery
• Fast recovery avoids slow start after a fast
retransmit
• Intuition: Duplicate ACKs indicate that
data is getting through
• After three duplicate ACKs set:
– Retransmit packet that is presumed
lost
– ssthresh = cwnd/2
– cwnd = cwnd+3
– (note the order of operations)
– Increment cwnd by one for each
additional duplicate ACK
• When ACK arrives that acknowledges
“new data” (here: AckNo=6148), set:
cwnd=ssthresh
enter congestion avoidance
1K SeqNo=0
AckNo=1024
AckNo=1024
1K SeqNo=1024
SeqNo=2048
1K
AckNo=1024
SeqNo=3072
1K
SeqNo=4096
1K
1. duplicate
2. duplicate
AckNo=1024
SeqNo=1024
1K
SeqNo=5120
1K
3. duplicate
cwnd=12
sshtresh=5
cwnd=12
sshtresh=5
cwnd=12
sshtresh=5
cwnd=12
sshtresh=5
cwnd=15
sshtresh=6
AckNo=6148cwnd=6
sshtresh=6
ACK for new data
47

SACK
• SACK = Selective acknowledgment
• Issue: Reno and New Reno retransmit at most 1 lost packet per
round trip time
• Selective acknowledgments: The receiver can acknowledge
non-continuous blocks of data (SACK 0-1023, 1024-2047)
• Multiple blocks can be sent in a single segment.
• TCP SACK:
– Enters fast recovery upon 3 duplicate ACKs
– Sender keeps track of SACKs and infers if segments are
lost. Sender retransmits the next segment from the list of
segments that are deemed lost.
48

09 coms 525 tcpip - tcp 2

Recommended

More Related Content

What's hot (19)

Similar to 09 coms 525 tcpip - tcp 2 (20)

More from Palanivel Kuppusamy (17)

Recently uploaded (20)

09 coms 525 tcpip - tcp 2