Van Jacobson, "Congestion Avoidance and Control" 0. Paper is about algorithms addded to 4BSD TCP after a series of "congestion collapses" in the Internet. Big Idea--Conservation of Packets Principle: For a connection in equilibrium, a new packet shouldn't be put onto the network until an old packet leaves. Packet Conservation can fail: i) connection doesn't get to equilibrium ii) sender injects a new packet before an old packet has exited iii)equilibrium can't be reached because of resource limits I. Slow-Start - for solving "getting to equilibrium": problem is that TCP is self-clocking: we don't send a packet till we receive ACKs. But, we don't get ACKs before we send a packet. (chicken/egg?) - Slow-Start idea is to gradually increase amount of data in transit. - tcp implementation: * cwnd variable per-connection * when starting after a loss, set cwnd=1packet * on each new ack, increase cwnd by one packet * when sending data, send min of receiver's window & cwnd II. Estimating Round-trip Time - TCP Spec: R = aR + (1 - a)M. R = roundtrip time (rtt) M = rtt of most recent ACK a = constant (0.9) - retransmit timeout is: bR. b accounts for RTT variation. Problem is that rtt variation increases with load. So, a constant value of b will either be bad for small loads, or bad for big loads, etc. A cheap method for estimating b dynamically has been developed (Appendix A). - also, do exponential backoff on retransmits. III. Congestion Avoidance - If retransmit timers are doing their job, we can say that packet loss is due to congestion or damage. Damage occurs rarely in wired world. - when network is congested, packet queue lengths grow exponentially. To stabilize, sources have to throttle back at same rate. - when network is not congested, want to increase utilization to find the bandwidth limit - TCP algorithm: on congestion: W(i) = d*W(i-1) (d<1) w/out congestion: W(i) = W(i-1) + u (u<