Экспоненциальная отсрочка

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

Алгоритм двоичного экспоненциального отката [ править ]

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

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

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

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

Пример алгоритма экспоненциальной отсрочки [ править ]

Этот пример взят из протокола Ethernet ^[3], где отправляющий хост может знать, когда произошла коллизия (то есть другой хост пытался передать), когда он отправляет фрейм. Если оба хоста попытаются повторно передать данные, как только произойдет конфликт, произойдет еще одно столкновение, и шаблон будет продолжаться вечно. Хосты должны выбрать случайное значение из допустимого диапазона, чтобы этого не произошло. Поэтому используется экспоненциальный алгоритм отсрочки. Значение «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 ^c  - 1.

Ожидаемая отсрочка [ править ]

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

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

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

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

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

${\ Displaystyle N = 7,}$

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

•  Эта статья включает  материалы, являющиеся общественным достоянием, из документа Управления общих служб : «Федеральный стандарт 1037C» .