CS F303
(Computer Networks)
Vishal Gupta
Department of Computer Science and Information Systems
BITS Pilani Birla Institute of Technology and Science
Pilani|Dubai|Goa|Hyderabad
Pilani Campus, Pilani
BITS Pilani
Pilani|Dubai|Goa|Hyderabad
Agenda: TCP Congestion Control
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!
Transport Layer 3-3
Causes/costs of congestion: scenario 1
original data: lin throughput: lout
two senders, two
receivers Host A
one router, infinite unlimited shared
output link buffers
buffers
output link capacity: R
no retransmission
Host B
1. Large queuing R/2
delays are
delay
lout
experienced as the
packet arrival rate
nears the link
capacity. lin R/2 lin R/2
maximum per-connection large delays as arrival rate, lin,
throughput: R/2 approaches capacity
Transport Layer 3-4
Causes/costs of congestion: scenario 2
one router, finite buffers
sender retransmission of timed-out packet
application-layer input = application-layer output: lin = lout
transport-layer input includes retransmissions : lin lin’
lin : original data
lout
l'in: original data, plus
retransmitted data
Host A
finite shared output
Host B
link buffers
Transport Layer 3-5
Causes/costs of congestion: scenario 2
R/2
idealization: perfect
knowledge
lout
sender sends only when
router buffers available
lin R/2
lin : original data
lout
copy l'in: original data, plus
retransmitted data
A free buffer space!
finite shared output
Host B
link buffers
Transport Layer 3-6
Causes/costs of congestion: scenario 2
Idealization: known loss
packets can be lost,
dropped at router due to
full buffers
sender only resends if
packet known to be lost
lin : original data
lout
copy l'in: original data, plus
retransmitted data
A
no buffer space!
Host B
Transport Layer 3-7
Causes/costs of congestion: scenario 2
Idealization: known loss R/2
packets can be lost,
dropped at router due to
full buffers
lout
sender only resends if
packet known to be lost
lin R/2
lin : original data
lout
l'in: original data, plus
retransmitted data
A
free buffer space!
Host B
Transport Layer 3-8
Causes/costs of congestion: scenario 2
Realistic: duplicates R/2
packets can be lost, dropped
at router due to full buffers when sending at R/2,
some packets are
lout
sender times out prematurely, retransmissions
sending two copies, both of including duplicated
that are delivered!
which are delivered lin R/2
lin
timeout
copy l'in lout
A
free buffer space!
Host B
Transport Layer 3-9
Causes/costs of congestion: scenario 2
Realistic: duplicates R/2
packets can be lost, dropped
at router due to full buffers when sending at R/2,
some packets are
lout
sender times out prematurely, retransmissions
sending two copies, both of including duplicated
that are delivered!
which are delivered lin R/2
“costs” of congestion:
The sender must perform retransmissions in order to
compensate for dropped (lost) packets due to buffer
overflow.
Unneeded retransmissions by the sender in the face of large
delays may cause a router to use its link bandwidth to
forward unneeded copies of a packet.
Transport Layer 3-10
Causes/costs of congestion: scenario 3
four senders Q: what happens as lin and lin’
increase ?
multihop paths A: as red lin’ increases, all arriving
timeout/retransmit blue pkts at upper queue are
dropped, blue throughput g 0
Host A
lin : original data lout
Host B
l'in: original data, plus
retransmitted data
finite shared output
link buffers
Host D
Host C
Transport Layer 3-11
Causes/costs of congestion: scenario 3
C/2
lout
lin’ C/2
another “cost” of congestion:
when packet dropped, any “upstream
transmission capacity used for that packet was
wasted!
Transport Layer 3-12
Approaches towards congestion control
two broad approaches towards congestion control:
end-end congestion network-assisted
control: congestion control:
no explicit feedback routers provide
feedback to end systems
from network
single bit indicating
congestion inferred congestion (SNA,
from end-system DECbit, TCP/IP ECN,
observed loss, delay ATM)
approach taken by explicit rate for sender
TCP to send at
Transport Layer 3-13
Chapter 3 outline
3.1 transport-layer 3.5 connection-oriented
services transport: TCP
3.2 multiplexing and segment structure
demultiplexing reliable data transfer
3.3 connectionless flow control
transport: UDP connection management
3.4 principles of reliable 3.6 principles of congestion
data transfer control
3.7 TCP congestion control
Transport Layer 3-14
TCP Congestion Control
• Should TCP use end-to-end congestion control??
• How does a TCP sender limit the rate at which it sends traffic into its
connection?
• How does a TCP sender perceive that there is congestion on the path
between itself and the destination ?
• What algorithm should the sender use to change its send rate as a
function of perceived end-to-end congestion ??
VISHAL GUPTA, PhD 15 BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
TCP congestion control:
additive increase multiplicative decrease
approach: sender increases transmission rate (window
size), probing for usable bandwidth, until loss occurs
additive increase: increase cwnd by 1 MSS every
RTT until loss detected
multiplicative decrease: cut cwnd in half after loss
additively increase window size …
…. until loss occurs (then cut window in half)
congestion window size
cwnd: TCP sender
AIMD saw tooth
behavior: probing
for bandwidth
time
Transport Layer 3-16 BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
TCP Congestion Control: details
sender sequence number space
cwnd TCP sending rate:
roughly: send cwnd
bytes, wait RTT for
last byte last byte
ACKed sent, not- sent ACKS, then send more
yet ACKed
(“in-
flight”)
bytes
cwnd
sender limits transmission: rate ~
~ bytes/sec
RTT
LastByteSent-LastByteAcked < cwnd
cwnd is dynamic, function of
perceived network congestion
Transport Layer 3-17
TCP Slow Start
Host A Host B
when connection begins,
increase rate exponentially
until first loss event:
RTT
initially cwnd = 1 MSS
double cwnd every RTT
done by incrementing cwnd
for every ACK received
summary: initial rate is
slow but ramps up
exponentially fast
time
Transport Layer 3-18
TCP: detecting, reacting to loss
loss indicated by timeout:
cwnd set to 1 MSS;
window then grows exponentially (as in slow start) to threshold, then grows
linearly
loss indicated by 3 duplicate ACKs: TCP RENO
dup ACKs indicate network capable of delivering some segments
cwnd is cut in half window then grows linearly
TCP Tahoe always sets cwnd to 1 (timeout or 3 duplicate acks)
Transport Layer 3-19
Summary: TCP Congestion Control
New
New ACK!
ACK! new ACK
duplicate ACK
dupACKcount++ new ACK
.
cwnd = cwnd + MSS (MSS/cwnd)
dupACKcount = 0
cwnd = cwnd+MSS transmit new segment(s), as allowed
dupACKcount = 0
L transmit new segment(s), as allowed
cwnd = 1 MSS
ssthresh = 64 KB cwnd > ssthresh
dupACKcount = 0 slow L congestion
start timeout avoidance
ssthresh = cwnd/2
cwnd = 1 MSS duplicate ACK
timeout dupACKcount = 0 dupACKcount++
ssthresh = cwnd/2 retransmit missing segment
cwnd = 1 MSS
dupACKcount = 0
retransmit missing segment New
ACK!
timeout
ssthresh = cwnd/2
cwnd = 1 New ACK
dupACKcount = 0
cwnd = ssthresh dupACKcount == 3
dupACKcount == 3 retransmit missing segment dupACKcount = 0
ssthresh= cwnd/2 ssthresh= cwnd/2
cwnd = ssthresh + 3 cwnd = ssthresh + 3
retransmit missing segment retransmit missing segment
fast
recovery
duplicate ACK
cwnd = cwnd + MSS
transmit new segment(s), as allowed
Transport Layer 3-20 BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
TCP: switching from slow start to CA
Q: when should the
exponential increase
switch to linear?
A: when cwnd gets to
1/2 of its value before
timeout.
Implementation:
variable ssthresh
on loss event, ssthresh is
set to 1/2 of cwnd just
before loss event
Transport Layer 3-21
TCP segment structure
32 bits
URG: urgent data counting
(generally not used) source port # dest port #
by bytes
sequence number of data
ACK: ACK #
valid acknowledgement number (not segments!)
head not
PSH: push data now len used
UAP R S F receive window
(generally not used) # bytes
checksum Urg data pointer
rcvr willing
RST, SYN, FIN: to accept
options (variable length)
connection estab
(setup, teardown
commands)
application What should
Internet data be the packet
checksum (variable length) structure of
(as in UDP) UDP ?
Transport Layer 3-22
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani
Pilani|Dubai|Goa|Hyderabad
