Karns Algorithmus liefert ein zuverlässiges Maß für die Round-Trip-Verzögerungszeit (RTT) bei der Übertragung von Paketen über ein Netzwerk über TCP . Der Algorithmus wurde 1987 von Phil Karn vorgeschlagen.
Das Erhalten einer zuverlässigen RTT-Messung ist mit TCP komplex, da eine erneute Übertragung von Paketen zu Mehrdeutigkeiten führt. Die RTT-Schätzung wird erhalten, indem die Zeitdifferenz zwischen der Übertragung eines Pakets und dem Empfang der Bestätigung dieses Pakets berechnet wird, und wenn Pakete erneut übertragen werden, kann die Bestätigung dem Empfang der ersten Übertragung oder einer der erneuten Übertragungen entsprechen. Somit werden die erneut übertragenen Pakete nicht für die Schätzung der RTT im Karn-Algorithmus verwendet. Die Schätzung verwendet nur eindeutige Bestätigungen, die nur einmal gesendeten Paketen entsprechen.
Diese vereinfachte Implementierung des Algorithmus führt auch zu Problemen. Wenn wir einen starken Anstieg der Übertragungsverzögerung in Betracht ziehen, berechnet TCP anhand der vorherigen RTT die Zeit vor der erneuten Übertragung nicht bestätigter Pakete. Da die Übertragungsverzögerung erhöht wurde, werden möglicherweise nie Bestätigungen vor ihnen empfangen. Neuübertragungen. Das RTT wird daher niemals aktualisiert und TCP überträgt die Pakete weiterhin erneut, ohne die Verzögerung für die erneute Übertragung anzupassen. Eine Lösung für dieses Problem besteht darin, zunächst eine erste Verzögerung vor der erneuten Übertragung zu berechnen. Wenn diese Verzögerung für ein Paket überschritten wird, wird das Paket erneut übertragen und die Verzögerung erhöht, üblicherweise multipliziert mit dem Faktor 2.
Es hat sich gezeigt, dass dieser Algorithmus in Netzwerken mit einer hohen Paketverlustrate sehr effektiv ist.