- Kent Brockman
After a brief defense of the internet protocols, Jacobsen et al. begin their paper with a description of a real-world internet meltdown. What would otherwise be a fairly abstract and sober discussion is therefore framed by a crisis: protocols aside, the implementations were broken and needed immediate repair.
They begin with the intuition that a well-behaved and stable network obeys the packet conservation principle: at equilibrium, a packet leaves for every packet entering the system, and vice versa. Even ignoring the notion of equilibrium this notion addresses congestion; if we send a packet only after receiving the ACK for our previous packet (this would be self-clocking), we guarantee a stable system but squander its resources, leaving gaps in the pipe and the queues. Slow start addresses the issue of filling those queues and pipes (even though doing so more aggressively than self-clocking risks overwhelming the receiver) safely; every ACK means injection of a new packet plus a +1 increase in the window; thus the window increases exponentially and we approach equilibrium logarithmically, guaranteed to exceed the receiver's capacity by at most 2X. As slow-start addresses the problem of efficiently reaching equilibrium, round-trip estimation addresses maintaining that equilibrium. As a network becomes congested, variance increases as well as round-trip time, so making accurate estimates must involve a variance measure; otherwise it will be reacting to noise as much as congestion. The authors favor mean deviation (the avg(|m-a|) rather than sum((m-a)**2) ) as a cheaper (and overflow-safe) approximation of real variance. Finally, addressing resource issues on the whole path that might prevent a connection from reaching equilibrium requires a real congestion avoidance algorithm based in queueing theory: this is the additive increase/multiplicative decrease that is addressed mathematically in Chiu et al.
This is new material for me, so few criticisms spring immediately to mind. I think it is cool to observe complicated theory generating very simple implementations, and even cooler that independent theories (slow start and AI/MD) compose so well into a single algorithm. Clearly there are a number of assumptions in spite of the formality of the discussion, but I am unsure how reasonable they are. It is assumed, for example, that all packets are either eventually ACKed, or fail to be because of buffer expiry or damage (they further indicate that loss due to damage is much less than 1%, but I am unsure where this comes from).
No comments:
Post a Comment