=head1 Congestion Avoidance and Control Van Jacobson (LBL) and Michael Karels (Berkeley), 1988 B Due to explosion of network usage, congestion problems have become severe. The problem is not within the I specification, but within the implementation of the protocol. The authors observed that TCP flows should obey a I principle: a packet should not be introduced into a flow until a previous packet has left the flow. They claim that if such a principle is followed such that flows are in I (stable with a full window in transit) networks should be robust in the face of congestion. However, packet conservation can fail in 3 ways. Below are the 3 failure modes & what the authors suggest to avoid the failure modes. =over 4 =item 1) the connection can fail to reach equilibrium (use slow-start to quickly get to equilibrium) =item 2) a packet is introduced prematurely (use average rtt with variance) =item 3) the connection cannot reach equilibrium due to resource limits (in times of congestion, use +increase/*decrease) =back =head1 More Detail B The conservation of packet principle introduces a chicken & egg problem: one can only send out packets in response to an ack; yet to get an ack, one must send out a packet. Slow start is an algorithm for getting a flow up to the equilibrium point fast. The algorithm is: =over 4 =item * introduce state variable I. When starting, set I to one. =item * when an ack is received, increase I by one =item * sender sets window size W to MIN(I, advertised window) =back "Slow" start isn't really slow: it reaches equilibrium in RlgW where R is the round-trip time and W is the equilibrium window size. B Under conservation of packets, the only way to introduce a packet early is due to a timing error or, in other words, the RTO (round-trip time-out) is incorrectly set. A common mistake is to not use the variance in rtt. Queue theory says that the variance of RTT increases greatly with load. An example: if the load is 75%, one can expect RTT to vary by a factor of 16. The authors use a I to estimate the RTT: RTT = RTT * I + R*(1-I). They've chosen to make I = .9. They then adjust the RTO to take into account the variance: RTO = I * RTT. Again, I is not a fixed value but rather an estimated variance. B A congestion avoidance algorithm has two components: feedback from the network and an endpoint policy that acts on the feedback. Here, the feedback used is the acks (or lack of acks) and the policy is additive increase of the window size when feedback indicates no congestion and multiplicative decrease otherwise. The additive increase is 1; the multiplicative factor for decrease is .5. Multiplicative increase leads to the I: it's easy to saturate the network but very difficult to recover. (Recall, also, that Jain stated that +/+ is unfair.) The algorithm is as follows: =over 4 =item * * decrease: on timeout, set I to 50% of W =item * + increase: on each ack, increase I by 1/I (just a fraction, but by the time all the acks have been received, the fractions will add up to one). =item * sender always sets W to MIN(advertised window, I) =back B The algorithms for slow-start and congestion avoidance are presented separately because they address different implementation pathologies. In reality, however, they are implemented together. Here is the (real) algorithm with the two combined: =over 4 =item * on timeout: set variable I = 50% of W, set I = 1 (to trigger slow-start) =item * when ack received: if (I > I), I += 1; else I += 1/I. =back B The next step is to address I at the gateway level. The aggregate information necessary to detect congestion and provide fairness is only available there. If the feedback mechanism used is to drop packets, the gateways get I for free (since they just drop the packets of the network hog in questions.) They note that Jain's queue averaging over the regeneration period might help with the bursty nature of network traffic but it has other problems under high-load.