Экспоненциальная выдержка

Экспоненциальная выдержка — это алгоритм, использующий обратную связь для мультипликативного уменьшения частоты некоторого процесса, чтобы постепенно найти приемлемую частоту.

Двоичная экспоненциальная выдержка / усечённая экспоненциальная выдержка

Во множестве компьютерных сетей понятие двоичная экспоненциальная выдержка или усечённая двоичная экспоненциальная выдержка относится к алгоритму прореживания повторяющихся отсылок одного и того же блока данных, часто как часть мер для избежания перегрузки сети.

Примеры — это повторная отправка кадров данных в сетях carrier sense multiple access with collision avoidance (CSMA/CA) и carrier sense multiple access with collision detection (CSMA/CD), где этот алгоритм является частью метода доступа к каналу, используемому для отсылки данных по этим сетям. В сетях Ethernet этот алгоритм обычно используется для планирования повторных отправок после коллизий. Повторная отправка задерживается на количество времени, зависящее от slot time и количества попыток отправки.

После c коллизий выбирается случайное количество slot time между 0 и 2^c−1. После первой коллизии каждый отправитель будет ждать 0 или 1 slot time. После второй коллизии отправители будут ждать где-то от 0 до 3 slot times включительно. После третьей коллизии отправители будут ждать где-то от 0 до 7 slot times включительно, и т. д. По мере увеличения количества попыток повторной отправки количество вариантов задержки растёт экспоненциально.

Слово «усечённый» означает , что после некоторого количества приращений экспоненциальный рост останавливается, то есть тайм-аут повторной передачи достигает потолка, и после этого больше не растёт. Например, если потолок задан как i = 10 (как в стандарте IEEE 802.3 CSMA/CD), то максимальная задержка равна 1023 slot times.

Поскольку эти задержки вызывают коллизии у других станций, посылающих данные, существует вероятность, что в занятой сети сотни людей могут быть пойманы в единый набор коллизий. Из-за существования такой возможности процесс обрывается после 16 попыток передачи.

Пример алгоритма экспоненциальной выдержки

Этот пример взят из описания протокола Ethernet, где отправитель имеет возможность узнать во время отправки кадра, что произошла коллизия (то есть другой хост пытался отправить данные). Если бы оба хоста пытались повторно отправить данные, как только произошла коллизия, произошла бы следующая коллизия, и эта последовательность продолжалась бы вечно. Хосты обязаны выбрать случайное значение внутри приемлемого интервала для гарантии, что эта ситуация не случится, поэтому используется алгоритм экспоненциальной выдержки. Здесь в качестве примера используется число 51,2 мкс, но это slot time для линии 10 Mbit/s Ethernet (см. Slot time). Но на практике 51,2 мкс может быть заменено на любое другое положительное значение.

1. Когда происходит первая коллизия, послать «Сигнал затора», чтобы предотвратить отсылку дальнейших данных.
2. Повторно послать кадр после выдержки в 0 или 51,2 мкс, выбранной случайно.
3. Если отправка не удастся, повторно отправить кадр после выдержки 0, 51,2 мкс, 102,4 мкс или 153,6 мкс.
4. Если и в этом случае неудача, переотправить кадр после выдержки k · 51,2 мкс, где k - это случайное целое число в интервале от 0 до 2³−1.
5. В общем случае, после c-й неудачной отправки, повторно отправить кадр после выдержки k · 51,2 мкс, где k - это случайное целое между 0 и 2^c−1.

Ожидаемая выдержка

Если задано равномерное распределение времён выдержки, математическое ожидание времени выдержки является средним значением из всех возможных. То есть, после c коллизий, количество слотов выдержки находится в интервале [0, 1, …, N] где N = 2^c−1, и ожидаемое время выдержки (в слотах) равно

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

Например, ожидаемая выдержка для третьей (c = 3) коллизии можно сначала вычислить максимальное время выдержки N:

$N=2^{c}-1$

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

$N=7$

… а затем рассчитать среднее значение среди всех вариантов выдержки:

$\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}}$

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

… получив 3.5 в качестве ожидаемого количества слотов выдержки после трёх коллизий.

Приведённое выше получение в значительной степени не нужно, когда Вы понимаете, что среднее значение следующих друг за другом целых чисел равно среднему из наименьшего и наибольшего чисел в наборе. Это значит, что среднее для набора A последовательных целых a₀, a₁, a₂, … a_m это просто среднее для a₀ и a_m или (a₀ + a_m)/2.

В приложении к выше приведённой проблеме поиска ожидаемого времени выдержки формула упрощается:

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

… или, в частном случае, интерпретируется как половина максимально возможного времени задержки.

Также заметьте, что итоговая сумма это Треугольное число, такое как например равно…

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

…которое сокращается со знаменателем за пределами суммы, и остаётся только…

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