Files in this item



application/pdfWU-THESIS-2015.pdf (606kB)
(no description provided)PDF


Title:Efficient large flow detection over arbitrary windows: an exact algorithm outside an ambiguity region
Author(s):Wu, Hao
Advisor(s):Hu, Yih-Chun
Department / Program:Electrical & Computer Engineering
Discipline:Electrical & Computer Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Large flow detection
Arbitrary window model
Stream processing
Network security
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.
Issue Date:2015-10-15
Rights Information:Copyright 2015 Hao Wu
Date Available in IDEALS:2016-03-02
Date Deposited:2015-12

This item appears in the following Collection(s)

Item Statistics