Feature #11: Weighted Exponential Back-off

Description

In our network topology, we have a shared communication channel. On this channel, all the connected devices can simultaneously transmit data, resulting in a collision. The transmission is time-slotted. After a collision, the transmitting devices back off, that is, they refrain from retransmitting for a random number of time slots.

To this end, the device draws a random integer, r, between 1 and 9 and waits for as many time slots. In case of another collision on the first retry, the device draws a random integer again, r, between 1 and 9, and waits for $10*r$ time slots. In case of $[i]$ successive retransmission failures, the device backs off for $10^i*r$ time slots, where r is a random integer between 1 and 9.

Note: This is known as the weighted exponential back-off.

We can further represent the selected random integers as a linked list, where each node consists of a digit ranging between 1 and 9. This way, the head of the linked list will point to the least significant digit unit place, the second node will point to the digit at the tenth place, and so on. Given two such linked lists, we want to determine the total number of time slots for which the device backed off.

Let’s review a few examples below: