research-article

Free access

Elastic sketch: adaptive and fast network-wide measurements

Authors:

Steve UhligAuthors Info & Claims

SIGCOMM '18: Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication

Pages 561 - 575

https://doi.org/10.1145/3230543.3230544

Published: 07 August 2018 Publication History

Abstract

When network is undergoing problems such as congestion, scan attack, DDoS attack, etc., measurements are much more important than usual. In this case, traffic characteristics including available bandwidth, packet rate, and flow size distribution vary drastically, significantly degrading the performance of measurements. To address this issue, we propose the Elastic sketch. It is adaptive to currently traffic characteristics. Besides, it is generic to measurement tasks and platforms. We implement the Elastic sketch on six platforms: P4, FPGA, GPU, CPU, multi-core CPU, and OVS, to process six typical measurement tasks. Experimental results and theoretical analysis show that the Elastic sketch can adapt well to traffic characteristics. Compared to the state-of-the-art, the Elastic sketch achieves 44.6 ∼ 45.2 times faster speed and 2.0 ∼ 273.7 smaller error rate.

References

[1]

Gurmeet Singh Manku and Rajeev Motwani. Approximate frequency counts over data streams. In Proc. VLDB, 2002.

Digital Library

[2]

Zaoxing Liu, Antonis Manousis, Gregory Vorsanger, Vyas Sekar, and Vladimir Braverman. One sketch to rule them all: Rethinking network flow monitoring with univmon. In Proceedings of the 2016 conference on ACM SIGCOMM 2016 Conference. ACM, 2016.

Digital Library

[3]

Ran Ben Basat, Gil Einziger, Roy Friedman, Marcelo Caggiani Luizelli, and Erez Waisbard. Constant time updates in hierarchical heavy hitters. arXiv preprint arXiv:1707.06778, 2017.

Digital Library

[4]

Cristian Estan and George Varghese. New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice. ACM Transactions on Computer Systems (TOCS), 21(3), 2003.

Digital Library

[5]

Er Krishnamurthy, Subhabrata Sen, and Yin Zhang. Sketchbased change detection: Methods, evaluation, and applications. In In ACM SIGCOMM Internet Measurement Conference. Citeseer, 2003.

Digital Library

[6]

Xin Li, Fang Bian, Mark Crovella, Christophe Diot, Ramesh Govindan, Gianluca Iannaccone, and Anukool Lakhina. Detection and identification of network anomalies using sketch subspaces. In Proc. ACM IMC, 2006.

Digital Library

[7]

MyungKeun Yoon, Tao Li, Shigang Chen, and J-K Peir. Fit a spread estimator in small memory. In Proc. IEEE INFOCOM, 2009.

[8]

Graham Cormode. Sketch techniques for approximate query processing. Foundations and Trends in Databases. NOW publishers, 2011.

[9]

Srikanth Kandula, Sudipta Sengupta, Albert Greenberg, Parveen Patel, and Ronnie Chaiken. The nature of data center traffic: measurements & analysis. In Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference. ACM, 2009.

Digital Library

[10]

Graham Cormode and Shan Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1), 2005.

Digital Library

[11]

Minlan Yu, Lavanya Jose, and Rui Miao. Software defined traffic measurement with opensketch. In NSDI, volume 13, 2013.

Digital Library

[12]

Qun Huang, Xin Jin, Patrick PC Lee, Runhui Li, Lu Tang, Yi-Chao Chen, and Gong Zhang. Sketchvisor: Robust network measurement for software packet processing. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication. ACM, 2017.

Digital Library

[13]

Yi Lu, Andrea Montanari, Balaji Prabhakar, Sarang Dharmapurikar, and Abdul Kabbani. Counter braids: a novel counter architecture for per-flow measurement. ACM SIGMETRICS Performance Evaluation Review, 36(1), 2008.

Digital Library

[14]

Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. Automata, languages and programming, 2002.

Digital Library

[15]

Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. Efficient computation of frequent and top-k elements in data streams. In Proc. Springer ICDT, 2005.

Digital Library

[16]

Vibhaalakshmi Sivaraman, Srinivas Narayana, Ori Rottenstreich, S Muthukrishnan, and Jennifer Rexford. Heavy-hitter detection entirely in the data plane. In Proceedings of the Symposium on SDN Research. ACM, 2017.

Digital Library

[17]

Abhishek Kumar, Minho Sung, Jun Jim Xu, and Jia Wang. Data streaming algorithms for efficient and accurate estimation of flow size distribution. In Proc. ACM SIGMETRICS, 2004.

Digital Library

[18]

Yuliang Li, Rui Miao, Changhoon Kim, and Minlan Yu. Flowradar: A better netflow for data centers. In NSDI, 2016.

Digital Library

[19]

Arjun Roy, Hongyi Zeng, Jasmeet Bagga, George Porter, and Alex C Snoeren. Inside the social network's (datacenter) network. In ACM SIGCOMM Computer Communication Review. ACM, 2015.

Digital Library

[20]

Neil Spring, Ratul Mahajan, and David Wetherall. Measuring isp topologies with rocketfuel. ACM SIGCOMM Computer Communication Review, 32(4), 2002.

Digital Library

[21]

Zheng Zhang, Ming Zhang, Albert G Greenberg, Y Charlie Hu, Ratul Mahajan, and Blaine Christian. Optimizing cost and performance in online service provider networks. In NSDI, 2010.

Digital Library

[22]

Yin Zhang, Matthew Roughan, Walter Willinger, and Lili Qiu. Spatiotemporal compressive sensing and internet traffic matrices. In ACM SIGCOMM Computer Communication Review, volume 39. ACM, 2009.

Digital Library

[23]

Mojgan Ghasemi, Partha Kanuparthy, Ahmed Mansy, Theophilus Benson, and Jennifer Rexford. Performance characterization of a commercial video streaming service. In Proceedings of the 2016 Internet Measurement Conference. ACM, 2016.

Digital Library

[24]

Theophilus Benson, Ashok Anand, Aditya Akella, and Ming Zhang. Understanding data center traffic characteristics. In Proceedings of the 1st ACM workshop on Research on enterprise networking. ACM, 2009.

Digital Library

[25]

Kun Xie, Lele Wang, and et al. Accurate recovery of internet traffic data: A sequential tensor completion approach. IEEE/ACM Transactions on Networking (TON), 26(2):793--806, 2018.

Digital Library

[26]

Kun Xie, Xiaocan Li, Xin Wang, and et al. Fast tensor factorization for accurate internet anomaly detection. IEEE/ACM Transactions on Networking, 25(6):3794--3807, 2017.

Digital Library

[27]

Kun Xie, Xiaocan Li, Xin Wang, and et al. On-line anomaly detection with high accuracy. IEEE/ACM Transactions on Networking, 2018.

[28]

Ramesh Govindan, Ina Minei, Mahesh Kallahalla, Bikash Koley, and Amin Vahdat. Evolve or die: High-availability design principles drawn from googles network infrastructure. In Proceedings of the 2016 ACM SIGCOMM Conference. ACM, 2016.

Digital Library

[29]

Michael Mitzenmacher, George Varghese, et al. Carousel: scalable logging for intrusion prevention systems. In Proceedings of the 7th USENIX conference on Networked systems design and implementation. USENIX Association, 2010.

Digital Library

[30]

Will E Leland, Murad S Taqqu, Walter Willinger, and Daniel V Wilson. On the self-similar nature of ethernet traffic. In ACM SIGCOMM computer communication review, volume 23. ACM, 1993.

Digital Library

[31]

Eric Rozner, Jayesh Seshadri, Yogita Mehta, and Lili Qiu. Soar: Simple opportunistic adaptive routing protocol for wireless mesh networks. IEEE transactions on Mobile computing, 8(12), 2009.

Digital Library

[32]

Y Oh Soon, Eun-Kyu Lee, and Mario Gerla. Adaptive forwarding rate control for network coding in tactical manets. In MILITARY COMMUNICATIONS CONFERENCE, 2010-MILCOM 2010. IEEE, 2010.

[33]

Bo Yu, Cheng-Zhong Xu, and Minyi Guo. Adaptive forwarding delay control for vanet data aggregation. IEEE Transactions on Parallel and Distributed systems, 23(1), 2012.

Digital Library

[34]

Theophilus Benson, Aditya Akella, and David A Maltz. Network traffic characteristics of data centers in the wild. In Proceedings of the 10th ACM SIGCOMM conference on Internet measurement. ACM, 2010.

Digital Library

[35]

Graham Cormode, Balachander Krishnamurthy, and Walter Willinger. A manifesto for modeling and measurement in social media. First Monday, 15(9), 2010.

[36]

Theophilus Benson, Aditya Akella, and David A Maltz. Unraveling the complexity of network management. In NSDI, 2009.

Digital Library

[37]

Ilker Nadi Bozkurt, Yilun Zhou, Theophilus Benson, Bilal Anwer, Dave Levin, Nick Feamster, Aditya Akella, Balakrishnan Chandrasekaran, Cheng Huang, Bruce Maggs, et al. Dynamic prioritization of traffic in home networks. 2015.

[38]

Open-source p4 implementation of features typical of an advanced l2/l3 switch. https://github.com/p4lang/switch.

[39]

László A Jeni, Jeffrey F Cohn, and Fernando De La Torre. Facing imbalanced data-recommendations for the use of performance metrics. In Affective Computing and Intelligent Interaction (ACII), 2013 Humaine Association Conference on. IEEE, 2013.

Digital Library

[40]

Masoud Moshref, Minlan Yu, Ramesh Govindan, and Amin Vahdat. Trumpet: Timely and precise triggers in data centers. In Proceedings of the 2016 conference on ACM SIGCOMM 2016 Conference. ACM, 2016.

Digital Library

[41]

Srinivas Narayana, Anirudh Sivaraman, Vikram Nathan, Prateesh Goyal, Venkat Arun, Mohammad Alizadeh, Vimalkumar Jeyakumar, and Changhoon Kim. Language-directed hardware design for network performance monitoring. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication. ACM, 2017.

Digital Library

[42]

Chuanxiong Guo, Lihua Yuan, Dong Xiang, Yingnong Dang, Ray Huang, Dave Maltz, Zhaoyi Liu, Vin Wang, Bin Pang, Hua Chen, et al. Pingmesh: A large-scale system for data center network latency measurement and analysis. In ACM SIGCOMM Computer Communication Review, volume 45. ACM, 2015.

Digital Library

[43]

Masoud Moshref, Minlan Yu, Ramesh Govindan, and Amin Vahdat. Dream: dynamic resource allocation for software-defined measurement. ACM SIGCOMM Computer Communication Review, 44(4), 2015.

Digital Library

[44]

Burton H Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 1970.

Digital Library

[45]

Michael T Goodrich and Michael Mitzenmacher. Invertible bloom lookup tables. In Communication, Control, and Computing (Allerton), 2011 49th Annual Allerton Conference on. IEEE, 2011.

[46]

Vladimir Braverman and Rafail Ostrovsky. Generalizing the layering method of indyk and woodruff: Recursive sketches for frequency-based vectors on streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 2013.

[47]

The source codes of our and other related algorithms. https://github.com/BlockLiu/ElasticSketchCode.

[48]

Tian Bu, Jin Cao, Aiyou Chen, and Patrick PC Lee. Sequential hashing: A flexible approach for unveiling significant patterns in high speed networks. Computer Networks, 54(18), 2010.

Digital Library

[49]

Haoyu Song, Sarang Dharmapurikar, Jonathan Turner, and John Lockwood. Fast hash table lookup using extended bloom filter: an aid to network processing. ACM SIGCOMM Computer Communication Review, 35(4), 2005.

Digital Library

[50]

Adam Kirsch, Michael Mitzenmacher, and George Varghese. Hash-based techniques for high-speed packet processing. In Algorithms for Next Generation Networks. Springer, 2010.

[51]

Berthold Vöcking. How asymmetry helps load balancing. Journal of the ACM (JACM), 50(4), 2003.

Digital Library

[52]

Bin Fan, Dave G Andersen, Michael Kaminsky, and Michael D Mitzenmacher. Cuckoo filter: Practically better than bloom. In Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies. ACM, 2014.

Digital Library

[53]

Dong Zhou, Bin Fan, Hyeontaek Lim, Michael Kaminsky, and David G Andersen. Scalable, high performance ethernet forwarding with cuck-ooswitch. In Proceedings of the ninth ACM conference on Emerging networking experiments and technologies. ACM, 2013.

Digital Library

[54]

Xiaozhou Li, David G Andersen, Michael Kaminsky, and Michael J Freedman. Algorithmic improvements for fast concurrent cuckoo hashing. In Proceedings of the Ninth European Conference on Computer Systems. ACM, 2014.

Digital Library

[55]

Hyeontaek Lim, Donsu Han, David G Andersen, and Michael Kaminsky. Mica: A holistic approach to fast in-memory key-value storage. USENIX, 2014.

Digital Library

[56]

Bin Fan, David G Andersen, and Michael Kaminsky. Memc3: Compact and concurrent memcache with dumber caching and smarter hashing. In NSDI, volume 13, 2013.

Digital Library

[57]

Hyeontaek Lim, Bin Fan, David G Andersen, and Michael Kaminsky. Silt: A memory-efficient, high-performance key-value store. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles. ACM, 2011.

Digital Library

[58]

Baek-Young Choi, Jaesung Park, and Zhi-Li Zhang. Adaptive packet sampling for accurate and scalable flow measurement. In Global Telecommunications Conference, 2004. GLOBECOM'04. IEEE, volume 3. IEEE, 2004.

[59]

Kyu-Young Whang, Brad T Vander-Zanden, and Howard M Taylor. A linear-time probabilistic counting algorithm for database applications. ACM Transactions on Database Systems (TODS), 15(2), 1990.

Digital Library

[60]

Haipeng Dai, Muhammad Shahzad, Alex X Liu, and Yuankun Zhong. Finding persistent items in data streams. Proceedings of the VLDB Endowment, 10(4):289--300, 2016.

Digital Library

[61]

Haipeng Dai, L Meng, and Alex X Liu. Finding persistent items in distributed, datasets. In Proc. IEEE INFOCOM, 2018.

[62]

Haipeng Dai, Yuankun Zhong, Alex X Liu, Wei Wang, and Meng Li. Noisy bloom filters for multi-set membership testing. In Proc. ACM SIGMETRICS, pages 139--151, 2016.

Digital Library

[63]

Barefoot tofino: World's fastest p4--programmable ethernet switch asics. https://barefootnetworks.com/products/brief-tofino/.

[64]

Nvidia cuda c programming guide, version 9.0. http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html.

[65]

The CAIDA Anonymized Internet Traces. http://www.caida.org/data/overview/.

[66]

Amit Goyal, Hal Daumé III, and Graham Cormode. Sketch algorithms for estimating point queries in nlp. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. Association for Computational Linguistics, 2012.

Digital Library

[67]

Robert Schweller, Ashish Gupta, Elliot Parsons, and Yan Chen. Reversible sketches for efficient and accurate change detection over network data streams. In Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, 2004.

Digital Library

[68]

Ashwin Lall, Vyas Sekar, Mitsunori Ogihara, Jun Xu, and Hui Zhang. Data streaming algorithms for estimating entropy of network traffic. In Proc. ACM SIGMETRICS, 2006.

Digital Library

[69]

David MW Powers. Applications and explanations of zipf's law. In Proceedings of the joint conferences on new methods in language processing and computational natural language learning. Association for Computational Linguistics, 1998.

Digital Library

[70]

FAST platform website. http://www.fastswitch.org.

Cited By

Ran DChen XSong L(2024)ComPipe: A Novel Flow Placement and Measurement Algorithm for Programmable Composite PipelinesElectronics10.3390/electronics1306102213:6(1022)Online publication date: 8-Mar-2024
https://doi.org/10.3390/electronics13061022
Zhang ZLu JRen QLi ZHu YChen H(2024)An Accurate and Invertible Sketch for Super Spread DetectionElectronics10.3390/electronics1301022213:1(222)Online publication date: 3-Jan-2024
https://doi.org/10.3390/electronics13010222
Abboud RFriedman R(2024)Practical Heavy-Hitter Detection Algorithms for Programmable Switches2024 IFIP Networking Conference (IFIP Networking)10.23919/IFIPNetworking62109.2024.10619799(377-385)Online publication date: 3-Jun-2024
https://doi.org/10.23919/IFIPNetworking62109.2024.10619799
Show More Cited By

Index Terms

Elastic sketch: adaptive and fast network-wide measurements
1. Networks
  1. Network performance evaluation
    1. Network measurement
  2. Network services
    1. Network monitoring

Recommendations

FCM-sketch: generic network measurements with data plane support
CoNEXT '20: Proceedings of the 16th International Conference on emerging Networking EXperiments and Technologies

Sketches have successfully provided accurate and fine-grained measurements (e.g., flow size and heavy hitters) which are imperative for network management. In particular, Count-Min (CM) sketch is widely utilized in many applications due to its simple ...
Propagation of Love waves in a non-homogeneous orthotropic elastic layer under initial stress overlying semi-infinite medium

In this paper, Love waves in a non-homogeneous orthotropic elastic medium under changeable initial stress has been studied. Fourier transform method has been applied to find the dispersion equation. It has been shown that the velocity of Love waves lies ...
Elastic-plastic analysis of a thin rotating disk of exponentially variable thickness with inclusion

Transition theory has been used to derive the elastic-plastic and transitional stresses. Results obtained have been discussed numerically and depicted graphically. It has been observed that for disc with exponentially varying thickness (k=2), high ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '18: Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication

August 2018

604 pages

ISBN:9781450355674

DOI:10.1145/3230543

General Chairs:
Sergey Gorinsky
IMDEA, Spain
,
János Tapolcai
BME, Hungary

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 August 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGCOMM '18

Sponsor:

SIGCOMM

SIGCOMM '18: ACM SIGCOMM 2018 Conference

August 20 - 25, 2018

Budapest, Hungary

Acceptance Rates

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

394
Total Citations
View Citations
8,000
Total Downloads

Downloads (Last 12 months)1,517
Downloads (Last 6 weeks)152

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ran DChen XSong L(2024)ComPipe: A Novel Flow Placement and Measurement Algorithm for Programmable Composite PipelinesElectronics10.3390/electronics1306102213:6(1022)Online publication date: 8-Mar-2024
https://doi.org/10.3390/electronics13061022
Zhang ZLu JRen QLi ZHu YChen H(2024)An Accurate and Invertible Sketch for Super Spread DetectionElectronics10.3390/electronics1301022213:1(222)Online publication date: 3-Jan-2024
https://doi.org/10.3390/electronics13010222
Abboud RFriedman R(2024)Practical Heavy-Hitter Detection Algorithms for Programmable Switches2024 IFIP Networking Conference (IFIP Networking)10.23919/IFIPNetworking62109.2024.10619799(377-385)Online publication date: 3-Jun-2024
https://doi.org/10.23919/IFIPNetworking62109.2024.10619799
Sateesan AVliegen JScherrer SHsiao HPerrig AMentens N(2024)SPArch: A Hardware-oriented Sketch-based Architecture for High-speed Network Flow MeasurementsACM Transactions on Privacy and Security10.1145/368747727:4(1-34)Online publication date: 8-Aug-2024
https://dl.acm.org/doi/10.1145/3687477
Ben Basat REinziger GHan WTayh B(2024)SQUID: Faster Analytics via Sampled Quantile EstimationProceedings of the ACM on Networking10.1145/36768732:CoNEXT3(1-23)Online publication date: 21-Aug-2024
https://doi.org/10.1145/3676873
Monterubbiano ALanglet JWalzer SAntichi GReviriego PPontarelli S(2024)Lightweight Acquisition and Ranging of Flows in the Data PlaneACM SIGMETRICS Performance Evaluation Review10.1145/3673660.365506352:1(21-22)Online publication date: 13-Jun-2024
https://dl.acm.org/doi/10.1145/3673660.3655063
Srivastava MSekar VSekar VYu MSeneviratne AVeitch D(2024)Poster: Circa: Re-imagining Network Telemetry from an Approximation-First PerspectiveProceedings of the ACM SIGCOMM 2024 Conference: Posters and Demos10.1145/3672202.3673742(57-59)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3672202.3673742
Li EWu WZhaohua WLi ZNiu J(2024)SAROS: A Self-Adaptive Routing Oblivious Sampling Method for Network-wide Heavy Hitter DetectionProceedings of the 8th Asia-Pacific Workshop on Networking10.1145/3663408.3663429(142-148)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.1145/3663408.3663429
Liu KZhang JJiang ZZhang XGuo SBai YDong YZhang ZShi XWang LWei HWang ZPan YPan THuang T(2024)Hostmesh: Monitor and Diagnose Networks in Rail-optimized RoCE ClustersProceedings of the 8th Asia-Pacific Workshop on Networking10.1145/3663408.3663426(122-128)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.1145/3663408.3663426
Monterubbiano ALanglet JWalzer SAntichi GReviriego PPontarelli SGaretto MMarin ACiucu FFanti GRighter R(2024)Lightweight Acquisition and Ranging of Flows in the Data PlaneAbstracts of the 2024 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems10.1145/3652963.3655063(21-22)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3652963.3655063
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents