Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3341302.3342076acmconferencesArticle/Chapter ViewAbstractPublication PagescommConference Proceedingsconference-collections
research-article
Public Access

Nitrosketch: robust and general sketch-based monitoring in software switches

Published: 19 August 2019 Publication History

Abstract

Software switches are emerging as a vital measurement vantage point in many networked systems. Sketching algorithms or sketches, provide high-fidelity approximate measurements, and appear as a promising alternative to traditional approaches such as packet sampling. However, sketches incur significant computation overhead in software switches. Existing efforts in implementing sketches in virtual switches make sacrifices on one or more of the following dimensions: performance (handling 40 Gbps line-rate packet throughput with low CPU footprint), robustness (accuracy guarantees across diverse workloads), and generality (supporting various measurement tasks).
In this work, we present the design and implementation of NitroSketch, a sketching framework that systematically addresses the performance bottlenecks of sketches without sacrificing robustness and generality. Our key contribution is the careful synthesis of rigorous, yet practical solutions to reduce the number of per-packet CPU and memory operations. We implement NitroSketch on three popular software platforms (Open vSwitch-DPDK, FD.io-VPP, and BESS) and evaluate the performance. We show that accuracy is comparable to unmodified sketches while attaining up to two orders of magnitude speedup, and up to 45% reduction in CPU usage.

Supplementary Material

MP4 File (p334-liu.mp4)

References

[1]
Omid Alipourfard, Masoud Moshref, and Minlan Yu. 2015. Re-evaluating Measurement Algorithms in Software. In Proc. of ACM HotNets.
[2]
Omid Alipourfard, Masoud Moshref, Yang Zhou, Tong Yang, and Minlan Yu. 2018. A Comparison of Performance and Accuracy of Measurement Algorithms in Software. In Proc. of ACM SOSR.
[3]
Mohammad Alizadeh, Tom Edsall, Sarang Dharmapurikar, Ramanan Vaidyanathan, Kevin Chu, Andy Fingerhut, Vinh The Lam, Francis Matus, Rong Pan, Navindra Yadav, and George Varghese. 2014. CONGA: Distributed Congestion-aware Load Balancing for Datacenters. In Proc. of ACM SIGCOMM.
[4]
Mohammad Alizadeh, Shuang Yang, Milad Sharif, Sachin Katti, Nick McKeown, Balaji Prabhakar, and Scott Shenker. 2013. pFabric: Minimal Near-optimal Datacenter Transport. In Proc. of ACM SIGCOMM.
[5]
Noga Alon, Yossi Matias, and Mario Szegedy. 1996. The Space Complexity of Approximating the Frequency Moments. In Proc. of ACM STOC.
[6]
Eran Assaf, Ran Ben-Basat, Gil Einziger, and Roy Friedman. 2018. Pay for a sliding bloom filter and get counting, distinct elements, and entropy for free. In Proc. of IEEE INFOCOM.
[7]
Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan. 2002. Counting Distinct Elements in a Data Stream. In Proc. of RANDOM.
[8]
Ran Ben Basat, Gil Einziger, Roy Friedman, Marcelo Caggiani Luizelli, and Erez Waisbard. 2017. Constant Time Updates in Hierarchical Heavy Hitters. In Proc. of ACM SIGCOMM and CoRR/1707.06778.
[9]
Ran Ben Basat, Gil Einziger, Roy Friedman, Marcelo Caggiani Luizelli, and Erez Waisbard. 2018. Volumetric Hierarchical Heavy Hitters. In Proc. of IEEE MASCOTS.
[10]
Ran Ben-Basat, Xiaoqi Chen, Gil Einziger, and Ori Rottenstreich. 2018. Efficient Measurement on Programmable Switches Using Probabilistic Recirculation. In Proc. of IEEE ICNP.
[11]
Theophilus Benson, Aditya Akella, and David A. Maltz. 2010. Network Traffic Characteristics of Data Centers in the Wild. In Proc. of ACM IMC.
[12]
Theophilus Benson, Ashok Anand, Aditya Akella, and Ming Zhang. 2011. MicroTE: Fine Grained Traffic Engineering for Data Centers. In Proc. of ACM CoNEXT.
[13]
Supratik Bhattacharyya, Andre Madeira, S. Muthukrishnan, and Tao Ye. 2007. How to Scalably and Accurately Skip Past Streams. In Proc. of IEEE ICDE.
[14]
CAIDA. 2016. The CAIDA UCSD Anonymized Internet Traces equinix-chicago. http://www.caida.org/data/passive/passive_2016_dataset.xml
[15]
CAIDA. 2018. The CAIDA UCSD Anonymized Internet Traces equinix-chicago. http://www.caida.org/data/passive/passive_dataset.xml
[16]
Cameron. 2015. Fast Concurrent Queue. https://github.com/cameron314/readerwriterqueue
[17]
Moses Charikar, Kevin Chen, and Martin Farach-Colton. 2002. Finding Frequent Items in Data Streams. In Proc. of ICALP.
[18]
Xiaoqi Chen, Shir Landau Feibish, Yaron Koral, Jennifer Rexford, and Ori Rottenstreich. 2018. Catching the Microburst Culprits with Snappy. In Proc. of SelfDN Workshop.
[19]
Xiaoqi Chen, Shir Landau Feibish, Yaron Koral, Jennifer Rexford, Ori Rottenstreich, Steven A. Monetti, and Wang Tzuu-Yi. 2019. Fine-Grained Queue Measurement in the Data Plane. In Proc. of ACM CoNEXT.
[20]
Kenjiro Cho. 2017. Recursive Lattice Search: Hierarchical Heavy Hitters Revisited. In Proc. of ACM IMC.
[21]
Cisco. 2012. Introduction to Cisco IOS NetFlow. https://www.cisco.com/c/en/us/products/collateral/ios-nx-os-software/ios-netflow/prod_white_paper0900aecd80406232.html
[22]
Cisco. 2015. Cisco Nexus 1000V Switch. https://www.cisco.com/c/en/us/products/switches/nexus-1000v-switch-vmware-vsphere/index.html
[23]
Yann Collet. 2016. xxHash Library. http://www.xxhash.com/
[24]
Gerald Combs. 1998. Wireshark. https://www.wireshark.org
[25]
Graham Cormode and Minos Garofalakis. 2007. Sketching Probabilistic Data Streams. In Proc. of ACM SIGMOD.
[26]
Graham Cormode, Flip Korn, S. Muthukrishnan, and Divesh Srivastava. 2008. Finding Hierarchical Heavy Hitters in Streaming Data. ACM Trans. Knowl. Discov. Data (2008).
[27]
Graham Cormode and S. Muthukrishnan. 2005. An Improved Data Stream Summary: The Count-Min Sketch and Its Applications. J. Algorithms (2005).
[28]
Andrew R. Curtis, Jeffrey C. Mogul, Jean Tourrilhes, Praveen Yalagandula, Puneet Sharma, and Sujata Banerjee. 2011. DevoFlow: Scaling Flow Management for High-performance Networks. In Proc. of ACM SIGCOMM.
[29]
Intel Ethernet Networking Division. 2018. Intel Ethernet Controller 710 Series Datasheet. https://www.intel.com/content/dam/www/public/us/en/documents/datasheets/xl710-10-40-controller-datasheet.pdf
[30]
Rick Durrett. 2010. Probability: Theory and Examples (4th ed.). Cambridge University Press.
[31]
Paul Emmerich, Sebastian Gallenmüller, Daniel Raumer, Florian Wohlfart, and Georg Carle. 2015. MoonGen: A Scriptable High-Speed Packet Generator. In Proc. of ACM IMC.
[32]
Zaoxing Liu et al. 2019. NitroSketch Source Code. https://github.com/zaoxing/NitroSketch
[33]
Seyed K. Fayaz, Yoshiaki Tobioka, Vyas Sekar, and Michael Bailey. 2015. Bohatei: Flexible and Elastic DDoS Defense. In Proc. of USENIX Security.
[34]
FD.io. 2018. Vector Packet Processing. https://fd.io/technology/
[35]
William Feller. 1943. Generalization of a Probability Limit Theorem of Cramér. Trans. Amer. Math. Soc. (1943).
[36]
Pedro Garcia-Teodoro, Jesus E. Diaz-Verdejo, Gabriel Macia-Fernandez, and E. Vazquez. 2009. Anomaly-Based Network Intrusion Detection: Techniques, Systems and Challenges. Computers and Security (2009).
[37]
Robert D Gordon. 1941. Values of Mills' Ratio of Area to Bounding Ordinate and of the Normal Probability Integral for Large Values of the Argument. The Annals of Mathematical Statistics (1941).
[38]
Arpit Gupta, Rob Harrison, Marco Canini, Nick Feamster, Jennifer Rexford, and Walter Willinger. 2018. Sonata: Query-Driven Streaming Network Telemetry. In Proc. of ACM SIGCOMM.
[39]
Sangjin Han, Keon Jang, Aurojit Panda, Shoumik Palkar, Dongsu Han, and Sylvia Ratnasamy. 2015. SoftNIC: A Software NIC to Augment Hardware. Technical Report.
[40]
Thomas Holterbach, Edgar Costa Molero, Maria Apostolaki, Alberto Dainotti, Stefano Vissicchio, and Laurent Vanbever. 2019. Blink: Fast Connectivity Recovery Entirely in the Data Plane. In Proc. of USENIX NSDI.
[41]
Nan Hua, Bill Lin, Jun (Jim) Xu, and Haiquan (Chuck) Zhao. 2008. BRICK: ANovel Exact Active Statistics Counter Architecture. In Proc. of ACM/IEEE ANCS.
[42]
Qi Huang, Ken Birman, Robbert van Renesse, Wyatt Lloyd, Sanjeev Kumar, and Harry C. Li. 2013. An Analysis of Facebook Photo Caching. In Proc. of ACM SOSP.
[43]
Qun Huang, Xin Jin, Patrick P. C. Lee, Runhui Li, Lu Tang, Yi-Chao Chen, and Gong Zhang. 2017. SketchVisor: Robust Network Measurement for Software Packet Processing. In Proc. of ACM SIGCOMM.
[44]
Qun Huang, Patrick PC Lee, and Yungang Bao. 2018. SketchLearn: Relieving User Burdens in ApproximateMeasurement with Automated Statistical Inference. In Proc. of ACM SIGCOMM.
[45]
Intel. 2012. Intel Advanced Vector Extensions. https://software.intel.com/en-us/isa-extensions/intel-avx
[46]
Intel. 2018. Intel VTune Amplifier. https://software.intel.com/en-us/vtune
[47]
T. S. Jayram, Andrew McGregor, S. Muthukrishnan, and Erik Vee. 2007. Estimating Statistical Aggregates on Probabilistic Data Streams. Proc. of ACM PODS (2007).
[48]
Xin Jin, Xiaozhou Li, Haoyu Zhang, Robert Soulé, Jeongkeun Lee, Nate Foster, Changhoon Kim, and Ion Stoica. 2017. NetCache: Balancing Key-Value Stores with Fast In-Network Caching. In Proc. of ACM SOSP.
[49]
Abdul Kabbani, Mohammad Alizadeh, Masato Yasuda, Rong Pan, and Balaji Prabhakar. 2010. AF-QCN: Approximate Fairness with Quantized Congestion Notification for Multi-tenanted Data Centers. In Prof. of IEEE HOTI.
[50]
Maurice George Kendall, Alan Stuart, and Keith Ord. 1987. Kendall's Advanced Theory of Statistics. Oxford University Press, Inc.
[51]
Balachander Krishnamurthy, Subhabrata Sen, Yin Zhang, and Yan Chen. 2003. Sketch-based Change Detection: Methods, Evaluation, and Applications. In Proc. of ACM IMC.
[52]
Ashwin Lall, Vyas Sekar, Mitsunori Ogihara, Jun Xu, and Hui Zhang. 2006. Data Streaming Algorithms for Estimating Entropy of Network Traffic. In Proc. of ACM SIGMETRICS/Performance.
[53]
Junda Liu, Aurojit Panda, Ankit Singla, Brighten Godfrey, Michael Schapira, and Scott Shenker. 2013. Ensuring Connectivity via Data Plane Mechanisms. In Proc. of USENIX NSDI.
[54]
Zaoxing Liu, Zhihao Bai, Zhenming Liu, Xiaozhou Li, Changhoon Kim, Vladimir Braverman, Xin Jin, and Ion Stoica. 2019. DistCache: Provable Load Balancing for Large-Scale Storage Systems with Distributed Caching. In Proc. of USENIX FAST.
[55]
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 Proc. of ACM SIGCOMM.
[56]
Zaoxing Liu, Greg Vorsanger, Vladimir Braverman, and Vyas Sekar. 2015. Enabling a "RISC" Approach for Software-Defined Monitoring Using Universal Streaming. In Proc. of ACM HotNets.
[57]
Yi Lu, Andrea Montanari, Balaji Prabhakar, Sarang Dharmapurikar, and Abdul Kabbani. 2008. Counter Braids: A Novel Counter Architecture for PerFlowMeasurement. In Proc. of ACM SIGMETRICS.
[58]
MACCDC. 2012. Capture Traces from Mid-Atlantic CCDC. http://www.netresec.com/?page=MACCDC
[59]
Jiri Matousek and Jan Vondrak. 2008. The Probabilistic Method-Lecture Notes. http://www.cs.cmu.edu/~15850/handouts/matousek-vondrak-prob-ln.pdf
[60]
Andrew McGregor, A Pavan, Srikanta Tirthapura, and David P. Woodruff. 2016. Space-Efficient Estimation of Statistics Over Sub-Sampled Streams. Algorithmica (2016).
[61]
Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. 2005. Efficient Computation of Frequent and Top-k Elements in Data Streams. In Proc. of ICDT.
[62]
Microsoft. 2016. Hyper-V Virtual Switch Overview. https://technet.microsoft.com/en-us/library/hh831823.aspx
[63]
Jayadev Misra and David Gries. 1982. Finding Repeated Elements. Technical Report.
[64]
M. Mitzenmacher, T. Steinke, and J. Thaler. 2012. Hierarchical Heavy Hitters with the Space Saving Algorithm. In Proc. of ALENEX.
[65]
Srinivas Narayana, Anirudh Sivaraman, Vikram Nathan, Prateesh Goyal, Venkat Arun, Mohammad Alizadeh, Vimalkumar Jeyakumar, and Changhoon Kim. 2017. Language-Directed Hardware Design for Network Performance Monitoring. In Proc. of ACM SIGCOMM.
[66]
George Nychis, Vyas Sekar, David G. Andersen, Hyong Kim, and Hui Zhang. 2008. An Empirical Evaluation of Entropy-based Traffic Anomaly Detection. In Proc. of ACM IMC.
[67]
Ben Pfaff, Justin Pettit, Teemu Koponen, Ethan Jackson, Andy Zhou, Jarno Rajahalme, Jesse Gross, Alex Wang, Joe Stringer, Pravin Shelar, Keith Amidon, and Martin Casado. 2015. The Design and Implementation of Open vSwitch. In Proc. of USENIX NSDI.
[68]
Robert Schweller, Ashish Gupta, Elliot Parsons, and Yan Chen. 2004. Reversible Sketches for Efficient and Accurate Change Detection over Network Data Streams. In Proc. of ACM IMC.
[69]
Vibhaalakshmi Sivaraman, Srinivas Narayana, Ori Rottenstreich, S. Muthukrishnan, and Jennifer Rexford. 2017. Heavy-Hitter Detection Entirely in the Data Plane. In Proc. of ACM SOSR.
[70]
Eric V Slud. 1977. Distribution inequalities for the binomial law. The Annals of Probability (1977).
[71]
Mea Wang, Baochun Li, and Zongpeng Li. 2004. sFlow: Towards Resource-Efficient and Agile Service Federation in Service Overlay Networks. In Proc. of IEEE ICDCS.
[72]
Li Yang, Wu Hao, Pan Tian, Dai Huichen, Lu Jianyuan, and Liu Bin. 2016. CASE: Cache-assisted Stretchable Estimator for High Speed Per-flow Measurement. In Proc. of IEEE INFOCOM.
[73]
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 Proc. of ACM SIGCOMM.
[74]
Lei Ying, R. Srikant, and Xiaohan Kang. 2015. The Power of Slightly More than One Sample in Randomized Load Balancing. In Proc. of IEEE INFOCOM.
[75]
Da Yu, Yibo Zhu, Behnaz Arzani, Rodrigo Fonseca, Tianrong Zhang, Karl Deng, and Lihua Yuan. 2019. dShark: A General, Easy to Program and Scalable Framework for Analyzing In-network Packet Traces. In Proc. of USENIX NSDI.
[76]
Minlan Yu, Lavanya Jose, and Rui Miao. 2013. Software Defined Traffic Measurement with OpenSketch. In Proc. of USENIX NSDI.

Cited By

View all
  • (2024)Flow/Path Performance ConsistencyProceedings of the 23rd ACM Workshop on Hot Topics in Networks10.1145/3696348.3696887(255-263)Online publication date: 18-Nov-2024
  • (2024)SQUID: Faster Analytics via Sampled Quantile EstimationProceedings of the ACM on Networking10.1145/36768732:CoNEXT3(1-23)Online publication date: 21-Aug-2024
  • (2024)RecenTo: Finding Top-K Flows of the Recent PastProceedings of the ACM on Networking10.1145/36768712:CoNEXT3(1-20)Online publication date: 21-Aug-2024
  • Show More Cited By

Index Terms

  1. Nitrosketch: robust and general sketch-based monitoring in software switches

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      SIGCOMM '19: Proceedings of the ACM Special Interest Group on Data Communication
      August 2019
      526 pages
      ISBN:9781450359566
      DOI:10.1145/3341302
      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

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 19 August 2019

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. flow monitoring
      2. sketch
      3. sketching algorithm
      4. software switch
      5. virtual switch

      Qualifiers

      • Research-article

      Funding Sources

      Conference

      SIGCOMM '19
      Sponsor:
      SIGCOMM '19: ACM SIGCOMM 2019 Conference
      August 19 - 23, 2019
      Beijing, China

      Acceptance Rates

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

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)650
      • Downloads (Last 6 weeks)107
      Reflects downloads up to 10 Nov 2024

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)Flow/Path Performance ConsistencyProceedings of the 23rd ACM Workshop on Hot Topics in Networks10.1145/3696348.3696887(255-263)Online publication date: 18-Nov-2024
      • (2024)SQUID: Faster Analytics via Sampled Quantile EstimationProceedings of the ACM on Networking10.1145/36768732:CoNEXT3(1-23)Online publication date: 21-Aug-2024
      • (2024)RecenTo: Finding Top-K Flows of the Recent PastProceedings of the ACM on Networking10.1145/36768712:CoNEXT3(1-20)Online publication date: 21-Aug-2024
      • (2024)Query Planning for Robust and Scalable Hybrid Network Telemetry SystemsProceedings of the ACM on Networking10.1145/36494712:CoNEXT1(1-27)Online publication date: 28-Mar-2024
      • (2024)Raising the Level of Abstraction for Sketch-Based Network Telemetry with SketchPlanProceedings of the 2024 ACM on Internet Measurement Conference10.1145/3646547.3689016(651-658)Online publication date: 4-Nov-2024
      • (2024)NetDPSyn: Synthesizing Network Traces under Differential PrivacyProceedings of the 2024 ACM on Internet Measurement Conference10.1145/3646547.3689011(545-554)Online publication date: 4-Nov-2024
      • (2024)High-Fidelity Cellular Network Control-Plane Traffic Generation without Domain KnowledgeProceedings of the 2024 ACM on Internet Measurement Conference10.1145/3646547.3688422(530-544)Online publication date: 4-Nov-2024
      • (2024)An Evaluation of Software Frequency SketchesProceedings of the 18th ACM International Conference on Distributed and Event-based Systems10.1145/3629104.3666028(18-29)Online publication date: 24-Jun-2024
      • (2024)CloudSentry: Two-Stage Heavy Hitter Detection for Cloud-Scale Gateway Overload ProtectionIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.330185235:4(616-633)Online publication date: Apr-2024
      • (2024) Marina : Realizing ML-Driven Real-Time Network Traffic Monitoring at Terabit Scale IEEE Transactions on Network and Service Management10.1109/TNSM.2024.338239321:3(2773-2790)Online publication date: Jun-2024
      • Show More Cited By

      View Options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Get Access

      Login options

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media