La detección temprana aleatoria ( RED ), también conocida como descarte temprano aleatorio o caída temprana aleatoria, es una disciplina de puesta en cola para un programador de red adecuado para evitar la congestión . [1]
En el algoritmo de caída de cola convencional , un enrutador u otro componente de red almacena en búfer tantos paquetes como puede y simplemente descarta los que no puede almacenar en búfer. Si los búferes están constantemente llenos, la red está congestionada . La caída de cola distribuye el espacio intermedio de manera injusta entre los flujos de tráfico. La caída de cola también puede conducir a la sincronización global de TCP, ya que todas las conexiones TCP "se detienen" simultáneamente y luego avanzan simultáneamente. Las redes se subutilizan y se inundan, alternativamente, en oleadas.
RED aborda estos problemas descartando paquetes de forma preventiva antes de que el búfer se llene por completo. Utiliza modelos predictivos para decidir qué paquetes descartar. Fue inventado a principios de la década de 1990 por Sally Floyd y Van Jacobson . [2]
Operación
RED monitorea el tamaño promedio de la cola y elimina (o marca cuando se usa junto con ECN ) paquetes basados en probabilidades estadísticas . Si el búfer está casi vacío, se aceptan todos los paquetes entrantes. A medida que crece la cola, también aumenta la probabilidad de descartar un paquete entrante. Cuando el búfer está lleno, la probabilidad ha llegado a 1 y todos los paquetes entrantes se descartan.
RED es más justo que la caída de la cola, en el sentido de que no posee un sesgo contra el tráfico en ráfagas que usa solo una pequeña parte del ancho de banda. Cuanto más transmite un host, más probable es que se descarten sus paquetes, ya que la probabilidad de que se descarte un paquete de un host es proporcional a la cantidad de datos que tiene en una cola. La detección temprana ayuda a evitar la sincronización global de TCP.
Problemas con el ROJO clásico
Según Van Jacobson, "no hay uno, sino dos errores en el rojo clásico". [3] Se desarrollaron mejoras en el algoritmo y se preparó un borrador del documento [4] , pero el documento nunca se publicó y las mejoras no se difundieron o implementaron ampliamente. Se ha trabajado un poco para intentar terminar la investigación y corregir los errores. [3]
Pure RED no se adapta a la diferenciación de calidad de servicio (QoS). ROJO ponderado (WRED) y ROJO con entrada y salida (RIO) [5] proporcionan una detección temprana con consideraciones de QoS.
Otras variantes
WRED
En RED ponderado puede tener diferentes probabilidades para diferentes prioridades ( precedencia de IP , DSCP ) y / o colas. [6]
UN ROJO
El algoritmo de RED adaptativo o RED activo (ARED) [7] infiere si hacer RED más o menos agresivo basándose en la observación de la longitud promedio de la cola. Si la longitud promedio de la cola oscila alrededor del umbral mínimo , la detección temprana es demasiado agresiva. Por otro lado, si la longitud promedio de la cola oscila alrededor del umbral máximo , la detección temprana está siendo demasiado conservadora. El algoritmo cambia la probabilidad de acuerdo con la agresividad con la que detecta que ha estado descartando tráfico.
Véase Srikant [8] para una descripción en profundidad de estas técnicas y su análisis.
RRED
Se propuso un algoritmo robusto de detección temprana aleatoria (RRED) para mejorar el rendimiento de TCP contra los ataques de denegación de servicio (DoS), en particular los ataques de denegación de servicio de baja tasa (LDoS). Los experimentos han confirmado que los algoritmos de tipo RED existentes son notablemente vulnerables a los ataques de denegación de servicio de baja velocidad (LDoS) debido al tamaño de la cola de TCP oscilante causado por los ataques. [9] El algoritmo RRED puede mejorar significativamente el rendimiento de TCP bajo ataques de denegación de servicio de baja velocidad. [9]
Ver también
Referencias
- ^ Floyd, Sally; Jacobson, Van (agosto de 1993). "Puertas de enlace de detección temprana aleatoria (RED) para evitar la congestión" . Transacciones IEEE / ACM sobre redes . 1 (4): 397–413. CiteSeerX 10.1.1.147.3833 . doi : 10.1109 / 90.251892 . Consultado el 16 de marzo de 2008 .
- ^ Hafner, Katie (4 de septiembre de 2019). "Sally Floyd, que ayudó a que todo funcionara sin problemas en línea, muere a los 69 años" , a través de NYTimes.com.
- ^ a b Gettys, Jim (17 de diciembre de 2010). "ROJO bajo una luz diferente" . Divagaciones de jg . Consultado el 27 de diciembre de 2010 .
- ^ Jacobson, Van; Nichols, Kathy; Poduri, Kedar (30 de septiembre de 1999). "ROJO bajo una luz diferente". CiteSeerX 10.1.1.22.9406 . Cite revista necesita
|journal=
( ayuda ) - ^ Clark, David D .; Wroclawski, John (julio de 1997). "Un enfoque para la asignación de servicios en Internet" . IETF. pag. 12 . Consultado el 27 de mayo de 2011 .
- ^ Chao, H. Jonathan (2002). "Frontmatter e Index". Control de calidad de servicio en redes de alta velocidad . 605 Third Avenue, Nueva York, NY: John Wiley & Sons Inc. págs. I – xvi. doi : 10.1002 / 0471224391.fmatter_indsub . ISBN 978-0-471-00397-7.Mantenimiento de CS1: ubicación ( enlace )
- ^ Floyd, Sally; Gummadi, Ramakrishna; Shenker, Scott (1 de agosto de 2001). "Red adaptable: un algoritmo para aumentar la robustez de la gestión activa de la cola de RED" . Consultado el 16 de marzo de 2008 . Cite revista necesita
|journal=
( ayuda ) - ^ Srikant, Rayadurgam (2004). Las matemáticas del control de la congestión de Internet . Boston, MA, EE.UU .: Birkhäuser. ISBN 978-0-8176-3227-4.
- ^ a b Zhang, Changwang; Yin, Jianping; Cai, Zhiping; Chen, Weifeng (1 de mayo de 2010). "RRED: algoritmo RED robusto para contrarrestar ataques de denegación de servicio de baja tasa". Cartas de comunicaciones de IEEE . 14 (5): 489–491. doi : 10.1109 / LCOMM.2010.05.091407 .
enlaces externos
- Gestión de colas RED (detección temprana aleatoria) . Autor: Sally Floyd
- Guduz : un simulador de detección temprana aleatoria (RED) simple
- Variantes de RED . Autor: Hei Xiao Jun
- Publicaciones recientes en esquemas de detección temprana aleatoria (RED)