Editing Exponential backoff (section)

==Collision avoidance==
Exponential backoff algorithms can be used to avoid network collisions. In a [[point-to-multipoint]] or [[multiplexed]] network, multiple senders communicate over a single shared channel. If two senders attempt to transmit a message at the same time, or ''talk over'' each other, a collision occurs and the messages are damaged or lost. Each sender can then back off before attempting to [[retransmission (data networks)|retransmit]] the same message again.

A [[Deterministic algorithm|deterministic]] exponential backoff algorithm is unsuitable for this use case since each sender would back off for the same time period, leading them to retransmit simultaneously and cause another collision. Instead, for purposes of collision avoidance, the time between retransmissions is [[Randomized algorithm|randomized]] and the exponential backoff algorithm sets the ''range'' of delay values that are possible. The time delay is usually measured in [[time-division multiplexing|slots]], which are fixed-length periods (or ''slices'') of time on the network. In a binary exponential backoff algorithm (i.e. one where {{math|1= ''b'' = 2}}), after {{mvar|c}} collisions, each retransmission is delayed by a random number of slot times between {{math|0}} and {{math|2<sup>''c''</sup> &minus; 1}}. After the first collision, each sender will wait 0 or 1 slot times. After the second collision, the senders will wait anywhere from 0 to 3 slot times ([[Interval (mathematics)|inclusive]]).  After the third collision, the senders will wait anywhere from 0 to 7 slot times (inclusive), and so forth. As the number of retransmission attempts increases, the number of possibilities for delay [[increases exponentially]]. This decreases the probability of a collision but increases the average latency.

Exponential backoff is utilised during retransmission of [[data frame|frames]] in [[carrier-sense multiple access with collision avoidance]] (CSMA/CA) and [[carrier-sense multiple access with collision detection]] (CSMA/CD) networks, where this algorithm is part of the [[Media access control|channel access]] method used to send data on these networks. In [[Ethernet]] networks, the algorithm is commonly used to schedule retransmissions after collisions. The retransmission is delayed by an amount of [[time]] derived from the [[slot time]] (for example, the time it takes to send 512 bits; i.e., 512 [[Bit time|bit-times]]) and the number of attempts to retransmit.

===Example===
This example is from the [[Ethernet]] protocol,<ref>{{cite book| title=Computer Networks: A Systems Approach |url=https://book.systemsapproach.org/ |last1=Peterson |first1=Larry L. |last2=Davie |first2=Bruce S. |chapter=Chapter 2: Direct Links | chapter-url=https://book.systemsapproach.org/direct/ethernet.html#transmitter-algorithm |page=120 |publisher=Morgan Kaufmann Publishers |edition=Sixth |year=2022 |isbn=978-0-12-818200-0 }}</ref> where a sending host is able to know when a collision has occurred (that is, another host has tried to transmit), when it is sending a frame. If both hosts attempted to re-transmit as soon as a collision occurred, there would be yet another collision &mdash; and the pattern would continue forever. The hosts must choose a random value within an acceptable range to ensure that this situation doesn't happen. An exponential backoff algorithm is therefore used. The value 51.2 μs is used as an example here because it is the [[slot time]] for a {{val|10 |u=Mbit|up=s}} Ethernet line. However, {{val|51.2 |u=μs}} could be replaced by any positive value, in practice.

# When a collision first occurs, send a ''jamming signal'' to prevent further data from being sent.
# Resend a frame after either 0 seconds or {{val|51.2 |u=μs}}, chosen at random.
# If that fails, resend the frame after either {{val|0 |u=s}}, {{val|51.2 |u=μs}}, {{val|102.4 |u=μs}}, or {{val|153.6 |u=μs}}.
# If that still fails, resend the frame after {{mvar|k}} · {{val|51.2 |u=μs}}, where {{mvar|k}} is a random integer between 0 and {{math|2<sup>3</sup> &minus; 1}}.
# For further failures, after the ''c''th failed attempt, resend the frame after {{mvar|k}} · {{val|51.2 |u=μs}}, where {{mvar|k}} is a random integer between 0 and {{math|2<sup>''c''</sup> &minus; 1}}.