だいぶ昔にnwr.jpに置いておいたネタの再掲です。
補数
数学的な準備をします。
$x$の補数$y$とは、ある基準となる数$C$があって、$x+y=C$になるような数を指します。本来これなんですが、もう少し広い使い方があって、$C=b^n$、すなわち$b$進数の$n$桁を表現するようなケースであれば$b$の補数と呼びならわすことがあります。
「2の補数」とよぶようなケースがこれで、桁数が明らかな場合には省略してこう呼ばれるわけです。
これと同じく「1の補数」は、実際には基準となる数が$C=2^n-1$であります。
結果、足したら$1....0 (0がn個)$となるのが「2の補数」、$1...1 (1がn個)$となるのが「1の補数」です。
計算
近年普通の計算機は、加算器がそのまま使えるという理由から2の補数を使用することが多い(というよりほかのものを見たことが無い)ですね。とすれば2の補数の計算から1の補数の計算を導けたらラクですよね。
実のところ、オーバーフローが起こらない範囲では2の補数の足し算も1の補数の足し算も同じ値を返します。なのでオーバーフロー、すなわち$C_1=b^n-1=65535$を超えたときにどうするかを考えるとよいわけです。
これは$65535+1$を考えるとよいでしょう。$C_2=65536$を基本の数とする2の補数の場合、$0$を与え"carry"ビットを立てる、というのが16ビット計算機の動作です。ところが
65535+0=C_1=65535
ですから、実は$65535$は$-0$なので、計算結果には$1$が欲しいことになります。昔の人は知っていました。これはキャリービットをそのまま足しこめばよい、と( RFC1071 )。答え書いてあるやないかー!
今では32ビット計算機も普及してきましたので、carryビットをいちいち足しこまなくても、最後に上半分の16ビットを足して結果を得る、でかまわなくなっています。
1の補数の性質(あとでつかう)
RFC1071の計算で1の補数の和を取るとき、$0$に$0$を足すと$0$になりますが、じつはこれ以外のケースでは$0$になりません。
2つの16ビット数の和の最大は $65535+65535=131070$ですが、これは"carry"+$65534$ですから、RFC1071に従ってcarryを足しこんでも$65535$です。
IPヘッダ
IPの形式はRFC791にあります。
IPv4のヘッダの形式書こうと思ったら Markdown では書けないんですね
| \ | 0 | 1 | 2 | 3 | ||||||||||||||||||||||||||||
| 0 | Version | Length | ToS | Length | ||||||||||||||||||||||||||||
| 4 | Id | Flags | Fragment offset | |||||||||||||||||||||||||||||
| 8 | TTL | Protocol | Checksum | 12 | Source IP Addrss | |||||||||||||||||||||||||||
| 16 | Destination IP Address | |||||||||||||||||||||||||||||||
こんな感じになっています。
| 名前 | 意味、値 |
|---|---|
| Version | IPプロトコルのバージョン、4で固定 |
| Length | IPヘッダの長さ(4バイト単位)、5 |
| ToS | Type of Service、パケットの優先度など |
| Length | パケットの長さ(ヘッダ込み) |
| Id | 送信元がばらけるように適当な値を入れる。重複監視等 |
| Flags | フラグ |
| Fragment offset | IPパケットが複数にバラされたとき、あとで1つのIPパケットに組み上げる。そのとき本パケットがどこに入るか |
| TTL | Time to live、ルータを通るたびに適当に増やされ、あまり多くなるとパケットは捨てられる。最低1秒に1増やす必要あり |
| Protocol | 上位層のプロトコル番号 |
| Checksum | ヘッダのチェックサム(1の補数) |
| Source IP Address | 送信元IPv4アドレス |
| Destination IP Address | 受信先IPv4アドレス |
この後ろにオプションヘッダと称する値がくっつくこともありましたが、ハードウェアで処理できないとかいう事情によりほとんど使われないままv6では廃棄処分にされました。(あらら)
また TTL がチェックサムに含まれるものですから、いちいちルータでチェックサムを書き換える必要があり面倒がられております (こちらは現行)。NATでも書き換えが必要なものですから、IPv6ではチェックサムが省略されました。どーせパケット転送でチェックしないといけませんですものね。
UDPヘッダ
UDPヘッダの形式はRFC768にあります。
| \ | 0 | 1 | 2 | 3 | ||||||||||||||||||||||||||||
| 0 | Source port | Destination port | ||||||||||||||||||||||||||||||
| 4 | Length | Checksum | ||||||||||||||||||||||||||||||
チェックサムはUDPパケットだけでなく、疑似ヘッダというものを作ってこれも足し合わせます。疑似ヘッダv4はこんなの。
| \ | 0 | 1 | 2 | 3 | ||||||||||||||||||||||||||||
| 0 | Source IP Address | |||||||||||||||||||||||||||||||
| 4 | Destination IP Addres | |||||||||||||||||||||||||||||||
| 8 | Zero | Protocol | Checksum | |||||||||||||||||||||||||||||
これもよく見るとフィールド全部が0にはなりません(protocolが0じゃない)。
UDPv4では、チェックサムに0が入っているときは、チェックサムは取られていないものとして取り扱われます。
今回はこのチェックサムのお話であります
1の補数
IPv4のチェックサムフィールドは、16ビットありますから、16ビットでの1の補数、上記で言えば$C=65535$の補数となります。
RFC791にはこう書いてあります:
The checksum field is the 16 bit one's complement of the one's
complement sum of all 16 bit words in the header. For purposes of
computing the checksum, the value of the checksum field is zero.
チェックサムフィールドを0にしておいて、16ビットで総和を(1の補数計算で)もとめ、さらにその1の補数を取ってチェックサムフィールドへ埋めよ。(で、その計算は [RFC1071] ("rfc-editor.org/rfc/rfc1071") に書いてあると) なお1の補数を取るのはビット単位のnotを取るのと一緒です。
ゼロの扱い
さきほどこそっと示した通りですが、IPv4ヘッダは0ではありません(Vers=4)ので、総和が0になることはありません。すなわちchecksum fieldがオール1になることは無いわけです。
UDPv4でも同じなわけですが、ここでUDPv4のときchecksum fieldが全部0のときはチェックサムは無効と言いました。ならば総和の結果が65535の時はどうするの? というと、実はオール1を埋めておけ、というルールになっております。これにより計算結果が無いときと結果がアレなときの衝突が避けられているわけです。
まとめ
RFC791をみると、
This is a simple to compute checksum and experimental evidence
indicates it is adequate, but it is provisional and may be replaced
by a CRC procedure, depending on further experience.
CRCとかも検討対象じゃね? とか書いてありますが、実際にはチェックサム自体が消失したのは
すべての卵を１つのかごに入れよ、ただし本当に丈夫なかごを作ってから
という業界ことわざを思い出します。
以上です。