Mass Purging of Stale TCP Flows in Per-Flow Monitoring Systems

Timely deletion of a large number of stale sessions monitored by Internet routers, particularly in the presence of SYN floods, is critical to prevent flow table explosion. We investigate two frameworks for purging of stale sessions: "opportunistic" purging that employs a free-list of pointers to memory and "deterministic purging" involving logical swapping of a 1-bit flow enable and touch-bit vectors without requiring a free list. We compare the performance of our algorithms with a state-of-the-art algorithm, namely finger-compressed filter (FCF). Our analysis using Internet traces shows that the deterministic purging, with no purging overhead, is ideal in that it reduces false positive and negative rates as compared to FCF by 52.5% and 59.2%, when the table size is twice the average number of active flows.