TY - GEN
T1 - BeauCoup
T2 - 2020 Annual Conference of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication, SIGCOMM 2020
AU - Chen, Xiaoqi
AU - Landau-Feibish, Shir
AU - Braverman, Mark
AU - Rexford, Jennifer
N1 - Funding Information:
This research is supported in part by NSF Grant No. CNS-1704077, the NSF Alan T. Waterman Award Grant No. 1933331, a Packard Fellowship in Science and Engineering, the Simons Collaboration on Algorithms and Geometry and The Eric and Wendy Schmidt Fund for Strategic Innovation.
PY - 2020/7/30
Y1 - 2020/7/30
N2 - Network administrators constantly monitor network traffic for congestion and attacks. They need to perform a large number of measurements on the traffic simultaneously, to detect different types of anomalies such as heavy hitters or super-spreaders. Existing techniques often focus on a single statistic (e.g., traffic volume) or traffic attribute (e.g., destination IP). However, performing numerous heterogeneous measurements within the constrained memory architecture of modern network devices poses significant challenges, due to the limited number of memory accesses allowed per packet. We propose BeauCoup, a system based on the coupon collector problem, that supports multiple distinct counting queries simultaneously while making only a small constant number of memory accesses per packet. We implement BeauCoup on PISA commodity programmable switches, satisfying the strict memory size and access constraints while using a moderate portion of other data-plane hardware resources. Evaluations show BeauCoup achieves the same accuracy as other sketch-based or sampling-based solutions using 4x fewer memory access.
AB - Network administrators constantly monitor network traffic for congestion and attacks. They need to perform a large number of measurements on the traffic simultaneously, to detect different types of anomalies such as heavy hitters or super-spreaders. Existing techniques often focus on a single statistic (e.g., traffic volume) or traffic attribute (e.g., destination IP). However, performing numerous heterogeneous measurements within the constrained memory architecture of modern network devices poses significant challenges, due to the limited number of memory accesses allowed per packet. We propose BeauCoup, a system based on the coupon collector problem, that supports multiple distinct counting queries simultaneously while making only a small constant number of memory accesses per packet. We implement BeauCoup on PISA commodity programmable switches, satisfying the strict memory size and access constraints while using a moderate portion of other data-plane hardware resources. Evaluations show BeauCoup achieves the same accuracy as other sketch-based or sampling-based solutions using 4x fewer memory access.
KW - Data Plane
KW - Distinct Counting
KW - Network Measurement
KW - Programmable Switch
KW - Sketching
KW - Streaming Algorithm
UR - http://www.scopus.com/inward/record.url?scp=85094862064&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85094862064&partnerID=8YFLogxK
U2 - 10.1145/3387514.3405865
DO - 10.1145/3387514.3405865
M3 - Conference contribution
AN - SCOPUS:85094862064
T3 - SIGCOMM 2020 - Proceedings of the 2020 Annual Conference of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication
SP - 226
EP - 239
BT - SIGCOMM 2020 - Proceedings of the 2020 Annual Conference of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication
PB - Association for Computing Machinery
Y2 - 10 August 2020 through 14 August 2020
ER -