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

Найдите значение слова backoff в Викисловаре, бесплатном словаре.

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

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

Алгоритм экспоненциального отката — это форма замкнутой системы управления , которая снижает скорость контролируемого процесса в ответ на неблагоприятные события. Например, если приложение для смартфона не может подключиться к своему серверу, оно может повторить попытку через 1 секунду, затем, если снова произойдет сбой, через 2 секунды, затем через 4 и т. д. Каждый раз пауза умножается на фиксированную величину (в данном случае на 2). В этом случае неблагоприятным событием является отсутствие подключения к серверу. Другие примеры неблагоприятных событий включают столкновения сетевого трафика , ответ об ошибке от службы или явный запрос на снижение скорости (т. е. откат ).

Снижение скорости можно смоделировать как экспоненциальную функцию :

t=b^{c}

или

f={\frac {1}{b^{c}}}

Здесь $t$ — это временная задержка, применяемая между действиями, $b$ — мультипликативный фактор или база , $c$ — количество наблюдаемых неблагоприятных событий, а $f$ — частота (или скорость) процесса (т. е. количество действий в единицу времени). Значение $c$ увеличивается каждый раз, когда наблюдается неблагоприятное событие, что приводит к экспоненциальному росту задержки и, следовательно, к обратно пропорциональной скорости. Алгоритм экспоненциальной отсрочки, где $b = 2,$ называется алгоритмом двоичной экспоненциальной отсрочки.

Когда скорость была снижена в ответ на неблагоприятное событие, она обычно не остается на этом сниженном уровне навсегда. Если в течение некоторого периода времени, часто называемого временем восстановления или периодом остывания , не наблюдается никаких неблагоприятных событий, скорость может быть снова увеличена. Период времени, который должен пройти до попытки снова увеличить скорость, может быть определен алгоритмом экспоненциального отката. Обычно восстановление скорости происходит медленнее, чем снижение скорости из-за отката, и часто требует тщательной настройки, чтобы избежать колебаний скорости. ^[1] Точное поведение восстановления зависит от реализации и может быть информировано любым количеством факторов окружающей среды.

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

Ограничение скорости

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

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

В простой версии алгоритма сообщения задерживаются на предопределенное (неслучайное) время. Например, в протоколе SIP по ненадежному транспорту (например, UDP ) клиент повторно передает запросы с интервалом, который начинается с T1 секунд (обычно,500 мс , что является оценкой времени приема-передачи ) и удваивается после каждой повторной передачи, пока не достигнет T2 секунд (что по умолчанию4 с ). Это приводит к интервалам повторной передачи500 мс ,1 с ,2 с ,4 с ,4 с ,4 с и т.д. ^[2]

Избежание столкновений

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

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

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

Пример

Этот пример взят из протокола Ethernet , ^[3] , где отправляющий хост может узнать, когда произошло столкновение (то есть, другой хост пытался передать), когда он отправляет кадр. Если оба хоста попытаются повторно передать, как только произойдет столкновение, произойдет еще одно столкновение — и эта схема будет продолжаться вечно. Хосты должны выбрать случайное значение в приемлемом диапазоне, чтобы гарантировать, что эта ситуация не произойдет. Поэтому используется алгоритм экспоненциальной задержки. Значение 51,2 мкс используется здесь в качестве примера, поскольку это время слота дляЛиния Ethernet 10 Мбит/с . Однако,На практике 51,2 мкс можно заменить любым положительным значением.

При первом столкновении отправьте сигнал глушения , чтобы предотвратить дальнейшую отправку данных.
Повторно отправьте кадр через 0 секунд или51,2 мкс , выбрано случайным образом.
Если это не помогло, отправьте кадр повторно после0 с ,51,2 мкс ,102,4 мкс , или153,6 мкс .
Если это не помогло, отправьте кадр повторно после $k$ ·51,2 мкс , где $k$ — случайное целое число от 0 до $23 - 1$ .
В случае дальнейших неудач, после c -й неудачной попытки, повторно отправьте кадр через $k$ ·51,2 мкс , где $k$ — случайное целое число от 0 до $2 c - 1$ .

История и теория

В основополагающей статье, опубликованной в AFIPS 1970, ^[4] Норман Абрамсон представил идею о нескольких «пользователях» на разных островах, совместно использующих один радиоканал (т. е. одну частоту) для доступа к главному компьютеру в Гавайском университете без какой-либо синхронизации по времени. Конфликты пакетов на приемнике главного компьютера обрабатываются отправителями после тайм-аута как обнаруженные ошибки. Каждый отправитель, не получивший положительного подтверждения от главного компьютера, повторно передавал свой «потерянный» пакет. Абрамсон предположил, что последовательность пакетов, передаваемых в общий канал, представляет собой пуассоновский процесс со скоростью $G$ , которая является суммой скорости $S$ поступления новых пакетов отправителям и скорости повторной передачи пакетов в канал. Предполагая устойчивое состояние, он показал, что пропускная способность канала имеет максимальное значение 1/(2 $e$ ) = 0,184 в теории. $S=Ge^{-2G}$

Ларри Робертс рассматривал канал ALOHA с временными интервалами, каждый из которых был достаточно длинным для времени передачи пакета. (Спутниковый канал, использующий протокол TDMA, имеет временные интервалы.) Используя тот же процесс Пуассона и предположения о стационарном состоянии, что и Абрамсон, Ларри Робертс показал, что максимальная пропускная способность в теории составляет 1/ $e$ = 0,368. ^[5] Робертс был программным менеджером исследовательского проекта ARPANET . Вдохновленный идеей слотированного ALOHA, Робертс инициировал новый проект спутниковой системы ARPANET (ASS) для включения спутниковых каналов в ARPANET.

Результаты моделирования Абрамсона, его коллег и других показали, что канал ALOHA, слотированный или нет, нестабилен и иногда может прийти в состояние коллапса перегрузки . Сколько времени до коллапса перегрузки зависело от скорости поступления новых пакетов, а также от других неизвестных факторов. В 1971 году Ларри Робертс попросил профессора Леонарда Клейнрока и его аспиранта Саймона Лэма из Калифорнийского университета в Лос-Анджелесе присоединиться к проекту спутниковой системы ARPANET . Саймон Лэм работал над стабильностью, оценкой производительности и адаптивным управлением слотированной ALOHA для своей докторской диссертации. Первой статьей, которую он написал в соавторстве с Клейнроком, была ARPANET Satellite System (ASS) Note 12, распространенная среди группы ASS в августе 1972 года. ^[6] В этой статье для повторной передачи использовался слот, выбранный случайным образом из интервала из $K$ слотов. Новый результат модели заключается в том, что увеличение $K$ увеличивает пропускную способность канала, которая сходится к 1/ $e$ по мере того, как $K$ увеличивается до бесконечности. Эта модель сохранила предположения о пуассоновском распределении и устойчивом состоянии и не была предназначена для понимания статистического поведения и коллапса перегрузки.

Стабильность и адаптивный откат

Чтобы понять устойчивость, Лэм создал модель цепи Маркова с дискретным временем для анализа статистического поведения слотированного ALOHA в главе 5 своей диссертации. ^[7] Модель имеет три параметра: N , s и p . N — общее количество пользователей. В любой момент времени каждый пользователь может быть бездействующим или заблокированным. У каждого пользователя есть не более одного пакета для передачи в следующем временном интервале. Бездействующий пользователь генерирует новый пакет с вероятностью s и немедленно передает его в следующем временном интервале. Заблокированный пользователь передает свой отложенный пакет с вероятностью p , где 1/ p = ( K +1)/2, чтобы сохранить средний интервал повторной передачи тем же. Результаты пропускной способности-задержки двух методов повторной передачи были сравнены с помощью обширного моделирования и оказались по существу одинаковыми. ^[8]

Модель Лэма дает математически строгие ответы на вопросы стабильности слотового ALOHA, а также эффективный алгоритм для вычисления производительности пропускной способности-задержки для любой стабильной системы. Ниже приведены 3 ключевых результата из модели цепи Маркова Лэма в Главе 5 его диссертации (также опубликованной совместно с профессором Леном Клейнроком в IEEE Transactions on Communications. ^[9] )

Слотовый алгоритм ALOHA с пуассоновскими поступлениями (т. е. бесконечным N ) по своей сути нестабилен, поскольку стационарного распределения вероятностей не существует. (Достижение устойчивого состояния было ключевым предположением, используемым в моделях Абрамсона и Робертса.)
Для слотированной ALOHA с конечным N и конечным K модель цепи Маркова может использоваться для определения того, является ли система стабильной или нестабильной для заданной скорости ввода ( N × s ), и, если она стабильна, вычислить ее среднюю задержку пакетов и пропускную способность канала.
Увеличение K увеличивает максимальное количество пользователей, которых может обслуживать стабильный слотированный канал ALOHA. ^[10]

Следствие

Для конечного ( N × s ) нестабильный канал для текущего значения K можно сделать стабильным, увеличив K до достаточно большого значения, которое будет называться его K ( N , s ). ^[11]

Эвристический RCP для адаптивного отката

Лэм использовал теорию принятия решений Маркова и разработал оптимальные политики управления для слотированной ALOHA, но эти политики требуют, чтобы все заблокированные пользователи знали текущее состояние (количество заблокированных пользователей) цепи Маркова. В 1973 году Лэм решил, что вместо использования сложного протокола для пользователей для оценки состояния системы, он создаст простой алгоритм для каждого пользователя, чтобы использовать его собственную локальную информацию, т. е. количество коллизий, с которыми столкнулся его отставший пакет. ^[13] Применяя приведенное выше следствие, Лэм изобрел следующий класс адаптивных алгоритмов отсрочки (названный эвристическим RCP).

Эвристический алгоритм RCP состоит из следующих шагов: (1) Пусть m обозначает количество предыдущих столкновений, возникших у пакета у пользователя, в качестве информации обратной связи в его контуре управления. Для нового пакета K (0) инициализируется значением 1. (2) Интервал повторной передачи пакета K ( m ) увеличивается с увеличением m (пока канал не станет стабильным, как следует из приведенного выше следствия). Для реализации с K (0)=1, по мере увеличения m, K ( m ) может быть увеличен путем умножения (или сложения).

Наблюдение

Двоичная экспоненциальная задержка (BEB), использованная в Ethernet несколько лет спустя, является частным случаем эвристического RCP с . $K(м)=2^{м}$

BEB очень прост в реализации. Однако он не оптимален для многих приложений, поскольку BEB использует 2 в качестве единственного множителя, что не обеспечивает гибкости для оптимизации. В частности, для системы с большим количеством пользователей BEB увеличивает K ( m ) слишком медленно. С другой стороны, для системы с небольшим количеством пользователей достаточно небольшого K , чтобы система была стабильной, и откат не понадобится.

Чтобы проиллюстрировать пример мультипликативного RCP, который использует несколько множителей, см. нижнюю строку в Таблице 6.3 на стр. 214 в Главе 6 диссертации Лэма или нижнюю строку в Таблице III на стр. 902 в статье Лэма-Клейнрока. В этом примере:

Новый пакет передается немедленно, m = 0, K (0) = 1
Для пакета с 1 предыдущей коллизией K (1) = K (0) × 10 = 10 (множитель резко возрастает до K ^* = 10, что оказалось оптимальным значением K в устойчивом состоянии для данной конкретной системы (слотовый ALOHA для спутникового канала).
Для пакета с 2 предыдущими столкновениями K (2) = K (1) × 10 = 100 (еще одно столкновение, K увеличивается в 10 раз).
К (3) = К (2) × 2 = 200
K ( m )= K ( m −1) для m ≥4

Для этого примера K = 200 достаточно для стабильной щелевой системы ALOHA с N , равным примерно 400, что следует из результата 3 выше Следствия. Нет необходимости увеличивать K дальше.

Усеченный экспоненциальный откат

«Усеченный» вариант алгоритма вводит ограничение на $c$ . Это просто означает, что после определенного количества увеличений возведение в степень останавливается. Без ограничения на $c$ задержка между передачами может стать нежелательно большой, если отправитель неоднократно наблюдает неблагоприятные события, например, из-за ухудшения сетевого обслуживания. В рандомизированной системе это может произойти случайно, что приведет к непредсказуемой задержке; более длительные задержки из-за неограниченного увеличения $c$ экспоненциально менее вероятны, но они фактически неизбежны в загруженной сети из-за закона действительно больших чисел . Ограничение $c$ помогает уменьшить вероятность неожиданно больших задержек передачи и улучшить время восстановления после кратковременного сбоя.

Например, если потолок установлен на $i = 10$ в усеченном двоичном экспоненциальном алгоритме задержки (как в стандарте IEEE 802.3 CSMA/CD ^[14] ), то максимальная задержка составит 1023 временных интервала, т.е. $210 - 1$ .

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

Ожидаемый откат

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

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

Например, для ожидаемого времени отсрочки для третьего ( $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={\frac {1}{N+1}}{\frac {N(N+1)}{2}}={\frac {N}{2}}={\frac {2^{c}-1}{2}}

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

Смотрите также

Ссылки

^ Таненбаум и Ветералл, 2010, стр. 395
^ Розенберг и др. RFC3261 – SIP: протокол инициирования сеанса. Internet Society. 2002.
^ Петерсон, Ларри Л.; Дэви, Брюс С. (2022). «Глава 2: Прямые ссылки». Компьютерные сети: системный подход (шестое изд.). Morgan Kaufmann Publishers. стр. 120. ISBN 978-0-12-818200-0.
^ Абрамсон, Норман (1970). Система ALOHA — еще одна альтернатива компьютерным коммуникациям (PDF) . Труды Объединенной компьютерной конференции осени 1970 г. AFIPS Press.
^ Робертс, Лоуренс Г. (апрель 1975 г.). «Система пакетов ALOHA с и без слотов и захвата». Computer Communications Review . 5 (2): 28–42. doi :10.1145/1024916.1024920.
^ Клейнрок, Леонард; Саймон С. Лэм (август 1972 г.). Аналитические результаты для модели спутниковой системы ARPANET, включая эффекты распределения задержки повторной передачи (PDF) (технический отчет). Информационный центр сети ARPA, Стэнфордский исследовательский институт , Менло-Парк, Калифорния. Примечание ASS 12 (NIC 11294).
^ Лэм, Саймон С. (март 1974 г.). Коммутация пакетов в широковещательном канале с множественным доступом и применение к спутниковой связи в компьютерной сети, докторская диссертация, 306 страниц (диссертация). UCLA-ENG-7429 (ARPA), Школа инженерии и прикладных наук Калифорнийского университета в Лос-Анджелесе.
↑ Рис. 5-1 на стр. 100, Глава 5, в диссертации Лэма.
^ Клейнрок, Леонард; Лам С., Саймон (апрель 1975 г.). «Коммутация пакетов в широковещательном канале с множественным доступом: оценка производительности» (PDF) . IEEE Transactions on Communications . COM-23 (4): 410–423. doi :10.1109/TCOM.1975.1092814 . Получено 16 февраля 2023 г. .
↑ Рис. 5-9 на стр. 114 в главе 5 диссертации Лэма или рис. 10 на стр. 418 в статье Клейнрока-Лэма 1975 года.
↑ Рис. 5-10 на стр. 116 в главе 5 диссертации Лэма или рис. 11 на стр. 418 в статье Клейнрока-Лэма 1975 года.
^ Лэм, Саймон С.; Клейнрок, Леонард (сентябрь 1975 г.). «Коммутация пакетов в широковещательном канале с множественным доступом: процедуры динамического управления» (PDF) . IEEE Transactions on Communications . COM-23 (9): 891–904. doi :10.1109/TCOM.1975.1092917 . Получено 16 июля 2023 г. .
^ См. Алгоритм 4 на страницах 901–902 в статье Лэма-Клейнрока ^[12] или подраздел 6.7.2 на страницах 209–210 в главе 6 диссертации Лэма.
^ "Стандарт IEEE 802.3-2015". IEEE . Получено 20 марта 2022 г. .(покупка)
^ Таненбаум и Везералл 2010, стр. 285

Библиография

Таненбаум, Эндрю; Везеролл, Дэвид (2010). Компьютерные сети (5-е изд.). Пирсон. ISBN 978-0132126953.

В этой статье использованы материалы из Федерального стандарта 1037C. Администрация общих служб . Архивировано из оригинала 22 января 2022 г.