Алгоритм управления перегрузкой на основе обратной связи AIMD
Additive increase/multiplicative decrease
Алгоритм AIMD: управление перегрузкой в TCP/IP. Линейное увеличение окна при отсутствии потерь, экспоненциальное – при их возникновении. Стабильность сети!
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Алгоритм управления с обратной связью, используемый в управлении перегрузками
Алгоритм аддитивного увеличения/мультипликативного уменьшения (AIMD) — это алгоритм управления с обратной связью, наиболее известный своим применением в управлении перегрузками TCP. AIMD сочетает в себе линейное увеличение окна перегрузки при отсутствии перегрузок и экспоненциальное уменьшение при обнаружении перегрузок. Множественные потоки, использующие управление перегрузками AIMD, в конечном итоге приходят к равному использованию общего канала связи. Связанные схемы мультипликативного увеличения/мультипликативного уменьшения (MIMD) и аддитивного увеличения/аддитивного уменьшения (AIAD) не достигают стабильности.
Feedback control algorithm used in congestion control
The additive increase/multiplicative decrease (AIMD) algorithm is a feedback control algorithm best known for its use in TCP congestion control. AIMD combines linear growth of the congestion window when there is no congestion with an exponential reduction when congestion is detected. Multiple flows using AIMD congestion control will eventually converge to an equal usage of a shared link. The related schemes of multiplicative increase/multiplicative decrease (MIMD) and additive increase/additive decrease (AIAD) do not reach stability.
Алгоритм
Принимаемый подход заключается в увеличении скорости передачи (размер окна), поиске доступной полосы пропускания до возникновения потерь. Политика аддитивного увеличения может, например, увеличивать окно перегрузки на фиксированную величину с каждым временем кругового обхода. При обнаружении перегрузки передатчик уменьшает скорость передачи на мультипликативный коэффициент; например, уменьшает окно перегрузки вдвое после потери. В результате получается поведение, напоминающее пилу, отражающее процесс исследования полосы пропускания. AIMD требует бинарного сигнала о перегрузке. Чаще всего в качестве сигнала выступает потеря пакетов; мультипликативное уменьшение инициируется при истечении времени ожидания или когда сообщение подтверждения указывает на потерю пакета. Также сетевые коммутаторы и маршрутизаторы могут сигнализировать о перегрузке (без отбрасывания пакетов), как, например, в механизме явного уведомления о перегрузке (ECN).
The approach taken is to increase the transmission rate (window size), probing for usable bandwidth, until loss occurs. The policy of additive increase may, for instance, increase the congestion window by a fixed amount every round trip time. When congestion is detected, the transmitter decreases the transmission rate by a multiplicative factor; for example, cut the congestion window in half after loss. The result is a saw tooth behavior that represents the process of bandwidth probing. AIMD requires a binary congestion signal. Most frequently, packet loss serves as the signal; the multiplicative decrease is triggered when a timeout or an acknowledgement message indicates a packet lost. It is also possible for in network switches/routers to mark congestion (without discarding packets) as in Explicit Congestion Notification (ECN).
Математическая формула
Пусть `w` – размер окна перегрузки, указывающий объем данных в процессе передачи в течение временного слота `t`, `α` – параметр аддитивного увеличения, а `β` – коэффициент мультипликативного уменьшения. В TCP после медленного старта параметр аддитивного увеличения `α` обычно равен одному MSS (максимальному размеру сегмента) за время кругового обхода, а коэффициент мультипликативного уменьшения `β` обычно равен 1/2.
Let be the congestion window size indicating the amount of data in flight during time slot , be the additive increase parameter, and be the multiplicative decrease factor. In TCP, after slow start, the additive increase parameter is typically one MSS (maximum segment size) per round trip time, and the multiplicative decrease factor is typically 1/2.