Efficient large flow detection over arbitrary windows: an exact algorithm outside an ambiguity region

Abstract

Being able to exactly detect large network flows under an arbitrary time win- dow model is expected in many current and future applications like Denial- of-Service (DoS) flow detection, bandwidth guarantee, etc. However, to the best of our knowledge, there is no existing work that can achieve exact large flow detection without per-flow status. Maintaining per-flow status requires a large amount of expensive line-speed storage, thus it is not practical in real systems. Therefore, we proposed a novel model of an arbitrary time window with exactness outside an ambiguity region, which trades the level of exactness for scalability. Although some existing work also uses some techniques like sampling, multistage filters, etc. to make the system scal- able, most of them do not support the arbitrary time window model and they usually introduce a lot of false positives for legitimate flows. Inspired by a frequent item finding algorithm, we proposed Exact-outside-Ambiguity- Region Detector (EARDet), an arbitrary-window-based, efficient, simple, and no-per-flow-status large flow detector, which is exact outside an ambi- guity window defined by a high-bandwidth threshold and a low-bandwidth threshold. EARDet is able to catch all large flows violating the high- bandwidth threshold; meanwhile it protects all legitimate flows complying with the low-bandwidth threshold. Because EARDet focuses on flow clas- sification but not flow size estimation, it demonstrates amazing scalability such that we can fit the storage into on-chip Static Random-Access Memory (SRAM) to achieve line-speed detection. To evaluate EARDet, we not only theoretically proved properties of EARDet above, but also evaluated them with real traffic, and the result perfectly supports our analysis.