Transcript Congestion Avoidance and Control Van Jacobson

Congestion Avoidance and Control
Van Jacobson
Jonghyun Kim
April 1, 2004
E-mail :[email protected]
Introduction
• To achieve network stability, TCP entity
should obey a ‘packet conservation’ principle,
which is borrowed from physics.
• What is packet conservation principle?
A new packet is not put into the network until
an old packet leaves( i.e. ‘conservation’) while
maintaining ‘equilibrium’ in which a
connection runs stably by effectively using
the bandwidth available on the path.
• Three failures of packet conservation
1. The connection does not get to equilibrium
2. A sender injects a new packet before an old packet
has exited
3. The equilibrium can’t be reached because of
resource limits along the path
1, 3 : Equilibrium problem
2 : Conservation problem
• To fix those failures, three algorithm are
introduced
* Slow-start algorithm for 1.
* Retransmit timeout estimation algorithm for 2.
* Congestion avoidance algorithm for 3.
Slow-start algorithm
• To understand slow-start algorithm, we should understand
‘self-clocking’ system
• Things for sender to do
1. Sender finds the bandwidth of the slowest link in the path and
sends to the receiver the bursts of packets based on that
bandwidth (This is the core of slow-start algorithm)
2. After that, if a new packet is sent whenever receiving an ACK (i.e.
‘self-clocking’), this connection will get to equilibrium without
wasting the bandwidth.
• How to find the bandwidth of the slowest link in the path
If timeout occurs, we roughly know the bandwidth
bandwidth ≈ The last bursts of sent packets/2
• Slow-start algorithm (Pseudo-code based on C)
cwnd : congestion window
rwnd : receiver’s advertised window
cwnd = 1;
while(1)
{
send packets of min (cwnd, rwnd); // bursts of packets
wait until receiving all ACKs for the previous sent packets
if ( timeout occurs )
cwnd = 1;
else
cwnd = 2*cwnd;
}
• Startup behavior of TCP with Slow-start
• Startup behavior of TCP without Slow-start
Retransmit timeout estimation algorithm
• To estimate retransmit timeout correctly, we should know the
mean and variance of round trip time
• The algorithm of RFC 793
SRTT = α*SRTT + (1- α)*RTT
RTO = β*SRTT
-SRTT: Smoothed RTT (mean) -RTT : Recently measured RTT
-α : Smoothing factor (=0.9)
-β : Delay variance (=2)
-RTO : Retransmit timeout interval
*The problem of this algorithm
Since β is fixed value, RTO is not proportional to the variance
• The algorithm of Jacobson
The idea is to make β above roughly proportional to the standard
deviation of RTT by using mean deviation
Standard deviation (sdev) = E[( RTT  SRTT ) ]
Mean deviation (mdev) = E[| RTT  SRTT |]
mdev ≈ 1.25*sdev
SRTT = α*SRTT + (1- α)*RTT
SMD = β*SMD +(1- β)*(|SRTT-RTT|)
RTO = SRTT + 4*SMD
(α = 0.125, β = 0.25)
-SMD : smoothed mean deviation
- α ,β : smoothing factor
2
• Performance of the algorithm of RFC793
• Performance of the algorithm of Jacobson
D1>D2. It means that Jacobson’s algorithm estimates RTO more flexibly
because RTO varies proportionally to the mean deviation
Congestion avoidance algorithm
• We always want to use the full bandwidth available on the subnet,
keeping stable network. In order to do so, the congestion
window size is increased slowly (i.e. additive increase) to probe
for more bandwidth becoming available (e.g. when a host closes
its connection). However, on any timeout, the congestion
window size is decreased fast (i.e. multiplicative decrease) to
avoid congestion
On no congestion (to probe for more bandwidth) :
cwnd = cwnd + 1 ;
On congestion (to avoid congestion) :
cwnd = cwnd/2 ;
• Illustration of congestion avoidance algorithm
To find current To avoid
bandwidth
congestion
64
To probe
more bandwidth
To avoid
congestion
To probe
more bandwidth
Timeout
Congestion window (Kbyte)
52
48
44
Timeout
40
36
32
28
24
•••
Threshold
20
16
12
8
4
0
1 2 3 4 5 6 7 8 9 10 111213 14 151617 181920212223 24 252627 2829 30 31 32
Transmission number
• Congestion avoidance algorithm (pseudo-code based on C)
cwnd = 1;
while(1) {
send packets of min (cwnd, rwnd);
// burst
wait until receiving all ACKs for the previous sent packets
slow-start
if ( timeout occurs ) break;
else cwnd = 2*cwnd;
}
threshold = cwnd/2; cwnd = 1;
while(1){
if ( cwnd < threshold ){
send packets of min (cwnd, rwnd);
//burst
wait until receiving all ACKs for the previous sent packets
slow-start
if ( timeout occurs ){ threshold = cwnd/2; cwnd = 1;}
else cwnd = 2*cwnd;}
if ( cwnd == threshold || cwnd > threshold )
send packets of min (threshold, rwnd);
//burst
} else if ( cwnd > threshold ){
send a new packet whenever an ACK is received //self-clocking
if ( Sender receives all ACKs for the previous sent packets )
{cwnd = cwnd + 1; send a new packet;} //to probe more bandwidth
if ( timeout occurs)
{threshold = cwnd/2; cwnd = 1;}
//to avoid congestion
}
}
• Multiple conversation test setup
When receiving more than
50 packets/sec,
the routers will drop packets
* Experimental Parameters
Local bandwidth
: 1MB/s
P2P link bandwidth
: 25KB/s
Receiver’s window size : 16KB
Packet size
: 512 Byte
50-packet size
: 25KB
Since four connections can send
64KB (4*16KB) at a time, they will
cause congestion easily.
• Multiple, simultaneous TCPs with no congestion avoidance
* Result
-4,000 (36%) of 11,000 packets were retransmitted
• Multiple, simultaneous TCPs with congestion avoidance
* Result
-89 (1%) of 8281packets were retransmitted
Big retransmission means big congestion occurrence.
On the other hand, small retransmission means small congestion occurrence
• Total bandwidth used by old and new TCPs
Thin line : old TCP
Thick line : new TCP
Bandwidth negotiation
among four connection
Reaching equilibrium
Bandwidth renegotiation
due to connection
one shutting down
• Effective bandwidth of old and new TCPs
Thin line : old TCP
Thick line : new TCP
Old TCP uses 75% of the link bandwidth
New TCP uses almost 100% of the link bandwidth
Summary
We can think of network system as a linear system. To
make network system stable, TCP should conform a
‘packet conservation’ principle.
There exist three failures of packet conservation in the
network system. To fix those failures, three algorithms
are introduced. (Slow-start, retransmit timeout
estimation, congestion avoidance)
This paper introduced only host-centric congestion
control, but we also need to learn router-centric
congestion control.
Reference
• JACOBSON, V. Congestion avoidance and control. Proceedings
of the ACM SIGCOMM conference on applications, technologies,
architectures, and protocols for computer communication
(Stanford, California, USA), 18, 4, August 1988, 314-329.
• ANDREW S. TANENBAUM, Computer Networks, 2003
• RFC 793