Clock-like flow replacement schemes for resilient flow monitoring

In the context of a collaborating surveillance system for active TCP sessions handled by a networking device, we consider two problems. The first is the problem of protecting a flow table from overflow and the second is developing an efficient algorithm for estimating the number of active flows coupled with the identification of "heavy-hitter" TCP sessions. Our proposed techniques are sensitive to limited hardware and software resources allocated for this purpose in the linecards in addition to the very high data rates that modern line cards handle; specifically we are interested in cooperatively maintaining a per-flow state with a low cost, which has resiliency on dynamic traffic mix. We investigate a traditional timeout processing mechanism to manage the flow table for per-flow monitoring, called Timeout-Based Purging (TBP), our proposed Clock-like Flow Replacement (CFR) algorithms using a replacement policy, called "clock", and a hybrid approach combining these two. Experiments with Internet traces show that our CFR schemes can significantly reduce both false positive and false negative rates, regardless of whether the flow table is fully occupied (even under SYN flooding) or sufficiently empty. Our hybrid scheme estimates the number of active flows accurately, and confines the heavy-hitters without storing packet counters.