An Efficient Approach to Per-Flow State Tracking for High-Speed Networks

Maintaining per-flow information and state is a crucial topic in network monitoring. Tracking per-flow state is a relatively new area. Two main approaches have been proposed for tracking state: Binned Duration Flow Tracking (BDFT) and Fingerprint-Compressed Filter Approximate Concurrent State Machine (FCF ACSM). BDFT which uses Bloom filters is time efficient, whereas FCF ACSM using d-left hash tables has near-perfect memory efficiency but has higher computational cost. This paper presents a hybrid method (BDFT-H) by employing the best features of BDFT and FCF ACSM to achieve both time and space efficiency. Performance analysis and comparisons are conducted for BDFT, FCF ACSM, and BDFT-H. These methods are all intended for implementation on high-speed routers where resources such as memory and CPU time are limited. For the computational performance of the three schemes, we find that based on analysis, d-left hashing may require substantially more computational resources than Bloom filters. We also conduct simulations to compare the accuracy of these three schemes and the results show that all three methods can achieve over 99% accuracy on traces of real traffic. The proposed approach provides the best overall tradeoff between time and space efficiency.