カーンのアルゴリズム

カーンのアルゴリズムは、コンピュータネットワークで伝送制御プロトコル(TCP)を使用する際に、メッセージの往復時間を正確に推定する問題に対処します。このアルゴリズムは、カーン・パートリッジアルゴリズム^[1]とも呼ばれ、1987 年にフィル・カーンとクレイグ・パートリッジの論文で提案されました。^[2]

TCP では、再送されたセグメントによってあいまいさが生じるため、正確な往復時間の推定値を計算することが難しい場合があります。往復時間は、セグメントが送信された時間と、その確認応答が送信者に返された時間の差として推定されますが、パケットが再送されると、あいまいさが生じます。確認応答は、セグメントの最初の送信に対する応答である場合もあれば、その後の再送に対する応答である場合もあります。

Karn のアルゴリズムは、往復時間の推定値を更新するときに再送信されたセグメントを無視します。往復時間の推定値は、1 回だけ送信されたセグメントの確認応答である明確な確認応答のみに基づきます。

Karn のアルゴリズムのこの単純な実装も、問題を引き起こす可能性があります。遅延が急激に増加した後に TCP がセグメントを送信するとどうなるか考えてみましょう。TCP は、以前の往復時間の推定値を使用して、タイムアウトを計算し、セグメントを再送信します。TCP が再送信されたすべてのパケットの往復時間を無視すると、往復時間の推定値は更新されず、TCP はすべてのセグメントを再送信し続け、増加した遅延に調整されません。

この問題の解決策は、送信タイムアウトをタイマー バックオフ戦略に組み込むことです。タイマー バックオフ戦略は、初期タイムアウトを計算します。タイマーが期限切れになり再送信が発生する場合、TCP はタイムアウトを通常 2 倍に増やします。このアルゴリズムは、パケット損失が多いネットワークでパフォーマンスと効率のバランスをとるのに非常に効果的であることが証明されています。 ^{[3] [ページが必要]理想的には、Karn のアルゴリズムは必要ありません。ラウンドトリップ時間と再送信タイムアウトが長いネットワークは、}根本原因分析技術を使用して調査する必要があります。^[4]

• RFC 2581 - TCP 輻輳制御
• RFC 2988 - TCP の再送信タイマーの計算 (RFC 6298 により廃止)
• RFC 6298 - TCP の再送タイマーの計算