More Web Proxy on the site http://driver.im/

research-article

SCREAM: sketch resource allocation for software-defined measurement

Authors:

Masoud Moshref,

Ramesh Govindan,

Amin VahdatAuthors Info & Claims

CoNEXT '15: Proceedings of the 11th ACM Conference on Emerging Networking Experiments and Technologies

Article No.: 14, Pages 1 - 13

https://doi.org/10.1145/2716281.2836099

Published: 01 December 2015 Publication History

Abstract

Software-defined networks can enable a variety of concurrent, dynamically instantiated, measurement tasks, that provide fine-grain visibility into network traffic. Recently, there have been many proposals for using sketches for network measurement. However, sketches in hardware switches use constrained resources such as SRAM memory, and the accuracy of measurement tasks is a function of the resources devoted to them on each switch. This paper presents SCREAM, a system for allocating resources to sketch-based measurement tasks that ensures a user-specified minimum accuracy. SCREAM estimates the instantaneous accuracy of tasks so as to dynamically adapt the allocated resources for each task. Thus, by finding the right amount of resources for each task on each switch and correctly merging sketches at the controller, SCREAM can multiplex resources among network-wide measurement tasks. Simulations with three measurement tasks (heavy hitter, hierarchical heavy hitter, and super source/destination detection) show that SCREAM can support more measurement tasks with higher accuracy than existing approaches.

References

[1]

Amazon CloudWatch. http://aws.amazon.com/cloudwatch/.

[2]

Amazon Web Services' Growth Unrelenting. http://news.netcraft.com/archives/2013/05/20/amazon-web-services-growth-unrelenting.html.

[3]

CAIDA Anonymized Internet Traces 2014. http://www.caida.org/data/passive/passive_2014_dataset.xml.

[4]

HP 5120 EI Switch Series: QuickSpecs. http://h18000.www1.hp.com/products/quickspecs/13850_na/13850_na.PDF.

[5]

P. K. Agarwal, G. Cormode, Z. Huang, J. Phillips, Z. Wei, and K. Yi. Mergeable Summaries. In PODS, 2012.

Digital Library

[6]

M. Al-Fares, S. Radhakrishnan, B. Raghavan, N. Huang, and A. Vahdat. Hedera: Dynamic Flow Scheduling for Data Center Networks. In NSDI, 2010.

Digital Library

[7]

T. Bu, J. Cao, A. Chen, and P. P. C. Lee. Sequential Hashing: A Flexible Approach for Unveiling Significant Patterns in High Speed Networks. Computer Networks, 54(18):3309--3326, 2010.

Digital Library

[8]

J. Cao, Y. Jin, A. Chen, T. Bu, and Z.-L. Zhang. Identifying High Cardinality Internet Hosts. In INFOCOM, 2009.

[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]

Y. Chen, R. Griffith, J. Liu, R. H. Katz, and A. D. Joseph. Understanding TCP Incast Throughput Collapse in Datacenter Networks. In WREN, 2009.

Digital Library

[11]

H. Chernoff. A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations. The Annals of Mathematical Statistics, 23(4), 1952.

[12]

S. R. Chowdhury, M. F. Bari, R. Ahmed, and R. Boutaba. PayLess: A Low Cost Network Monitoring Framework for Software Defined Networks. In IEEE/IFIP Network Operations and Management Symposium, 2014.

[13]

G. Cormode. Sketch Techniques for Approximate Query Processing. In P. H. G. Cormode, M. Garofalakis and C. Jermaine, editors, Synposes for Approximate Query Processing: Samples, Histograms, Wavelets and Sketches, Foundations and Trends in Databases. NOW publishers, 2011.

[14]

G. Cormode and M. Hadjieleftheriou. Finding Frequent Items in Data Streams. In VLDB, 2008.

Digital Library

[15]

G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava. Finding Hierarchical Heavy Hitters in Data Streams. In VLDB, 2003.

Digital Library

[16]

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

[17]

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

Digital Library

[18]

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

[19]

A. Curtis, J. Mogul, J. Tourrilhes, P. Yalagandula, P. Sharma, and S. Banerjee. DevoFlow: Scaling Flow Management for High-Performance Networks. In SIGCOMM, 2011.

Digital Library

[20]

P. Flajolet and G. N. Martin. Probabilistic Counting Algorithms for Data Base Applications. Journal of computer and system sciences, 31(2):182--209, 1985.

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]

M. Hadjieleftheriou, J. W. Byers, and J. Kollios. Robust Sketching and Aggregation of Distributed Data Streams. Technical report, Boston University Computer Science Department, 2005.

[23]

S. Heule, M. Nunkesser, and A. Hall. HyperLogLog in Practice: Algorithmic Engineering of a State of the Art Cardinality Estimation Algorithm. In International Conference on Extending Database Technology, 2013.

Digital Library

[24]

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

[25]

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

Digital Library

[26]

B. Krishnamurthy, S. Sen, Y. Zhang, and Y. Chen. Sketch-based Change Detection: Methods, Evaluation, and Applications. In IMC, 2003.

Digital Library

[27]

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

[28]

G. M. Lee, H. Liu, Y. Yoon, and Y. Zhang. Improving Sketch Reconstruction Accuracy Using Linear Least Squares Method. In IMC, 2005.

Digital Library

[29]

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

[30]

Y. Lu, A. Montanari, B. Prabhakar, S. Dharmapurikar, and A. Kabbani. Counter braids: A Novel Counter Architecture for Per-flow Measurement. SIGMETRICS Performance Evaluation Review, 36(1):121--132, 2008.

Digital Library

[31]

S. Meng, A. K. Iyengar, I. M. Rouvellou, and L. Liu. Volley: Violation Likelihood Based State Monitoring for Dataceners. ICDCS, 2013.

Digital Library

[32]

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

Digital Library

[33]

M. Moshref, M. Yu, R. Govindan, and A. Vahdat. DREAM: Dynamic Resource Allocation for Software-defined Measurement. In SIGCOMM, 2014.

Digital Library

[34]

M. Moshref, M. Yu, R. Govindan, and A. Vahdat. SCREAM: Sketch Resource Allocation for Software-defined Measurement. Technical Report 15-960, Computer Science, USC, 2015. http://www.cs.usc.edu/assets/007/96891.pdf.

Digital Library

[35]

R. Schweller, A. Gupta, E. Parsons, and Y. Chen. Reversible Sketches for Efficient and Accurate Change Detection over Network Data Streams. In IMC, 2004.

Digital Library

[36]

V. Sekar, N. G. Duffield, O. Spatscheck, J. E. van der Merwe, and H. Zhang. LADS: Large-scale Automated DDoS Detection System. In ATC, 2006.

Digital Library

[37]

V. Sekar, M. K. Reiter, W. Willinger, H. Zhang, R. R. Kompella, and D. G. Andersen. CSAMP: A System for Network-Wide Flow Monitoring. In NSDI, 2008.

Digital Library

[38]

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

[39]

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

[40]

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

Digital Library

[41]

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

Digital Library

Cited By

Chen XXiao QLiu HHuang QZhang DLiu XHu LZhou HWu CRen KSekar VYu MSeneviratne AVeitch D(2024)Eagle: Toward Scalable and Near-Optimal Network-Wide Sketch Deployment in Network MeasurementProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672244(291-310)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672244
Srivastava MHung SNamkung HLin KLiu ZSekar VVallina-Rodríguez NSuarez-Tángil GLevin DPelsser C(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
https://dl.acm.org/doi/10.1145/3646547.3689016
Misa CDurairajan RRejaie RWillinger W(2024)DynATOS+: A Network Telemetry System for Dynamic Traffic and Query WorkloadsIEEE/ACM Transactions on Networking10.1109/TNET.2024.336743232:4(2810-2825)Online publication date: Aug-2024
https://doi.org/10.1109/TNET.2024.3367432
Show More Cited By

Index Terms

SCREAM: sketch resource allocation for software-defined measurement
1. Networks

Recommendations

DREAM: dynamic resource allocation for software-defined measurement
SIGCOMM '14: Proceedings of the 2014 ACM conference on SIGCOMM

Software-defined networks can enable a variety of concurrent, dynamically instantiated, measurement tasks, that provide fine-grain visibility into network traffic. Recently, there have been many proposals to configure TCAM counters in hardware switches ...
DREAM: dynamic resource allocation for software-defined measurement
SIGCOMM'14

Software-defined networks can enable a variety of concurrent, dynamically instantiated, measurement tasks, that provide fine-grain visibility into network traffic. Recently, there have been many proposals to configure TCAM counters in hardware switches ...
A case for on-machine load balancing

This paper diverges from the traditional load balancing, and introduces a new principle called the on-machine load balance rule. The on-machine load balance rule leads to resource allocations that are better in tolerating uncertainties in the processing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CoNEXT '15: Proceedings of the 11th ACM Conference on Emerging Networking Experiments and Technologies

December 2015

483 pages

ISBN:9781450334129

DOI:10.1145/2716281

General Chairs:
Felipe Huici
NEC Europe Ltd
,
Giuseppe Bianchi
University of Rome Tor Vergata

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

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

CoNEXT '15

Sponsor:

SIGCOMM

CoNEXT '15: Conference on emerging Networking Experiments and Technologies

December 1 - 4, 2015

Heidelberg, Germany

Acceptance Rates

Overall Acceptance Rate 198 of 789 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

90
Total Citations
View Citations
414
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)3

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen XXiao QLiu HHuang QZhang DLiu XHu LZhou HWu CRen KSekar VYu MSeneviratne AVeitch D(2024)Eagle: Toward Scalable and Near-Optimal Network-Wide Sketch Deployment in Network MeasurementProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672244(291-310)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672244
Srivastava MHung SNamkung HLin KLiu ZSekar VVallina-Rodríguez NSuarez-Tángil GLevin DPelsser C(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
https://dl.acm.org/doi/10.1145/3646547.3689016
Misa CDurairajan RRejaie RWillinger W(2024)DynATOS+: A Network Telemetry System for Dynamic Traffic and Query WorkloadsIEEE/ACM Transactions on Networking10.1109/TNET.2024.336743232:4(2810-2825)Online publication date: Aug-2024
https://doi.org/10.1109/TNET.2024.3367432
Li FLv YYan YGao CWang XCao J(2024)Learning-Based Sketch for Adaptive and High-Performance Network MeasurementIEEE/ACM Transactions on Networking10.1109/TNET.2024.336417632:3(2571-2585)Online publication date: Jun-2024
https://doi.org/10.1109/TNET.2024.3364176
Chen XLiu HXiao QHuang QZhang DZhou HZhou BWu CLiu XYang Q(2024)Hermes: Low-Overhead Inter-Switch Coordination in Network-Wide Data Plane Program DeploymentIEEE/ACM Transactions on Networking10.1109/TNET.2024.336132432:4(2842-2857)Online publication date: Aug-2024
https://doi.org/10.1109/TNET.2024.3361324
Sun HHuang QLee PBai WZhu FBao Y(2024)Distributed Network Telemetry With Resource Efficiency and Full AccuracyIEEE/ACM Transactions on Networking10.1109/TNET.2023.332734532:3(1857-1872)Online publication date: Jun-2024
https://doi.org/10.1109/TNET.2023.3327345
Li FChen SJia XGao CWang PWang XCao J(2024)Distributed Program Deployment for Resource-Aware Programmable SwitchesIEEE Transactions on Computers10.1109/TC.2024.335578673:5(1357-1370)Online publication date: 18-Jan-2024
https://dl.acm.org/doi/10.1109/TC.2024.3355786
Misa CDurairajan RGupta ARejaie RWillinger W(2024)Leveraging Prefix Structure to Detect Volumetric DDoS Attack Signatures with Programmable Switches2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00267(4535-4553)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00267
Aguilar RReviriego PLarrabeiti D(2024)Combined Filtering and Frequency Estimation with the Integrated Xor Filter and Count-Min Sketch2024 IEEE 25th International Conference on High Performance Switching and Routing (HPSR)10.1109/HPSR62440.2024.10635957(155-160)Online publication date: 22-Jul-2024
https://doi.org/10.1109/HPSR62440.2024.10635957
Liu HSun XChen XHuang QZhang DZhou HWu CLiu XKhan M(2024) : Low-latency and reliable event collection in network measurement Journal of Network and Computer Applications10.1016/j.jnca.2024.103904228(103904)Online publication date: Aug-2024
https://doi.org/10.1016/j.jnca.2024.103904
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents