Paper Review #9: Controlling Queue Delay

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..

Screen Shot 2015-11-21 at 12.37.36 PM.png

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.

Screen Shot 2015-11-21 at 12.38.07 PM.png

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

Screen Shot 2015-11-21 at 12.38.58 PM.png

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.

Advertisements

Paper Review #8: A Generalized Processor Sharing to Flow Control in Integrated Services Networks: The Single Node Case

A CS 255 Paper Review for  A Generalized Processor Sharing to Flow COntrol in Integrated Services Networks: The Single Node Case by Abhay K. Parekh

In our tech-savvy world today, we see and use a variety of network traffic types (realtime games, video, audio, chat, etc) in our every day lives. Because of this, network flexibility is becoming a primary concern to network providers and administrators. With the needed flexibility, other important network aspects such as performance guarantees and fairness should still not be compromised. Fairness such that other users’ experience should not be degraded just to serve a more demanding traffic on another. Flexibility such that the network can give different performance guarantees to different customers depending on their needs and demands in the network.

These concepts, concerns, and solutions were widely tackled in the paper A Generalized Processor Sharing to Flow Control in Integrated Services Networks: The Single Node Case by Abhay K. Parekh. The use of the Generalized Processor Sharing (GPS) together with leaky buckets was given focused especially on its ability to provide flexibility as well as worst case performance guarantees. The paper assumes that rate admission control is done in the leaky buckets as it shapes incoming traffic.

GPS, in its vanilla version, does not transmit packets as entities but instead assumes that packets are infinitely divisible. With this limitation came another variant: the GPS with leaky bucket that operates on packets called the Weighted Fair Queueing or PGPS (Packet by packet Generalized Processor Sharing).

Proofs and lemmas were shown where appropriate to better strengthen the concepts being discussed.  The paper is also effective in uniting and connecting two separate proofs to arrive at another final conclusion.

A comparison of PGPS to other schemes such as the virtual clock multiplexing by Zhang was tackled next. The virtual clock multiplexing provides a guaranteed rate as well but what makes it different from PGPS is that it has a bias against bursts even if network load is light. A helpful numerical example was given for this concept:

Screen Shot 2015-11-18 at 11.20.01 AM

At time 0 to 900, only session 1 is using the network but on t = 901 onwards, another session, session 2, also started transmitting in the network. In this setup, at 901, only connection 2 will be served with virtual clock multiplexing. Only until all of its packets have been transmitted will connection 1 be served again. Connection 1 was “punished” for having solely used the network during 0 – 900 even if it was not in the expense of session 2 or any other sessions. In contrast to this mechanism, PGPS uses a round robin fashion in determining who it will serve next in the event that multiple sessions are needing network throughput ensuring that everyone get’s their network share in a limited amount of time.

Leaky buckets were widely discussed next and how it is able to bound busy system periods. Sessions are provided with tokens which they can use to transmit. As long as tokens are still available, sessions are free to transmit in the network.

Overall, the paper provided a very comprehensive and technical discussion on generalized processing systems (and its per packet counterpart) as well as on leaky buckets. Proofs, lemmas, graphs, and illustrations were very helpful to prove and elaborate on different major points and concepts. The paper could have also capped off its technicality with a brief conclusion summarizing its main points but this is only minor as the introduction had already given an overview of what the paper is all about. 🙂

 

Paper Review #7: Random Early Detection Gateways for Congestion Avoidance

A CS 255 Paper Review for Random Early Detection Gateways for Congestion Avoidance by Sally Floyd and Van Jacobson

The paper comprehensively discusses Random Early Detection (RED) gateways for congestion avoidance.This algorithm notifies connections of congestion either by dropping packets or tagging each arriving packet (by setting a bit in the packet headers) randomly with a certain probability if the average queue length is between a given range. A probability such that it is proportional to the connection’s share in network throughput. RED gateways are designed for transport layer protocols that respond to congestion through marked packets (either dropped or with the congestion bit set). It was also mentioned that even if the transport protocol is not cooperating (it still floods the network even with congestion), the RED algorithm can still control the average queue length since it can drop the non-cooperating connection’s packets.

The paper also extensively compared early models of early detection congestion avoidance mechanisms and how each performed in various scenarios. The two most discussed mechanisms were Early Random Drop and Drop Tail gateways. The Early Randrom Drop gateway is almost the same as RED but it uses a  fixed probability (i.e. does not adjust to network throughput) in determining which connection to notify. While for Drop Tail, on the other hand, since packets are dropped from several connections, global synchronization is introduced. Global synchronization is where multiple nodes receive the congestion notice so they all decrease their throughput at the same time, thus falling below optimal utilization of the network – a scenario that must be avoided and has long been studied.

Another congestion avoidance scheme that was thoroughly discussed and compared with RED is the DECbit congestion avoidance scheme. In contrasts to RED, DECbit marks all incoming packet when there is a congestion (RED select randomly with probability). Because of this, the receiving transport layer protocol still have to compute if the fraction of the received bits are enough to imply congestion. The arking overhead issue was also brought up with DECbit as it tags all incoming packets.

network-congestion-vpisystems.png

Hope there’s also a RED algorithm for traffic congestion.

Next,  the Design for the RED algorithm was presented. One of the highlights was flexibility through the parameters min, max, and average wherein the first 2 can be controlled and set by the system administrator. This flexibility also was complemented by the paper’s provided guidelines in choosing the right values( i.e. the minimum should not be too low that it would already lead to low network utilization, while the maximum must be high enough to approximate bursts but not too high that it won’t be able to prevent congestion).

The paper also did not lack in discussing the implementation details such as employing parallel computation so as to not consume much computation time especially in networks where a lot already happens in a split second. And how RED will tag all arriving packets if the average queue length is already way past the given maximum threshold.

Elaborations on actual network issues such as bursts (and what are the most like reasons behind them) and misbehaving users (users who still consume a large chunk of the network even if network congestion notice has already been sent) and how RED respond to these scenarios capped off the entire paper with a feel of real life applications and solutions.

Overall, the paper was a great and comprehensive read on the Random Early Detection gateways for congestion avoidance. Motivations behind, related mechanisms, design, and implementation details were thoroughly discussed and tackled. There was also an abundance of graphs, formulas, and chunks of pseudocode which made understanding the paper easier.

Photo from: community.michelinchallengebibendum.com