パケットサンプリングの基礎知識
Peter Phaal and Sonia Panchen, sFlow.org
[注]本資料は ”Packet Sampling Basics”(http://www.sflow.org/packetSamplingBasics/index.htm) について翻訳およびコメントを加えものです。翻訳およびコメントについては無保証ですので、内容に関しては必ず原典を参照してください。
始めに
パケットサンプリング方法はネットワークトラヒックの特徴化に広く用いられている。パケットサンプリングはサンプリング時に乱数性を活用しており、これは定期的なパターンをもつトラヒックと同期してしまうことを避けるためである。通常はパケットN個対して一つのパケットのキャプチャと解析を行う。
パケットサンプリングは100%正確な結果を教えてくれないが、定量化できる精度を与えてくれる。本論では例と計算結果の基本的なテクニック、およびパケットサンプルしたデータの計算処理時における精度の定量化について述べる。
例
100万パケットのネットワーク転送を想定する。うち0.25%(2500パケット)をランダムにサンプルする。その中で、もし1000パケットが特定クラス[1]のトラヒックとして音声トラヒックであったとすると、100万パケットのうちどれほどが本当に音声パケットだろうか? 少なくとも、1000パケットは必ず音声パケットであり、もちろんこれらはすでにサンプルされた中にあるからである。考えられる最大の音声パケット数は998,500パケットであり、なぜならサンプル済の1500パケットは非音声パケットであったためである。しかしながら、この2つの値[2]はありそうではない。全体に占める音声パケットの比率はサンプル済の比率である40%(1000÷2500)とおそらく同じであろう。すなわち、40万フレーム[3]が音声パケットの最適な推定値となる。
一般的に、総パケット数をN、総サンプル数をn、サンプル内の特定のクラスに属するパケット数をc とすると、特定クラスに属する総パケット数 
は次の等式で推定できる。
数式 1 
もちろん、音声パケットがキッチリ40万であることはありえない。狭い範囲を特定する代りに、可能性の高い、たとえば95%ぐらいの実効値であるとする。この値が95%の確率で信頼できるとすると、実際の音声パケット数は381,000から419,000であろう。 [4]
次の式で
分散の推定値 
が計算される:[5]
数式 2 
の95%信頼区間は以下のようになる:[6]
別の表現方法としてパーセントで表すと、40万パケット±4.8%の音声フレームが送信される、または言い換えると最大の誤差は4.8%となる。
次の式は誤差率の推定式を単純化したものである:
数式 4 
この等式をグラフにしたものはc [7]が増加する毎にサンプリング精度が改善することを表している。
図 1相対的サンプリング誤差
例として、c=1000とすると誤差率は約6%である。
興味深いことに、計測精度はフレームの総数には依存せず、単純に計測に使用するサンプル数に左右されるのである[8]。この性質は非常に便利であり、とくに高速のスイッチやルータを計測するときに有利である。たとえば、低速のスイッチを計測する場合、たとえば平均トラヒックが400フレーム/秒に1つサンプルすると、そのサンプル率を0.25%となる。他方、同等の観測精度で高速スイッチを観測するなら、4万フレーム/秒に1つサンプルすればよく、そのサンプル率はたったの0.0025%である。
統計的なサンプリングが引きおこす結果が真値付近で大きく変化することがあるが、これは計測間隔が短いときやトラヒックが微量のときである。この現象は例で図示している[9]。
ここで想定するのは、音声トラヒックが毎秒1つ転送され、同トラヒックが1時間にわたって観測された場合である。すると1時間に3600個の音声パケットが生成される。サンプル率を0.25%とすると、約9個の音声パケットがサンプルされる。このケースの誤差率は65%である。この結果が意味は、推測される1時間の音声パケット数の範囲は1200～6000パケット[10]ということである。
精度を改善するには2つの方法がある。ひとつはサンプル率を上げることである。サンプル率を1%に上げた場合、約36個の音声パケットが1時間にサンプルされ、かつ誤差率は33%となり、期待できる毎時の推定値はより狭い範囲の2400～4800個[11]になる。注意すべきこととして、サンプル率を上げるとサンプルトラヒック量も増加し、かつ解析を行うために十分な性能が必要となることである。
もう一つの精度改善の方法はより長期にわたって観測することである。月単位の解析を同様のサンプル率0.25%で行うと約6700個の音声パケット[12]サンプルが期待される。これは誤差率がたった2.4%[13]となり、月間の音声パケット数の見積りは261万～274万パケット[14]となる。従って、週間や月間など長期間の観測に用いる、たとえばネットワーク利用率による課金などがあるが、これはより正確なデータが必要とされる。
ほとんどの場合でサンプリングはうまく機能する。多量のトラヒック元は短期で十分な精度が得られ、リアルタイムで効果的なトラヒック管理ができる。課金や収容計画などのアプリケーションの利用において、より十分な精度が求められるものは長期にわたってのデータ収集が行われることで妥当な精度になる。
理論
パケットサンプリングは二項分布にモデル化できる[15]。二項分布についての良い説明はYale大の統計学のWebサイト[16]にある。
二項分布が c の計量に関する振舞を記述するために、以下の条件を考える:
1. 観測される n は固定である。
2. 各観測はそれぞれ独立している。
3. 各観測では2つ("成功"か"失敗")のうち1つを示す。
4. 成功の確率 p は各観測ですべて同じである。
もしこれらの条件がそろうなら、c は nとp を引数とする二項分布に従う。次の2つの式は二項分布の平均と分散を示す[17]。
数式 5 
数式 6 
パケットサンプリングにおいて、母集団の割合は不明であるが(ここで、あるクラスに属するサンプルの出現確率をp とする)、我々はサンプル[18]における割合を観測する。ここで、"成功"した数を観測されたパケット数で割ると:
数式 7 
・P = サンプル中の割合
・c = あるクラスに所属するサンプル数(これを"成功"としてカウントする)
・n = 総サンプル数
Jedwabら[19]はあらゆるランダムパケットサンプリングにおいて条件4が満たされることを証明した。すなわち、あるグループの"成功"した 数c は、観測数が n、成功確率[20]がp の二項分布に従い、これはサンプル中の割合Pの分布に従うことが導かれる。
平均値について乗法の性質[21]により、Pの平均値の分布はc÷n の平均分布となる:
数式 8 
すなわちサンプルの割合P は母集団の割合pについて偏りのない推定量となりうる。
Pの分散は c÷n の分散に等しい。ある乱数の定数倍の分散について以下の等式が成立する:
数式 9 
従って:
もしサンプル数n が十分に大きければ、サンプル中の割合は平均pと 分散p(1-p)/n の正規分布におおよそ従い、これは中心極限定理により導かれる。
これらの近似を利用すると、p(母集団における割合)の最大数のみつもりは、サンプル中の割合Pとなる。かつ、サンプル数の分散は母集団割合の分散に関する偏りのない推定値となる:
数式 11[23] 
補足:除数は n でなく (n-1) となるが、これは我々が統計値を扱っているためであり、既知の分布よりも相応しい[24]。sci.math[25] のnewsにおける David Sealの投稿がより詳しい説明であろう。
しかしなら、我々は特定クラスの総フレーム数 を推定したときの分散に興味があるので、ここで以下を考える:
数式 12 
・N は総フレーム数
数式 13 
の95%信頼区間は以下になる[26]:
数式 14 
この区間を別の表現にするともっとも有用な値となる[27]:
数式 15 
単純化します:
数式 16 
一般に n>>c とすると、次式となる:
数式 17 
既出の等式はすべてパケットカウントの推定を扱っていた。しばしば有用となるのが、特定クラスのバイト数の見積りである。バイト数の推計は次式で簡単に計算される:
数式 18 
・
はクラス c の総バイト数
・
はクラス c における平均パケットサイズ
平均パケットサイズとパケットサイズの分散は以下で簡単に求められる:
数式 19 
数式 20 
ここで、2つの乱数を乗ずると、積の分散は以下の等式で得られる:
数式 21 
この等式を適用すると、は以下になる:
数式 22 
(以上)
Japanese translation and added some comments by Hirotaka Tajima.