Exponential exposure

Exponential exposure is an algorithm that uses feedback to multiplicatively reduce the frequency of a process in order to gradually find an acceptable frequency.

Content

Binary Exponential Exposure / Truncated Exponential Exposure

In many computer networks, the concept of binary exponential exposure or truncated binary exponential exposure refers to a decimation algorithm for repeated sending of the same data block, often as part of measures to avoid network congestion.

Examples are the retransmission of data 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 channel access method used to send data over to these networks. In Ethernet networks , this algorithm is commonly used to schedule retransmissions after collisions. Re-sending is delayed by the amount of time that depends on slot time and the number of attempts to send.

After c collisions, a random number of slot times between 0 and 2 ^c −1 is selected. After the first collision, each sender will wait for 0 or 1 slot times. After the second collision, senders will wait somewhere from 0 to 3 slot times inclusive. After the third collision, senders will wait anywhere from 0 to 7 slot times inclusive, and so on. As the number of retry attempts increases, the number of delay options increases exponentially.

The word “truncated” simply means that after a certain number of increments the exponential growth stops, that is, the retransmission timeout reaches the ceiling, and after that it does not grow anymore. For example, if the ceiling is set as i = 10 (as in the IEEE 802.3 CSMA / CD standard ^[1] ), then the maximum delay is 1023 slot times.

Since these delays cause collisions at other stations sending data, there is a possibility that hundreds of people can be caught in a single set of collisions in a busy network. Due to this possibility, the process ends after 16 transmission attempts.

Exponential Exposure Algorithm Example

This example is taken from the description of the Ethernet protocol ^[2] , where the sender has the opportunity to find out at the time of sending the frame that a collision occurred (that is, another host tried to send data). If both hosts tried to resend the data as soon as the collision occurred, the next collision would occur, and this sequence would go on forever. Hosts are required to select a random value within an acceptable interval to ensure that this situation does not happen, therefore, an exponential exposure algorithm is used. Here, the number 51.2 μs is used as an example, but this is slot time for the 10 Mbit / s Ethernet line (see Slot time ). But in practice, 51.2 μs can be replaced with any other positive value.

When the first collision occurs, send a “Congestion Signal” to prevent further data from being sent.
Resend the frame after a shutter speed of 0 or 51.2 μs, selected randomly.
If the sending fails, resend the frame after a shutter speed of 0, 51.2 μs, 102.4 μs or 153.6 μs.
If in this case as well, resend the frame after exposure k · 51.2 μs, where k is a random integer in the range from 0 to 2 ³ −1.
In the general case, after the c- th unsuccessful sending, resend the frame after exposure k · 51.2 μs, where k is a random integer between 0 and 2 ^s −1.

Expected Exposure

If a uniform distribution of exposure times is specified, the mathematical expectation of exposure time is the average of all possible values. That is, after c collisions, the number of exposure slots is in the interval [0, 1, ..., N ] where N = 2 ^s −1, and the expected exposure time (in slots) is

{\frac {1}{N+1}}\sum _{i=0}^{N}i

{\ displaystyle {\ frac {1} {N + 1}} \ sum _ {i = 0} ^ {N} i}

.

For example, the expected exposure for the third ( c = 3) collision, you can first calculate the maximum exposure time N :

N=2^{c}-1

{\ displaystyle N = 2 ^ {c} -1}

N=2^{3}-1=8-1

{\ displaystyle N = 2 ^ {3} -1 = 8-1}

N=7

{\ displaystyle N = 7}

... and then calculate the average of all exposure options:

\operatorname {E} (c)={\frac {1}{N+1}}\sum _{i=0}^{N}i

{\ displaystyle \ operatorname {E} (c) = {\ frac {1} {N + 1}} \ sum _ {i = 0} ^ {N} i}

\operatorname {E} (3)={\frac {1}{7+1}}\sum _{i=0}^{7}i={\frac {1}{8}}(0+1+2+3+4+5+6+7)={\frac {28}{8}}

{\ displaystyle \ operatorname {E} (3) = {\ frac {1} {7 + 1}} \ sum _ {i = 0} ^ {7} i = {\ frac {1} {8}} (0 + 1 + 2 + 3 + 4 + 5 + 6 + 7) = {\ frac {28} {8}}}

\operatorname {E} (3)=3.5

{\ displaystyle \ operatorname {E} (3) = 3.5}

... having received 3.5 as the expected number of exposure slots after three collisions.

The above receipt is largely unnecessary when you realize that the average value of successive integers is equal to the average of the smallest and largest numbers in the set. This means that the average for a set A of consecutive integers a ₀ , a ₁ , a ₂ , ... a _m is simply the average for a ₀ and a _m or ( a ₀ + a _m ) / 2.

In the appendix to the above problem of finding the expected exposure time, the formula is simplified:

\operatorname {E} (c)={\frac {2^{c}-1}{2}}

{\ displaystyle \ operatorname {E} (c) = {\ frac {2 ^ {c} -1} {2}}}

... or, in a particular case, is interpreted as half the maximum possible delay time.

Also note that the total is a Triangular number , such as, for example, equal to ...

{\frac {(2^{c}-1)2^{c}}{2}}={\frac {N(N+1)}{2}}

{\ displaystyle {\ frac {(2 ^ {c} -1) 2 ^ {c}} {2}} = {\ frac {N (N + 1)} {2}}}

... which shrinks with the denominator outside of the amount, and remains only ...

{\frac {N}{2}}={\frac {2^{c}-1}{2}}

{\ displaystyle {\ frac {N} {2}} = {\ frac {2 ^ {c} -1} {2}}}

Links

↑ IEEE Standard 802.3-2008 (neopr.) . IEEE Date of treatment September 22, 2010.
↑ Computer Networks , Peterson and Davie

[IEEE_802_3-1] IEEE Standard 802.3-2008 (neopr.) . IEEE Date of treatment September 22, 2010.

[2] Computer Networks , Peterson and Davie