Ethernet上のTCP/IPで、間違ったパケットを検知できない確率。cognitionCognitiveはよいぞ。2012-07-05Ethernet上のTCP/IPで、間違ったパケットを検知できない確率。未分類TweetTwitterの140文字に慣れてしまっていましたが、ブログの重要性を再認識している今日この頃のみかんさんです。TCP/IPでは転送されたデータの信頼性を保つためにchecksumを持っていますが、この値が「偶然」一致してしまいデータが欠損してしまう確率はどの程度でしょうか?http://q.hatena.ne.jp/1255666844この記事の回答が気になったので計算してみましょう。チェックサムってなに?まずはみんな大好きWikipediaとe-Words。簡単に説明すると、(元のデータの正しさを)チェック(するための)サム(合計値)です。つまるところ、「データの正しさを証明するためのデータ」です。いう、1か0が10個というデータがあったとしましょう。これに1が5個と0が5個あるとして、送信元のコンピュータが(1505)という証明データをつけたとしましょう。この場合、元のデータが20文字なのに対して、4文字の証明データをつけることになり、実際には25文字のデータが受信側に届くことになります。このように、データは1と0で構成されていて、その数をカウントする証明データをつける、20文字のデータと4文字の証明データを送信する(受信する)というのはお互い事前に知っている取り決め(プロトコル)とします。1406)というデータを送信します。1406)というデータが届きました。受信側では何が届くかなんてわからないんで、「うーん、このデータは正しいかな?」と確かめる必要があるわけです。正しいデータを受信したとき。1406)ということは・・・1が4個0が6個・・・うむ、あってる!」と判断できるわけです。次に間違ったデータを受信したとき。1406)というデータを受信したとしましょう。この場合、受信側は「1が3個、0が7個あれ?4個と6個のはずなのに合ってないぞ?間違ってるなあ・・・送り直してもらうかあ」と思うわけです。1406)となったらどうなるでしょうか?この場合、受信者は「えっと1と0がいくつだ・・・間違ってないな。オッケーオッケー!」となっちゃうわけです。(補足ですが、証明データのほうでエラーが出た場合も間違ってると認識できますし、元データと証明データ両方にエラーが出て、その個数が偶然一致した場合はエラーと見えないわけですね。)これが本題の質問です。TCPでこの仕事をしているのがTCPのChecksumフィールドで用いられている1の補数、Ethernetでこの仕事をしているのがCRCです。CRCとはなんじゃらほいってことで今から見ていきましょう。1の補数ってなに?まずはWikipedia。checksumでも扱われている16bitの数字で表現することにしましょう。-32767へと1減るごとに1減ります(負の数で言えば数字は増える)。(便宜上+0と-0と表示させてもらってます。)これだと、すべてのビットを反転(0→1、1→0)すると、正の数と負の数を入れ替えることができます。0と32767の例を見て頂くと丁度逆になっていますね。これの何がうれしいかというと、こちらのサイトをご覧ください。1の補数演算http://4049.nwr.jp/comp/ip_csum.html大体このサイトに乗っているので、やる気のある方は是非見てください。要約すると・・・チェックサムはヘッダなどの合計だが、0(0x0000)になることはあり得ない計算方法が単純なので機械で計算するのが高速チェックサムを計算するデータはいくら長くてもいい以上の性質を持っているので、TCPのチェックサムにはこの1の補数で計算をして、チェックするデータを付加しています。次にCRCを見てみましょう。CRCってなに?何はともあれみんな大好きWikipediaとe-Words。Check、巡回冗長検査)とは、先の説明のように、ミスがあったのを検知、検出する(太字で書くぐらい重要)ものです。言っても、文章ではわかりづらいと思うのでこちらのサイトをどうぞ。http://jp.fujitsu.com/platform/server/unix/term/crc/#気が向いたらノートに概念図を書いて追記します・・・なぜCRCがいいかというと、この計算は、計算機的には非常に早く実現できるからです。2進数の割り算というのは非常にパソコンさんには都合がいいのです。以上で説明が終わりましたが、この二つの方法というのは、どれくらいの確率で「偶然一致」するのでしょうか。一致する確率さて、以上で各々の解説は終わりです。その確率を計算しましょう。3.イーサネットのフレーム・フォーマットhttp://www.atmarkit.co.jp/fwin2k/network/tcpip007/tcpip03.html上記を見て頂くと、イーサネットでは4オクテット(1オクテットは8bit)なので、チェックサムの大きさは32bitです。そのため、チェックサムは4,294,967,296通り≒約43億分の1の確率で同じものとぶち当たります。Corruptionで述べられているように、単純に考えると、TCPチェックサムは16bitなので、衝突する確率は2^16=65,536通り≒約6万5千分の1となります。ぶっちゃけデータサイズわかってるんだからこの二つの項って引用要らないよね(※あくまでチェックサムで算出される値に"偏りが無い"場合なので、そういう統計的な偏りがある場合は確率は変わってきます・・・そこまで示した論文があれば教えてください)ということで、この二つのチェックをかいくぐるにはこの二つの事象を同時にクリアするということなんで、4,294,967,296×65,536=2.81474977×10^14≒280兆分の1となるはずですね。これが質問の答えになります。・・・で終わるとおもしろくないですよね。後日、実際のTCP通信でどのような、どれくらいのエラーが起こっているのかについて、またブログを書きます。22:29Ethernet上のTCP/IPで、間違ったパケットを検知できない確率。LinuxOSで日本語が入力できなくなったら。ライセンスと取得方法が変...ブログ納め。転職に1年1ヶ月かかった元SIerの失業保険とかの話。ロゴ運用についての疑問(と、支援士会...転職活動の結果、内定を貰ったので戦略の見直しについて書く。月別アーカイブプロフィールid:kitkatayama主に格闘ゲーム、翻訳、ITのことを書いている人。読者になるはてなブログをはじめよう!kitkatayamaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。