Sampling for the Flow Size Distribution

In high speed network measurement, such as in core Internet routers, there may only be a few nanoseconds available per packet for measurement purposes. Our objective is to be able to accurately measure the flow size distribution, that is the number of packets that belong to the same data transfer (think TCP connection), in such an environment.  The flow size distribution is an important metric for traffic managment, profiling, and security purposes.

Two paradigms are available to cope with the tight resources constraints: sampling  (cut down the amount of input packets to measure), and sketching (insert packets into a small memory data structure allowing fast updates, but imperfect recording). We compare and contrast these, and introduce a hybrid `skampling' method, OFSS, which combines sampling and sketching in an optimal way.  We use the well known concept of Fisher Information from estimation theory to evaluate its fundamental information gathering power. We also revisit an existing technique, the `Eviction Sketch', define an optimized version of it, and compare and constrast with OFSS.