El algoritmo de Karn

El algoritmo de Karn aborda el problema de obtener estimaciones precisas del tiempo de ida y vuelta de los mensajes al utilizar el Protocolo de Control de Transmisión (TCP) en redes informáticas . El algoritmo, también conocido a veces como algoritmo de Karn-Partridge ^{[ 1 ],} fue propuesto en un artículo por Phil Karn y Craig Partridge en 1987. ^{[ 2 ]}

Calcular con precisión el tiempo de ida y vuelta en TCP puede resultar difícil debido a la ambigüedad que generan 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 recibió su acuse de recibo. Sin embargo, cuando se retransmiten 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 acuses de recibo inequívocos, que son los acuses de recibo de los segmentos que se enviaron una sola vez.

Esta implementación simplista del algoritmo de Karn también puede generar problemas. Consideremos qué sucede cuando TCP envía un segmento tras un aumento brusco del retardo. Utilizando la estimación previa del tiempo de ida y vuelta, TCP calcula un tiempo de espera y retransmite el 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 seguirá retransmitiendo cada segmento, sin ajustarse al retardo aumentado.

Una solución a este problema consiste en incorporar tiempos de espera de transmisión con una estrategia de retroceso de temporizador. Esta estrategia calcula un tiempo de espera inicial. Si el temporizador expira y provoca una retransmisión, TCP aumenta el tiempo de espera generalmente al doble. Este algoritmo ha demostrado ser extremadamente eficaz para equilibrar el rendimiento y la eficiencia en redes con alta pérdida de paquetes. ^{[ 3 ]} Idealmente, el algoritmo de Karn no sería necesario. Las redes con tiempos de ida y vuelta elevados y tiempos de espera de retransmisión elevados deberían investigarse mediante técnicas de análisis de causa raíz . ^{[ 4 ]}

• 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