4 ms·

Sounds like an interesting story, you were working with Van Jacobsen, and made the suggestion to him? (since he's usually credited with that form of congestion

Sounds like an interesting story, you were working with Van Jacobsen, and made the suggestion to him? (since he's usually credited with that form of congestion control, folks might appreciate a little more explanation). Was there an unstated assumption that packet sizes might scale up with network speeds? (and not get trapped at the original 10mbit ethernet frame size as it turned out). Today we send teeny micropackets relative to link speeds, and increasing by one packet at a time is (in retrospect) a weird outcome. But like Chesterton's fence, it's nice to know how it got there.

Animats 10y ago
See RFC896, "Congestion Control in IP/TCP Internetworks" (1984) [1] and RFC 970, "On Packet Switches With Infinite Storage" (1985).[2] I wrote both. The first one introduced adjusting the offered window based on congestion. The second RFC introduced "fair queuing" and "congestion collapse". I coined both terms. Back then, there were ICMP Source Quench packets, which told the sender to slow down. We used those, but Berkeley didn't, and they eventually were abandoned. The second paper is more philosophical. Back then, the big issue in networking was running out of buffers. Memory was expensive, and everything had tiny buffers by modern standards. Running out of buffer space had been a big problem in the ARPANET, and the original ARPANET protocols focused on not running out of buffers. (The original ARPANET had hard backpressure - if there wasn't enough buffer space in the network nodes, you couldn't send. Packets were never dropped for congestion reasons.) I pointed out that even with infinite buffer space, congestion was still possible. This is now conventional wisdom (see "bufferbloat"), but back then, it was a new idea. The other new idea was viewing congestion as a closed-loop game theory problem. See the section "Game Theoretic Aspects of Network Congestion" in RFC970. Today everybody involved with networking traffic management thinks about router strategy and end node strategy interacting. But classical queuing theory was about stochastic arrival rates. The classic paper back then was Kleinrock's "Message delay in communication nets with storage"[3], which is considered part of the theoretical underpinnings of the ARPANET. Kleinrock also wrote the classic text on queuing theory. But Kleinrock wasn't studying the ARPANET; he was studying Western Union Plan 55-A, a distributed message switching system. (Think of a system that works like email forwarding over fixed links, with lots of forwarding. Plan 55-A was like Sendmail, built out of paper tape punches and readers and phone-type switchgear. A switching node was a large building.) Plan 55-A had no influence over the rate at which people submitted telegrams. That model didn't consider behavior of senders (end nodes) at all. So looking at the problem as a game-theory problem was new. Somehow, the network had to not reward the sender who sends the most. A FIFO queue rewards the sender who sends the most. (Hence "bufferbloat", which is what happens when you have a huge, dumb FIFO queue.) That leads to everybody over-sending, long queues, and many dropped packets. So I devised fair queuing, with a queue for each sender, to eliminate the reward for over-sending. If you're sending into a fair router, your optimal strategy is to send just enough that your own private queue has 1 or 2 packets. Now the job is to make the end node (at the TCP level) try to do that. Hence congestion windows and other forms of end node traffic shaping. I got out of networking in 1986; I was involved with a startup doing something else. So I was out of this before Van Jacobson really got into it. [1] https://tools.ietf.org/html/rfc896 https://tools.ietf.org/html/rfc896 [2] https://tools.ietf.org/html/rfc970 https://tools.ietf.org/html/rfc970 [3] https://dspace.mit.edu/bitstream/handle/1721.1/11562/33840535-MIT.pdf https://dspace.mit.edu/bitstream/handle/1721.1/11562/3384053...
- majke 10y ago
  I just wanted to chime in and say thank-you. Your technical answers are always very interesting.
- jimgettys 10y ago
  Yes, John's work is seminal, and fair (flow) queuing is essential in cleaning up the bufferbloat mess. Flow queuing has a bigger effect on end user experience than mark/drop algorithms to signal TCP (though that is also needed to keep TCP from losing its mind). I distinguish flow queuing from fair queuing as it has aspects that are not "fair", but the fundamentals are the same. The recent BBR work at Google is another key to solving bufferbloat. I finally think we have the tools needed to really solve the problem, between flow queuing and new mark drop agorithms (e.g. Codel, CAKE, PIE, fq_codel, etc.) and BBR. So again thanks to John for his key work. Jim Gettys (who coined the word bufferbloat).

Animats 10y ago

See RFC896, "Congestion Control in IP/TCP Internetworks" (1984) [1] and RFC 970, "On Packet Switches With Infinite Storage" (1985).[2] I wrote both. The first one introduced adjusting the offered window based on congestion. The second RFC introduced "fair queuing" and "congestion collapse". I coined both terms. Back then, there were ICMP Source Quench packets, which told the sender to slow down. We used those, but Berkeley didn't, and they eventually were abandoned. The second paper is more philosophical. Back then, the big issue in networking was running out of buffers. Memory was expensive, and everything had tiny buffers by modern standards. Running out of buffer space had been a big problem in the ARPANET, and the original ARPANET protocols focused on not running out of buffers. (The original ARPANET had hard backpressure - if there wasn't enough buffer space in the network nodes, you couldn't send. Packets were never dropped for congestion reasons.) I pointed out that even with infinite buffer space, congestion was still possible. This is now conventional wisdom (see "bufferbloat"), but back then, it was a new idea. The other new idea was viewing congestion as a closed-loop game theory problem. See the section "Game Theoretic Aspects of Network Congestion" in RFC970. Today everybody involved with networking traffic management thinks about router strategy and end node strategy interacting. But classical queuing theory was about stochastic arrival rates. The classic paper back then was Kleinrock's "Message delay in communication nets with storage"[3], which is considered part of the theoretical underpinnings of the ARPANET. Kleinrock also wrote the classic text on queuing theory. But Kleinrock wasn't studying the ARPANET; he was studying Western Union Plan 55-A, a distributed message switching system. (Think of a system that works like email forwarding over fixed links, with lots of forwarding. Plan 55-A was like Sendmail, built out of paper tape punches and readers and phone-type switchgear. A switching node was a large building.) Plan 55-A had no influence over the rate at which people submitted telegrams. That model didn't consider behavior of senders (end nodes) at all. So looking at the problem as a game-theory problem was new. Somehow, the network had to not reward the sender who sends the most. A FIFO queue rewards the sender who sends the most. (Hence "bufferbloat", which is what happens when you have a huge, dumb FIFO queue.) That leads to everybody over-sending, long queues, and many dropped packets. So I devised fair queuing, with a queue for each sender, to eliminate the reward for over-sending. If you're sending into a fair router, your optimal strategy is to send just enough that your own private queue has 1 or 2 packets. Now the job is to make the end node (at the TCP level) try to do that. Hence congestion windows and other forms of end node traffic shaping. I got out of networking in 1986; I was involved with a startup doing something else. So I was out of this before Van Jacobson really got into it. [1] https://tools.ietf.org/html/rfc896 https://tools.ietf.org/html/rfc896 [2] https://tools.ietf.org/html/rfc970 https://tools.ietf.org/html/rfc970 [3] https://dspace.mit.edu/bitstream/handle/1721.1/11562/33840535-MIT.pdf https://dspace.mit.edu/bitstream/handle/1721.1/11562/3384053...

majke 10y ago
I just wanted to chime in and say thank-you. Your technical answers are always very interesting.
jimgettys 10y ago
Yes, John's work is seminal, and fair (flow) queuing is essential in cleaning up the bufferbloat mess. Flow queuing has a bigger effect on end user experience than mark/drop algorithms to signal TCP (though that is also needed to keep TCP from losing its mind). I distinguish flow queuing from fair queuing as it has aspects that are not "fair", but the fundamentals are the same. The recent BBR work at Google is another key to solving bufferbloat. I finally think we have the tools needed to really solve the problem, between flow queuing and new mark drop agorithms (e.g. Codel, CAKE, PIE, fq_codel, etc.) and BBR. So again thanks to John for his key work. Jim Gettys (who coined the word bufferbloat).