Leaking bucket of water

Leaky Bucket Algorithm

Liam Relihan News & Updates

Occasionally, we aim to publish something that has to do with how we implement our hardware and software solutions. Here is one of these “somethings”….

On one of our embedded devices there is the facility to automatically dispatch text messages in response to particular events. However, to protect against the possibility of the device sending out a storm of text messages (e.g. due to a bug in the event detection code), we decided to create a little algorithm to limit the generation of messages in any given period.

To do this we used a little algorithm from the computer networks field called the “leaky bucket” algorithm. Here is what it does…
when the user wishes to do a controlled action (e.g. send an SMS), he tries to add a “drop” of water to the “bucket” using addDropToBucket()
addDropToBucket() checks to see whether some drops should have leaked out since the last call. If so, it lets them leak
then addDropToBucket() checks to see if there is space in the bucket for a single drop. If there is, it adds the drop and returns true, otherwise it returns false
if the user receives “true” he carries out the controlled action, otherwise he doesn’t.

Essentially, the metaphor is that of a leaky bucket leaking out water at a certain rate.

Finally here’s the java code to make it all happen…

 
 /**
     * Leaky bucket algorithm to prevent huge amounts of SMS text messages
     * from being dispatched by any insane processes. Each SMS message
     * sent adds a drop to the
     * bucket which leaks at a constant rate. Once the bucket fills, no
     * message can be sent until a drop has leaked out.
     */
    private class LeakyBucketLimiter {

        private int numDropsInBucket = 0;
        private Date timeOfLastDropLeak = null;
        private final int _BUCKET_SIZE_IN_DROPS = 20;
        private final long _MS_BETWEEN_DROP_LEAKS = 1000 * 60 * 60; // 1 hour

        public synchronized boolean addDropToBucket() {
            Date now = new Date();
            // first of all, let the bucket leak by the appropriate amount
            if (timeOfLastDropLeak != null) {
                long deltaT = now.getTime() - timeOfLastDropLeak.getTime();
                // note round down as part of integer arithmetic
                long numberToLeak = deltaT / _MS_BETWEEN_DROP_LEAKS;
                if (numberToLeak > 0) { //now go and do the leak
                    if (numDropsInBucket <= numberToLeak) {
                        numDropsInBucket = 0;
                    } else {
                        numDropsInBucket -= (int) numberToLeak;
                    }
                    timeOfLastDropLeak = now;
                }
            }

            if (numDropsInBucket < _BUCKET_SIZE_IN_DROPS) {
                numDropsInBucket++;
                return true; // drop added
            }

            return false; // overflow
        }
    }


    // here is how you use it
    bucketLimiter = new LeakyBucketLimiter();
    if (bucketLimiter.addDropToBucket()) {
        // dispatch SMS
    }


 

The above might seem a little excessive, but long term reliability in our measurement and control devices is a really big thing for us. Ideally, each device needs to be able to take care of itself for many years at a time – in fact virtually all of the devices that we installed in our first year of operation 7 years ago are still running. Most have never once being touched by a human hand.