More flood protection

[fanf]

Following on from http://www.livejournal.com/users/fanf/36178.html
I have updated the document at http://www.cus.cam.ac.uk/~fanf2/hermes/doc/antiforgery/ratelimit.html with a new subsection that does a little analysis of the behaviour of the mathematical model.

On Saturday night at j4 I gave hoiho a quick run-down on what it was all about. (We really know how to party in Cambridge!) He suggested looking at the leaky bucket model which is often used in networking circles, because it fairly closely models the way that packet buffers operate. From the mathematical point of view it's probably similar to adjusting the moving average for variable event frequencies as I have done for the exponentially-weighted average.

The reason I didn't look at it initially was because the amount of state it requires increases with the permitted sending rate and burstiness. This is OK if you are a router and are already keeping that state along with the packets, but I have to re-load and re-save the state for each message. However it turns out that the model I picked has pretty much the same intuitive model, where one of the configuration parameters can be thought of as the bucket size, i.e. the maximum size of a burst of messages.

It's nice when a result shows you that your first choice of maths turned out to be a better fit than you expected, and pleasingly neat to boot. It has been fun resurrecting some more of my secondary school knowledge :-)

Comments

[captain-aj.livejournal.com]

Now, what was I telling you about iptables limit module? ;-)

[kaet.livejournal.com]

One of the models I've used in the past (probably not appropriate here) has been the bead-on-string model.

I don't seem to have my explaining head on today, but I'll give it a go. :)

You have a single variable as state, which contains an absolute time. Whenever the variable is Examined it is first tested if it is in the past and if so is reset to the present. To determine if something should be blocked the variable is Examined. A constant is established which is an interval of time, and determines the allowances for bursts. If the variable, upon Examination, is between the present and present+burst-interal, it is not blocked: if it is beyond that point, then it is blocked (or, rather, delayed until the condition is met). A rate is established (the long-term rate limit itself) in units of resource per unit time. When a request is allowed the resources consumed are exchanged at the determined rate into a time and the bead pushed into the future by that amount.

This establishes, with minimal state, a rate-limit with hard bounds (over a period of t, r(t+b) resources at most are consumed, where r is the long-term rate limit, t the period and b the burst allowance, rb being the largest download which can occur instantaneously without rate-limiting).

[fanf]

I think what I described in the post is not the traditional leaky-bucket model - or at least the implementation I had in mind was wrong.

The usual description is as follows. You have a bucket which is filled at a constant rate. Any overflow is discarded. When you want to send a message, you must fill a cup from the bucket. If the bucket doesn't have enough water in it, you can't send. The implementation of this is a measure of the volume in the bucket and the time of the last packet. When you want to send, the volume is incremented by the time interval multiplied by the fill rate, and the result is checked against the volume of the cup.

Your model seems to be effectively the same, but with less state, which is nice :-)

They both have the disadvantage that they only provide a boolean comparison between the rate of incoming events and a benchmark rate - you just get an above/below result. A model that actually provides a measurement of the sending rate as an output is more useful for logging and diagnostic purposes.

[kaet.livejournal.com]

Ah yes, it does sound very similar. I'd not seen an explanation like that before. My big worry about moving averages is that it's difficult to put hard limits on things. I don't think it's a problem in the case of email rate limiting: most of the time I need to mess with such things it relates to fairness given bandwidth limits.