ALGORITMOS DE CONTROL DE CONGESTION

 año , caracteristicas condiciones, desventajas  basado

TCP Tahoe

En 1988 y a raíz de la problemática descrita, Van Jacobsen propuso en [5], un mecanismo de control de congestión basado en el concepto de ventanas de congestión, cwnd, y en la definición de tres  algoritmos:arranque lento (slow start), prevención de congestión (congestion avoindace) y retransmisión rápida (fast retransmit). A cada extremo en una conexión TCP se le asigna una ventana de congestión, cwnd, indicativa del número de segmentos que puede enviar a la red sin esperar por

reconocimientos explícitos desde el receptor (ACK). Al inicio, en la fase de operación de arranque lento (slow start), cwnd se configura en uno o dos segmentos de máximo tamaño (MSS) y su valor se

incrementará en un segmento por cada reconocimiento recibido desde su par receptor (ACK).  Durante la fase operativa de arranque lento, cwnd experimentará uncrecimiento exponencial, tal como se ilustra
Tahoe: si se reciben tres ACK duplicados (es decir, cuatro ACK que reconocen el mismo paquete, que no están respaldados por datos y no cambian la ventana anunciada del receptor), Tahoe realiza una retransmisión rápida, establece el umbral de inicio lento a la mitad de la congestión actual ventana, reduce la ventana de congestión a 1 MSS y se restablece al estado de inicio lento

Reno

TCP Reno surgió en 1990 como el sucesor de TCP Tahoe y fue implementado por primera vez en el sistema operativo 4.3BSD Unix. Si bien mantuvo las características de su antecesor, incorporó el algoritmo de recuperación rápida o fast recovery [6]. El algoritmo de recuperación rápida (FR) evita el ingreso a la fase de arranque lento (SS), cuando se detectan tres reconocimientos duplicados (ACKs) en la fase prevención de congestión (CA) y bajo esta circunstancia el emisor ejecuta las siguientes acciones: reconfigura la variable ssthresh al valor cwnd/2, retransmite el segmento perdido y actualiza la ventana de congestión a cwnd=ssthresh+3, finalmente abandona la fase de recuperación rápida para regresar a la fase de prevención de congestión (CA).

Una de las vulnerabilidades de TCP Reno se manifiesta cuando en la fase fast recovery (FR) se origina un evento de perdida de múltiples segmentos para el valor actual de cwnd. Bajo esta circunstancia TCP Reno alternará su operación entre las fases CA/FR, y provocará una reducción sucesiva del valor de la variable umbral de arranque lento (ssthresh), y de la ventana de congestión (cwnd). Como consecuencia se produce una importante disminución en el desempeño (thrughput) de la conexión TCP. Atentos a la problemática descrita,
Reno, en contraste,
sondas para ancho de banda directo adicional al aumentar la ventana
Tamaño continuamente.
Reno: si se reciben tres ACK duplicados, Reno realizará una retransmisión rápida y omitirá la fase de inicio lento reduciendo a la mitad la ventana de congestión (en lugar de establecerla en 1 MSS como Tahoe), configurando el umbral de inicio lento igual a la nueva ventana de congestión e ingrese a una fase llamada recuperación rápida

Vegas,
1995
 particularmente sensible respecto al resto de los protocolos . no le permite sostener un uso de ancho de banda cuando compite con los restantes protocolos seleccionados para realizar las pruebas. Así Vegas resigna ancho de banda y pasa a un segundo plano.  En Vegas [10], el remitente mide los llamados esperados y Tasas reales donde cwnd es el tamaño actual de la ventana TCP, BaseRTT es

el mínimo de tiempos medidos de ida y vuelta, y RTT es el tiempo de ida y vuelta suavizado medido. La diferencia de la tasa es Cuando, hay un enlace de cuello de botella donde los paquetes de la conexión se acumulan. Deje el trabajo atrasado en el cola se denota por. Tenemos Es decir, atribuimos el retraso adicional al enlace del cuello de botella en el segundo término del lado derecho arriba. Reorganizando, tenemos Vegas intenta mantenerse en un rango pequeño ajustando el tamaño de la ventana TCP de forma proactiva, evitando así la pérdida de paquetes debido al desbordamiento del búfer por completo. Lamentablemente, esta proactiva el ajuste de la ventana también pone a Las Vegas en desventaja cuando hay conexiones Reno coexistentes en su camino [4], [20], [30]
ya que es menos agresivo que la política de Reno, que continúa
para aumentar el tamaño de la ventana hasta que se produce la pérdida de paquetes.
Un segundo problema con Vegas es que el retraso acumulado que mide
No es necesario la acumulación de datos [3]. En redes asimétricas
donde el enlace del cuello de botella está en la ruta inversa, la acumulación
como se indica en la ecuación anterior, puede deberse al retraso
de confirmación TCP en el enlace del cuello de botella. Debido a esto
retraso, Vegas no continuaría aumentando el tamaño de la ventana
para permitir una mayor velocidad de envío de datos en el camino directo incluso
aunque su camino hacia adelante todavía está libre de congestión

Hasta mediados de la década de 1990, todos los tiempos de espera establecidos por TCP y los retrasos medidos de ida y vuelta se basaban solo en el último paquete transmitido en el búfer de transmisión. Los investigadores de la Universidad de Arizona Larry Peterson y Lawrence Brakmo presentaron TCP Vegas (llamado así por Las Vegas , la ciudad más grande de Nevada) en el que se establecieron tiempos de espera y se midieron los retrasos de ida y vuelta para cada paquete en el búfer de transmisión. Además, TCP Vegas utiliza aumentos aditivos en la ventana de congestión. En un estudio comparativo de varios algoritmos de control de congestión TCP, TCP Vegas parecía ser el más fluido seguido por TCP CUBIC. ^[15]

TCP Vegas no se implementó ampliamente fuera del laboratorio de Peterson, pero se seleccionó como el método de control de congestión predeterminado para el firmware DD-WRT v24 SP2.

 New Reno

1999 Floyd y otros en [7] y [8] introdujeron un simple refinamiento al algoritmo fast recovery (FR). En la fase congestion avoindance (CA), al recibir tres ACK´s duplicados, ingresa a la fase fast recovery,  pero a diferencia de TCP Reno, no abandona la fase fast recovery hasta que se produzca la confirmación (acknowledged) de todos los segmentos de la ventana de congestión (cwnd). Más formalmente, TCP  NewReno utiliza una variable de estado adicional para registrar el número de secuencia del último segmento TCP enviado antes de entrar a la fase fast recovery.

TCP NewReno resuelve el problema de bajo desempeño ante eventos de múltiples pérdidas en la ventana de congestión (cwnd) pero como contrapartida  emplea un tiempo excesivo en el proceso de

recuperación, pues le toma un Round Trip Time (RTT) recuperar cada uno de los segmentos perdidos en la ventana de congestión. Diversas estrategias se formularon para mejorar el desempeño de TCP NewReno en la fase fast recovery y una excelente referencia que investiga exhaustivamente numerosas propuestas puede encontrarse en

TCP New Reno, definido por RFC  6582 (que obsoleta las definiciones anteriores en RFC 3782 y RFC 2582 ) , mejora la retransmisión durante la fase de recuperación rápida de TCP Reno. Durante la recuperación rápida, para mantener la ventana de transmisión llena, por cada ACK duplicado que se devuelve, se envía un nuevo paquete no enviado desde el final de la ventana de congestión. Por cada ACK que realiza un progreso parcial en el espacio de secuencia, el remitente asume que el ACK apunta a un nuevo agujero y se envía el siguiente paquete más allá del número de secuencia ACKed.   

Debido a que el tiempo de espera se restablece cada vez que hay progreso en el búfer de transmisión, New Reno puede llenar agujeros grandes, o agujeros múltiples, en el espacio de secuencia, al igual que TCP SACK . Debido a que New Reno puede enviar nuevos paquetes al final de la ventana de congestión durante la recuperación rápida, se mantiene un alto rendimiento durante el proceso de llenado de agujeros, incluso cuando hay múltiples agujeros, de múltiples paquetes cada uno. Cuando TCP ingresa a la recuperación rápida, registra el número de secuencia de paquete no reconocido más alto pendiente. Cuando se reconoce este número de secuencia, TCP vuelve al estado de evitación de congestión.

Se produce un problema con New Reno cuando no hay pérdidas de paquetes, sino que los paquetes se reordenan por más de 3 números de secuencia de paquetes. En este caso, New Reno ingresa por error una recuperación rápida. Cuando se entrega el paquete reordenado, se produce el progreso del número de secuencia ACK y desde allí hasta el final de la recuperación rápida, todo el progreso del número de secuencia produce una retransmisión duplicada e innecesaria que se ACK inmediatamente. ^{[ aclaración necesaria ]}

El nuevo Reno funciona tan bien como el SACK con tasas de error de paquete bajas, y supera sustancialmente a Reno con tasas de error altas

Veno, 2001
Distinguir entre pérdida de congestión y pérdida aleatoria, y Proporcionar diferentes medidas para hacerles frente es fundamental problema que sigue sin resolverse para TCP. Veno hace uso de un  mecanismo similar al de Las Vegas para estimar el estado de la conexión, sin embargo, tal esquema se utiliza para deducir qué tipo de pérdida de paquetes (pérdida de congestión o pérdida aleatoria) es la mayoría probable que haya ocurrido, en lugar de perseguir la prevención de paquetes pérdida como en Vega. Si se detecta pérdida de paquetes mientras la conexión está en estado congestivo, Veno asume que la pérdida se debe a la congestión; de lo contrario, se supone que la pérdida es aleatoria. Veno hace uso de un mecanismo similar al de Las Vegas para estimar el estado de la conexión, sin embargo, tal esquema se usa para deducir qué tipo de pérdida de paquetes, pérdida de congestión o
1TCP Veno se ha implementado en NetBSD1.1, FreeBSD4.2 y Linux 2.4.
Westwood,
2001
También noté que al mismo tiempo, otro TCP modificado llamado Westwood [40] propuso un enfoque alternativo para lidiar con el sufrimiento del TCP en las redes inalámbricas.
pérdida aleatoria: es más probable que haya ocurrido, en lugar de
perseguir la prevención de la pérdida de paquetes como en Las Vegas.
A. Distinguir entre congestivo y no congestivo
Estados
SACK, 
 2003
Su versión mejorada Veno con opción de reconocimiento selectivo (SACK) también tiene implementado, sus códigos fuente están disponibles por correo electrónico, para un trabajo más detallado, consulte la referencia [1] y [41] documentada en julio de 2001, nosotros
. La idea principal de nuestro algoritmo, Veno, es que usaremos
la medición de no como una forma de ajustar el tamaño de la ventana
proactivamente, sino más bien como una indicación de si la conexión
Está en un estado congestivo. La idea esencial de Reno, en la que el
el tamaño de la ventana aumenta progresivamente cuando no hay paquete
pérdida, permanece intacta en Veno.
Específicamente, si cuando se detecta una pérdida de paquete, Veno
asumirá que la pérdida es aleatoria en lugar de congestiva, y
un esquema de ajuste de ventana diferente al de Reno
ser usado; de lo contrario, Veno asumirá que la pérdida es congestiva,
y se adoptará el esquema de ajuste de la ventana de Reno. Nuestra
Los experimentos indican que es un buen escenario.
Vale la pena señalar que el algoritmo original de Vegas,
BaseRTT se actualiza continuamente durante todo el tiempo en vivo del
Conexión TCP con el tiempo mínimo de ida y vuelta recogido para
lejos. En nuestro trabajo, sin embargo, BaseRTT se restablece cada vez que el paquete

TCP Hybla 2004

TCP Hybla tiene como objetivo eliminar las penalizaciones a las conexiones TCP que incorporan enlaces de radio terrestre o satelital de alta latencia. Las mejoras de Hybla se basan en la evaluación analítica de la dinámica de la ventana de congestió

TCP BIC

2006 El desempeño del protocolo TCP basado en TCP Reno y TCP NewReno no es satisfactorio en redes de alta velocidad, con elevados RTT entre los host que se comunican, y el factor limitante es el

comportamiento conservativo de ajuste de la ventana de congestión que gobierna la tasa de transmisión del emisor [10]. Por tal razón surgieron una serie de propuestas basadas en reformular la vía con la cual TCP adapta la ventana de congestión. Un intento exitoso para crear un control de congestión que pueda escalar en  ssthresh, Loss ,(timeout) ,SS CA SS CA CA,Loss,(dup ACKs),time,cwnd,FR. redes con alto valor BDP (bandwidth delay product) fue propuesto por Xu y otros en [11]. BIC (Binary Increase Congestión control) extiende TCP NewReno con una fase adicional denominada de convergencia rápida (Rapid Convergence or RC). La fase RC, tiene como objetivo descubrir mediante una rápida búsqueda binaria, el valor óptimo de la ventana de congestión en función de los recursos actuales de la red. El proceso de búsqueda binaria Inicialmente se establecen las variables Wmin=1 y Wmax en un valor arbitrariamente alto. Si la red entrega correctamente todos los segmentos emitidos (el emisor recibe todos los ACKs correspondientes al último RTT), la ventana de congestión se actualiza al valor promedio entre Wmax y Wmin (A en la Figura 3) y Wmin adquiere el tamaño de la ventana de congestión previa. Cuando se detecta una pérdida, BIC reduce Wmax al  valor actual de la ventana de congestión (B en la Figura 3) y como en TCP NewReno ingresa a la fase de recuperación rápida (FR). Para incrementar la tasa de convergencia, en ambientes de bajo nivel de pérdidas, BIC reduce el coeficiente de decremento multiplicativo desde 0.5 a 0.125, para lograr mayor velocidad de respuesta.

Las características del algoritmo de búsqueda binaria se traducen en tiempos de convergencia muy bajos que pueden provocar degradación en conexiones TCP. Si la ventana de congestión se incrementa drásticamente, un grupo significativo de segmentos pueden perderse. Por esta razón BIC implementa un algoritmo de arranque lento restringido [12] que limita el incremento en cada paso de slow start a un valor máximo de 100 segmentos. En la misma dirección, BIC impone límites al crecimiento de la ventana de congestión en la fase de convergencia rápida cuando el rango de búsqueda binaria es muy amplio, y no permite incrementar la ventana de congestión más allá de un valor predefinido Smax.

En el caso opuesto, cuando el rango de búsqueda binaria es pequeño, y por tanto cercano al valor óptimo, BIC define el valor constante Smin como un quantum de incremento de la ventana de congestión.

Cuando el valor actual de la ventana de congestión alcanza el valor optimo, o lo excede, BIC conmuta a la fase de arranque lento restringido, no limitado por el valor umbral de ssthresh (slow start threshold).
El propósito de esta acción es descubrir un nuevo límite superior para luego reiniciar la fase de búsqueda binaria. La Figura 4 ilustra la dinámica de la ventana de congestión de una conexión para
Binary Increase Congestion Control (BIC) es una implementación de TCP con un CCA optimizado para redes de alta velocidad con alta latencia, conocidas como redes largas y gruesas . ^[19] BIC se usa por defecto en los núcleos de Linux 2.6.8 a 2.6.18.

 FACK,

LP

(Low Proprity),

 HS (High Speed)

, H-TCP,

 Hybla,  destinados a redes

de alta velocidad, tienden a dominar a sus contrapartes en los ensayos e intentan

capturar el mayor ancho de banda posible.

Illinois y aquellos destinados a redes

de alta velocidad, tienden a dominar a sus contrapartes en los ensayos e intentan

capturar el mayor ancho de banda posible.

Compound TCP

2008 Compound TCP es una implementación de TCP de Microsoft que mantiene dos ventanas de congestión diferentes simultáneamente, con el objetivo de lograr un buen rendimiento en LFN sin afectar la equidad . Se ha implementado ampliamente en versiones de Windows desde Microsoft Windows Vista y Windows Server 2008 y se ha portado a versiones anteriores de Microsoft Windows y Linux .

 Cubic,
2016

Es una derivada menos agresiva y más sistemática de BIC TCP , en la que el tamaño de la ventana es una función cúbica del tiempo desde el último evento de congestión, con el punto de inflexión establecido en el tamaño de la ventana antes del evento. Debido a que es una función cúbica, hay dos componentes para el crecimiento de la ventana. La primera es una parte cóncava donde el tamaño de la ventana aumenta rápidamente hasta el tamaño anterior al último evento de congestión. El siguiente es el crecimiento convexo donde CUBIC sondea para obtener más ancho de banda, lentamente al principio y luego muy rápidamente. CUBIC pasa mucho tiempo en una meseta entre la región de crecimiento cóncava y convexa que permite que la red se estabilice antes de que CUBIC comience a buscar más ancho de banda. ^[4]

Otra diferencia importante entre los sabores CUBIC y TCP estándar es que no depende de la cadencia de RTT para aumentar el tamaño de la ventana. ^[5] El tamaño de la ventana de CUBIC depende solo del último evento de congestión. Con TCP estándar, los flujos con tiempos de retardo de ida y vuelta (RTT) muy cortos recibirán ACK más rápido y, por lo tanto, sus ventanas de congestión crecerán más rápido que otros flujos con RTT más largos. CUBIC permite una mayor equidad entre los flujos, ya que el crecimiento de la ventana es independiente de RTT

Rhee y Xu en [13] observaron que

TCP BIC presenta problemas Wmax

A

B

Wmin

time

Loss

time

cuando dos o

más

flujos

de

bytes

con

diferencias

significativas en sus RTT compiten por el

ancho

de

banda

en

un

enlace

de

características restrictivas (bottleneck link).

Concretamente en [13] se demostró que

flujos de bytes con pequeños RTT escalan

rápidamente su ventana de congestión al

Congestion Windows

Congestión Windows valor óptimo y consumen los recursos de la

red, en detrimento de flujos con RTT

mayores.raíz de las observaciones

experimentales,

Rhee

y

Xu

[13]

propusieron el mecanismo de control de

congestión CUBIC, que constituye una

mejora de TCP BIC e implementa una

función para el crecimiento de TCP BIC e implementa una

función para el crecimiento de la ventana de

congestión en forma

independiente del

RTT para cada conexión en particular.

TCP CUBIC define una ventana de

congestión (w) como una función cubica

del tiempo transcurrido desde el último

evento de congestión (.):

¨

Ú *

S à Ô ë

%

/

S = % L. -

M

7

+

S à

Donde C es una constante predefinida, 􀟚 es un coeficiente multiplicativo

decreciente en la fase de recuperación

rápida, y 􀝓􀯠􀯔􀯫 es el tamaño de la ventana

de congestión inmediatamente antes de que

se detecte una perdida. La función presenta

un rápido crecimiento cuando 􀝓 es pequeña

respecto de 􀝓􀯠􀯔􀯫, y es muy conservativa

cuando 􀝓 se aproxima al valor de 􀝓􀯠􀯔􀯫 tal

como se ilustra en la Figura 5.

Figura 5: Descripción función cubica

La Figura 6 muestra la dinámica de la

ventana de congestión de TCP CUBIC. De

la observación se puede deducir que,

durante el paso inicial “1” se desconoce

􀝓􀯠􀯔􀯫 y para descubrir su valor se emplea la

sección derecha de la función cubica en la

Figura 5 (Max Probing), esta etapa finaliza

al detectarse una perdida. A continuación,

en la fase 2, se emplea la sección izquierda

de la función cubica, que implica una tasa de crecimiento en la ventana de congestión

menor al de la fase 1. La etapa 3 incluye

ambas etapas de la función cubica y finaliza

cuando se produce una perdida; en este caso

particular se actualiza el valor umbral de

􀝓􀯠􀯔􀯫

protocolos como Hybla, Illinois y aquellos destinados a redes

de alta velocidad, tienden a dominar a sus contrapartes en los ensayos e intentan

capturar el mayor ancho de banda posible.

Elastic-TCP

Elastic-TCP fue propuesto en febrero de 2019 por Mohamed A. Alrshah et al. ^[32]para aumentar la utilización del ancho de banda en redes de alto BDP para admitir aplicaciones recientes como computación en la nube, transferencia de grandes datos, IoT, etc. Es un CCA basado en Linux que está diseñado para el kernel de Linux. Es un algoritmo del lado del receptor que emplea un enfoque basado en el retraso de pérdida utilizando un mecanismo novedoso, llamado Función de ponderación correlacionada con ventanas (WWF). Tiene un alto nivel de elasticidad para lidiar con diferentes características de red sin necesidad de ajuste humano. Se ha evaluado comparando su rendimiento con Compound-TCP (el CCA predeterminado en MS Windows), CUBIC (el predeterminado de Linux) y TCP-BBR (el predeterminado de Linux 4.9 de Google) usando el simulador NS-2 y el banco de pruebas. Elastic-TCP mejora significativamente el rendimiento total en términos de rendimiento promedio, índice de pérdida y retraso