Transcript Document

TCP Congestion Control
NETS3303/3603
Week 9
School of Information Technologies
Outline
•
•
•
•
What is congestion?
Approaches to congestion control
TCP congestion control
TCP vs UDP
School of Information Technologies
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!
School of Information Technologies
Causes/costs of congestion
Host A
• two senders, two
receivers
• one router, infinite
buffers
• no retransmission
Host B
lout
lin : original data
unlimited shared
output link buffers
• large delays
when congested
• maximum
achievable
throughput
School of Information Technologies
Costs of congestion
• Reality: routers have finite buffers
– So packets can be lost
• Congestion causes:
– sender retransmit of lost packet
– retransmission of delayed (not lost) packet
– when packets dropped, any transmission
capacity used for that packet was wasted!
School of Information Technologies
Congestion Control
• routers may drop packets as its service is best
effort
– Implies congestion
• routers don’t have effective mechanism to indicate
congestion to sender
– ICMP source quench is not it...
• assumption:
– packet loss due to damage is small, therefore TCP
assumes it means congestion since ACKs do not come
back
School of Information Technologies
Approaches towards congestion
control
Two broad approaches towards congestion control:
End-end congestion
control:
Network-assisted
congestion control:
• no explicit feedback from • routers provide feedback
to end systems
network
– single bit indicating
• congestion inferred from
congestion (TCP/IP
end-system observed loss,
ECN, ATM)
delay
– explicit rate sender
• approach taken by TCP
should send at
School of Information Technologies
TCP Congestion Control
• end-end control (no network assistance)
• Assumes long delays (packet loss) is due to
congestion
• Uses successive retransmissions as measure of
congestion
– Reduces effective window as retransmissions increase
• Effective window is minimum of receiver’s
advertisement and computed quantity known as
the congestion window (cwnd)
School of Information Technologies
Congestion Control II
• TCP uses slow start and multiplicative decrease
to deal with congestion
• Van Jacobson 1988 outlined these ideas
• slow-start roughly: whenever starting traffic or
recovering from congestion, start cwnd at the size
of a single segment and increase it (up to a point)
as ACKs show up
School of Information Technologies
Slow Start
• Used when starting traffic or when recovering
from congestion
• Self-clocking startup to increase transmission rate
rapidly as long as no packets are lost
• When starting traffic, initialize the cwnd to the
size of a single MSS
• Increase cwnd by size of 1 segment each time an
ACK arrives without retransmission – till ssthresh
School of Information Technologies
Slow Start II
• When connection begins,
increase rate exponentially
until first loss event:
Host B
RTT
Host A
– double cwnd every RTT
– done by incrementing cwnd
for every ACK received
• Summary: initial rate is
slow but ramps up
exponentially fast
time
School of Information Technologies
Congestion Avoidance
• Slow start is used until cwnd reaches
ssthresh
• Exponential growth is stopped
• Above threshold, slow down and increase
cwnd by 1 segment per RTT
School of Information Technologies
TCP Congestion control
CW Size
ssthresh
Time
slow-start
School of Information Technologies
congestion avoidance
Retransmissions
• TCP uses both Go back-N and selective
repeat for retransmissions
• If timeout (=> congestion):
– Go Back-N and go into slow start
• If an isolated error (more next slide)
– Selective repeat and go to ssthresh, enter
congestion avoidance
School of Information Technologies
Fast Retransmit Rule
• RTO expires up to secs after segment
dropped
• If an isolated error, may be can do better
than being too conservative!
• Fast retransmission
– Sender uses three duplicate ACKs as trigger
– Sender retransmits ‘‘early’’ before timeout
– Sender reduces cwnd to half (instead of 1)
School of Information Technologies
CC Refinements
• After 3 dup ACKs:
– cwnd is cut in half
– window then grows linearly
• But after timeout event:
– cwnd instead set to 1 MSS;
– window then grows
exponentially
– to a threshold, then grows
linearly
School of Information Technologies
Philosophy:
• 3 dup ACKs indicates
network capable of
delivering some segments
• timeout before 3 dup
ACKs is “more alarming”
Summary of TCP Congestion Control
• When cwin is below SSThresh, sender in slow-start
phase, window grows exponentially.
• When cwin is above SSThresh, sender is in congestionavoidance phase, window grows linearly.
• When a triple duplicate ACK occurs, SSThresh set to
cwin/2 and cwin set to SSThresh.
• When timeout occurs, SSThresh set to cwin/2 and
cwin is set to 1 MSS.
School of Information Technologies
Congestion and Routers with RED
• routers might use an obvious queue-drop
mechanism
– too many packets; drop packets at end of queue call this
a“tail-drop” policy
– on heavily multiplexed router TCP connections may
lose many packets and be forced into slow-start
• routers may use Random Early Detection (or
RED) - basically randomly discard packets in
queue at certain thresholds
– thus avoid tail-drop policy
School of Information Technologies
Comparison Of UDP and TCP
School of Information Technologies
Summary Of TCP
• Major transport service in the Internet (85% of
traffic)
• Connection oriented
• Provides end-to-end reliability
• Uses adaptive retransmission
• Includes facilities for flow control and congestion
avoidance
• Uses 3-way handshake for connection startup and
shutdown
School of Information Technologies