Design principles and algorithms for effective high-speed IP flow monitoring

In this paper, we present design principles and related implementation experience for building effective and scalable IP flow monitoring systems. We focus on the monitoring of high-speed links, where the short packet inter-arrival time and the huge number of simultaneous flows impose a number of challenging requirements. First, the small inter-arrival times imply that algorithms for packet attribution to flows must be fast and efficient. To this purpose, an appropriate model for hash-based packet classification is proposed. Second, also the update of per-flow information must be fast, which suggests that fast memories are needed in order to avoid that memory access becomes the system bottleneck. But fast memories are still expensive and small, while the number of simultaneous flow in high-speed links is large. Therefore, the need arises to introduce strategies that help in keeping memory requirements low: one of these is the fast identification of timed out flows. Finally, identifying and periodically reporting information about long-lived flows receiving a lot of traffic is of paramount importance for those applications that cannot simply wait for the termination of these flows to receive the corresponding information.We provide design principles and algorithms that can be applied to all these tasks. A comparative study of some of them is carried out and performance figures are obtained using significant metrics.