research-article

Free access

Re-evaluating Measurement Algorithms in Software

Authors:

Omid Alipourfard,

Masoud Moshref,

Minlan YuAuthors Info & Claims

HotNets-XIV: Proceedings of the 14th ACM Workshop on Hot Topics in Networks

Article No.: 20, Pages 1 - 7

https://doi.org/10.1145/2834050.2834064

Published: 16 November 2015 Publication History

Abstract

With the advancement of multicore servers, there is a new trend of moving network functions to software servers. Measurement is critical to most network functions as it not only helps the operators understand the network usage and detect anomalies, but also produces feedback to the control loop in management tasks such as load balancing and traffic engineering. Traditional researches on measurement algorithms mainly focus on reducing the memory usage leveraging the fact that measurement can sustain bounded inaccuracy. In this study, we re-evaluate these algorithms on software servers in order to understand their tradeoffs of accuracy and performance. We observe that simple hash tables work better than more advanced measurement algorithms for a variety of measurement scenarios. This is because with better cache design in modern servers and the skewness in the access patterns of measurement tasks, the memory usage of measurement tasks is largely irrelevant to the packet processing performance.

Supplementary Material

MP4 File (a20.mp4)

Download
849.34 MB

References

[1]

http://www.7-cpu.com/cpu/Haswell.html.

[2]

Benchmarks : Intel mobile haswell (crystalwell): Memory sub-system. http://www.sisoftware.net/?d=qa&f=mem_hsw.

[3]

CAIDA Anonymized Internet Traces 2012. http://www.caida.org/data/passive/passive_2012_dataset.xml.

[4]

DPDK. http://dpdk.org.

[5]

AT&T Domain 2.0 vision white paper. http://goo.gl/YqSjkA, 2013.

[6]

M. Alizadeh, A. Greenberg, D. A. Maltz, J. Padhye, P. Patel, B. Prabhakar, S. Sengupta, and M. Sridharan. Data Center TCP (DCTCP). SIGCOMM computer communication review, 41(4):63--74, 2011.

Digital Library

[7]

T. Benson, A. Akella, and D. A. Maltz. Network Traffic Characteristics of Data Centers in the Wild. In IMC, 2010.

Digital Library

[8]

S. Boyd-Wickizer, M. F. Kaashoek, R. Morris, and N. Zeldovich. Non-scalable Locks Are Dangerous. In Linux Symposium, 2012.

[9]

M. Charikar, K. Chen, and M. Farach-Colton. Finding Frequent Items in Data Streams. In Automata, Languages and Programming, pages 693--703. Springer, 2002.

Digital Library

[10]

B. Claise. Cisco systems NetFlow services export version 9. 2004.

[11]

G. Cormode and M. Hadjieleftheriou. Finding Frequent Items in Data Streams. VLDB Endowment, 1(2), 2008.

Digital Library

[12]

G. Cormode and S. Muthukrishnan. An Improved Data Stream Summary: The Count-Min Sketch and its Applications. Journal of Algorithms, 55(1), 2005.

Digital Library

[13]

G. Cormode and S. Muthukrishnan. Space Efficient Mining of Multigraph Streams. In PODS, 2005.

Digital Library

[14]

G. Cormode and S. Muthukrishnan. Summarizing and Mining Skewed Data Streams. In SIAM International Conference on Data Mining, 2005.

[15]

A. Das. Intel's Embedded DRAM: New Era of Cache Memory, Overcoming SRAM's scaling. http://www.eetimes.com/author.asp?doc_id=1323410, 2014.

[16]

M. Dobrescu, K. Argyraki, G. Iannaccone, M. Manesh, and S. Ratnasamy. Controlling Parallelism in a Multicore Software Router. In PRESTO, 2010.

Digital Library

[17]

M. Dobrescu, K. Argyraki, and S. Ratnasamy. Toward Predictable Performance in Software Packet-Processing Platforms. In NSDI, 2012.

Digital Library

[18]

N. Duffield, C. Lund, and M. Thorup. Estimating Flow Distributions from Sampled Flow Statistics. In SIGCOMM, 2003.

Digital Library

[19]

D. Egloff and M. Leippold. Quantile Estimation with Adaptive Imprtance Sampling. The Annals of Statistics, 38(2):pp. 1244--1278, 2010.

[20]

C. Estan and G. Varghese. New Directions in Traffic Measurement and Accounting. In SIGCOMM, 2002.

Digital Library

[21]

É. Fusy, G. Olivier, and F. Meunier. Hyperloglog: The Analysis of a Near-optimal Cardinality Estimation Algorithm. In Analysis of Algorithms (AofA), 2007.

[22]

A. Ghodsi, V. Sekar, M. Zaharia, and I. Stoica. Multi-resource Fair Queueing for Packet Processing. In SIGCOMM, 2012.

[23]

M. Greenwald and S. Khanna. Space-efficient Online Computation of Quantile Summaries. In SIGMOD, 2001.

Digital Library

[24]

N. Hohn and D. Veitch. Inverting Sampled Traffic. In IMC, 2003.

Digital Library

[25]

J. Hwang, K. K. Ramakrishnan, and T. Wood. NetVM: High Performance and Flexible Networking Using Virtualization on Commodity Platforms. In NSDI, 2014.

Digital Library

[26]

A. Kalia, D. Zhou, M. Kaminsky, and D. G. Andersen. Raising the Bar for Using GPUs in Software Packet Processing. In NSDI, 2015.

Digital Library

[27]

F. Khan, N. Hosein, C.-N. Chuah, and S. Ghiasi. Streaming Solutions for Fine-Grained Network Traffic Measurements and Analysis. In ANCS, 2011.

Digital Library

[28]

E. Kohler, R. Morris, B. Chen, J. Jannotti, and M. F. Kaashoek. The Click Modular Router. Transaction on Computer Systems, 18(3):263--297, Aug. 2000.

Digital Library

[29]

F. Korn, S. Muthukrishnan, and Y. Wu. Modeling Skew in Data Streams. In SIGMOD, 2006.

Digital Library

[30]

A. Kumar, M. Sung, J. J. Xu, and J. Wang. Data Streaming Algorithms for Efficient and Accurate Estimation of Flow Size Distribution. In SIGMETRICS, 2004.

Digital Library

[31]

A. Lall, V. Sekar, M. Ogihara, J. Xu, and H. Zhang. Data Streaming Algorithms for Estimating Entropy of Network Traffic. In SIGMETRICS/Performance, 2006.

Digital Library

[32]

D. Levinthal. Performance Analysis Guide for Intel Core i7 Processor and Intel Xeon 5500 processors. https://software.intel.com/sites/products/collateral/hpc/vtune/performance_analysis_guide.pdf.

[33]

P. Li and C.-H. Zhang. A New Algorithm for Compressed Counting with Applications in Shannon Entropy Estimation in Dynamic Data. In COLT, 2011.

[34]

G. S. Manku, S. Rajagopalan, and B. G. Lindsay. Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets. In SIGMOD, 1999.

Digital Library

[35]

J. Martins, M. Ahmed, C. Raiciu, V. Olteanu, M. Honda, R. Bifulco, and F. Huici. ClickOS and the Art of Network Function Virtualization. In NSDI, 2014.

Digital Library

[36]

A. Metwally, D. Agrawal, and A. El Abbadi. Efficient computation of frequent and top-k elements in data streams. In ICDT, 2005.

Digital Library

[37]

M. Mitzenmacher, T. Steinke, and J. Thaler. Hierarchical heavy hitters with the space saving algorithm. arXiv preprint arXiv:1102.5540, 2011.

[38]

M. Moshref, M. Yu, and R. Govindan. Resource/Accuracy Tradeoffs in Software-Defined Measurement. In HotSDN, 2013.

Digital Library

[39]

A. Nucci and S. Ranjan. Method and apparatus for worm detection and containment in the internet core, 2010. US Patent 7,712,134.

[40]

P. Patel, D. Bansal, L. Yuan, A. Murthy, A. Greenberg, D. A. Maltz, R. Kern, H. Kumar, M. Zikos, H. Wu, C. Kim, and N. Karri. Ananta: Cloud Scale Load Balancing. In SIGCOMM, 2013.

Digital Library

[41]

R. Schweller, Z. Li, Y. Chen, Y. Gao, A. Gupta, Y. Zhang, P. A. Dinda, M.-Y. Kao, and G. Memik. Reversible Sketches: Enabling Monitoring and Analysis over High-speed Data Streams. Transaction on Networking, 15(5), Oct. 2007.

Digital Library

[42]

V. Sekar, M. K. Reiter, and H. Zhang. Revisiting the Case for a Minimalist Approach for Network Flow Monitoring. In IMC, 2010.

Digital Library

[43]

A. Vahdat. Enter the Andromeda zone - Google Cloud Platform's Latest Networking Stack. http://goo.gl/smN6W0.

[44]

S. Venkataraman, D. Song, P. B. Gibbons, and A. Blum. New Streaming Algorithms for Fast Detection of Superspreaders. In NDSS, 2005.

[45]

A. Verma, L. Pedrosa, M. Korupolu, D. Oppenheimer, E. Tune, and J. Wilkes. Large-scale cluster management at Google with Borg. In EuroSys, 2015.

Digital Library

[46]

R. Wang, D. Butnariu, and J. Rexford. OpenFlow-based Server Load Balancing Gone Wild. In Hot-ICE, 2011.

Digital Library

[47]

M. Yu, L. Jose, and R. Miao. Software Defined Traffic Measurement with OpenSketch. In NSDI, 2013.

Digital Library

[48]

Y. Zhang. An Adaptive Flow Counting Method for Anomaly Detection in SDN. In CoNEXT, 2013.

Digital Library

Cited By

Miao RZhang YZheng ZWang RZhang RYang TLiu ZJiang J(2023)CocoSketch: High-Performance Sketch-Based Measurement Over Arbitrary Partial Key QueryIEEE/ACM Transactions on Networking10.1109/TNET.2023.325722631:6(2653-2668)Online publication date: Dec-2023
https://doi.org/10.1109/TNET.2023.3257226
He JZhu JHuang Q(2023)HistSketch: A Compact Data Structure for Accurate Per-Key Distribution Monitoring2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00156(2008-2021)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00156
Zhang YLiu ZWang RYang TLi JMiao RLiu PZhang RJiang JKuipers FCaesar M(2021)CocoSketchProceedings of the 2021 ACM SIGCOMM 2021 Conference10.1145/3452296.3472892(207-222)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1145/3452296.3472892
Show More Cited By

Index Terms

Re-evaluating Measurement Algorithms in Software

Recommendations

Software maintainability measurement: a task complexity perspective
Foundations of a weak measurement-theoretic approach to software measurement
FASE'03: Proceedings of the 6th international conference on Fundamental approaches to software engineering

Measurement Theory has been proposed as an approach for providing software measurement with a sound basis. However, Measurement Theory has hardly ever been used for building new measures. Much more often, it has been used to analyze the properties of ...
Software Process and Product Measurement: International Conference, IWSMMENSURA 2007, Palma de Mallorca, Spain, November 5-8, 2007, Revised Papers

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

HotNets-XIV: Proceedings of the 14th ACM Workshop on Hot Topics in Networks

November 2015

189 pages

ISBN:9781450340472

DOI:10.1145/2834050

General Chairs:
Jaudelice de Oliveira
Drexel University
,
Jonathan Smith
University of Pennsylvania
,
Program Chairs:
Katerina Argyraki
EPFL
,
Philip Levis
Stanford University

Copyright © 2015 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 November 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Conference

HotNets-XIV

Sponsor:

SIGCOMM

HotNets-XIV: The 14th ACM Workshop on Hot Topics in Networks

November 16 - 17, 2015

PA, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 110 of 460 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
492
Total Downloads

Downloads (Last 12 months)93
Downloads (Last 6 weeks)18

Reflects downloads up to 08 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Miao RZhang YZheng ZWang RZhang RYang TLiu ZJiang J(2023)CocoSketch: High-Performance Sketch-Based Measurement Over Arbitrary Partial Key QueryIEEE/ACM Transactions on Networking10.1109/TNET.2023.325722631:6(2653-2668)Online publication date: Dec-2023
https://doi.org/10.1109/TNET.2023.3257226
He JZhu JHuang Q(2023)HistSketch: A Compact Data Structure for Accurate Per-Key Distribution Monitoring2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00156(2008-2021)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00156
Zhang YLiu ZWang RYang TLi JMiao RLiu PZhang RJiang JKuipers FCaesar M(2021)CocoSketchProceedings of the 2021 ACM SIGCOMM 2021 Conference10.1145/3452296.3472892(207-222)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1145/3452296.3472892
Tangari GCharalambides MTuncer DPavlou G(2020)Accuracy-Aware Adaptive Traffic Monitoring for Software DataplanesIEEE/ACM Transactions on Networking10.1109/TNET.2020.297695228:3(986-1001)Online publication date: Jun-2020
https://doi.org/10.1109/TNET.2020.2976952
Wang SSun CMeng ZWang MCao JXu MBi JHuang QMoshref MYang THu HZhang G(2020)Martini: Bridging the Gap between Network Measurement and Control Using Switching ASICs2020 IEEE 28th International Conference on Network Protocols (ICNP)10.1109/ICNP49622.2020.9259415(1-12)Online publication date: 13-Oct-2020
https://doi.org/10.1109/ICNP49622.2020.9259415
Liu ZBen-Basat REinziger GKassner YBraverman VFriedman RSekar VWu JHall W(2019)NitrosketchProceedings of the ACM Special Interest Group on Data Communication10.1145/3341302.3342076(334-350)Online publication date: 19-Aug-2019
https://dl.acm.org/doi/10.1145/3341302.3342076
Cohen RNezri Y(2019)Cardinality Estimation in a Virtualized Network Device Using Online Machine LearningIEEE/ACM Transactions on Networking10.1109/TNET.2019.294070527:5(2098-2110)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1109/TNET.2019.2940705
Wang YYang TWang RTai C(2019)Dynamic Sketch: Efficient and Adjustable Heavy Hitter Detection for Software Packet Processing2019 IEEE 8th International Conference on Cloud Networking (CloudNet)10.1109/CloudNet47604.2019.9064148(1-7)Online publication date: Nov-2019
https://doi.org/10.1109/CloudNet47604.2019.9064148
Zhou YAlipourfard OYu MYang T(2018)Accelerating network measurement in softwareACM SIGCOMM Computer Communication Review10.1145/3276799.327680048:3(2-12)Online publication date: 7-Sep-2018
https://dl.acm.org/doi/10.1145/3276799.3276800
Huang QLee PBao YGorinsky STapolcai J(2018)SketchlearnProceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication10.1145/3230543.3230559(576-590)Online publication date: 7-Aug-2018
https://dl.acm.org/doi/10.1145/3230543.3230559
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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