Queue Management Algorithms Differences

[JonathanLee]

Hello Fellow Netgate Community,

I wanted to make a post about the differences between Queue Management Algorithms Tail Drop, CoDel, PIE, RED, GRED. Have you ever wondered about the true differences within these options? I have been researching this topic after my Sierra College computer science class CSCI13 this week helped explained how Queues work, I wanted to share this post from my researching, maybe you have more information and want to add some knowledge just please reply below. This is all about expanding knowledge on Queue Management Algorithms. I am left with questions on why a proxy is not introduced into this Algorithm to look at HTTP headers and Get requests that could be configured to have a higher priority for lets say Zoom or Hulu headers. Why are we stuck waiting for a update to run that should be delayed for when users are on the system, let the update take the bandwidth when there is less traffic. Right?

I learned so far Tail Drop Queue will only drop packets when the queue is full. However what is the best to use for a home end user with a bandwidth limit only being the speed of the ISP? Codel stopped the BufferBloat, however why only use Tail Drop inside of this? The configuration example from Netgate Docs shows to use this enable Tail Drop, is there a better option?

(Prabhakar)

(Prabhakar)

"RANDOM EARLY DETECTION (RED)
RED algorithm has been proposed by Floyd and Jacobson (1993) for one of the most known AQM. One goal of using the RED algorithm is to detect instantaneous congestion. Another goal is to avoid congestion by controlling the average queue size for the router in a region of low delay and high throughput (Al-Nabhan et al., 2006; James Abu and Gordon, 2011). The aql is compared to two thresholds. If the aql value is smaller than minimum threshold, no packets will be dropped. On the other hand, if the aql value is larger than maximum threshold, a heavy congestion occurs and the arriving packet is marked. Finally, when the aql is between minimum and maximum thresholds, the congestion occurs and the router drops the packet with the probability of Dp (Floyd and Jacobson, 1993)" (Mahmoud).

(Prabhakar)

(Prabhakar)

(Prabhakar).

"GENTLE RANDOM EARLY DETECTION (GRED) METHOD
GRED was proposed by Floyd (2000) to deal with some of RED’s issues (Floyd, 2000; Aweya et al., 2001; Floyd et al., 2001). The pseudocode of GRED is shown in Figure 1 and a description (definition) of the parameters used in the pseudocode is presented in Table 1.
Figure 1 shows that every time a packet arrives at the router buffer, the aql value is calculated as in RED (Floyd and Jacobson, 1993), as given in the following equation:

If the aql value is smaller than the min threshold position, no packets will be dropped and the Dp value is set to zero. On the other hand, if the aql value is larger than or equal to double max threshold position, a severe congestion occurs and afterward every arriving packet will be dropped with DP =1. Finally, when the aql value is between min threshold and double max threshold positions, a congestion occurs and the router buffer drops the arriving packets probabilistically (0<Dp<1). The result of Dinit varies between Dmax and 1 as long as the aql value varies between max threshold and double max threshold positions (Floyd, 2000). This variance produces further harmony to the parameter settings of max threshold and Dmax" (Mahmoud).

"CHOKe

(CHOose and Keep for responsive flows, CHOose and Kill for unresponsive flows) aims to approximate max-min fairness for the flows that pass through a congested route?. The basic idea behind CHOKe is that the contents of the FIFO buffer form a “sufficient statistic” about the incoming traffic and can be used in a simple fashion to penalize misbehaving flows" (Stanford).

(Prabhakar)

Controlled Delay (CoDel)

"In order to mitigate the bufferbloat problem, it is presented Controlled Delay2 (CoDel), an innovative Active Queue Management (AQM) that adapts to changing links rates and it is suitable for deployment and experimentation in Linux-based routers. The goal of CoDel3 is to contain the queuing latency while maximizing the throughput. CoDel does not require any parameters tuning and it has been designed to work across a wide range of conditions with different links and round-trip times. Figure 1 illustrate a scenario where CoDel AQM is used to manage the queue. Firstly, a timestamp is added to every incoming packet. Then, by measuring the departure time of every packet in the queue, it is determined for how long a packet was waiting in the queue. Consequently, CoDel algorithm determines whether the enqueued packets are going to be dropped or not" (ce.sc.edu).

(ce.sc.edu)

Proportional Integral controller Enhanced (PIE)

"PIE drops an incoming packet when p ≤ pdrop, where p is drawn at random from a uniform distribution in [0, 1], and pdrop is an internal variable updated every λ = 30 ms according to:

E[T] and E[T]old represent the current and previous estimation of the queuing delay. τ is PIE’s target delay. α determines how the deviation of current queuing delay from τ affects the drop probability, whereas β exerts additional adjustments depending on whether the queuing delay is trending up or down" (arxiv).

When we require performance that is built to specific user needs that are changing rapidly within business and home use, an HTTP header based option that works alongside a proxy could be an answer to a new Queue algorithm. We may soon have an ability to change items on the fly. Again this could be as easy as entering a URL once configuration is completed. If one wants Zoom traffic to take priority in the Queue just enter this URL and the system will use the HTTP get requests to prioritize traffic based on when that request is seen inside the proxy, once a stream starts to run it will adjust the Queue for priority traffic. Hulu, new streaming services, Disney plus, and the ever changing user needs list could be built right into an HTTP get request that would maximize end to end user traffic shaping, on a smaller more user friendly scale.

Works Cited:

ALTQ scheduler types. Traffic Shaper - ALTQ Scheduler Types | pfSense Documentation. (n.d.). Retrieved April 28, 2022, from https://docs.netgate.com/pfsense/en/latest/trafficshaper/altq-scheduler-types.html

Choke a stateless active queue management scheme ... - stanford university. (n.d.). Retrieved May 2, 2022, from https://web.stanford.edu/~balaji/papers/00chokea.pdf

Improving PIE’s performance over high-delay paths. (n.d.). Retrieved April 29, 2022, from https://arxiv.org/pdf/1602.00569.pdf

Lab 18: Controlled delay (CODEL) active queue ... - ce.sc.edu. (n.d.). Retrieved April 29, 2022, from http://ce.sc.edu/cyberinfra/workshops/Material/NTP/Lab%2018.pdf

Mahmoud Baklizi, Hussein Abdel- jaber, Sureswaran Ramadass, Nibras Abdullah and Mohammed Anbar, 2012. Performance Assessment of AGRED, RED and GRED Congestion Control Algorithms. Information Technology Journal, 11: 255-261.
DOI: 10.3923/itj.2012.255.261
URL: https://scialert.net/abstract/?doi=itj.2012.255.261

Prabhakar, B., & McKeown, N. (n.d.). EE384Y: Packet Switch Architectures - II. Index of /class/EE384Y/handouts. Retrieved April 29, 2022, from https://web.stanford.edu/class/ee384y/Handouts/

[dtaht]

@jonathanlee Thank you very much for this attempt. I am personally very graphically untalented, but very responsive to good graphs. If ever you have a chance to give this a go again, to revisit and re-use your first tail drop diagram in contrast with codel alone - codel drops from the head of the queue, not the tail, and I would perhaps draw a 5ms target window at the same 4 packets you use here and feature a few more packet slots as a shock absorber. then three phases

1. queue over target showing timestamps
2. shock absorber filling -> dropping from head when too old
3. queue below or at target

I have NEVER managed to describe how codel operates well enough to suit me, and fq_codel, or for that matter, cake, oh, man...

https://lists.bufferbloat.net/pipermail/bloat/2013-February/004888.html

To try and describe how fq-codel works, I would use a single queue on the front left there with different colors for packets and their bunches. I do things like

AAAAAABBFBBEAAAFEAAACAAA ->

And coming out:

BABAABFA BCEFCA

Which is kind of accurate for a per packet FQ system, but DRR is different and having the longer blobs to represent bytes rather than packets might help.

Does that help any?