Add RED AQM.

[squidarth]

Hey there,

@vsrinivas and I were working on experimenting with different congestion control schemes and wanted to try out our congestion control schemes w/ different queueing disciplines. We were particularly interested in RED, and wrote an implementation in mahimahi to try out.

There's a high level overview of the algorithm in this RFC, and more detail in this paper.

Algorithm & Parameters

The general idea behind RED is that it drops packets probabilistically, where that probability is determined by an exponentially weighted average of the depth of the queue.

If the queue is empty, we decay the weighted average by the amount of time the queue has been empty to prevent the case where the queue is empty but the weighted average remains high because of the lower number of enqueues that happen (this is outlined in the paper as well).

There are three parameters:

• wq: This is a weight that governs how heavily to weight the the current depth of the queue when updating the weighted average. The higher this is, the more reactive RED is to random bursts of packets
• minthresh: This is the minimum threshold to drop packets (as a % of the queue size). If the queue depth is is below min_thresh, no packets are dropped
• maxthresh: This is the point at which all packets are dropped (as a % of the queue size)

The paper I link to above has a guide for how to tune these parameters.

Thanks for putting the simulator on github--it's been super helpful in learning how this congestion control stuff works, and let me know if you'd like to make any changes here.

[squidarth]

@keithw awesome, thanks for looking at this & the feedback! I resolved most of your comments except for the argument parsing stuff, which I need to think about a little bit. min and max thresholds could certainly be read in as ints, but wq is a little bit tougher, so I might change this to parse arguments "properly".

Couple things I changed that are worth pointing out:

• I had earlier hard-coded s, a variable for managing decaying the weighted average. This should be a parameter to the queuing algorithm, so I added that
• I saw your comment about computing the random number more efficiently, and decided to switch out the implementation to match the one in the paper more closely (scroll down to the "Implementation" section & the pseudo-code if you're curious).

Thanks again for taking a look at this!

[squidarth]

@keithw this is ready for another look! I updated the argument parsing to first convert the arguments into a map<string, string> map first, and then passes that into each queue. DroppingPacketQueue has simple get_int_arg and get_float_arg that work properly.

Note: I copied the tokenize.hh file that I saw you were using in the http module into util. If you're happy with this change I can remove tokenize.hh from the util module and add util to the -I of src/http/Makefile.am.

Error Catching

I tested this with this command:

$ mm-link 2.64mbps-poisson.trace 2.64mbps-poisson.trace --downlink-queue=red  --downlink-queue-args=packets=1000,wq=0.002,minthresh=0.2,maxthresh=5,transmission_time=5

Messing with the args to not use "=" properly results in:

$ mm-link 2.64mbps-poisson.trace 2.64mbps-poisson.trace --downlink-queue=red  --downlink-queue-args=packets1000,wq=0.002,minthresh=0.2,maxthresh=5,transmission_time=5

Died on std::runtime_error: Queue args passed in wrong format

Passing in an incorrect int results in:

$ mm-link 2.64mbps-poisson.trace 2.64mbps-poisson.trace --downlink-queue=red  --downlink-queue-args=packets=x1000,wq=0.002,minthresh=0.2,maxthresh=5,transmission_time=5

Died on std::runtime_error: Invalid integer: x1000

And passing in an incorrect float results in:

$ mm-link 2.64mbps-poisson.trace 2.64mbps-poisson.trace --downlink-queue=red  --downlink-queue-args=packets=1000,wq=x0.002,minthresh=0.2,maxthresh=5,transmission_time=5

Died on std::runtime_error: Invalid floating-point number: x0.002

Let me know what you think! Thanks again for looking at this

[keithw]

Looks really good! (And sorry for the delayed review...) This is almost ready pending:

1. Yes, if you want to use tokenize.hh outside of http, please just move it to util and remove the copy in http. src/http/Makefile.am already has a -I flag for the util directory in AM_CPPFLAGS so I don't think a lot needs to change...

2. On the argument parsing: I'm nervous about the implicit "0" default value in the implementations of get_int_arg and get_float_arg (or that these are static methods that take the argument map by const reference). I think this could lead to user confusion (which leads to emails requesting help with mahimahi, which we are trying to reduce through defensive software engineering...).

Would you be willing to try the following:

a. Instead of returning the map, parse_queue_args returns a ParsedArguments class, and that class encapsulates the map (as a private member) and also exposes public accessors for get_int_arg and get_float_arg.

b. The call signature for get_int_arg and get_float_arg has an optional variable for the default value. If the argument was not provided, and no default value was provided at the call site, the method throws an exception for a missing required argument. If the argument was not provided, and a default value WAS provided, the method provides the default value but also logs a warning to stderr ("Note: Using default value of xxx for parameter yyy").

3. Once those are both done, please squash and make 1-3 semantic commits without fixup commits in the mix.

Other than that I think it's good to go. Thanks again for all your work on this.

[keithw]

Wanted to follow up on this -- we're still really interested in merging RED.

[squidarth]

Hey @keithw, sorry about the radio silence (i've had a really busy past couple months). I'd love to finish this up--I'll take care of it this weekend!

[squidarth]

Hey @keithw,

Sorry again for being so late to get back on this--I just started a new job which has been crazy. I resolved the changes that you mentioned--the main file to look at in the diff is "parsed_arguments.hh". I put it in the frontend folder, which makes the import in the packet classes somewhat awkward, do you think it makes sense to put it in util? That didn't seem totally right either.

Besides that, I think this should be good to go. Sorry again for the long delay.

[keithw]

Yeah, let's put it in util so you don't have to do the weird import.

[squidarth]

Updated!

[squidarth]

Hey @keithw, just wanted to check-in again to see if there's anything else you wanted to see here!

[squidarth]

hey--i know this has been sitting here for a while but just wanted to double check if there was anything else you needed here!