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 BDFT-H provides the best overall tradeoff between time and space efficiency. Both BDFT and FCF ACSM may have the false positive issue. This paper also presents two additional BDFT extensions: BDFT-FPR (false positive removal) and BDFT-FPC (false positive correction) to deal with the false positive issue. Performance comparisons for BDFT and these two BDFT extensions are also conducted using real traffic traces for comparison.

Additional Metadata
Keywords Bloom filter, d-Left hashing, Flow tracking, High-speed networks, Network monitoring
Persistent URL dx.doi.org/10.1016/j.comcom.2012.12.010
Journal Computer Communications
Citation
Whitehead, B. (Brad), Lung, C.H, & Rabinovitch, P. (Peter). (2013). An efficient hybrid approach to per-flow state tracking for high-speed networks. Computer Communications, 36(8), 927–938. doi:10.1016/j.comcom.2012.12.010