2012/07/05
Ethernet上のTCP/IPで、間違ったパケットを検知できない確率。

Twitterの140文字に慣れてしまっていましたが、ブログの重要性を再認識している今日この頃のみかんさんです。

TCP/IPでは転送されたデータの信頼性を保つためにchecksumを持っていますが、この値が「偶然」一致してしまいデータが欠損してしまう確率はどの程度でしょうか?

http://q.hatena.ne.jp/1255666844

この記事の回答が気になったので計算してみましょう。

チェックサムってなに?

まずはみんな大好きWikipediae-Words
簡単に説明すると、(元のデータの正しさを)チェック(するための)サム(合計値)です。つまるところ、「データの正しさを証明するためのデータ」です。
例えば、(10 10 10 10 10) という、1か0が10個というデータがあったとしましょう。これに1が5個と0が5個あるとして、送信元のコンピュータが(1505)という証明データをつけたとしましょう。
この場合、元のデータが20文字なのに対して、4文字の証明データをつけることになり、実際には25文字のデータが受信側に届くことになります。
このように、データは1と0で構成されていて、その数をカウントする証明データをつける、20文字のデータと4文字の証明データを送信する(受信する)というのはお互い事前に知っている取り決め(プロトコル)とします。
お断り:抽象的な話をしているので元データも証明データもビット列でも何でもないのでサイズは気にしないでください( ゚ω゚ ) 

送信側では、(10 10 10 10 00)というデータを送りたいので、「うん、1が4個、0が6個だな!」として、(1406)と証明データが計算されて、(10 10 10 10 00 1406)というデータを送信します。
さて、なんやかんやで(10 10 10 10 00 1406)というデータが届きました。受信側では何が届くかなんてわからないんで、「うーん、このデータは正しいかな?」と確かめる必要があるわけです。

まず正しいデータを受信したとき。「うん、(10 10 10 10 00 1406)ということは・・・1が4個0が6個・・・うむ、あってる!」と判断できるわけです。
次に間違ったデータを受信したとき。何かのエラーで(10 10 10 00 00 1406)というデータを受信したとしましょう。この場合、受信側は「1が3個、0が7個あれ?4個と6個のはずなのに合ってないぞ?間違ってるなあ・・・送り直してもらうかあ」と思うわけです。

ここで問題。
(10 10 10 10 00 1406)が、(11 10 10 00 00 1406)となったらどうなるでしょうか?
この場合、受信者は「えっと1と0がいくつだ・・・間違ってないな。オッケーオッケー!」となっちゃうわけです。
(補足ですが、証明データのほうでエラーが出た場合も間違ってると認識できますし、元データと証明データ両方にエラーが出て、その個数が偶然一致した場合はエラーと見えないわけですね。)

これが本題の質問です。TCPでこの仕事をしているのがTCPのChecksumフィールドで用いられている1の補数、Ethernetでこの仕事をしているのがCRCです。ではCRCとはなんじゃらほいってことで今から見ていきましょう。

1の補数ってなに?

まずはWikipedia。はい、わからないですね♪
説明するにあたって数字をどう表現するかを決めないといけないので、TCP checksumでも扱われている16bitの数字で表現することにしましょう。
(つまり、0000 0000 0000 0000 ~ 1111 1111 1111 1111の範囲、16進数なら 0x0000 ~ 0xFFFFまでです)
「1の補数」で扱う数というのは、正の数は0000 0000 0000 0000 → +0 ~ 0111 1111 1111 1111 → +32767 まで順番にカウントしていき、負の数は 1111 1111 1111 1111 → -0 ~ 1000 0000 0000 0000 → -32767へと1減るごとに1減ります(負の数で言えば数字は増える)。
(便宜上+0と-0と表示させてもらってます。)
これだと、すべてのビットを反転(0→1、1→0)すると、正の数と負の数を入れ替えることができます。0と32767の例を見て頂くと丁度逆になっていますね。

で、これの何がうれしいかというと、こちらのサイトをご覧ください。


IP のチェックサム -- 1の補数演算
http://4049.nwr.jp/comp/ip_csum.html

大体このサイトに乗っているので、やる気のある方は是非見てください。で、要約すると・・・

  • チェックサムはヘッダなどの合計だが、0(0x0000)になることはあり得ない
  • 計算方法が単純なので機械で計算するのが高速
  • チェックサムを計算するデータはいくら長くてもいい

以上の性質を持っているので、TCPのチェックサムにはこの1の補数で計算をして、チェックするデータを付加しています。
では、次にCRCを見てみましょう。

CRCってなに?

何はともあれみんな大好きWikipediae-Words
CRC(Cyclic Redundancy Check、巡回冗長検査)とは、先の説明のように、ミスがあったのを検知、検出する(太字で書くぐらい重要)ものです。

簡単に言うと、「元のデータとある決めた値のデータを2進数で割り算して余ったデータ」 です。
と言っても、文章ではわかりづらいと思うのでこちらのサイトをどうぞ。

http://jp.fujitsu.com/platform/server/unix/term/crc/

#気が向いたらノートに概念図を書いて追記します・・・

なぜCRCがいいかというと、この計算は、計算機的には非常に早く実現できるからです。2進数の割り算というのは非常にパソコンさんには都合がいいのです。
で、Ethernetの場合、 100 1100 0001 0001 1101 1011 0111 (0x04C11DB7) というのを使ってます。

以上で説明が終わりましたが、この二つの方法というのは、どれくらいの確率で「偶然一致」するのでしょうか

偶然一致する確率

さて、以上で各々の解説は終わりです。さて、その確率を計算しましょう。

連載:詳説 TCP/IPプロトコル 第7回 イーサネット(その2) イーサネットのフレーム構造 -- 3.イーサネットのフレーム・フォーマット
http://www.atmarkit.co.jp/fwin2k/network/tcpip007/tcpip03.html

上記を見て頂くと、イーサネットでは4オクテット(1オクテットは8bit)なので、チェックサムの大きさは32bitです。そのため、チェックサムは4,294,967,296通り≒約43億分の1の確率で同じものとぶち当たります。となります。

End-to-End Internet Packet Dynamics
https://cseweb.ucsd.edu/classes/wi01/cse222/papers/paxson-e2e-packets-sigcomm97.pdf
そして、TCPでは上記の3.3 Packet Corruptionで述べられているように、単純に考えると、TCPチェックサムは16bitなので、衝突する確率は2^16=65,536通り≒約6万5千分の1となります。ぶっちゃけデータサイズわかってるんだからこの二つの項って引用要らないよね

(※あくまでチェックサムで算出される値に"偏りが無い"場合なので、そういう統計的な偏りがある場合は確率は変わってきます・・・そこまで示した論文があれば教えてください)

ということで、この二つのチェックをかいくぐるにはこの二つの事象を同時にクリアするということなんで、4,294,967,296×65,536=2.81474977×10^14≒280兆分の1となるはずですね。これが質問の答えになります。

以上、気になったことはこれでおしまい、ちゃんちゃん♪

・・・で終わるとおもしろくないですよね。
後日、実際のTCP通信でどのような、どれくらいのエラーが起こっているのかについて、またブログを書きます。お楽しみに。



0 Comments | コメントを書く
Template Design: © 2007 Envy Inc.