Algorithme de Karn

L'algorithme de Karn permet d'obtenir une mesure fiable du round-trip delay time (RTT) lors de la transmission de paquets à travers un réseau via TCP. L'algorithme a été proposé par Phil Karn en 1987^[1].

Obtention de la mesure

Obtenir une mesure fiable du RTT est complexe avec TCP car la retransmission de paquets amène une ambiguïté. L'estimation du RTT est obtenue en calculant la différence de temps entre l'émission d'un paquet et la réception de l'accusé de réception de ce paquet, et quand des paquets sont retransmis l'accusé de réception peut correspondre à la réception du premier envoi ou d'une des retransmissions. Ainsi les paquets qui ont été retransmis ne sont pas utilisés pour l'estimation du RTT dans l'algorithme de Karn. L'estimation n'utilise que les accusés de réception sans équivoque, qui correspondent aux paquets émis une seule fois.

Résistance à des variations brusques de temps de transmission

Cette implémentation simpliste de l'algorithme conduit elle aussi à des problèmes. Si on considère une augmentation brusque du délai de transmission, TCP va utiliser le précédent RTT pour calculer le temps avant de retransmettre les paquets non confirmés, et comme le délai de transmission a été augmenté, les accusés de réception peuvent ne jamais être reçus avant les retransmissions. Le RTT ne sera ainsi jamais mis à jour et TCP continuera de retransmettre les paquets sans ajuster son délai de retransmission. Une solution à ce problème est de commencer par calculer un premier délai avant retransmission, quand ce délai est dépassé pour un paquet, le paquet est retransmis et le délai est augmenté, généralement multiplié par un facteur 2.

Cet algorithme s'est montré très efficace dans des réseaux avec un taux de perte de paquets élevé^[2].

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Karn's Algorithm » (voir la liste des auteurs)

• Portail de l’algorithmique
• Portail de l’informatique