Runs bAsed Traffic Estimator (RATE): A Simple, Memory Efficient Scheme for Per-Flow Rate Estimation

To reduce the measurement overhead, many previous papers have proposed the use of random sampling and this is also used in commercial routers (Cisco's NetFlow). Our goal is to develop a new scheme that has very low memory requirements and has quick convergence to within a pre-specified accuracy. We achieve this by use of a novel approach based on sampling two-runs to estimate per-flow traffic. (A flow has a two-run when two consecutive samples belongs to the same flow.) Sampling two-runs automatically biases the samples towards the larger flows thereby making the estimation of these sources more accurate. This biased sampling leads to significantly smaller memory requirement compared to random sampling schemes. The scheme is very simple to implement and performs extremely well.