Advanced Computer Networks: Lecture 36 - Dr. Amir Qayyum
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (345.14 KB, 17 trang )
CS716
Advanced Computer Networks
By Dr. Amir Qayyum
1
1
Lecture No. 36
2
Congestion Control
• Basics: problem, terminology, approaches,
metrics
• Solutions
– Routerbased: queuing disciplines
– Hostbased: TCP congestion control
• Congestion avoidance
– DECbit
– RED gateways
• Quality of service
3
Host Solutions:
TCP Congestion Control
• Host has very little information
– Assumes besteffort network
– Acts independently of other hosts
• Host infers congestion
– From synchronization feedback
– e.g. dropped packet timeouts, duplicate ACK’s
– Loss on wired lines rarely due to transmission error
• Host acts
– Reduce transmission rate below congestion threshold
– Continuously monitor network for signs of congestion
4
TCP Congestion Control
• Add notion of congestion window
• Effective sliding window is smaller of
– Remote advertised window (flow control)
– Local congestion window (congestion
control)
• Changes in congestion window size
– Slow increases to absorb new bandwidth
– Quick decreases to eliminate congestion
5
TCP Congestion Control Strategy
• Selfclocking
– Send data only when outstanding data ACK’d
– Equivalent to send window limitation mentioned
• Growth
– Add one Maximum Segment Size (MSS) per
congestion window of data ACK’d
– It’s really done this way, at least in Linux: see
tcp_cong_avoid in tcp_input.c. Actually, every ack
for new data is treated as an MSS ACK’d… any
problems with that?
– Known as additive increase
6
TCP Congestion Control Strategy
• Decrease
– Cut window in half when timeout
occurs
– In practice, set window = window/2
– Known as multiplicative decrease
• Additive Increase, Multiplicative
Decrease (AIMD)
7
TCP Congestion Control
• AIMD sawtooth trace
8
TCP Congestion Control
• AIMD fairness for two competing flows
– Slope of 1 for additive increase
– Proportional decrease (towards origin) for
multiplicative decrease
9
Initialization of Congestion Window
• Congestion window should start small
• Avoid congestion due to new
connections
• Start at 1 MSS, reset to 1 MSS with each
timeout (note that timeouts are coarse
grained, ~1/2 seconds)
• Known as slow start
10
Initialization of Congestion Window
• To make up for slow start, ramp up quickly
• Maintain threshold window size
• Use multiplicative increase
– When congestion window is smaller than
threshold
– Double window for each window ACK’d
11
Initialization of Congestion Window
• Threshold value
– Initially set to maximum window size
– Set to 1/2 of current window on
timeout
• In practice, increase congestion window
by 1 MSS for each ACK of new data (or
N bytes for N bytes)
12
TCP Congestion Control
• Coarsegrained timeouts lead to idle periods …
• Solution: fast retransmission
– Send ACK for each segment received
– When duplicate ACK’s received
• Resend lost segment immediately
• Do not wait for timeout
• In practice, retransmit on 3rd duplicate
– Fast recovery
• When fast retransmission occurs, skip slow start
• Congestion window becomes 1/2 of the previous
• Start additive increase immediately
13
TCP Congestion Window Trace
14
Congestion Avoidance
Flight Planning for Your Air Travel
•
•
•
•
Planning a vacation for your semester break ?
Trying for a trip to scenic Northern Areas
No way to go (route is too congested)
Delay your program till next semester
Islamabad
Airport
CASE
Flights
are
FULL
Peshawer
Sakardu
16
Congestion Avoidance
• Control vs Avoidance
– Control: minimize impact of congestion when it occurs
– Avoidance: avoid producing congestion
• In terms of operating point limits:
17
