メインコンテンツまでスキップ

4. PAWS -- シーケンス番号の折り返しに対する保護

4.1 はじめに​

セクション4.2では、オープンなTCP接続を破壊する可能性のある古い重複セグメントを拒否する簡単なメカニズムについて説明します。このメカニズムをPAWS (Protect Against Wrapped Sequence numbers、シーケンス番号の折り返しに対する保護) と呼びます。PAWSは、接続制御ブロックに保存された状態を使用して、単一のTCP接続内で動作します。セクション4.3および付録Cでは、同じ接続の以前のインカーネーションからの古い重複を回避するためのPAWSメカニズムの影響について説明します。

4.2 PAWSメカニズム​

PAWSは、前述のRTTMメカニズムと同じTCP Timestampsオプションを使用し、受信したすべてのTCPセグメント (データセグメントとACKセグメントを含む) には、時間的に単調非減少なタイムスタンプSEG.TSvalが含まれていると仮定します。基本的な考え方は、この接続で最近受信したタイムスタンプよりも小さいタイムスタンプSEG.TSvalで受信された場合、そのセグメントを古い重複として破棄できるということです。

PAWSとRTTMメカニズムの両方において、「タイムスタンプ (timestamps)」はモジュラー32ビット空間における32ビット符号なし整数です。したがって、「less than (未満)」はTCPシーケンス番号と同じ方法で定義され、同じ実装技術が適用されます。sとtがタイムスタンプ値である場合、0 < (t - s) < 2**31のときs < tであり、符号なし32ビット算術で計算されます。

この比較のために保存される着信タイムスタンプの選択は、単調増加する値を保証する必要があります。たとえば、受信ウィンドウの左端を最後に進めたセグメント、つまり最新のシーケンス内セグメントからタイムスタンプを保存する場合があります。代わりに、PAWSとRTTMの両方に共通の値を使用すると両方の実装が簡素化されるため、セクション3.4でRTTMメカニズムのために導入された値TS.Recentを選択します。セクション3.4で説明したように、TS.Recentは遅延ACKの場合にのみ最後のシーケンス内セグメントのタイムスタンプと異なり、したがって1ウィンドウ未満の差です。したがって、どちらの選択もシーケンス番号の折り返しに対して保護します。

RTTMは対称的に指定されているため、TSvalタイムスタンプはデータセグメントとACKセグメントの両方で運ばれ、返されるACKまたはデータセグメントで運ばれるTSecrフィールドでエコーされます。PAWSはすべての着信セグメントを同じテストに提出するため、データセグメントだけでなく重複ACKセグメントに対しても保護します。(代替の非対称アルゴリズムは、古い重複ACKに対して保護します。データの送信者は、ACKフィールドが送信ウィンドウの左端を進めた最後のセグメントから保存されたTSecrよりも小さいTSecr値を持つ着信ACKセグメントを拒否します。このアルゴリズムはメカニズムの経済性と対称性に欠けると見なされました。)

{SYN}および{SYN,ACK}セグメントで送信されるTSvalタイムスタンプは、PAWSを初期化するために使用されます。PAWSは、古い重複非SYNセグメント、および同期接続が存在する間に受信された重複SYNセグメントに対して保護します。接続が存在しないときに受信された重複{SYN}および{SYN,ACK}セグメントは、TCPの通常の3ウェイハンドシェイクとシーケンス番号チェックによって破棄されます。

RSTセグメントはタイムスタンプを運ばないこと、およびタイムスタンプに関係なくRSTセグメントが受け入れられることが推奨されます。古い重複RSTセグメントは極めて可能性が低く、そのクリーンアップ機能はタイムスタンプよりも優先されるべきです。

4.2.1 基本PAWSアルゴリズム​

PAWSアルゴリズムは、同期接続のすべての着信セグメントに対して次の処理を実行することを要求します。

到着したセグメントにTimestampsオプションがあり、SEG.TSval < TS.Recentであり、TS.Recentが有効である場合 (後述の議論を参照)、到着したセグメントを受け入れ不可として扱います。

RFC-793の69ページで指定されているように応答として確認応答を送信し、セグメントを破棄します。

注: ハーフオープン接続の検出と回復のためのTCPのメカニズムを保持するために、ACKセグメントを送信する必要があります。たとえば、RFC-793の図10を参照してください。

セグメントがウィンドウの外側にある場合は、それを拒否します (通常のTCP処理)

到着したセグメントがSEG.SEQ <= Last.ACK.sent (セクション3.4を参照) を満たす場合、そのタイムスタンプをTS.Recentに記録します。

到着したセグメントがシーケンス内 (つまり、左ウィンドウエッジにある) である場合、それを通常どおり受け入れます。

それ以外の場合は、セグメントを通常のウィンドウ内、シーケンス外TCPセグメントとして扱います (たとえば、後でユーザーに配信するためにキューに入れます)。

ステップR2、R4、およびR5は、RFC-793で指定されている通常のTCP処理ステップです。

タイムスタンプは、セグメントが受信者に最初に到着したときにのみチェックされることに注意することが重要です。これは、それがシーケンス内であるか、後で配信するためにキューに入れる必要があるかに関係ありません。次の例を考えてみましょう。

セグメントシーケンスA.1、B.1、C.1、...、Z.1が送信されたとします。ここで、文字はシーケンス番号を示し、数字はタイムスタンプを表します。また、セグメントB.1が失われたとします。TS.TStampのタイムスタンプは1 (A.1から) であるため、C.1、...、Z.1は受け入れ可能と見なされ、キューに入れられます。Bが最新のタイムスタンプを使用してセグメントB.2として再送信されると、それは穴を埋め、Zまでのすべてのセグメントが確認されユーザーに渡されます。キューに入れられたセグメントのタイムスタンプは、すでに受け入れられているため、この時点では再度検査されません。B.2が受け入れられると、TS.Stampは2に設定されます。

このルールは、損失下での合理的なパフォーマンスを可能にします。完全なデータウィンドウが常に転送中であり、損失後、1パケット少ない完全なウィンドウがシーケンス外として現れ、受信者でキューに入れられます (たとえば、最大〜2**30バイトのデータ)。タイムスタンプオプションは、このデータを破棄する結果になってはなりません。

特定のありそうもない状況では、ルールR1-R4のアルゴリズムが、次の例に示すように、いくつかのセグメントを不必要に破棄する可能性があります。

再び、セグメントA.1、B.1、C.1、...、Z.1が順番に送信され、セグメントB.1が失われたとします。さらに、C.1、...、Z.1の一部の配信が再送信B.2が受信者に到着した後まで遅延されたとします。これらの遅延されたセグメントは、到着したときに不必要に破棄されます。これは、そのタイムスタンプが現在古くなっているためです。

このケースは発生する可能性が非常に低いです。再送信がタイムアウトによってトリガーされた場合、セグメントC.1、...、Z.1の一部はRTO時間よりも長く遅延されている必要があります。これはおそらくありそうもないイベントであり、そうでなければ多くの偽のタイムアウトと再送信があるでしょう。Bの再送信が「高速再送信 (fast retransmit)」アルゴリズム、つまり重複ACKによってトリガーされた場合、これらのACKを引き起こしたキューに入れられたセグメントはすでに受信されている必要があります。

セグメントがRTOを過ぎて遅延された場合でも、高速再送信メカニズム [Jacobson90c] により、遅延されたパケットはB.2と同時に再送信され、余分なRTTを回避するため、非常に小さなパフォーマンスペナルティが発生します。

タイムスタンプがセグメントを不必要に破棄することによってパフォーマンス低下を引き起こす、発生確率が高いケースは知られていません。

4.2.2 タイムスタンプクロック​

PAWSアルゴリズムが送信者と受信者の間のクロック同期を必要としないことを理解することが重要です。送信者のタイムスタンプクロックはセグメントにスタンプを押すために使用され、送信者はエコーされたタイムスタンプを使用してRTTを測定します。ただし、受信者はタイムスタンプを単に単調増加するシリアル番号として扱い、そのクロックとの必要な接続はありません。受信者の観点からは、タイムスタンプはシーケンス番号の上位ビットの論理的拡張として機能しています。

受信者アルゴリズムは、タイムスタンプクロックの周波数にいくつかの要件を課します。

タイムスタンプクロックは「遅すぎて」はいけません。

送信される231バイトごとに少なくとも1回ティックする必要があります。実際、送信者にとってラウンドトリップタイミングに役立つためには、クロックはウィンドウ分のデータごとに少なくとも1回ティックする必要があり、RFC-1072ウィンドウ拡張を使用しても、231バイトは少なくとも2つのウィンドウである必要があります。

これをより定量的にするために、1 tick/secより速いクロックは、約8 Gbpsのリンク速度で古い重複セグメントを拒否します。1msタイムスタンプクロックは、最大8 Tbps (8*10**12) bpsのリンク速度で機能します。

タイムスタンプクロックは「速すぎて」はいけません。

そのリサイクル時間はMSL秒より大きくなければなりません。クロック (タイムスタンプ) は32ビットであり、最悪の場合のMSLは255秒であるため、最大許容クロック周波数は59 nsごとに1ティックです。

ただし、アイドル接続での古いタイムスタンプを処理するため (セクション4.2.3を参照)、およびシーケンス番号の折り返しを防ぐためのMSL要件を緩和するために、はるかに長いリサイクル期間を確立することが望ましいです。1 msタイムスタンプクロックを使用すると、32ビットタイムスタンプは24.8日で符号ビットを折り返します。したがって、MSLが24.8日以下の場合、同じ接続上の古い重複を拒否します。これは非常に安全な数値であると思われます。ゲートウェイシステムは、IP層のTTL値による正確なMSL実施を必要とせずに、24.8日以上のMSLをおそらく想定できます。

これらの考慮事項に基づいて、1ティックあたり1 msから1秒の範囲のタイムスタンプクロック周波数を選択します。この範囲は、再送信タイマーの粒度、たとえば数十または数百ミリ秒よりもはるかに高い解像度を必要としないRTTMメカニズムの要件にも一致します。

PAWSメカニズムは、送信者のタイムスタンプクロックに強い単調性要件も課します。この要件を満たすためのタイムスタンプクロックの実装方法は、システムのハードウェアとソフトウェアに依存します。

  • 一部のホストには、ハードウェアリセット間で単調であることが保証されているハードウェアクロックがあります。

  • クロック割り込みを使用して、バイナリ整数を定期的に1ずつインクリメントすることができます。

  • タイムスタンプクロックは、可変オフセット値を追加することによって、突然変更される可能性のあるシステムクロックから派生させることができます。このオフセットはゼロに初期化されます。新しいタイムスタンプクロック値が必要な場合、オフセットは必要に応じて調整され、新しい値が前の値 (この目的のために保存された) 以上になるようにします。

4.2.3 古いタイムスタンプ​

接続が十分に長くアイドル状態のままで、他のTCPのタイムスタンプクロックが符号ビットを折り返す場合、TS.Recentに保存された値は古くなりすぎます。その結果、PAWSメカニズムはすべての後続セグメントを拒否し、接続を凍結します (タイムスタンプクロックが再び符号ビットを折り返すまで)。

選択されたタイムスタンプクロック周波数の範囲 (1秒から1 ms) で、符号ビットを折り返す時間は24.8日から24800日の間になります。24日以上アイドル状態であった後に活動するTCP接続は非常に異常です。ただし、原則として、TCP接続のライフタイムに制限を設けることは望ましくありません。

したがって、PAWSの実装には、接続が24日以上アイドル状態のときにTS.Recent値を「無効化 (invalidate)」するメカニズムを含める必要があります。(古いタイムスタンプの問題の代替解決策は、非常に低いレートでキープアライブセグメントを送信することですが、それでもタイムスタンプの折り返し時間よりも頻繁に、たとえば1日に1回です。これはごくわずかなオーバーヘッドしか課しません。ただし、TCP仕様にはキープアライブが含まれたことがないため、無効化に基づく解決策が選択されました。)

TCPは他のTCPの周波数、したがって折り返し時間を知らないため、最悪の場合を想定する必要があることに注意してください。TS.Recentの有効性は、基本的なPAWSタイムスタンプチェックが失敗した場合、つまりSEG.TSval < TS.Recentの場合にのみチェックする必要があります。TS.Recentが無効であることがわかった場合、タイムスタンプチェックの失敗に関係なくセグメントが受け入れられ、ルールR3は新しいセグメントのTSvalでTS.Recentを更新します。

接続がアイドル状態であった期間を検出するために、TCPはTS.Recentが更新されるたびに、たとえば接続に関連付けられたクロックまたはタイムスタンプ値を更新できます。詳細は実装に依存します。

4.2.4 ヘッダー予測​

「ヘッダー予測 (Header prediction)」 [Jacobson90a] は、高速リンクに最も重要な高性能トランスポートプロトコル実装技術です。この技術は、最も一般的なケース、つまりセグメントを正しく順番に受信する場合のコードを最適化します。ヘッダー予測を使用すると、受信者は「このセグメントは次のシーケンスですか?」という質問をします。この質問は、「このセグメントはウィンドウ内にありますか?」という質問よりも少ない機械命令で答えることができます。

タイムスタンプ手順にヘッダー予測を追加すると、到着するTCPセグメントを処理するための次の推奨シーケンスになります。

タイムスタンプをチェックする (上記のステップR1と同じ)

ヘッダー予測を実行する。セグメントが次のシーケンスであり、追加の処理を必要とする特別な条件がない場合は、セグメントを受け入れ、そのタイムスタンプを記録し、H3をスキップします。

RFC-793で指定されているように、セグメントを通常どおり処理します。これには、ウィンドウの外側にあるセグメントを破棄し、おそらく確認応答を送信すること、およびウィンドウ内のシーケンス外セグメントをキューに入れることが含まれます。

別の可能性は、ステップH1とH2を入れ替えることです。つまり、ヘッダー予測ステップH2を最初に実行し、ヘッダー予測が失敗した場合にのみH1とH3を実行します。これは、ステップH1のタイムスタンプチェックが失敗する可能性が非常に低く、有限フィールドでの区間演算を必要とする比較的高価な操作であるため、パフォーマンスの向上になる可能性があります。すべてのセグメントに対してこのチェックを実行することは、ヘッダー予測の哲学に反しています。この変更により、高速ネットワークでのTCPプロトコル処理のCPU時間が最大5〜10%削減される可能性があると考えています。

ただし、H2を最初に置くと危険が生じます。過去2**32バイトのセグメントが正確に間違った時間に到着し、ヘッダー予測ステップによって誤って受け入れられる可能性があります。次の推論 [Jacobson90b] が導入され、この失敗の確率が無視できることを示しています。

すべてのセグメントが古い重複として現れる可能性が等しい場合、古い重複が左ウィンドウエッジと正確に一致する確率は、最大セグメントサイズ (MSS) をシーケンス空間のサイズで割ったものです。この比率は2**-16未満である必要があります。MSSは216未満である必要があるためです。たとえば、FDDIリンクの場合は (212)/(232) = 2-20になります。ただし、セグメントが古いほど、インターネットに保持される可能性は低くなり、セグメントのライフタイムの合理的なモデルでは、左ウィンドウエッジで正確に古い重複の確率は2**-16よりもはるかに小さくなければなりません。

16ビットTCPチェックサムは、2**16分の1の基本的な信頼性の低さも許容します。信頼性がTCPチェックサムの信頼性を超えるプロトコルメカニズムは、「十分に良い (good enough)」と見なされるべきです。つまり、全体的なエラー率に大きく寄与しません。したがって、タイムスタンプをチェックする前にヘッダー予測を実行することによって古い重複が受け入れられる問題を無視できると考えています。

ただし、この確率的議論は普遍的に受け入れられておらず、現在のコンセンサスは、一般的なケースではパフォーマンスの向上が危険を正当化しないというものです。したがって、H2はH1に従うことが推奨されます。

4.3 接続の以前の実体からの重複​

PAWSメカニズムは、高速接続でのシーケンス番号の折り返しによるエラーに対して保護します。同じ接続の以前のインカーネーションからのセグメントも、古い重複エラーの潜在的な原因です。どちらの場合も、このようなエラーを防ぐTCPメカニズムは、インターネット (IP) 層による最大セグメントライフタイム (MSL) の実施に依存します (詳細な議論についてはRFC-1185の付録を参照してください)。シーケンス空間の折り返しの場合とは異なり、以前のインカーネーションからの古い重複エラーを防ぐために必要なMSLは、転送速度に依存しません。IP層がTCPの推奨2分MSLを実施し、TCPルールが守られている場合、ネットワーク速度がどれほど高くても、TCP接続は以前のインカーネーションから安全です。したがって、このケースではPAWSメカニズムは必要ありません。

それでも、PAWSメカニズムが以前の接続からの古い重複に対して追加のセキュリティを提供できるかどうか、つまりIP層によるMSLの実施を緩和できるかどうかを尋ねることができます。付録Bはこの質問を探求し、PAWSを超えたさらなる仮定および/またはメカニズムが必要であることを示しています。これは現在の拡張の一部ではありません。