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 de Karn-Partridge [1], fue propuesto en un artículo de Phil Karn y Craig Partridge en 1987. [2]
Las estimaciones precisas de ida y vuelta en TCP pueden resultar difíciles de calcular debido a una ambigüedad creada por los segmentos retransmitidos. El tiempo de ida y vuelta se estima 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 los paquetes se retransmiten existe una ambigüedad: el acuse de recibo puede ser una respuesta al primero. 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 acuses de recibo inequívocos, que son acuses de recibo de segmentos que se enviaron sólo 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 fuerte aumento 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 viaje 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 retroceso del temporizador. La estrategia de retroceso del temporizador calcula un tiempo de espera inicial. Si el temporizador expira y provoca una retransmisión, TCP aumenta el tiempo de espera generalmente en 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 elevados y tiempos de espera de retransmisión deben investigarse utilizando técnicas de análisis de causa raíz . [4]