SAROS: A Self-Adaptive Routing Oblivious Sampling Method for Network-wide Heavy Hitter Detection
Pages 142 - 148
Abstract
Network-wide heavy hitter detection is usually performed by sampling on several network measurement points (NMPs) and merging the measurement results in the centralized controller to get a network-wide view. However, a packet may pass several NMPs and be counted multiple times when measurement results are merged, which causes the double-counting problem and leads to incorrect detection. Existing studies either overlook this problem or require significant memory usage. This paper proposes SAROS, a self-adaptive routing oblivious sampling method for accurate network-wide heavy hitter detection. Specifically, SAROS exploits a sampling mechanism in the data plane, where the sampling threshold on each measurement point is predicted and adaptively set by the control plane. Such guidance from the control plane greatly reduces the memory usage in the data plane, while mitigating the double-counting problem. Experimental results show that, compared with existing solutions, SAROS improves the F1-Score of heavy hitter detection by 10 ∼ 40%.
References
[1]
2024. SAROS. https://anonymous.4open.science/r/SAROS_HHD-078E/README.md.
[2]
Yehuda Afek, Anat Bremler-Barr, Shir Landau Feibish, and Liron Schiff. 2018. Detecting Heavy Flows in the SDN Match and Action Model. Computer Networks 136 (2018), 1–12.
[3]
Albert Gran Alcoz, Martin Strohmeier, Vincent Lenders, and Laurent Vanbever. 2022. Aggregate-based congestion control for pulse-wave DDoS defense. In Proceedings of the ACM SIGCOMM 2022 Conference. 693–706.
[4]
Ziv Bar-Yossef, TS Jayram, Ravi Kumar, D Sivakumar, and Luca Trevisan. 2002. Counting Distinct Elements in a Data Stream. In Randomization and Approximation Techniques in Computer Science: 6th International Workshop. 1–10.
[5]
Ran Ben Basat, Xiaoqi Chen, Gil Einziger, Shir Landau Feibish, Danny Raz, and Minlan Yu. 2020. Routing oblivious measurement analytics. In 2020 IFIP Networking Conference. 449–457.
[6]
T. Benson, A. Akella, and D. A. Maltz. 2010. Network Traffic Characteristics of Data Centers in the Wild. In ACM SIGCOMM Conference on Internet Measurement.
[7]
Kevin Beyer, Peter J Haas, Berthold Reinwald, Yannis Sismanis, and Rainer Gemulla. 2007. On synopses for distinct-value estimation under multiset operations. In Proceedings of the 2007 ACM SIGMOD international conference on Management of data. 199–210.
[8]
Pierre Borgnat, Guillaume Dewaele, Kensuke Fukuda, Patrice Abry, and Kenjiro Cho. 2009. Seven years and one day: Sketching the evolution of internet traffic. In IEEE INFOCOM 2009. 711–719.
[9]
Pat Bosshart, Dan Daly, Glen Gibb, Martin Izzard, Nick McKeown, Jennifer Rexford, Cole Schlesinger, Dan Talayco, Amin Vahdat, George Varghese, 2014. P4: Programming protocol-independent packet processors. ACM SIGCOMM Computer Communication Review 44 (2014), 87–95.
[10]
Graham Cormode. 2009. Count-Min Sketch.
[11]
Damu Ding, Marco Savi, Gianni Antichi, and Domenico Siracusa. 2020. An Incrementally-Deployable P4-Enabled Architecture for Network-Wide Heavy-Hitter Detection. IEEE Transactions on Network and Service Management 17 (2020), 75–88.
[12]
Damu Ding, Marco Savi, Federico Pederzolli, and Domenico Siracusa. 2021. INVEST: Flow-based Traffic Volume Estimation in Data-plane Programmable Networks. In 2021 IFIP Networking Conference. 1–9.
[13]
Nick G Duffield and Matthias Grossglauser. 2001. Trajectory sampling for direct traffic observation. IEEE/ACM transactions on networking 9, 3 (2001), 280–292.
[14]
Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. 2007. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. In Discrete Mathematics and Theoretical Computer Science. 137–156.
[15]
Einollah Jafarnejad Ghomi, Amir Masoud Rahmani, and Nooruldeen Nasih Qader. 2017. Load-balancing algorithms in cloud computing: A survey. Journal of Network and Computer Applications 88 (2017), 50–71.
[16]
Alex Graves and Alex Graves. 2012. Long Short-Term Memory. Supervised Sequence Labelling With Recurrent Neural Networks (2012), 37–45.
[17]
Arpit Gupta, Rob Harrison, Marco Canini, Nick Feamster, Jennifer Rexford, and Walter Willinger. 2018. Sonata: Query-driven streaming network telemetry. In Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication. 357–371.
[18]
Rob Harrison, Qizhe Cai, Arpit Gupta, and Jennifer Rexford. 2018. Network-Wide Heavy Hitter Detection with Commodity Switches. In Proceedings of the Symposium on SDN Research. 1–7.
[19]
Yuliang Li, Rui Miao, Changhoon Kim, and Minlan Yu. 2016. FlowRadar: A better netflow for data centers. In { USENIX} Symposium on Networked Systems Design and Implementation. 311–324.
[20]
Zaoxing Liu, Antonis Manousis, Gregory Vorsanger, Vyas Sekar, and Vladimir Braverman. 2016. One sketch to rule them all: Rethinking network flow monitoring with UnivMon. In Proceedings of the 2016 ACM SIGCOMM Conference. 101–114.
[21]
Zaoxing Liu, Hun Namkung, Georgios Nikolaidis, Jeongkeun Lee, Changhoon Kim, Xin Jin, Vladimir Braverman, Minlan Yu, and Vyas Sekar. 2021. Jaqen: A { High-Performance}{ Switch-Native} approach for detecting and mitigating volumetric { DDoS} attacks with programmable switches. In 30th USENIX Security Symposium (USENIX Security 21). 3829–3846.
[22]
Biswanath Mukherjee, L Todd Heberlein, and Karl N Levitt. 1994. Network intrusion detection. IEEE network 8, 3 (1994), 26–41.
[23]
Yuan Tao and Shui Yu. 2013. DDoS attack detection at local area networks using information theoretical metrics. In 2013 12th IEEE international conference on trust, security and privacy in computing and communications. IEEE, 233–240.
[24]
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Advances in Neural Information Processing Systems 30 (2017).
[25]
Tong Yang, Jie Jiang, Peng Liu, Qun Huang, Junzhi Gong, Yang Zhou, Rui Miao, Xiaoming Li, and Steve Uhlig. 2018. Elastic Sketch: Adaptive and Fast Network-Wide Measurements. In Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication. 561–575.
[26]
Menghao Zhang, Guanyu Li, Shicheng Wang, Chang Liu, Ang Chen, Hongxin Hu, Guofei Gu, Qianqian Li, Mingwei Xu, and Jianping Wu. 2020. Poseidon: Mitigating volumetric ddos attacks with programmable switches. In the 27th Network and Distributed System Security Symposium (NDSS 2020).
[27]
Huancheng Zhou, Sungmin Hong, Yangyang Liu, Xiapu Luo, Weichao Li, and Guofei Gu. 2023. Mew: Enabling large-scale and dynamic link-flooding defenses on programmable switches. In 2023 IEEE Symposium on Security and Privacy (SP). IEEE, 3178–3192.
[28]
Yibo Zhu, Nanxi Kang, Jiaxin Cao, Albert Greenberg, Guohan Lu, Ratul Mahajan, Dave Maltz, Lihua Yuan, Ming Zhang, Ben Y Zhao, 2015. Packet-level telemetry in large datacenter networks. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. 479–491.
Index Terms
- SAROS: A Self-Adaptive Routing Oblivious Sampling Method for Network-wide Heavy Hitter Detection
Recommendations
Heavy-Hitter Detection Entirely in the Data Plane
SOSR '17: Proceedings of the Symposium on SDN ResearchIdentifying the "heavy hitter" flows or flows with large traffic volumes in the data plane is important for several applications e.g., flow-size aware routing, DoS detection, and traffic engineering. However, measurement in the data plane is constrained ...
High Throughput Sketch Based Online Heavy Hitter Detection on FPGA
HEART '15In the context of networking, a heavy hitter is an entity in a data stream whose amount of activity (such as bandwidth consumption or number of connections) is higher than a given threshold. Detecting heavy hitters is a critical task for network ...
High Throughput Hierarchical Heavy Hitter Detection in Data Streams
HIPC '15: Proceedings of the 2015 IEEE 22nd International Conference on High Performance Computing (HiPC)Detecting heavy activity aggregation in data streams is a critical task for many networking, data base and data-mining applications. The aggregation points often belong to hierarchical domains (e.g. IP domain, XML data tree, etc.). These aggregation ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2024
230 pages
ISBN:9798400717581
DOI:10.1145/3663408
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 03 August 2024
Check for updates
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
Conference
APNet 2024
Acceptance Rates
APNet '24 Paper Acceptance Rate 50 of 118 submissions, 42%;
Overall Acceptance Rate 50 of 118 submissions, 42%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 112Total Downloads
- Downloads (Last 12 months)112
- Downloads (Last 6 weeks)36
Reflects downloads up to 19 Nov 2024
Other Metrics
Citations
View Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in