Exponential backoff

Posted on Posted in Uncategorized

In a variety of computer networks, binary exponential backoff or truncated binary exponential backoff refers to an algorithm used to space out repeated retransmissions of the same block of data, often as part of network congestion avoidance.

Wikipedia Exponential backoff

Here is an implementation in Java

    /**
     * Calculate Exponential backoff
     * 
     * @param attempt
     *            number that we are checking
     * @param maxDelayInSeconds
     *            Max amount of time to wait
     * @param multiplier
     *            How much of backoff to perform
     * @return
     */
    public static long backoff(final int attempt, final long maxDelayInSeconds, final double multiplier)
    {
        final double delayInSec = (Math.pow(2.0, attempt) - 1.0) * .5;
        return Math.round(Math.min(delayInSec * multiplier, maxDelayInSeconds));
    }

Example

Here we have exponential backoff defined with three different parameters for the muliplier and 120 seconds as the max time.

 
System.out.println(String.format("Attempt\t\t 1\t4\t8\n"));
 
for (int i = 0; i < 10; i++)
{
    final long b1 = backoff(i, 120, 1);
    final long b2 = backoff(i, 120, 4);
    final long b3 = backoff(i, 120, 8);
 
    System.out.println(String.format("%d\t\t %d\t%d\t%d", i, b1, b2, b3));    
}

		 1	4	8

0		 0	0	0
1		 1	2	4
2		 2	6	12
3		 4	14	28
4		 8	30	60
5		 16	62	120
6		 32	120	120
7		 64	120	120
8		 120	120	120
9		 120	120	120

From the results above we can see that changing the multiplier can have significant implications. The larger the multiplier the faster we will be approaching our maxDelay and we will have longer paused between each attempt.

In next post, we will create a Data Retrieval Service that will utilize Exponential backoff.

Leave a Reply

Your email address will not be published. Required fields are marked *