Document Open Access Logo

Give Me Some Slack: Efficient Network Measurements

Authors Ran Ben Basat, Gil Einziger, Roy Friedman

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.34.pdf
  • Filesize: 0.63 MB
  • 16 pages

Document Identifiers

Author Details

Ran Ben Basat
  • Department of Computer Science, Technion
Gil Einziger
  • Nokia Bell Labs
Roy Friedman
  • Department of Computer Science, Technion

Cite As Get BibTex

Ran Ben Basat, Gil Einziger, and Roy Friedman. Give Me Some Slack: Efficient Network Measurements. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.34

Abstract

Many networking applications require timely access to recent network measurements, which can be captured using a sliding window model. Maintaining such measurements is a challenging task due to the fast line speed and scarcity of fast memory in routers. In this work, we study the impact of allowing slack in the window size on the asymptotic requirements of sliding window problems. That is, the algorithm can dynamically adjust the window size between W and W(1+tau) where tau is a small positive parameter. We demonstrate this model's attractiveness by showing that it enables efficient algorithms to problems such as Maximum and General-Summing that require Omega(W) bits even for constant factor approximations in the exact sliding window model. Additionally, for problems that admit sub-linear approximation algorithms such as Basic-Summing and Count-Distinct, the slack model enables a further asymptotic improvement.
The main focus of the paper is on the widely studied Basic-Summing problem of computing the sum of the last W integers from {0,1 ...,R} in a stream. While it is known that Omega(W log R) bits are needed in the exact window model, we show that approximate windows allow an exponential space reduction for constant tau.
Specifically, for tau=Theta(1), we present a space lower bound of Omega(log(RW)) bits. Additionally, we show an Omega(log (W/epsilon)) lower bound for RW epsilon additive approximations and a Omega(log (W/epsilon)+log log R) bits lower bound for (1+epsilon) multiplicative approximations. Our work is the first to study this problem in the exact and additive approximation settings. For all settings, we provide memory optimal algorithms that operate in worst case constant time. This strictly improves on the work of [Mayur Datar et al., 2002] for (1+epsilon)-multiplicative approximation that requires O(epsilon^(-1) log(RW)log log (RW)) space and performs updates in O(log (RW)) worst case time. Finally, we show asymptotic improvements for the Count-Distinct, General-Summing and Maximum problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Streaming
  • Network Measurements
  • Statistics
  • Lower Bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Pankaj K. Agarwal, Graham Cormode, Zengfeng Huang, Jeff Phillips, Zhewei Wei, and Ke Yi. Mergeable summaries. In ACM PODS, 2012. Google Scholar
  2. Mohammad Alizadeh, Tom Edsall, Sarang Dharmapurikar, Ramanan Vaidyanathan, Kevin Chu, Andy Fingerhut, Vinh The Lam, Francis Matus, Rong Pan, Navindra Yadav, and George Varghese. Conga: Distributed congestion-aware load balancing for datacenters. In ACM SIGCOMM 2014 Conference, SIGCOMM'14, Chicago, IL, USA, August 17-22, 2014, ACM SIGCOMM 2014, 2014. URL: http://dx.doi.org/10.1145/2619239.2626316.
  3. Ran Ben Basat, Gil Einziger, Roy Friedman, and Yaron Kassner. Efficient Summing over Sliding Windows. In SWAT, 2016. Google Scholar
  4. Ran Ben Basat, Gil Einziger, Roy Friedman, Marcelo Caggiani Luizelli, and Erez Waisbard. Constant time updates in hierarchical heavy hitters. In ACM SIGCOMM, 2017. Google Scholar
  5. R. Ben Basat, G. Einziger, and R. Friedman. Give Me Some Slack: Efficient Network Measurements. ArXiv e-prints, 2018. URL: http://arxiv.org/abs/1703.01166.
  6. Ran Ben-Basat, Gil Einziger, Roy Friedman, and Yaron Kassner. Heavy hitters in streams and sliding windows. In IEEE INFOCOM, 2016. Google Scholar
  7. Ran Ben-Basat, Gil Einziger, Roy Friedman, and Yaron Kassner. Optimal elephant flow detection. In IEEE INFOCOM, 2017. Google Scholar
  8. Ran Ben-Basat, Gil Einziger, Roy Friedman, and Yaron Kassner. Randomized admission policy for efficient top-k and frequency estimation. In IEEE INFOCOM, 2017. Google Scholar
  9. Theophilus Benson, Ashok Anand, Aditya Akella, and Ming Zhang. Microte: Fine grained traffic engineering for data centers. In ACM CoNEXT, 2011. Google Scholar
  10. Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, and George Varghese. An improved construction for counting bloom filters. In ESA, 2006. Google Scholar
  11. Y. Chabchoub and G. Hebrail. Sliding hyperloglog: Estimating cardinality in a data stream over a sliding window. In 2010 IEEE ICDM Workshops, 2010. Google Scholar
  12. Varun Chandola, Arindam Banerjee, and Vipin Kumar. Anomaly detection: A survey. In ACM CSUR, 2007. Google Scholar
  13. Min Chen and Shigang Chen. Counter tree: A scalable counter architecture for per-flow traffic measurement. In IEEE ICNP, 2015. Google Scholar
  14. Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics over sliding windows. SIAM Journal of Computing, 2002. Google Scholar
  15. G. Einziger and R. Friedman. TinyLFU: A highly efficient cache admission policy. In PDP 2014, 2014. Google Scholar
  16. Gil Einziger, Benny Fellman, and Yaron Kassner. Independent counter estimation buckets. In IEEE INFOCOM, 2015. Google Scholar
  17. Gil Einziger and Roy Friedman. Counting with TinyTable: Every Bit Counts! In ICDCN 2016, 2016. Google Scholar
  18. Cristian Estan, George Varghese, and Mike Fisk. Bitmap algorithms for counting active flows on high speed links. In ACM IMC, 2003. Google Scholar
  19. Éric Fusy and Frécéric Giroire. Estimating the number of active flows in a data stream over a sliding window. In ANALCO, 2007. Google Scholar
  20. Sumit Ganguly, Minos Garofalakis, Rajeev Rastogi, and Krishan Sabnani. Streaming algorithms for robust, real-time detection of ddos attacks. In 27th IEEE International Conference on Distributed Computing Systems (ICDCS 2007), June 25-29, 2007, Toronto, Ontario, Canada, ICDCS, 2007. Google Scholar
  21. Pedro Garcia-Teodoro, Jesús E. Díaz-Verdejo, Gabriel Maciá-Fernández, and E. Vázquez. Anomaly-based network intrusion detection: Techniques, systems and challenges. Computers and Security, 2009. Google Scholar
  22. Phillip B. Gibbons and Srikanta Tirthapura. Distributed streams algorithms for sliding windows. In SPAA, 2002. Google Scholar
  23. Nan Hua, Bill Lin, Jun (Jim) Xu, and Haiquan (Chuck) Zhao. Brick: A novel exact active statistics counter architecture. In ACM/IEEE ANCS, 2008. Google Scholar
  24. Abdul Kabbani, Mohammad Alizadeh, Masato Yasuda, Rong Pan, and Balaji Prabhakar. Af-qcn: Approximate fairness with quantized congestion notification for multi-tenanted data centers. In IEEE HOTI, 2010. Google Scholar
  25. Yang Liu, Wenji Chen, and Yong Guan. Near-optimal approximate membership query over time-decaying windows. In IEEE INFOCOM, 2013. Google Scholar
  26. B. Mukherjee, L.T. Heberlein, and K.N. Levitt. Network intrusion detection. Network, IEEE, 1994. Google Scholar
  27. Moni Naor and Eylon Yogev. Sliding bloom filters. In ISAAC. Springer, 2013. Google Scholar
  28. Erez Tsidon, Iddo Hanniel, and Isaac Keslassy. Estimators also need shared values to grow together. In IEEE INFOCOM, 2012. Google Scholar
  29. Hao Wang, H. Zhao, Bill Lin, and Jun Xu. Dram-based statistics counter array architecture with performance guarantee. IEEE/ACM Transactions on Networking, 2012. Google Scholar
  30. Li Yang, Wu Hao, Pan Tian, Dai Huichen, Lu Jianyuan, and Liu Bin. Case: Cache-assisted stretchable estimator for high speed per-flow measurement. In IEEE INFOCOM, 2016. Google Scholar
  31. L. Ying, R. Srikant, and X. Kang. The power of slightly more than one sample in randomized load balancing. In IEEE INFOCOM, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact