El algoritmo de aumento aditivo / disminución multiplicativa ( AIMD ) es un algoritmo de control de retroalimentación mejor conocido por su uso en el control de la congestión de TCP . AIMD combina el crecimiento lineal de la ventana de congestión cuando no hay congestión con una reducción exponencial cuando se detecta la congestión. Múltiples flujos que utilizan el control de congestión AIMD eventualmente convergerán en un uso equitativo de un enlace compartido. [1] Los esquemas relacionados de aumento-multiplicativo / disminución-multiplicativo (MIMD) y aumento-aditivo / disminución-aditivo (AIAD) no alcanzan la estabilidad .
Algoritmo
El enfoque adoptado es aumentar la velocidad de transmisión (tamaño de la ventana), buscando el ancho de banda utilizable, hasta que se produzca una pérdida. La política de aumento aditivo puede, por ejemplo, aumentar la ventana de congestión en una cantidad fija cada tiempo de ida y vuelta . Cuando se detecta congestión, el transmisor reduce la velocidad de transmisión en un factor multiplicativo; por ejemplo, corte la ventana de congestión a la mitad después de una pérdida. El resultado es un comportamiento de diente de sierra que representa el proceso de sondeo de ancho de banda.
AIMD requiere una señal de congestión binaria. Con mayor frecuencia, la pérdida de paquetes sirve como señal; la disminución multiplicativa se activa cuando un tiempo de espera o un mensaje de reconocimiento indican que se perdió un paquete. También es posible que los conmutadores / enrutadores dentro de la red marquen la congestión (sin descartar paquetes) como en la Notificación explícita de congestión (ECN).
Fórmula matemática
Dejar ser el tamaño de la ventana de congestión que indica la cantidad de datos en vuelo durante el intervalo de tiempo, () ser el parámetro de aumento aditivo, y () sea el factor de disminución multiplicativo.
En TCP, después de un inicio lento , el parámetro de aumento aditivoes típicamente un MSS ( tamaño máximo de segmento ) por tiempo de ida y vuelta , y el factor de disminución multiplicativo es típicamente 1/2.
Protocolos
La prevención de la congestión AIMD se utiliza o se utilizó en:
- Protocolo de control de transmisión (TCP)
- TCP escalable (STCP)
- Transporte OSI Clase 4 [1]
- DCCP (en algunos modos) [2]
- DECnet [1]
Referencias
- ^ a b c Chiu, Dah-Ming; Raj Jain (1989). "Análisis de algoritmos de aumento y disminución para evitar la congestión en redes informáticas". Redes informáticas y sistemas RDSI . 17 : 1-14.
- ^ Floyd. "4341: Perfil RFC para Protocolo de control de congestión de datagramas (DCCP) Control de congestión ID 2: Control de congestión similar a TCP" .