TY - GEN
T1 - Efficient large flow detection over arbitrary windows
T2 - 2014 ACM Internet Measurement Conference, IMC 2014
AU - Wu, Hao
AU - Hsiao, Hsu Chun
AU - Hu, Yih Chun
N1 - Publisher Copyright:
Copyright © 2014 by the Association for Computing Machinery, Inc. (ACM).
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
Y2 - 5 November 2014 through 7 November 2014
ER -