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

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

Экспоненциальный алгоритм отсрочки

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

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

$t=b^{c}$

или

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

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

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

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

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

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

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

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

Предотвращение столкновений

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

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

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

Пример

Этот пример взят из протокола 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 .

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

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

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

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

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

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

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

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

Следствие

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

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

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

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

Наблюдение

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

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

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

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

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

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

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

Например, если потолок установлен на уровне i = 10 в алгоритме усеченной двоичной экспоненциальной отсрочки (как в стандарте IEEE 802.3 CSMA/CD) . ), то максимальная задержка составляет 1023 слот-времени, т.е. 2 ¹⁰ − 1 .

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

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

Учитывая равномерное распределение времени отсрочки, ожидаемое время отсрочки является средним из возможных. После c коллизий в алгоритме двоичной экспоненциальной отсрочки задержка выбирается случайным образом из [0, 1,..., N ] слотов, где N = 2 ^с − 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). Компьютерные сети (5-е изд.). Пирсон. ISBN  978-0132126953 .

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