Fast, Memory-Efficient Traffic Estimation by Coincidence Counting

We consider the problem of fast estimation of flow rates in backbone network links with possible millions of flows. Accurate flow rate estimation is necessary for network traffic management, network planning, measuring compliance to service level agreements, and network security. Ideally, a rate estimation shceme should have short estimation times with provable bounds on estimation error, be low in memory usage, and be easily implementable in hardware for operation at high speeds. We develop such a scheme, and achieve up to two orders of magnitude speed-up in estimation time over the previously proposed two-runs-based RATE scheme [5].