Loading article…
多くのプロトコルとアルゴリズムでは、関連するエンティティのシリアル化または列挙が必要です。たとえば、通信プロトコルは、あるパケットが他のパケットの「前」に来るか「後」に来るかを知る必要があります。IETF (インターネット技術タスクフォース) RFC 1982は、これらのシーケンス番号を 操作および比較する目的で「シリアル番号の演算」を定義しようとしています。簡単に言うと、シリアル番号の絶対値が最大値の半分以上減少した場合 (たとえば、8 ビット値で 128)、それは前者の「後」にあると見なされ、その他の減少は「前」にあると見なされます。
このタスクは、ほとんどのアルゴリズムがシーケンス番号に固定サイズ (バイナリ) 表現を使用するため、一見するよりも複雑です。数値が非常に大きくなり、最後にもう一度増分されて最大数値範囲を「ラップ」する (大きな正の数から 0 または大きな負の数に瞬時に変わる) ときに、アルゴリズムが「破綻」しないようにすることが重要です。一部のプロトコルでは、問題が発生する前にプログラムが置き換えられる (または廃止される) ことを期待して、これらの問題を無視し、カウンターに非常に大きな整数を使用するように選択しています ( Y2Kを参照)。
多くの通信プロトコルは、スライディングウィンドウプロトコルの実装において、パケットシーケンス番号にシリアル番号演算を適用します。TCPの一部のバージョンでは、ラップされたシーケンス番号に対する保護（PAWS）を使用します。PAWSは、パケットのタイムスタンプに同じシリアル番号演算を適用し、タイムスタンプをシーケンス番号の上位ビットの拡張として使用します。[1]
シーケンス番号の操作
シーケンス番号への小さな正の整数の加算と 2 つのシーケンス番号の比較についてのみ説明します。符号なしバイナリ実装についてのみ説明します。任意のサイズのビットは RFC 全体 (および以下) で「SERIAL_BITS」として示されています。
追加
シーケンス番号に整数を追加するのは、単純な符号なし整数の加算であり、その後に符号なしモジュロ演算を実行して結果を範囲内に戻します (ほとんどのアーキテクチャでは、通常、符号なし加算では暗黙的に行われます)。
- s ' = ( s + n ) モジュロ 2 SERIAL_BITS
0 未満または 2 SERIAL_BITS−1 − 1 を超える値の追加は未定義です。基本的に、この範囲を超える値を追加すると、結果のシーケンス番号が「ラップ」し、多くの場合、元のシーケンス番号よりも「小さい」と見なされる番号になります。
比較
2 つのシーケンス番号i 1とi 2 (シーケンス番号s 1とs 2の符号なし整数表現)を比較する手段が提示されます。
等価性は単純な数値の等価性として定義されます。
比較のために提示されたアルゴリズムは複雑で、最初のシーケンス番号がその値の範囲の「終わり」に近いかどうかを考慮する必要があり、したがって、より小さい「ラップされた」番号は実際には最初のシーケンス番号よりも「大きい」と見なされる場合があります。したがって、i 1がi 2より小さいと見なされるのは、次の場合のみです。
- ( i 1 < i 2かつi 2 − i 1 < 2 SERIAL_BITS−1 ) または
- ( i 1 > i 2かつi 1 − i 2 > 2 SERIAL_BITS−1 )
不足点
RFC で提示されたアルゴリズムには、少なくとも 1 つの重大な欠点があります。比較が定義されていないシーケンス番号があります。多くのアルゴリズムは複数の独立した協力者によって個別に実装されるため、このような状況の発生をすべて防ぐことは不可能な場合がよくあります。
RFC 1982の著者は、 一般的な解決策を提示せずにこれを認めています。
不等式がこの驚くべき性質を持たないようにテストを定義することは可能だが、すべての値のペアに対して定義されるが、そのような定義は実装に不必要に負担がかかり、理解しにくく、次のようなケースも許容してしまう。
s1 < s2 かつ (s1 + 1) > (s2 + 1)これも同様に直感的ではありません。
したがって、問題のケースは未定義のままであり、実装はどちらかの結果を返すか、エラーをフラグ付けするかを自由に選択でき、ユーザーは特定の結果に依存しないように注意する必要があります。通常、これは特定の数値のペアが共存しないようにすることを意味します。
したがって、シーケンス番号のすべての「未定義」の比較を回避することは困難または不可能であることが多いです。ただし、比較的簡単な解決策があります。符号なしのシーケンス番号を符号付きの2 の補数算術演算にマッピングすることで、あらゆるシーケンス番号のすべての比較が定義され、比較演算自体が大幅に簡素化されます。RFC で指定されているすべての比較は、元の真理値を保持します。影響を受けるのは、以前に「未定義」であった比較のみです。
一般的な解決策
RFC 1982 アルゴリズムでは、Nビットのシーケンス番号の場合、2 N −1 − 1 個の値が「より大きい」とみなされ、2 N −1 − 1個 が「より小さい」とみなされると規定されています。残りの値 (正確に 2 N −1離れている) との比較は「未定義」とみなされます。
最近のハードウェアのほとんどは、符号付き2 の補数バイナリ算術演算を実装しています。これらの演算は、与えられたオペランドの値の範囲全体に対して完全に定義されています。Nビットのバイナリ数は 2 Nの異なる値を含むことができ、そのうちの 1 つは値 0 で占められるため、ゼロ以外の正の数と負の数すべてに奇数個のスペースが残ります。表現可能な負の数は正の数より 1 つ多いだけです。たとえば、16 ビットの 2 の補数値には、−32 768から+32 767 .
したがって、シーケンス番号を 2 の補数の整数として単純に再キャストし、「より大きい」と見なされるシーケンス番号の数より「より小さい」と見なされるシーケンス番号が 1 つ多いようにすれば、RFC で提案されている論理的に不完全な式の代わりに、単純な符号付き算術比較を使用できるはずです。
以下に、ランダムなシーケンス番号と値 0 のシーケンス番号を比較した例をいくつか示します (これも 16 ビット)。
符号なしバイナリ 符号付き
シーケンス値の距離
-------- ------ --------
32767 == 0x7FFF == 32767
1 == 0x0001 == 1
0 == 0x0000 == 0
65535 == 0xFFFF == −1
65534 == 0xFFFE == −2
32768 == 0x8000 == −32768
問題のシーケンス番号を「回転」させて、その 0 が比較するシーケンス番号と一致するようにすれば、シーケンス番号の符号付き解釈が正しい順序になっていることは簡単にわかります。これは、符号なし減算を使用して、結果を符号付き 2 の補数として解釈するだけで済みます。結果は、2 つのシーケンス番号間の符号付き「距離」です。もう一度言いますが、i1と がシーケンス番号s 1とs 2i2の符号なし 2 進表現である場合、 s 1からs 2までの距離は次のようになります。
距離= (符号付き)( i1 - i2 )
距離が 0 の場合、数値は等しくなります。距離が 0 未満の場合は、s 1はs 2より「小さい」または「前」になります。シンプルで、簡潔で、効率的で、完全に定義されています。ただし、驚きがないわけではありません。
すべてのシーケンス番号の演算は、シーケンス番号の「ラッピング」を処理する必要があります。RFC 1982シーケンス番号の用語では、数値 2 N −1は両方向に等距離です 。私たちの計算では、これらは両方とも互いに「小さい」と見なされます。
距離1 = (符号付き)( 0x8000 - 0x0 ) == (符号付き) 0x8000 == -32768 < 0距離2 = (符号付き)( 0x0 - 0x8000 ) == (符号付き) 0x8000 == -32768 < 0
これは、0x8000 の距離にある任意の 2 つのシーケンス番号に当てはまります。
さらに、2 の補数演算を使用してシリアル番号演算を実装すると、マシンの整数サイズ (通常は 16 ビット、32 ビット、64 ビット) と一致するビット長のシリアル番号が必要になります。20 ビットのシリアル番号を実装するには、シフトが必要です (32 ビット整数を想定)。
距離= (符号付き)(( i1 << 12 ) - ( i2 << 12 ))
参照
参考文献
- ^ RFC 1323: 「高パフォーマンスのための TCP 拡張」、セクション 4.2。