Algoritmo de Karn
El algoritmo de Karn aborda el problema de obtener estimaciones precisas del tiempo de ida y vuelta de los mensajes cuando se utiliza el Protocolo de Control de Transmisión (TCP) en redes informáticas . El algoritmo, también denominado a veces algoritmo Karn-Partridge [1], fue propuesto en un artículo de Phil Karn y Craig Partridge en 1987. [2]
En TCP, puede resultar difícil calcular con precisión el tiempo de ida y vuelta debido a la ambigüedad que generan los segmentos retransmitidos. El tiempo de ida y vuelta se calcula como la diferencia entre el momento en que se envió un segmento y el momento en que se devolvió su acuse de recibo al remitente, pero cuando se retransmiten los paquetes existe una ambigüedad: el acuse de recibo puede ser una respuesta a la primera transmisión del segmento o a una retransmisión posterior.
El algoritmo de Karn ignora los segmentos retransmitidos al actualizar la estimación del tiempo de ida y vuelta. La estimación del tiempo de ida y vuelta se basa únicamente en reconocimientos inequívocos, que son reconocimientos para segmentos que se enviaron solo una vez.
Esta implementación simplista del algoritmo de Karn también puede generar problemas. Considere lo que sucede cuando TCP envía un segmento después de un aumento brusco en el retraso. Utilizando la estimación del tiempo de ida y vuelta anterior, TCP calcula un tiempo de espera y retransmite un segmento. Si TCP ignora el tiempo de ida y vuelta de todos los paquetes retransmitidos, la estimación del tiempo de ida y vuelta nunca se actualizará y TCP continuará retransmitiendo cada segmento, sin ajustarse nunca al aumento del retraso.
Una solución a este problema es incorporar tiempos de espera de transmisión con una estrategia de reducción de tiempo del temporizador. La estrategia de reducción de tiempo del temporizador calcula un tiempo de espera inicial. Si el temporizador expira y provoca una retransmisión, TCP aumenta el tiempo de espera generalmente por un factor de dos. Este algoritmo ha demostrado ser extremadamente eficaz para equilibrar el rendimiento y la eficiencia en redes con alta pérdida de paquetes. [3] [ página necesaria ] Idealmente, el algoritmo de Karn no sería necesario. Las redes que tienen tiempos de ida y vuelta altos y tiempos de espera de retransmisión altos deberían investigarse utilizando técnicas de análisis de causa raíz . [4]
Referencias
- ^ Redes de computadoras: un enfoque de sistemas, Serie de Morgan Kaufmann sobre redes, Larry L. Peterson , Bruce S. Davie, Edición 5, Elsevier, 2011, pág. 418
- ^ Karn, Phil; Partridge, Craig (1987). Mejora de las estimaciones de tiempo de ida y vuelta en protocolos de transporte fiables ( PostScript ) . Proc. ACM SIGCOMM. págs. 2–7.
- ^ Comer, Douglas (2006). Interconexión de redes con TCP/IP (Quinta ed.). Prentice Hall.
- ^ "¿Qué es el algoritmo de Karn?". Archivado desde el original el 14 de noviembre de 2016. Consultado el 7 de septiembre de 2016 .
Enlaces externos
- RFC 2581 - Control de congestión TCP
- RFC 2988 - Cálculo del temporizador de retransmisión de TCP (obsoleto por RFC 6298)
- RFC 6298 - Cálculo del temporizador de retransmisión de TCP
