{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/88960"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/88960","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Wu, Hao"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engineering","degree_department":null,"school":null,"contributors":["Hu, Yih-Chun"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-03-02T19:33:20Z","date_published":"2016-03-02T19:33:20Z","updated_at":"2026-07-22T22:26:32Z","subjects":["Large flow detection","Arbitrary window model","Stream processing","Network security"],"languages":["en"],"rights":["Copyright 2015 Hao Wu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/88960","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hu, Yih-Chun"]},{"key":"dc:creator","label":"Author","values":["Wu, Hao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2016-03-02T19:33:20Z","2015-10-15","2015-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Large flow detection","Arbitrary window model","Stream processing","Network security"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2015 Hao Wu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/88960"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-03-02 without embargo terms","The student, Hao Wu, accepted the attached license on 2015-10-13 at 16:33.","The student, Hao Wu, submitted this Thesis for approval on 2015-10-13 at 16:34.","This Thesis was approved for publication on 2015-10-15 at 15:41.","DSpace SAF Submission Ingestion Package generated from Vireo submission #8721 on 2016-03-02 at 12:49:29","Made available in DSpace on 2016-03-02T19:33:20Z (GMT). No. of bitstreams: 4 WU-THESIS-2015.pdf: 606016 bytes, checksum: 0f3d293dba3bc78f83a6ffa2ecbdf705 (MD5) sourcefiles.zip: 2003549 bytes, checksum: 2d06d56ffe374b0f2ac05df0fc168c63 (MD5) LICENSE.txt: 4203 bytes, checksum: 1e27d1d672baf42c02b1f44bd0d69f13 (MD5) RightsLink Printable License (for EARDet paper).pdf: 75653 bytes, checksum: 22f82a9226caa1aa5e89d0ab968cac72 (MD5) Previous issue date: 2015-10-15"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Efficient large flow detection over arbitrary windows: an exact algorithm outside an ambiguity region"]}]}],"canonical_facts":{"dc:contributor":["Hu, Yih-Chun"],"dc:creator":["Wu, Hao"],"dc:date":["2016-03-02T19:33:20Z","2015-10-15","2015-12"],"dc:description":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-03-02 without embargo terms","The student, Hao Wu, accepted the attached license on 2015-10-13 at 16:33.","The student, Hao Wu, submitted this Thesis for approval on 2015-10-13 at 16:34.","This Thesis was approved for publication on 2015-10-15 at 15:41.","DSpace SAF Submission Ingestion Package generated from Vireo submission #8721 on 2016-03-02 at 12:49:29","Made available in DSpace on 2016-03-02T19:33:20Z (GMT). No. of bitstreams: 4 WU-THESIS-2015.pdf: 606016 bytes, checksum: 0f3d293dba3bc78f83a6ffa2ecbdf705 (MD5) sourcefiles.zip: 2003549 bytes, checksum: 2d06d56ffe374b0f2ac05df0fc168c63 (MD5) LICENSE.txt: 4203 bytes, checksum: 1e27d1d672baf42c02b1f44bd0d69f13 (MD5) RightsLink Printable License (for EARDet paper).pdf: 75653 bytes, checksum: 22f82a9226caa1aa5e89d0ab968cac72 (MD5) Previous issue date: 2015-10-15"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/88960"],"dc:language":["en"],"dc:rights":["Copyright 2015 Hao Wu"],"dc:subject":["Large flow detection","Arbitrary window model","Stream processing","Network security"],"dc:title":["Efficient large flow detection over arbitrary windows: an exact algorithm outside an ambiguity region"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:32Z"}