Экспоненциальный откат

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

• 1 Алгоритм двоичной экспоненциальной отсрочки
• 2 Пример алгоритма экспоненциальной отсрочки
• 3 Ожидаемая отсрочка
• 4 См. Также
• 5 Ссылки

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

Примеры: повторная передача кадров в множественном доступе с контролем несущей с предотвращение коллизий (CSMA / CA) и множественный доступ с контролем несущей с обнаружением коллизий (CSMA / CD), в которых этот алгоритм является частью метода доступа к каналу, используемого для отправки данные в этих сетях. В сетях Ethernet алгоритм обычно используется для планирования повторных передач после конфликтов. Повторная передача задерживается на величину времени, полученную из времени слота (например, время, необходимое для отправки 512 битов; то есть 512 битов ) и количество попыток ретрансляции.

После c коллизий выбирается случайное количество слотов от 0 до 2 - 1. После первого конфликта каждый отправитель будет ждать 0 или 1 слот раз. После второй коллизии отправители будут ждать от 0 до 3 временных интервалов (включительно ). После третьего столкновения отправители будут ждать от 0 до 7 временных интервалов (включительно) и так далее. По мере увеличения количества попыток повторной передачи количество возможностей для задержки увеличивается экспоненциально.

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

Этот пример взят из Ethernet протокол, в котором хост-отправитель может знать, когда произошла коллизия (то есть другой хост пытался передать), когда он отправляет фрейм. Если оба хоста попытаются выполнить повторную передачу, как только произойдет конфликт, произойдет еще одно столкновение, и шаблон будет продолжаться вечно. Хосты должны выбрать случайное значение из допустимого диапазона, чтобы этого не произошло. Поэтому используется экспоненциальный алгоритм отсрочки. Значение «51,2 мкс» используется здесь в качестве примера, потому что это время слота для линии Ethernet 10 Мбит / с (см. Время слота ). Однако на практике 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-1.

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

$1\; N\; +\; 1\; \sum \; я\; =\; 0\; N\; я.\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{N\; +\; 1\}\}\; \backslash \; sum\; \_\; \{i\; =\; 0\}\; ^\; \{N\}\; i.\}$

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

$N\; =\; 2\; c\; -\; 1\; \{\backslash \; displaystyle\; N\; =\; 2\; ^\; \{c\}\; -1\}$

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

$N\; =\; 7,\; \{\backslash \; displaystyle\; N\; =\; 7,\}$

, а затем вычислить среднее возможное время отсрочки:

$E\; \; (c)\; Знак\; равно\; 1\; N\; +\; 1\; \sum \; я\; знак\; равно\; 0\; N\; я\; знак\; равно\; 1\; N\; +\; 1\; N\; (N\; +\; 1)\; 2\; =\; N\; 2\; =\; 2\; c\; -\; 1\; 2\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{E\}\; (c)\; =\; \{\backslash \; frac\; \{1\}\; \{N\; +\; 1\}\}\; \backslash \; sum\; \_\; \{i\; =\; 0\}\; ^\; \{N\}\; i\; =\; \{\backslash \; frac\; \{1\}\; \{N\; +\; 1\}\}\; \{\backslash \; frac\; \{N\; (N\; +\; 1)\}\; \{2\}\}\; =\; \{\backslash \; frac\; \{N\}\; \{2\}\}\; =\; \{\backslash \; frac\; \{2\; ^\; \{c\}\; -1\}\; \{2\}\}\}$.

что составляет, например, E (3) = 3,5 слота.

• Теория управления

• Эта статья включает материалы общественного достояния из документа General Services Administration : «Федеральный стандарт 1037C».