Thoughts on Queues and Congestion Avoidance

1. 1. Ideally, each node knows its bandwidth share and sends exactly with that bandwidth share.
2. 2. Ideally, the nodes would send their packets in a round-robin fashion, i.e. the packets arrive at the bottleneck gateway in equal time intervals at the same rate they go through the bottleneck link. E.g. if a packet needs 1 ms for transmisson on the bottleneck, node 1 sends now, node 2 1ms later, node 3 2ms later, ... node n n-1 ms later, node 1 sends the packet n ms later.
3. 3. Provided 1 and 2, there would be no queue necessary.
4. 4. A congestion protocol should try to maintain 1 and 2 as best as possible, that way no queue is necessary (by 3). There will be low delays.
   
5. 5. Given 4, the function of a queue is to catch up bursty traffic.
6. 6. The opposite situation of 2 is global syncronization: all nodes send their packets at the same time. The queue will be long, there will be long delays.
   
7. 7. 2 is hard to accomplish, the best situation to hope for is that each node sends the packet in a random time, the random distribution will have relatively small clusters which can be buffered in the queue.
8. 8. There are two quantities to control: the queue size and the arrival rates of packets at a gateway. The first one is to be kept low (to have low delay and be able to deal with bursts), the second one is to be kept at the output link rate of the gateway.
9. 9. The queue size is the integral of the difference of arrival rate-output rate over time.
10. 10. The necessary reaction to a too large queue size and a too arrival rates have to be different: the first one requires that the senders interrupt sending packets for a short while, the second one requires that the senders change their packet rate. This is similar to the situation when having a car driving in front of you on a highway. When you see that the car is slower than you, you reduce your target speed until it matches the target speed, when you see that the car is too close, you keep the same target speed, just briefly slow down below target speed until there is sufficient distance.
11. 11. Because traffic demands are changing, 1 can only be archived through feedback loops.
12. 12. The success of the feedback loop (in terms of efficient use of bandwidth, keeping low delay and fairness) will depend on how soon and how precisely the senders can sense a congestion situation.
    
13. 13. The original Jacobson paper on Congestion avoidance assume that the only way of the gateway signaling congestion is dropping packets when the queue is full. It is even unclear what this signals with respect to point 10. Too high arrival rate is signaled indirectly because it will eventually cause a too high queue size.
    
14. 14. In the original Jacobson paper on Congestion avoidance (Van Jacobson, Michael J. Karels, "Congestion Avoidance and Control"), congestion was sensed through packet loss, which happens "late".
15. 15. "In the absense of explicit feedback from the gateway, trasport-layer protocols could infer congestion from ... changes in end-to-end delay [or] packet drops [...]. Nevertheless, the view of an individual connection is limited by the timescales of the connection, the lack of knowledge of the number of congested gateways, the possibilities of routing changes, as well as by other difficulties in distinguishing propagation delay from persistent queueing delay." (Sally Floyd, Van Jacobson, "Random Early Detection Gateways for Congestion Avoidance")
    
16. 16. Because of 15, Gateways need to give feedback to the nodes. "The gateway can reliably distinguish between propagation delay and persistent queueing delay." (Sally Floyd, Van Jacobson, "Random Early Detection Gateways for Congestion Avoidance")
    
17. 17. Because of 12, the situation gets worse with throughput-delay product.
18. 18. It is better to buffer a packet at the sender than in a queue of a gateway of the network to keep delays low.
19. 19. The oscillatory behavior of a congestion avoidance algorithm will be stronger if the feedback times are long and if the actions of the algorithm are discontinuous in the input to the algorithm.
20. 20. The difference of necessary behavior in 10 is also charaterized by time scales: "Using tools from control theory, we conjecture that congestion feedback based on rate-mismatch should be inversely proportional to delay, and feedback based on queue-mismatch should be inversely proportional to the square of the delay." (Dina Katabi, Mark Handley, Charlie Rohrs, "Congestion Control for High Bandwidth-Delay Product Networks")
21. 21. The optimal size for the congestion window is the maximal amount of traffic on the network links (not the queues) when using the fair share of bandwidth, i.e. bandwidth*transit times (not including queueing delays)