A Resource-minimalist Flow Size Histogram Estimator

The histogram of network flow sizes is an important yet dif-ficult metric to estimate in network monitoring. It is im-portant because it characterizes traffic compositions and is a crucial component of anomaly detection methods. It is difficult to estimate because of its high memory and com-putational requirements. Existing algorithms compute fine grained estimates for each flow size, i.e. 1, 2,... up to the maximum number observed over a finite time interval. Our approach instead relies on the insight that, while many ap-plications require fine grained estimates of small flow sizes, i.e. {1, 2,..., k} with a small k, network operators are of-ten only interested in coarse grained estimates of larger flow sizes. Thus, we propose an estimator that outputs a binned histogram of size distributions. Our estimator computes this histogram in O(k3 + logW) operations, where W is the largest flow size of interest to the network operator, while requiring only a few bits of memory per measured flow. This translates into more than 4 fold memory savings and an ex-ponential speedup in the estimator as compared to previous works, greatly increasing the possibility of performing on-line estimation inside a router. 1