Ran Ben Basat
ABSTRACT
Network measurement is an essential building block for a variety of network applications such as traffic engineering, quality of service, load-balancing and intrusion detection. Maintaining a per-flow state is often impractical due to the large number of flows, and thus modern systems use complex data structures that are updated with each incoming packet. Therefore, designing measurement applications that operate at line speed is a significant challenge in this domain.
In this work, we address this challenge by providing a unified mechanism that improves the update time of a variety of network algorithms. We do so by identifying, studying, and optimizing a common algorithmic pattern that we call q-MAX. The goal is to maintain the largest q values in a stream of packets. We formally analyze the problem and introduce interval and sliding window algorithms that have a worst-case constant update time. We show that our algorithms perform up to X20 faster than library algorithms, and using these new algorithms for several popular measurement applications yields a throughput improvement of up to X12 on real network traces. Finally, we implemented the scheme within Open vSwitch, a state of the art virtual switch. We show that q-MAX based monitoring runs in line speed while current monitoring techniques are significantly slower.
- https://www.openvswitch.org/.Google Scholar
- Network-wide routing-oblivious heavy hitters - available: https://github.com/jalilm/tdhh.Google Scholar
- q-max: A unified scheme for improving network measurement throughput - available: https://github.com/jalilm/q-max.Google Scholar
- Redis - in-memory data structure store.Google Scholar
- The CAIDA UCSD Anonymized Internet Traces 2016 - January. 21st.Google Scholar
- The CAIDA UCSD Anonymized Internet Traces 2018 - equinix-nyc 2018-03-15, Direction A. https://www.caida.org/data/monitors/passive-equinix-nyc.xml.Google Scholar
- Anderson, D., Beyan, P., Lang, K., Liberty, E., Rhodes, L., and Thaler, J. A high-performance algorithm for identifying frequent items in data streams. In ACM IMC (2017).Google Scholar
- Andersson, A., Hagerup, T., Nilsson, S., and Raman, R. Sorting in linear time? J. Computer and System Sciences (1998).Google Scholar
- Arashloo, M. T., Koral, Y., Greenberg, M., Rexford, J., and Walker, D. Snap: Stateful network-wide abstractions for packet processing. In ACM SIGCOMM (2016).Google Scholar
- Assaf, E., Ben-Basat, R., Einziger, G., and Friedman, R. Pay for a sliding bloom filter and get counting, distinct elements, and entropy for free. In IEEE INFOCOM (2018).Google Scholar
- B Yossef, Z., Jayram, T., Kumar, R., Sivakumar, D., and Trevisan, L. Counting distinct elements in a data stream. In RANDOM (2002).Google Scholar
- Basat, R., Einziger, G., Friedman, R., Luizelli, M., and Waisbard, E. Constant time updates in hierarchical heavy hitters. In ACM SIGCOMM (2017).Google Scholar
- Basat, R. B., Chen, X., Einziger, G., Friedman, R., and Kassner, Y. Randomized admission policy for efficient top-k, frequency, and volume estimation. IEEE/ACM Trans. Netw. (2019).Google Scholar
- Basat, R. B., Einziger, G., and Friedman, R. Give Me Some Slack: Efficient Network Measurements. In MFCS (2018).Google Scholar
- Ben-Basat, R., Chen, X., Einziger, G., and Rottenstreich, O. Efficient measurement on programmable switches using probabilistic recirculation. In IEEE ICNP (2018).Google Scholar
- Ben-Basat, R., Einziger, G., Friedman, R., and Kassner, Y. Heavy hitters in streams and sliding windows. In IEEE INFOCOM (2016).Google Scholar
- Ben-Basat, R., Einziger, G., Keslassy, I., Orda, A., Vargaftik, S., and Waisbard, E. Memento: making sliding windows efficient for heavy hitters. In ACM CoNEXT (2018).Google Scholar
- Ben Basat, R., Einziger, G., Moraney, J., and Raz, D. Network-wide routing oblivious heavy hitters. In ACM/IEEE ANCS (2018).Google Scholar
- Benson, T., Akella, A., and Maltz, D. A. Network traffic characteristics of data centers in the wild. In ACM IMC (2010).Google Scholar
- Benson, T., Anand, A., Akella, A., and Zhang, M. Microte: Fine grained traffic engineering for data centers. In ACM CoNEXT (2011).Google Scholar
- Blum, M., Floyd, R. W., Pratt, V., Riyest, R. L., and Tarjan, R. E. Time bounds for selection. J. of Computer and System Sciences (1973).Google Scholar
- Charikar, M., Chen, K., and Farach-Colton, M. Finding frequent items in data streams. In ICALP (2002).Google ScholarDigital Library
- Chiesa, M., Rétyári, G., and Schapira, M. Lying your way to better traffic engineering. In ACM CoNEXT (2016).Google ScholarDigital Library
- Cohen, E., and Kaplan, H. Summarizing data using bottom-k sketches. In ACM PODC (2007).Google Scholar
- Cohen, E., and Strauss, M. Maintaining time-decaying stream aggregates. In ACM SIGMOD (2003), pp. 223--233.Google ScholarDigital Library
- Cormode, G., Korn, F., and Tirthapura, S. Exponentially decayed aggregates on data streams. In IEEE ICDE (April 2008).Google Scholar
- Cormode, G., and Muthukrishnan, S. Diamond in the rough: Finding hierarchical heavy hitters in multi-dimensional data. In In Proceedings of the 23rd ACM SIGMOD International Conference on Management of Data (2004).Google ScholarDigital Library
- Cormode, G., and Muthukrishnan, S. An improved data stream summary: The count-min sketch and its applications. J. Algorithms 55 (2004).Google Scholar
- Cormode, G., and Muthukrishnan, S. What's hot and what's not: Tracking most frequent items dynamically. ACM Trans. Database Syst. (2005).Google Scholar
- Cormode, G., and Muthukrishnan, S. What's hot and what's not: Tracking most frequent items dynamically. ACM Trans. Database Syst. (2005).Google Scholar
- Cormode, G., and Muthukrishnan, S. What's hot and what's not: Tracking most frequent items dynamically. ACM Trans. Database Syst. 30, 1 (Mar. 2005).Google ScholarDigital Library
- Datar, M., Gionis, A., Indyk, P., and Motwani, R. Maintaining stream statistics over sliding windows. SIAM J. Comput. (2002).Google Scholar
- Demaine, E. D., López-Ortiz, A., and Munro, J. I. Frequency estimation of internet packet streams with limited space. In Proc. of the 10th Annual European Symposium on Algorithms (2002), ESA, Springer-Verlag.Google ScholarCross Ref
- Demianiuk, V., Gorinsky, S., Nikolenko, S. I., and Kogan, K. Robust Distributed Monitoring of Traffic Flows. In IEEE ICNP (2019).Google Scholar
- Dimitropoulos, X., Hurley, P., and Kind, A. Probabilistic lossy counting: An efficient algorithm for finding heavy hitters. SIGCOMM Comput. Commun. Rev. 38, 1 (Jan. 2008).Google ScholarDigital Library
- Dittmann, G., and Herkersdorf, A. Network processor load balancing for high-speed links. In SPECTS (2002).Google Scholar
- Duffield, N., Lund, C., and Thorup, M. Priority sampling for estimation of arbitrary subset sums. J. ACM (2007).Google Scholar
- Duffield, N., Xu, Y., Xia, L., Ahmed, N. K., and Yu, M. Stream aggregation through order sampling. In ACM CIKM (2017).Google Scholar
- Duffield, N. G., and Grossglauser, M. Trajectory sampling for direct traffic observation. IEEE/ACM Transactions Networking (2001).Google Scholar
- Estan, C., and Varghese, G. New directions in traffic measurement and accounting. SIGCOMM Comput. Commun. Rev. 32, 4 (Aug. 2002).Google ScholarDigital Library
- Fusy, E., and Giroire, F. Estimating the number of active flows in a data stream over a sliding window. In ANALCO (2007).Google Scholar
- Garcia-Teodoro, P., DãŊaz-Verdejo, J. E., Maciãą-Fernãąndez, G., and Vãązquez, E. Anomaly-based network intrusion detection: Techniques, systems and challenges. Computers and Security (2009).Google Scholar
- Gu, Y., McCallum, A., and Towsley, D. Detecting anomalies in network traffic using maximum entropy estimation. In ACM IMC (2005).Google Scholar
- Gupta, A., Harrison, R., Pawar, A., Birkner, R., Canini, M., Feamster, N., Rexford, J., and Willinger, W. Sonata: Query-driven network telemetry. ACM SIGCOMM (2018).Google Scholar
- Han, Y. Deterministic sorting in o(nlog log n) time and linear space. In ACM STOC (2002).Google Scholar
- Han, Y., and Thorup, M. Integer sorting in o (n(log log n)) expected time and linear space. In IEEE FOCS (2002).Google Scholar
- Harrison, R., Cai, Q., Gupta, A., and Rexford, J. Network-wide heavy hitter detection with commodity switches. In ACM SOSR (2018).Google Scholar
- Harrison, R., Cai, Q., Gupta, A., and Rexford, J. Network-wide heavy hitter detection with commodity switches. In SOSR (2018).Google Scholar
- Huang, Q., Jin, X., Lee, P. P. C., Li, R., Tang, L., Chen, Y.-C., and Zhang, G. Sketchvisor: Robust network measurement for software packet processing. In ACM SIGCOMM (2017).Google Scholar
- Jung, J., Paxson, V., Berger, A. W., and Balakrishnan, H. Fast portscan detection using sequential hypothesis testing. In IEEE S&P (2004).Google Scholar
- Kabbani, A., Alizadeh, M., Yasuda, M., Pan, R., and Prabhakar, B. Af-qcn: Approximate fairness with quantized congestion notification for multi-tenanted data centers. In HOTI (2010).Google Scholar
- Katta, N., Ghag, A., Hira, M., Keslassy, I., Bergman, A., Kim, C., and Rexford, J. Clove: Congestion-aware load-balancing at the virtual edge. In ACM CoNEXT (2017).Google Scholar
- Kranakis, E., Morin, P., and Tang, Y. Bounds for frequency estimation of packet streams. In In SIROCCO (2003).Google Scholar
- Langley, A., Riddoch, A., Wilk, A., Vicente, A., Krasic, C. B., Shi, C., Zhang, D., Yang, F., Kouranov, F., Swett, I., Iyengar, J., Bailey, J., Dorfman, J. C., Roskind, J., Kulik, J., Westin, P. G., Tenneti, R., Shade, R., Hamilton, R., Vasiliev, V., and Chang, W.-T. The quic transport protocol: Design and internetscale deployment. In ACM SIGCOMM (2017).Google Scholar
- Lee, D., Choi, J., Kim, J.-H., Noh, S. H., Min, S. L., Cho, Y., and Kim, C. S. Lrfu: a spectrum of policies that subsumes the least recently used and least frequently used policies. IEEE Trans. on Comp. (2001).Google Scholar
- Li, Y., Miao, R., Kim, C., and Yu, M. Flowradar: A better netflow for data centers. In USENIX NSDI (2016).Google Scholar
- Li, Y., Miao, R., Kim, C., and Yu, M. Lossradar: Fast detection of lost packets in data center networks. In ACM CoNEXT (2016).Google Scholar
- Liu, Y., Chen, W., and Guan, Y. Near-optimal approximate membership query over time-decaying windows. In IEEE INFOCOM (2013).Google Scholar
- Liu, Z., Ben-Basat, R., Einziger, G., Kassner, Y., Braverman, V., Friedman, R., and Sekar, V. Nitrosketch: Robust and general sketch-based monitoring in software switches. In ACM SIGCOMM (2019).Google Scholar
- Liu, Z., Manousis, A., Vorsanger, G., Sekar, V., and Braverman, V. One sketch to rule them all: Rethinking network flow monitoring with univmon. In ACM SIGCOMM (2016).Google Scholar
- Megiddo, N., and Modha, D. S. Arc: A self-tuning, low overhead replacement cache. In USENIX FAST (2003).Google Scholar
- Metwally, A., Agrawal, D., and Abbadi, A. E. Efficient computation of frequent and top-k elements in data streams. In IN ICDT (2005).Google Scholar
- Mukherjee, B., Heberlein, L., and Levitt, K. Network intrusion detection. Network, IEEE 8, 3 (May 1994).Google ScholarDigital Library
- Sivaraman, V., Narayana, S., Rottenstreich, O., Muthukrishnan, S., and Rexford, J. Heavy-hitter detection entirely in the data plane. In ACM SOSR (2017).Google Scholar
- Uyeda, F., Foschini, L., Baker, F., Suri, S., and Varghese, G. Efficiently measuring bandwidth at all time scales. In NSDI (2011).Google ScholarDigital Library
- Wang, D. Skiplist - ustcdane on github. https://github.com/ustcdane/skiplist.Google Scholar
- Yang, T., Jiang, J., Liu, P., Huang, Q., Gong, J., Zhou, Y., Miao, R., Li, X., and Uhlig, S. Elastic sketch: adaptive and fast network-wide measurements. In SIGCOMM (2018).Google Scholar
- Yu, M., Jose, L., and Miao, R. Software defined traffic measurement with opens-ketch. In USENIX NSDI (2013).Google ScholarDigital Library
- Zhu, Y., Kang, N., Cao, J., Greenberg, A., Lu, G., Mahajan, R., Maltz, D., Yuan, L., Zhang, M., Zhao, B. Y., and Zheng, H. Packet-level telemetry in large datacenter networks. In ACM SIGCOMM (2015).Google ScholarDigital Library
Index Terms
- q-MAX: A Unified Scheme for Improving Network Measurement Throughput
Recommendations
A faster and more efficient q-MAX algorithm
CoNEXT '20: Proceedings of the 16th International Conference on emerging Networking EXperiments and TechnologiesThe q-MAX problem, which seeks to find the q largest elements in a data stream, has numerous networking applications including sketches, network-wide heavy hitters, and others. In this poster, we propose an improvement to the q-MAX algorithm [5] that ...
A Predictive Q-Learning Algorithm for Deflection Routing in Buffer-less Networks
SMC '13: Proceedings of the 2013 IEEE International Conference on Systems, Man, and CyberneticsIn this paper, we introduce a predictive Q-learning deflection routing (PQDR) algorithm for buffer-less networks. Q-learning, one of the reinforcement learning (RL) algorithms, has been considered for routing in computer networks. The RL-based ...
L, Q, R, and T: which spin bit cousin is here to stay?
ANRW '21: Proceedings of the Applied Networking Research WorkshopNetwork operators utilize traffic monitoring to locate and fix faults or performance bottlenecks. This often relies on intrinsic protocol semantics, e.g., sequence numbers, that many protocols share implicitly through their packet headers. The arrival ...
Comments