CSEN 404
Introduction to Networks
Hisham Othman
Basma Mohamed Afifi
Nadeen Hamza
** Slides are attributed to J. F. Kurose
Lecture Outline
Principles of Flow Control
Receiver Buffer
rwind
Principles of Congestion Control
Tahoe
Reno
Flow Control
TCP Flow Control
receiver side of TCP
connection has a receive flow control
buffer: sender won’t overflow
receiver’s buffer by
(currently) transmitting too much,
IP TCP data application
unused buffer
datagrams space (in buffer) process too fast
rwnd
RcvBuffer speed-matching service:
app process may be slow at reading from matching send rate to
buffer receiving application’s
receiver: advertises unused buffer space drain rate
by including rwnd value in segment
header
guarantees receiver’s
sender: limits # of unACK’ed bytes to rwnd buffer doesn’t overflow
Congestion Control
TCP Congestion Control
Sliding Window Protocol
Sender maintains a congestion window (cwnd), in
addition to the receiver’s window (rwnd) advertised in
ACK
Allowed-window = min(cwnd, rwnd)
Ifno congestion: Allowed-window = rwnd
Packet loss is interpreted as congestion occurrence:
reduce congestion window size
TCP Congestion Control
Congestion control is performed at the sending host, using
feedback from the destination host (acknowledgments)
The sender keeps exponentially increasing the congestion window
cwnd until its value exceeds a slow start threshold (ssthresh),
then it starts to linearly increase the cwnd until packet loss
happens.
TCP Congestion Control
The original version of TCP, called TCP Tahoe, had only two
phases:
slow start (exponential increase) and
congestion avoidance (linear increase)
New version of TCP, called TCP Reno, has three states:
slow start,
congestion avoidance, and
fast recovery (to recover from errors faster)
Slow Start
Initially cwnd = 1 MSS, ssthresh =
64KB. Thus, sending rate = 1 MSS/RTT
The sender sends one segment and waits
for ACK
For every ACK received, increase cwnd
by 1 MSS (exponential increase)
Hint: MSS is the TCP Max Segment Size.
For example, if MTU=1500 Byte, see
below:
.
TCP Tahoe
Exponential increase takes place until one of 3 things
occur:
cwnd ≥ ssthresh, or
timeout event occurs, or
3 duplicate ACKs are detected
If cwnd ≥ ssthresh:
go to congestion avoidance state directly – steady “cautious”
transmission
If timeout or 3 duplicate ACKs:
set ssthresh = cwnd/2, and
set cwnd = 1,
Increase exponentially (go to slow start) until cwnd ≥ ssthresh,
then go to congestion avoidance state
TCP Congestion Avoidance
In congestion avoidance: increase cwnd by 1 MSS/cwnd (linear
increase)
How long do we stay in congestion avoidance until either a
timeout or 3 duplicate ACKs are detected
Reaction:
ssthresh = cwnd/2,
cwnd = 1,
enter slow start
Example
Assume 1 MSS = 1 KB
RTT cwnd ssthresh Event
1 Initial: 1 MSS = 1 KB Initial: 64KB
2 2 64
3 4 64
4 8 64
5 16 64 Timeout or 3 dup ACKs
cwnd
6 =1 1
2 8 ssthresh = cwnd/2
7 2 8
8 4 8
9 8 8
10 9 8
11 10 8 Timeout or 3 dup ACKs
12
13
Example
Assume 1 MSS = 1 KB
RTT cwnd ssthresh Event
1 Initial: 1 MSS = 1 KB Initial: 64KB
2 2 64
3 4 64
4 8 64
5 16 64 Timeout or 3 dup ACKs
cwnd
6 =1 1
2 8 ssthresh = cwnd/2
7 2 8
8 4 8
9 8 8
10 9 8
11 10 8 Timeout or 3 dup ACKs
12 1 5
13 2 5
TCP Reno
Slow start still incorporates exponential increase
If a timeout event occurs:
ssthresh = cwnd/2,
cwnd = 1,
increase exponentially until cwnd ≥ ssthresh, then enter congestion avoidance
The main difference is in the reaction to 3 duplicate ACKs
Recall: 3 duplicate ACKs means that one ACK is missing
Here, TCP Reno will enter fast recovery state:
go to congestion avoidance while waiting for missing ACK (increase linearly),
ssthresh = cwnd/2,
cwnd = cwnd/2
TCP Reno
Here, TCP Reno will enter fast recovery state:
go to congestion avoidance while waiting for missing ACK (increase linearly),
ssthresh = cwnd/2,
cwnd = cwnd/2
If the missing ACK did not arrive then a timeout will occur:
ssthresh = cwnd/2,
cwnd = 1,
go to slow start (increase exponentially)
If the missing ACK arrives:
cwnd = ssthresh,
stay in congestion avoidance (increase linearly)
Example
Any Question?
1-17
