トラフィック測定のためのサンプリング技術についてまとめる（Sample and Hold法）

はじめに

ネットワークトラフィック測定技術、ストリーミングアルゴリズムに興味があり色々と調べているのですが、今回はサンプリング技術についてまとめようと思います。
その中でも、2002年に発表されたSample and Hold法を提案している論文[1]を読んだので手法部分にフォーカスしてまとめます。
一部数式の記号を変更している箇所がございます。また、認識に誤りがある箇所がございましたらご指摘いただけますと幸いです。可及的速やかに訂正いたします。

[1] Cristian Estan and George Varghese, (2002). “New Directions in Traffic Measurement and Accounting.” In Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM, pp. 323–336, New York, NY, USA: Association for Computing Machinery.

論文のURLはこちらになります（フリーアクセスです）。
https://dl.acm.org/doi/10.1145/633025.633056

トラフィック測定とサンプリング技術

単純なトラフィック測定方法

ネットワークトラフィックの様態を知るためその特徴量を正確に把握することが求められます。その際、監視対象をフロー単位でまとめることが一般的です。

フローとは、通信の同一性を区別するために用いられる情報です。一般的には「送信元IPアドレス」「宛先IPアドレス」「送信元ポート番号」「宛先ポート番号」「プロトコル（IPヘッダ）」の5つの組で表現されます。

フロー情報で通信の同一性を区別できるので、フロー単位でトラフィックを監視して、単位時間ごとにその出現回数をカウントすれば、ネットワークトラフィックのパケットレートやエントロピー値などの特徴量を計算することができるようになります。なお、次のインターバルに移った時にはカウンタの値はクリアします。

単純な方法での問題点

しかしながら、ネットワークトラフィックの流量は大規模かつ高速であるため、単純な方法で実装してしまうと次のような問題点が発生します。

メモリ消費量の問題：出現回数を数えるということはメモリにフロー用のカウンタ（連想配列が主）を用意する必要があります。IPアドレスは理論的に $2^{32}$ 種類あることを考えればフローの種類数は膨大であり、出現回数も非常に多いことが予想されるので、メモリを大量に消費する可能性があります。
スケーラビティの問題： １パケット到着するたびにフローの出現回数を更新していくという方法では、単位時間あたりのメモリアクセス回数が膨大に増加してしまい、大量にトラフィックが到着したときに対応できなくなる可能性があります。

サンプリング法

メモリアクセス回数増加とメモリ消費量という課題に対して、サンプリング法が利用されています。サンプリング法を利用したものとしては、NetFlowなどが有名です。

サンプリング法では、サンプリングしたパケットのみを利用してフローの出現回数をカウントします。これにより処理対象となるフロー数が制限されることになりメモリ消費量を小さくできる可能性があります。また、サンプリングされたフローに関してだけメモリ中のカウンタを更新するため、通常の方法に比べてメモリアクセス数も少なくなります。

サンプリング法では単位時間（あるいはバイト数）ごとに、所与の確率 $p$ （=サンプリングレート）で、その間に到着したパケットそれぞれについてサンプリングするかどうか決めます。パケットのサンプリングに成功した場合は、パケットのフロー情報を取り出しそのフローに対応するカウンタ（以降フローカウンタ）を作ります。すでにフローカウンタが作られている場合は、出現回数を加算します。サンプリング処理を繰り返していって、フローカウンタを更新していくことで、フローごとの出現回数を算出します。

しかし、当然ながらサンプリングされたパケットのみを監視対象としてカウントしていくので、出現回数の推定値の誤差が大きくなることが予想されます。

Sample and Hold法

Sample and Hold法はサンプリング法の長所はある程度残しつつ、推定精度を向上させるために考案されました。
それでも推定精度にはまだ難はあり、同論文で別の手法も提案されていますが、実装が単純でリソースの消費量も少ないという点が利点です。

Sample and Hold法はサンプリング法と同じく所与のサンプリングレート $p$ でパケットを取得するのですが、その前にエントリが存在しているかどうかを確認します。
そして、フローカウンタが存在する場合は、サンプリングレートに関係なくパケット情報を取得し、対応するエントリを更新します。
フローカウンタが存在しない場合は、通常のサンプリング法と同様の処理を行います。

その違いについて直感的に捉えてみると、単純サンプリング法はすべてをサンプリングするので、真の出現回数との差が大きくなってしまう可能性があります。
一方、Sample and Hold法は一度サンプリングされたフローに関してはそれ以降取りこぼすことがないため、正確性が増します。ただしメモリアクセス回数はサンプリング法に比べて増加することがあります。

Sample and Hold法の理論的エラー率

論文では、その精度についても分析をしています。まずはフロー数の推定精度、そしてフローの観測成功確率をご紹介します。

フロー数についての推定精度

まずはフローの出現回数についての推定精度です。あるフローの実際の出現回数を $s$ 、Sample and Hold法による推定出現回数を $c$ として、その推定誤差を $\sqrt{E[(s-c)^{2}}]$ という式で評価することにします。

このSample and Hold法では一度でもサンプリングされれば情報をずっと保持します。つまり、推定出現回数 $c$ であるということは、本来 $s$ 回観測されるはずだったがそれまでに $(s-c)$ 回サンプリングに失敗したということになります。

成功するまでに $x = (s-c)$ 回サンプリングを失敗した場合を考えると、このときの確率を $(1-p)^{x}p$ という式で表すことができます。

このとき $x$ は幾何分布（Geometric Probability Distribution）に従い、それぞれ期待値 $E[x] = \frac{1}{p}$ 、分散は $Var[x] = \frac{1-p}{p^{2}}$ 、標準偏差は $SD[x] = \frac{\sqrt{1-p}}{p}$ となります。

ここで一般的な分散の定義式を変形すれば、二乗誤差の期待値 $E[x^{2}] = V[x] + E[x]^{2}$ となるので、

$E[x^{2}] = V[x] + E[x]^{2} = \frac{1-p}{p^{2}} + \frac{1}{p^{2}} = \frac{2-p}{p^{2}}$

したがって、

$\sqrt{E[(s-c)^{2}}] = \frac{\sqrt{2-p}}{p}$ となります。

観測成功率

メモリ容量的にフローテーブルを持てる数に限りがある場合を考えます。限りがあるということは、フロー数が多すぎると新規にフローテーブルを作れなくなるため、出現回数を全くカウントできないフローが存在する可能性があります。

ここからは、論文に示されている例示を紹介します。

ある測定期間中に、メモリ許容量を1%超える数のフローで構成されたトラフィックが流入してきたとし、その1%のフロー数は最大で100あるとします。
この時確保されるであろうフローカウンタは、100%のフロー数が10,000だとすれば、直感的には10,100必要になるはずです。
しかしここでは、フローメモリの限界が10,000だとします。トラフィックがメモリ許容量を超えている時のフローの観測成功率を考えます。

フローカウンタ数は10,000に抑えたいため、もしトラフィックのデータ量が $B$ バイト到着するときは、サンプリングレート $p=10,000/B$ に設定します(この例、というより論文全体では単位バイト数ごとにパケットのサンプリングを行います)。これで多くの場合は10,000種類のフローだけが取得されるようになります。

この時、メモリ許容量を1%超えるフローを $F$ として、その観測成功率を求めます。サンプリングレートが $10,000/B$ であることを考えると、
$F$ は $B/100$ バイト以上は送信されていることになります。（ $B$ の1%）。

この $F$ が全くサンプリングされない確率を考えると、 $(1-10000/B)^{B/100}$ となります。
この値は、 $B/100 = B^{\prime}$ とおけば、 $(1-10000/B)^{B/100} = (1-100/B^{\prime})^{B^{\prime}}$ と変形できます。

これを $\displaystyle \lim_{x \to \infty} \left( 1+\frac{x}{n} \right)^{n} = e^{x}$ と照らし合わせてみると、

$(1-100/B^{\prime})^{B^{\prime}} \approx e^{-100}$ となります。この100は、先程から考えている、メモリの許容量を1%超えたフロー数 $F$ と一致します。

つまり、メモリ許容量を超えたたために全くサンプリングされない確率は、そのはみ出ているフロー数を $f$ とすると、 $e^{-f}$ で近似することができます。
すなわち、メモリの許容量を超えているトラフィックが到着した際に、許容量を超えているフロー数 $f$ についてフローカウンタが存在する確率は $1-e^{-f}$ で近似できます。

では、 $F$ の5%のフロー数（5つ）が送信された時、それに対応するフローカウンタが存在する確率を確認します。

全くサンプリングされない確率は $e^{-5}$ で近似できるということなので、 $1-e^{-5}$ となり、フローカウンタが存在する確率は99%を超えることになります。

（自分の）TODO

※この章は論文著者が示した今後の課題ではなく自分のやり残したことを書いています。

単純な方法では色々と不都合があるので、同論文ではSample and Hold法以外にもMultistage Filter法という手法を考案しています。
また、これらの2つの手法をさらに改善する方法として、3つの工夫にも言及しています。

この記事はSample and Hold法単体に目を向けたものですので、これらについては別の記事でまとめようと思います。

まとめ

単純に実装してしまうとメモリ消費量とメモリアクセス回数が膨大になり処理効率が悪くなってしまいます。これを解決するためサンプリング法によって計算対象となるパケット数を減少させる方法が利用されています。

一方、サンプリング手法も推定精度に難があります。そこで推定精度を改善するため、一度サンプリングされたフローはその後常にカウント対象とするSample and Hold法が考案されました。

理論的な推定誤差・メモリ許容量を超えた時にフローカウンタが存在する確率については、論文に詳細に書かれた例示と数式をもとに自分なりにまとめました。

実証実験などの詳細については論文をご覧ください。
（ブログで詳細に正確に書こうとするともはや翻訳のようになり、著作権的にまずいのではないか…というのと、正直しんどいというのとがあります）。

勉強に利用した文献

T. H. Cormen, C. E. Leiserson, R. L. Rivest, (1992). Introduction To Algorithms 1st Edition, MIT PRESS, （T.H. コルメン，C. E. ライザーソン，R. L. リベスト　浅野哲夫，岩野和生，梅尾博司，山下雅史，和田幸一（共訳）（1995）. 『アルゴリズムイントロダクション［第１巻］数学的構造とデータ構造』　近代科学社　初版）
※図書館で借りたんですが丁寧に書いてあってめちゃくちゃわかりやすかったです。