Аддитивное увеличение/мультипликативное уменьшение

Алгоритм аддитивного увеличения/мультипликативного уменьшения ( AIMD ) — это алгоритм управления с обратной связью, наиболее известный благодаря использованию в управлении перегрузкой TCP . AIMD сочетает в себе линейный рост окна перегрузки при ее отсутствии с экспоненциальным уменьшением при обнаружении перегрузки. Множественные потоки, использующие контроль перегрузки AIMD, в конечном итоге сойдутся в равном использовании общего канала. ^{[ 1 ]} Родственные схемы мультипликативного увеличения/мультипликативного уменьшения (MIMD) и аддитивного увеличения/аддитивного уменьшения (AIAD) не достигают устойчивости .

Алгоритм

Принятый подход заключается в увеличении скорости передачи (размера окна), проверяя доступную полосу пропускания до тех пор, пока не произойдет потеря. Политика аддитивного увеличения может, например, увеличивать окно перегрузки на фиксированную величину каждый раз за время прохождения туда и обратно . При обнаружении перегрузки передатчик уменьшает скорость передачи на мультипликативный коэффициент; например, сократить окно перегрузки вдвое после потери. Результатом является пилообразное поведение, которое представляет собой процесс зондирования полосы пропускания.

AIMD требует двоичного сигнала перегрузки. Чаще всего сигналом служит потеря пакетов; мультипликативное уменьшение запускается, когда тайм-аут или сообщение подтверждения указывает на потерю пакета. Внутрисетевые коммутаторы/маршрутизаторы также могут отмечать перегрузку (без отбрасывания пакетов), как в явном уведомлении о перегрузке (ECN).

Математическая формула

Позволять $w(t)$ быть размером окна перегрузки, указывающим объем данных в передаче в течение временного интервала $t$ , $a$ ( $a>0$ ) — параметр аддитивного увеличения, а $b$ ( $0<b<1$ ) – коэффициент мультипликативного уменьшения.

$w(t+1)={\begin{cases}w(t)+a&{\text{ if congestion is not detected}}\\w(t)\times b&{\text{ if congestion is detected}}\end{cases}}$

В TCP после медленного старта параметр аддитивного увеличения $a$ обычно составляет один MSS ( максимальный размер сегмента ) за время прохождения туда и обратно , а коэффициент мультипликативного уменьшения $b$ обычно составляет 1/2.

Протоколы

Предотвращение перегрузки AIMD используется или использовалось в:

На природе

Было обнаружено, что AIMD используется различными биологическими системами , в том числе для регулирования добывания пищи колониями муравьев-жнецов , поддержания гомеостаза размера клеток , а также для синаптического обучения и адаптации в нейронных цепях . ^{[ 3 ]}

Ссылки

^ Перейти обратно: ^а ^б ^с Чиу, Да-Минг; Радж Джайн (1989). «Анализ алгоритмов увеличения и уменьшения перегрузок в компьютерных сетях». Компьютерные сети и системы ISDN . 17 : 1–14. дои : 10.1016/0169-7552(89)90019-6 .
^ Флойд; Колер (март 2006 г.). Профиль для протокола управления перегрузкой дейтаграмм (DCCP). Идентификатор контроля перегрузки 2: TCP-подобный контроль перегрузки . дои : 10.17487/RFC4341 . RFC 4341 .
^ Суен, Джонатан Ю.; Навлаха, Сакет (2022). «Принцип управления с обратной связью, общий для нескольких биологических и инженерных систем» . Журнал интерфейса Королевского общества . 19 (188): 20210711. doi : 10.1098/rsif.2021.0711 . ПМЦ 8889180 . ПМИД 35232277 .

[chui1989-1] Перейти обратно: ^а ^б ^с Чиу, Да-Минг; Радж Джайн (1989). «Анализ алгоритмов увеличения и уменьшения перегрузок в компьютерных сетях». Компьютерные сети и системы ISDN . 17 : 1–14. дои : 10.1016/0169-7552(89)90019-6 .

[2] Флойд; Колер (март 2006 г.). Профиль для протокола управления перегрузкой дейтаграмм (DCCP). Идентификатор контроля перегрузки 2: TCP-подобный контроль перегрузки . дои : 10.17487/RFC4341 . RFC 4341 .

[3] Суен, Джонатан Ю.; Навлаха, Сакет (2022). «Принцип управления с обратной связью, общий для нескольких биологических и инженерных систем» . Журнал интерфейса Королевского общества . 19 (188): 20210711. doi : 10.1098/rsif.2021.0711 . ПМЦ 8889180 . ПМИД 35232277 .

[ 1 ]

[ 2 ]

[ 3 ]