A CS 255 Paper Review for Controlling Queue Delay by Kathleen Nichols and Van Jacobson
In one of the past papers, we were able to see the RED (random early detection) model for congestion avoidance and the tail drop mechanism which have also been widely discussed in class. In these topics, queues have always been mentioned and it gives the impression that congestion results to queues but could also be the other way around, congestion happens because there are a lot of incoming packets from queues.
This paper presents a refreshing take on congestion avoidance and queue management. It clearly explains why queues exist and what are their original purpose – as shock absorbers for burst allowing for a smooth departure. Initial mechanisms, such as the first version of RED, were made in hopes of solving this congestion problem. But issues in usability, configurability, and user-friendliness was a hindrance for RED fully taking off. Succeeding AQMs inspired by RED were more complicated which made them not take off as well.
A lot of AQM (active queue management) systems have been developed but their success was hampered by their own misconceptions and wrongly perceived problems on the cause and meaning of queues. Since they are based on a wrong conceptual model – problems that were tried to be solved were actually not the root causes but could just be side effects or might not be related at all (solutions such minimizing bandwidth size, queue length, etc). Also, the need for dynamism in configurations is necessary as it is not impossible to pick a static size for all the metrics.
The paper was also full of helpful illustrations like the one below. It shows that when data comes through a bottle neck, from being the original vertical bar (height is in bits, width is in time), it stretches itself into a horizontal bar once it passes through the bottle link representing that it will take more time..
Simple as it is, but I think this is really a good illustration on how bottlenecks affect queueing. And how when they return after 1 RTT, the packets are now spaced. Equality of arrival rate to departure rate has been achieved.
Another comprehensive but simple and easy to understand illustration was also shown where the queue does not go to zero but remain steady. This is where window is 25 (5 more than what can actually fit), standing queue. The standing queue created delays but no improvement in throughput since the excess packets can’t really be served.
As the paper says, this is usually tried to be solved by limits imposed by providers to consumers (usage limits / penalties) but these don’t actually help much at all.
Queue, in its own essence, are not actually bad since they act as shock absorbers for bursts. Bt what makes a queue bad is if it stays long – more than 1 RTT. Queues that dissipate after 1 RTT (after a smooth and steady departure) are acceptable and are good!
In efforts to improve on the old RED algortihm, a new RED algorithm came up that required only one parameter: queue output bandwith / average departure rate. But again, it still has bias against bursty traffic.
As the paper defined, a good AQM is parameterless ( no need for configs to be manually set), dynamic (adapts to network situation), allows for bursts, and simple yet efficient. With these, CODEL (Controlled Delay) was introduced together with 3 of its innovations, the use of a local minimum queue, a single state variable, and a packet sojourn time (actual delay experienced) made it efficient, dynamic, and flexible.
The paper also described well its simulation environment – use of NS2, CUBIC for file transfer, PackMime for web browsing emulation, SACK was also used and the Jain index for measurement of fairness.
The results showed that RED and CODEL had almost the same delay when bandwidth was < 3 Mbps but CODEL had a little more when the bandwidth was higher. But for utilization, it was significant that CODEL had much more. This might be because in the recent improvement for RED, RED became more controlling that’s why the network was not utilized to its full capacity.
In comparison to Tail Drop, on the other hand, Tail Drop has almost the same utilization but CODEL has significantly lesser delays than Tail Drop which almost had delays all through out
In terms of fairness, CODEL won too as the newer version on RED already employed a less random mechansim in choosing which packets to drop.
Overall, the paper presented the concepts very well and was very good in using illustrations — tables, graphs, pictorial representation to supplement understanding and visualization.. It also explained very well the original purpose of queues which enables the reader to fully appreciate the presence of queues and need for managing them. Comparisons to present and past mechanisms were also made. The paper also provided explanations and results as to why CODEL is better. Pending real life concerns such as where to implement these were present as well.
Definitely one of the greatest reads I had for this semester! 🙂
Illustrations from the Paper Controlling Queue Delay by Kathleen Nichols and Van Jacobson.