Overview

backoffAlgorithm LibraryAlgorithm

A library that calculates the back-off period for a retry attempt using exponential back-off with jitter algorithm. This library uses the "Full Jitter" strategy for the exponential back-off with jitter algorithm.

More information about the algorithm can be seen in the Exponential Backoff and Jitter AWS blog.

Exponential backoff with jitter is typically used when retrying a failed network connection or operation request with the server. An exponential backoff with jitter helps to mitigate failed network operations with servers, that are caused due to network congestion or high request load on the server, by spreading out retry requests across multiple devices attempting network operations. Besides, in an environment with poor connectivity, a client can get disconnected at any time. A backoff strategy helps the client to conserve battery by not repeatedly attempting reconnections when they are unlikely to succeed.

Before retrying the failed communication to the server, there is a delay period. In this delay period, the task that is retrying must sleep for some random amount of milliseconds between 0 and the lesser of the backoff window (related to the retry attempt) and a predefined maximum delay value. The backoff window is doubled with each retry attempt until the maximum delay value is reached.

‍sleep_ms = random_between( 0, min( 2^{attempts_count} * base_ms, maximum_ms ) )

The library is written in C and designed to be compliant with ISO C90 and MISRA C:2012.

For a reference example of using the library, refer to the related README section in the repository here.

Memory Requirements

Memory requirements of the backoffAlgorithm library.

Code Size of backoffAlgorithm (example generated with GCC for ARM Cortex-M)
File	With -O1 Optimization	With -Os Optimization
backoff_algorithm.c	0.1K	0.1K
Total estimates	0.1K	0.1K

Design

backoffAlgorithm Library Design

Memory Usage

All functions in the backoffAlgorithm library operate only on the buffer provided and use only local variables on the stack.

Random Number Generation

The library takes a random number each time it calculates the backoff period value for the retry attempt. To avoid calculation of the same random numbers across your fleet of devices attempting retry of network operations, it is RECOMMENDED to generate the random number with a random number generator that is seeded with an entropy source unique to the device.

Compliance & Coverage

The backoffAlgorithm library is designed to be compliant with ISO C90 and MISRA C:2012. All functions are written to have minimal complexity. Unit tests are written to cover every path of execution and achieve 100% branch coverage.