{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T10:40:35Z","timestamp":1780483235362,"version":"3.54.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"CoNEXT1","license":[{"start":{"date-parts":[[2024,3,28]],"date-time":"2024-03-28T00:00:00Z","timestamp":1711584000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-2003257, OAC-2126281, and OAC-212632"],"award-info":[{"award-number":["CNS-2003257, OAC-2126281, and OAC-212632"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Verizon Innovation LLC."}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Netw."],"published-print":{"date-parts":[[2024,3,28]]},"abstract":"<jats:p>Network telemetry systems have become hybrid combinations of state-of-the-art stream processors and modern programmable data-plane devices. However, the existing designs of such systems have not focused on ensuring that these systems are also deployable in practice, i.e., able to scale and deal with the dynamics in real-world traffic and query workloads. Unfortunately, efforts to scale these hybrid systems are hampered by severe constraints on available compute resources in the data plane (e.g., memory, ALUs). Similarly, the limited runtime programmability of existing hardware data-plane targets critically affects efforts to make these systems robust. This paper presents the design and implementation of DynaMap, a new hybrid telemetry system that is both robust and scalable. By planning for telemetry queries dynamically, DynaMap allows the remapping of stateful dataflow operators to data-plane registers at runtime. We model the problem of mapping dataflow operators to data-plane targets formally and develop a new heuristic algorithm for solving this problem. We implement our algorithm in prototype and demonstrate its feasibility with existing hardware targets based on Intel Tofino. Using traffic workloads from different real-world production networks, we show that our prototype of DynaMap improves performance on average by 1-2 orders of magnitude over state-of-the-art hybrid systems that use only static query planning.<\/jats:p>","DOI":"10.1145\/3649471","type":"journal-article","created":{"date-parts":[[2024,3,28]],"date-time":"2024-03-28T12:07:53Z","timestamp":1711627673000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Query Planning for Robust and Scalable Hybrid Network Telemetry Systems"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2428-3044","authenticated-orcid":false,"given":"Chaofan","family":"Shou","sequence":"first","affiliation":[{"name":"UC Berkeley, Berkeley, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-4249-225X","authenticated-orcid":false,"given":"Rohan","family":"Bhatia","sequence":"additional","affiliation":[{"name":"Google Inc., Mountain View, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6378-7440","authenticated-orcid":false,"given":"Arpit","family":"Gupta","sequence":"additional","affiliation":[{"name":"UC Santa Barbara, Santa Barbara, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-3914-7576","authenticated-orcid":false,"given":"Rob","family":"Harrison","sequence":"additional","affiliation":[{"name":"U.S. Military Academy, Westpoint, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3166-9212","authenticated-orcid":false,"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"UC Santa Barbara, Santa Barbara, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1384-8188","authenticated-orcid":false,"given":"Walter","family":"Willinger","sequence":"additional","affiliation":[{"name":"NIKSUN, Inc., Princeton, New Jersey, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,28]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"2014 IEEE Workshop on Statistical Signal Processing (SSP).","author":"Altmann Y.","unstructured":"Y. Altmann, S. McLaughlin, and N. Dobigeon. 2014. Sampling from a multivariate Gaussian distribution truncated on a simplex: A review. In 2014 IEEE Workshop on Statistical Signal Processing (SSP)."},{"key":"e_1_2_1_2_1","volume-title":"USENIX Security Symposium.","author":"Borders Kevin","year":"2012","unstructured":"Kevin Borders, Jonathan Springer, and Matthew Burnside. 2012. Chimera: A declarative language for streaming network traffic analysis. In USENIX Security Symposium."},{"key":"e_1_2_1_3_1","volume-title":"Proc. ACM SIGCOMM.","author":"Chen X.","unstructured":"X. Chen, S. Landau-Feibish, M. Braverman, and J. Rexford. 2020. BeauCoup: Answering Many Network Traffic Queries, One Memory Update at a Time. In Proc. ACM SIGCOMM."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 8th USENIX Conference on Hot Topics in Cloud Computing","author":"Chen Yu-Ting","year":"2016","unstructured":"Yu-Ting Chen, Jason Cong, Zhenman Fang, Jie Lei, and Peng Wei. 2016. When Apache Spark Meets FPGAs: A Case Study for next-Generation DNA Sequencing Acceleration. In Proceedings of the 8th USENIX Conference on Hot Topics in Cloud Computing (Denver, CO) (HotCloud'16). USENIX Association, USA, 64--70."},{"key":"e_1_2_1_5_1","volume-title":"Proc. ACM SIGMOD.","author":"Cranor C.","unstructured":"C. Cranor, T. Johnson, O. Spatschek, and V. Shkapenyuk. 2003. Gigascope: A stream database for network applications. In Proc. ACM SIGMOD."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"A. Deshpande Z. Ives and V. Raman. 2007. Adaptive Query Planning. In Foundations and Trends in Databases.","DOI":"10.1561\/9781601980359"},{"key":"e_1_2_1_7_1","unstructured":"Edgecore. 2022. Programmable Tofino switches for data centers. https:\/\/www.edge-core.com\/productsInfo.php?id=335."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3484266.3487367"},{"key":"e_1_2_1_9_1","volume-title":"Proc. ACM SIGCOMM.","author":"Gupta A.","unstructured":"A. Gupta, R. Harrison, M. Canini, N. Feamster, J. Rexford, and W. Willinger. 2018. Sonata: Query-driven network telemetry. In Proc. ACM SIGCOMM."},{"key":"e_1_2_1_10_1","volume-title":"Proc. NSDI.","author":"Handigol N.","unstructured":"N. Handigol, B. Heller, V. Jeyakumar, D. Mazi\u00e8res, and N. McKeown. 2014. I know what your packet did last hop: Using packet histories to troubleshoot networks. In Proc. NSDI."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3405669.3405820"},{"key":"e_1_2_1_12_1","series-title":"Chapter 7","volume-title":"Readings in Database Systems","author":"Hellerstein J.M.","unstructured":"J.M. Hellerstein. 2017. Query optimization. In In P. Bailis, J.M. Hellerstein, and M. Stonebraker, editors, Readings in Database Systems (Chapter 7)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2008.05.004"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516719"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SECPRI.2004.1301325"},{"key":"e_1_2_1_16_1","volume-title":"Proc. SOSR.","author":"Kim C.","unstructured":"C. Kim, A. Sivaraman, N. Katta, A. Bas, A. Dixit, and L.J. Wobker. 2015. In-band network telemetry via programmable dataplanes. In Proc. SOSR."},{"key":"e_1_2_1_17_1","volume-title":"Proc. APSys.","author":"Li Y.","unstructured":"Y. Li, K. Gao, X. Jin, and W. Xu. 2020. Concerto: Cooperative Network-Wide Telemetry with Controllable Error Rate. In Proc. APSys."},{"key":"e_1_2_1_18_1","volume-title":"Proc. NSDI.","author":"Li Y.","unstructured":"Y. Li, R. Miao, C. Kim, and M. Yu. 2016. FlowRadar: A Better NetFlow for Data Centers. In Proc. NSDI."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341302.3342076"},{"key":"e_1_2_1_20_1","unstructured":"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 ACM SIGCOMM."},{"key":"e_1_2_1_21_1","volume-title":"Proc. USENIX NSDI'22","author":"Misa Chris","year":"2022","unstructured":"Chris Misa, Walt O'Connor, Durairajan Ramakrishnan, Reza Rejaie, and Walter Willinger. 2022. Dynamic Scheduling of Approximate Telemetry Queries. In Proc. USENIX NSDI'22."},{"key":"e_1_2_1_22_1","unstructured":"MoonGen. 2021. MoonGen Packet Generator. http:\/\/scholzd.github.io\/MoonGen\/."},{"key":"e_1_2_1_23_1","volume-title":"Proc. ACM SIGCOMM.","author":"Moshref M.","unstructured":"M. Moshref, M. Yu, R. Govindan, and A. Vahdat. 2014. DREAM: dynamic resource allocation for software-defined measurement. In Proc. ACM SIGCOMM."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934879"},{"key":"e_1_2_1_25_1","volume-title":"Proc. ACM SIGCOCMM.","author":"Narayana S.","unstructured":"S. Narayana, A. Sivaraman, V. Nathan, P. Goyal, V. Arun, M. Alizadeh, V. Jeyakumar, and C. Kim. 2017. Language- Directed Hardware Design for Network Performance Monitoring. In Proc. ACM SIGCOCMM."},{"key":"e_1_2_1_26_1","unstructured":"opensoc 2015. OpenSOC. http:\/\/opensoc.github.io\/."},{"key":"e_1_2_1_27_1","unstructured":"P4. 2022. P4Runtime Specification. https:\/\/p4.org\/p4-spec\/p4runtime\/main\/P4Runtime-Spec.html."},{"key":"e_1_2_1_28_1","unstructured":"report [n. d.]. Apache Flink. http:\/\/flink.apache.org\/."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Richard Serfozo. 1999. Introduction to Stochastic Networks.","DOI":"10.1007\/978-1-4612-1482-3"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190558"},{"key":"e_1_2_1_31_1","volume-title":"Proc. ATC.","author":"Sonchack J.","unstructured":"J. Sonchack, O. Michel, A.J. Aviv, E. Keller, and Smith J.M. 2018. Scaling Hardware Accelerated Monitoring to Concurrent and Dynamic Queries With ?Flow. In Proc. ATC."},{"key":"e_1_2_1_32_1","volume-title":"12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16). 233--248.","author":"Tammana Praveen","unstructured":"Praveen Tammana, Rachit Agarwal, and Myungjin Lee. 2016. Simplifying datacenter network debugging with pathdump. In 12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16). 233--248."},{"key":"e_1_2_1_33_1","volume-title":"15th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 18). 453--456.","author":"Tammana Praveen","unstructured":"Praveen Tammana, Rachit Agarwal, and Myungjin Lee. 2018. Distributed network monitoring and debugging with switchpointer. In 15th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 18). 453--456."},{"key":"e_1_2_1_34_1","volume-title":"Proc. EuroSys.","author":"Tokusashi Y.","unstructured":"Y. Tokusashi, H.T. Dang, F. Pedone, R. Soule, and N. Zilberman. 2019. The Case For In-Network Computing On Demand. In Proc. EuroSys."},{"key":"e_1_2_1_35_1","unstructured":"url [n. d.]. Apache Spark. http:\/\/spark.apache.org\/."},{"key":"e_1_2_1_36_1","unstructured":"url [n. d.]. Barefoot's Tofino. https:\/\/www.barefootnetworks.com\/technology\/."},{"key":"e_1_2_1_37_1","unstructured":"url [n. d.]. Sonata Queries. https:\/\/github.com\/sonata-queries\/sonata-queries."},{"key":"e_1_2_1_38_1","volume-title":"Praveen Tammana, Ang Chen, and TS Eugene Ng.","author":"Wang Weitao","year":"2022","unstructured":"Weitao Wang, Xinyu Crystal Wu, Praveen Tammana, Ang Chen, and TS Eugene Ng. 2022. Closed-loop Network Performance Monitoring and Diagnosis with SpiderMon. In USENIX NSDI."},{"key":"e_1_2_1_39_1","unstructured":"Wikipedia. 2022. F-score. https:\/\/en.wikipedia.org\/wiki\/F-score."},{"key":"e_1_2_1_40_1","volume-title":"Forecasting sales by exponentially weighted moving averages. Management science 6, 3","author":"Winters Peter R","year":"1960","unstructured":"Peter R Winters. 1960. Forecasting sales by exponentially weighted moving averages. Management science 6, 3 (1960), 324--342."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3484266.3487377"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230543.3230544"},{"key":"e_1_2_1_43_1","volume-title":"16th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 19). 207--220.","author":"Yu Da","unstructured":"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 16th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 19). 207--220."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314212.3314215"},{"key":"e_1_2_1_45_1","unstructured":"Minlan Yu Lavanya Jose and Rui Miao. 2013. Software Defined Traffic Measurement with OpenSketch. In USENIX NSDI."},{"key":"e_1_2_1_46_1","volume-title":"Proc. ACM SIGCOMM.","author":"Yuan Y.","unstructured":"Y. Yuan, D. Lin, A. Mishra, S. Marwaha, R. Alur, and B. T. Loo. 2017. Quantitative Network Monitoring with NetQRE. In Proc. ACM SIGCOMM."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3544216.3544239"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Yu Zhou Dai Zhang Kai Gao Chen Sun Jiamin Cao Yangyang Wang Mingwei Xu and Jianping Wu. 2020. Newton: intent-driven network traffic monitoring. In ACM CoNEXT. 295--308.","DOI":"10.1145\/3386367.3431298"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Yibo Zhu Nanxi Kang Jiaxin Cao Albert Greenberg Guohan Lu Ratul Mahajan Dave Maltz Lihua Yuan Ming Zhang Ben Y. Zhao and Haitao Zheng. 2015. Packet-level telemetry in large datacenter networks. In ACM SIGCOMM.","DOI":"10.1145\/2785956.2787483"}],"container-title":["Proceedings of the ACM on Networking"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649471","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3649471","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T20:31:25Z","timestamp":1755981085000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649471"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,28]]},"references-count":49,"journal-issue":{"issue":"CoNEXT1","published-print":{"date-parts":[[2024,3,28]]}},"alternative-id":["10.1145\/3649471"],"URL":"https:\/\/doi.org\/10.1145\/3649471","relation":{},"ISSN":["2834-5509"],"issn-type":[{"value":"2834-5509","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,28]]},"assertion":[{"value":"2024-03-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}