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

Hao Wu, Hsu Chun Hsiao, Yih Chun Hu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Many networking and security applications can benefit from exact detection of large flows over arbitrary windows (i.e. any possible time window). Existing large flow detectors that only check the average throughput over certain time period cannot detect bursty flows and are therefore easily fooled by attackers. However, no scalable approaches pro- vide exact classification in one pass. To address this chal- lenge, we consider a new model of exactness outside an ambi- guity region, which is defined to be a range of bandwidths be- low a high-bandwidth threshold and above a low-bandwidth threshold. Given this new model, we propose a deterministic algorithm, EARDet, that detects all large flows (including bursty flows) and avoids false accusation against any small flows, regardless of the input traffic distribution. EARDet monitors flows over arbitrary time windows and is built on a frequent items finding algorithm based on average frequency. Despite its strong properties, EARDet has low storage over- head regardless of input traffic and is surprisingly scalable because it focuses on accurate classification of large flows and small flows only. Our evaluations confirm that existing approaches suffer from high error rates (e.g., misclassifying 1% of small flows as large flows) in the presence of large flows and bursty flows, whereas EARDet can accurately detect both at gigabit line rate using a small amount of memory that fits into on-chip SRAM.

Original languageEnglish (US)
Title of host publicationIMC 2014 - Proceedings of the 2014 ACM
PublisherAssociation for Computing Machinery
Pages209-222
Number of pages14
ISBN (Electronic)9781450332132
DOIs
StatePublished - Nov 5 2014
Event2014 ACM Internet Measurement Conference, IMC 2014 - Vancouver, Canada
Duration: Nov 5 2014Nov 7 2014

Publication series

NameProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC

Other

Other2014 ACM Internet Measurement Conference, IMC 2014
CountryCanada
CityVancouver
Period11/5/1411/7/14

Fingerprint

Bandwidth
Static random access storage
Throughput
Detectors
Data storage equipment

Keywords

  • Ambiguity region
  • Arbitrary windows
  • Flow classification
  • Large flow detection

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Cite this

Wu, H., Hsiao, H. C., & Hu, Y. C. (2014). Efficient large flow detection over arbitrary windows: An algorithm exact outside an ambiguity region. In IMC 2014 - Proceedings of the 2014 ACM (pp. 209-222). (Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC). Association for Computing Machinery. https://doi.org/10.1145/2663716.2663724

Efficient large flow detection over arbitrary windows : An algorithm exact outside an ambiguity region. / Wu, Hao; Hsiao, Hsu Chun; Hu, Yih Chun.

IMC 2014 - Proceedings of the 2014 ACM. Association for Computing Machinery, 2014. p. 209-222 (Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Wu, H, Hsiao, HC & Hu, YC 2014, Efficient large flow detection over arbitrary windows: An algorithm exact outside an ambiguity region. in IMC 2014 - Proceedings of the 2014 ACM. Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC, Association for Computing Machinery, pp. 209-222, 2014 ACM Internet Measurement Conference, IMC 2014, Vancouver, Canada, 11/5/14. https://doi.org/10.1145/2663716.2663724
Wu H, Hsiao HC, Hu YC. Efficient large flow detection over arbitrary windows: An algorithm exact outside an ambiguity region. In IMC 2014 - Proceedings of the 2014 ACM. Association for Computing Machinery. 2014. p. 209-222. (Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC). https://doi.org/10.1145/2663716.2663724
Wu, Hao ; Hsiao, Hsu Chun ; Hu, Yih Chun. / Efficient large flow detection over arbitrary windows : An algorithm exact outside an ambiguity region. IMC 2014 - Proceedings of the 2014 ACM. Association for Computing Machinery, 2014. pp. 209-222 (Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC).
@inproceedings{e4e0a9f0f37e48caa3a6e066ea38d2e4,
title = "Efficient large flow detection over arbitrary windows: An algorithm exact outside an ambiguity region",
abstract = "Many networking and security applications can benefit from exact detection of large flows over arbitrary windows (i.e. any possible time window). Existing large flow detectors that only check the average throughput over certain time period cannot detect bursty flows and are therefore easily fooled by attackers. However, no scalable approaches pro- vide exact classification in one pass. To address this chal- lenge, we consider a new model of exactness outside an ambi- guity region, which is defined to be a range of bandwidths be- low a high-bandwidth threshold and above a low-bandwidth threshold. Given this new model, we propose a deterministic algorithm, EARDet, that detects all large flows (including bursty flows) and avoids false accusation against any small flows, regardless of the input traffic distribution. EARDet monitors flows over arbitrary time windows and is built on a frequent items finding algorithm based on average frequency. Despite its strong properties, EARDet has low storage over- head regardless of input traffic and is surprisingly scalable because it focuses on accurate classification of large flows and small flows only. Our evaluations confirm that existing approaches suffer from high error rates (e.g., misclassifying 1{\%} of small flows as large flows) in the presence of large flows and bursty flows, whereas EARDet can accurately detect both at gigabit line rate using a small amount of memory that fits into on-chip SRAM.",
keywords = "Ambiguity region, Arbitrary windows, Flow classification, Large flow detection",
author = "Hao Wu and Hsiao, {Hsu Chun} and Hu, {Yih Chun}",
year = "2014",
month = "11",
day = "5",
doi = "10.1145/2663716.2663724",
language = "English (US)",
series = "Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC",
publisher = "Association for Computing Machinery",
pages = "209--222",
booktitle = "IMC 2014 - Proceedings of the 2014 ACM",

}

TY - GEN

T1 - Efficient large flow detection over arbitrary windows

T2 - An algorithm exact outside an ambiguity region

AU - Wu, Hao

AU - Hsiao, Hsu Chun

AU - Hu, Yih Chun

PY - 2014/11/5

Y1 - 2014/11/5

N2 - Many networking and security applications can benefit from exact detection of large flows over arbitrary windows (i.e. any possible time window). Existing large flow detectors that only check the average throughput over certain time period cannot detect bursty flows and are therefore easily fooled by attackers. However, no scalable approaches pro- vide exact classification in one pass. To address this chal- lenge, we consider a new model of exactness outside an ambi- guity region, which is defined to be a range of bandwidths be- low a high-bandwidth threshold and above a low-bandwidth threshold. Given this new model, we propose a deterministic algorithm, EARDet, that detects all large flows (including bursty flows) and avoids false accusation against any small flows, regardless of the input traffic distribution. EARDet monitors flows over arbitrary time windows and is built on a frequent items finding algorithm based on average frequency. Despite its strong properties, EARDet has low storage over- head regardless of input traffic and is surprisingly scalable because it focuses on accurate classification of large flows and small flows only. Our evaluations confirm that existing approaches suffer from high error rates (e.g., misclassifying 1% of small flows as large flows) in the presence of large flows and bursty flows, whereas EARDet can accurately detect both at gigabit line rate using a small amount of memory that fits into on-chip SRAM.

AB - Many networking and security applications can benefit from exact detection of large flows over arbitrary windows (i.e. any possible time window). Existing large flow detectors that only check the average throughput over certain time period cannot detect bursty flows and are therefore easily fooled by attackers. However, no scalable approaches pro- vide exact classification in one pass. To address this chal- lenge, we consider a new model of exactness outside an ambi- guity region, which is defined to be a range of bandwidths be- low a high-bandwidth threshold and above a low-bandwidth threshold. Given this new model, we propose a deterministic algorithm, EARDet, that detects all large flows (including bursty flows) and avoids false accusation against any small flows, regardless of the input traffic distribution. EARDet monitors flows over arbitrary time windows and is built on a frequent items finding algorithm based on average frequency. Despite its strong properties, EARDet has low storage over- head regardless of input traffic and is surprisingly scalable because it focuses on accurate classification of large flows and small flows only. Our evaluations confirm that existing approaches suffer from high error rates (e.g., misclassifying 1% of small flows as large flows) in the presence of large flows and bursty flows, whereas EARDet can accurately detect both at gigabit line rate using a small amount of memory that fits into on-chip SRAM.

KW - Ambiguity region

KW - Arbitrary windows

KW - Flow classification

KW - Large flow detection

UR - http://www.scopus.com/inward/record.url?scp=84910142479&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84910142479&partnerID=8YFLogxK

U2 - 10.1145/2663716.2663724

DO - 10.1145/2663716.2663724

M3 - Conference contribution

AN - SCOPUS:84910142479

T3 - Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC

SP - 209

EP - 222

BT - IMC 2014 - Proceedings of the 2014 ACM

PB - Association for Computing Machinery

ER -