Loading article…
カーンのアルゴリズムは、コンピュータネットワークで伝送制御プロトコル（TCP）を使用する際に、メッセージの往復時間を正確に推定するという問題に対処するものです。このアルゴリズムは、カーン・パートリッジアルゴリズムとも呼ばれ[ 1 ]、 1987年にフィル・カーンとクレイグ・パートリッジによって論文で提案されました[ 2 ]。
TCPにおける正確な往復時間の推定は、再送信されたセグメントによって生じる曖昧さのために計算が難しい場合があります。往復時間は、セグメントが送信された時刻と、その確認応答が送信者に返された時刻の差として推定されますが、パケットが再送信されると、確認応答がセグメントの最初の送信に対する応答なのか、それともその後の再送信に対する応答なのかが曖昧になります。
カーンのアルゴリズムは、往復時間推定値を更新する際に、再送信されたセグメントを無視します。往復時間推定は、明確な確認応答のみに基づいており、これは一度だけ送信されたセグメントに対する確認応答です。
Karnのアルゴリズムをこのように単純に実装すると、問題が生じる可能性があります。TCPが遅延が急激に増加した後にセグメントを送信する場合を考えてみましょう。TCPは以前の往復時間推定値を使用してタイムアウトを計算し、セグメントを再送信します。TCPが再送信されたすべてのパケットの往復時間を無視すると、往復時間推定値は更新されず、TCPはすべてのセグメントを再送信し続け、遅延の増加に調整することはありません。
この問題の解決策は、タイマーバックオフ戦略で送信タイムアウトを組み込むことです。タイマーバックオフ戦略では、初期タイムアウトを計算します。タイマーが期限切れになり再送信が発生すると、TCP はタイムアウトを通常 2 倍に増やします。このアルゴリズムは、パケット損失率の高いネットワークでパフォーマンスと効率のバランスを取るのに非常に効果的であることが証明されています。[ 3 ]理想的には、Karn のアルゴリズムは必要ありません。往復時間と再送信タイムアウトが高いネットワークは、根本原因分析手法を使用して調査する必要があります。[ 4 ]