{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,22]],"date-time":"2026-10-22T17:47:10Z","timestamp":1792691230051,"version":"4.5.0"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T00:00:00Z","timestamp":1733788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2024,12,10]]},"abstract":"<jats:p>\n            In-band Network Telemetry (INT) enhances real-time, high-resolution network monitoring capabilities by incorporating fine-grained internal state information into packets. Utilizing INT for network-wide visualization can significantly bolster network management and operation. Although existing studies have made significant contributions, they have not been able to simultaneously meet the following two objectives: 1)\n            <jats:bold>Comprehensive visibility of the network's internal state,<\/jats:bold>\n            which refers to obtaining information on all switch ports and their corresponding link states; 2)\n            <jats:bold>Low measurement overhead,<\/jats:bold>\n            which involves reducing measurement bandwidth overhead and minimizing the impact of the measurement process on the network. We designed INT-MC to meet both of these objectives. INT-MC is an efficient and cost-effective network-wide telemetry solution based on matrix completion. By modeling link metadata as a matrix and leveraging its low-rank property, INT-MC selectively measures certain links. It then employs matrix completion algorithms to infer information about unmeasured links, thereby achieving low-overhead network-wide telemetry. Designing paths to cover the target links involves an NP-complete problem, and the high computational complexity may delay the measurement tasks. To circumvent this, we propose an improved scheme based on Eulerian digraph decomposition, transforming the path calculation problem into a high-information path selection problem, significantly reducing computational costs.\n          <\/jats:p>\n          <jats:p>We have implemented an INT-MC prototype within the NSFNet topology, consisting of 14 Tofino switches and 10 end-hosts, and conducted extensive experiments and evaluations. The results indicate that INT-MC incurs only 16% of the measurement overhead compared to existing network-wide telemetry solutions, while achieving nearly identical accuracy. Even under high-frequency measurements of 20 times per second, the bandwidth overhead of INT-MC is approximately 0.075% of the total bandwidth, exerting minimal impact on the network.<\/jats:p>","DOI":"10.1145\/3700433","type":"journal-article","created":{"date-parts":[[2024,12,13]],"date-time":"2024-12-13T12:12:12Z","timestamp":1734091932000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["INT-MC: Low-Overhead In-Band Network-Wide Telemetry Based on Matrix Completion"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-9637-8068","authenticated-orcid":false,"given":"Xin","family":"Zeng","sequence":"first","affiliation":[{"name":"Hunan University, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2163-2723","authenticated-orcid":false,"given":"Kun","family":"Xie","sequence":"additional","affiliation":[{"name":"Hunan University, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7408-2203","authenticated-orcid":false,"given":"Yanbiao","family":"Li","sequence":"additional","affiliation":[{"name":"Computer Network Information Center, Chinese Academy of Sciences &amp; University of Chinese Academy of Sciences, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4376-1800","authenticated-orcid":false,"given":"Ke","family":"Xu","sequence":"additional","affiliation":[{"name":"Computer Network Information Center, Chinese Academy of Sciences, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4964-1135","authenticated-orcid":false,"given":"Gaogang","family":"Xie","sequence":"additional","affiliation":[{"name":"Computer Network Information Center, Chinese Academy of Sciences &amp; University of Chinese Academy of Sciences, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7363-881X","authenticated-orcid":false,"given":"Jigang","family":"Wen","sequence":"additional","affiliation":[{"name":"Hunan University of Science and Technology, Xiangtan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5487-2814","authenticated-orcid":false,"given":"Yinchuan","family":"Cong","sequence":"additional","affiliation":[{"name":"Hunan University, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3813-3223","authenticated-orcid":false,"given":"Wei","family":"Liang","sequence":"additional","affiliation":[{"name":"Hunan University of Science and Technology, Xiangtan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,12,13]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18)","author":"Arzani Behnaz","year":"2018","unstructured":"Behnaz Arzani, Selim Ciraci, Luiz Chamon, Yibo Zhu, Hongqiang Harry Liu, Jitu Padhye, Boon Thau Loo, and Geoff Outhred. 2018. 007: Democratically finding the cause of packet drops. In 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18). 419--435."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789770.2789802"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3387514.3405894"},{"key":"e_1_2_1_4_1","unstructured":"Ding Ma Bhaskar Chinni. [n. d.]. Broadcom's In-band Flow Analyzer (IFA). https:\/\/www.broadcom.com\/blog\/network-performance-anomaly-detection-with-in-band-flow-analyzer"},{"key":"e_1_2_1_5_1","series-title":"SIAM Journal on optimization","volume-title":"A singular value thresholding algorithm for matrix completion","author":"Cai Jian-Feng","year":"2010","unstructured":"Jian-Feng Cai, Emmanuel J Cand\u00e8s, and Zuowei Shen. 2010. A singular value thresholding algorithm for matrix completion. SIAM Journal on optimization, Vol. 20, 4 (2010), 1956--1982."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2184319.2184343"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970395"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2009.2035722"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508865.1508905"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789272.2912096"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2024.105150"},{"key":"e_1_2_1_12_1","volume-title":"Chistov and Dima Grigoriev","author":"Alexander","year":"1984","unstructured":"Alexander L. Chistov and Dima Grigoriev. 1984. Complexity of Quantifier Elimination in the Theory of Algebraically Closed Fields. Springer-Verlag (1984)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/956993.956995"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ColComCon.2014.6860404"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190100307"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2020.3022757"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2503308.2503352"},{"key":"e_1_2_1_18_1","volume-title":"Eulerian graphs and related topics","author":"Fleischner Herbert","unstructured":"Herbert Fleischner. 1990. Eulerian graphs and related topics. Elsevier."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/637201.637203"},{"key":"e_1_2_1_20_1","volume-title":"Real-Time In-Band Network Link Loss Detection With Programmable Data Plane. In 2024 16th International Conference on Knowledge and Smart Technology (KST). IEEE, 167--172","author":"Ha Nguyen Viet","year":"2024","unstructured":"Nguyen Viet Ha, Tran Nguyen Tuan Kiet, Bui Ngoc Thanh Binh, Nguyen Minh Tri, Tran Thi Thao Nguyen, and Masato Tsuru. 2024. Real-Time In-Band Network Link Loss Detection With Programmable Data Plane. In 2024 16th International Conference on Knowledge and Smart Technology (KST). IEEE, 167--172."},{"key":"e_1_2_1_21_1","volume-title":"11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14)","author":"Handigol Nikhil","year":"2014","unstructured":"Nikhil Handigol, Brandon Heller, Vimalkumar Jeyakumar, David Mazi\u00e8res, and Nick McKeown. 2014. I know what your packet did last hop: Using packet histories to troubleshoot networks. In 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14). 71--85."},{"key":"e_1_2_1_22_1","volume-title":"Fast and accurate matrix completion via truncated nuclear norm regularization","author":"Hu Yao","year":"2012","unstructured":"Yao Hu, Debing Zhang, Jieping Ye, Xuelong Li, and Xiaofei He. 2012. Fast and accurate matrix completion via truncated nuclear norm regularization. IEEE transactions on pattern analysis and machine intelligence, Vol. 35, 9 (2012), 2117--2130."},{"key":"e_1_2_1_23_1","unstructured":"S. Anubolu R. Manur H. Holbrook A. Ghanwani D. Cai H. Ou Y. Li X. Wang J. Kumar S. Anubolu. 2024. Inband Flow Analyzer. Internet-Draft. https:\/\/datatracker.ietf.org\/doc\/draft-kumar-ippm-ifa\/"},{"key":"e_1_2_1_24_1","volume-title":"Advances in Neural Information Processing Systems","volume":"23","author":"Jain Prateek","year":"2010","unstructured":"Prateek Jain, Raghu Meka, and Inderjit Dhillon. 2010. Guaranteed rank minimization via singular value projection. Advances in Neural Information Processing Systems, Vol. 23 (2010)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2022.3201624"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3603269.3604853"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2890955.2890968"},{"key":"e_1_2_1_28_1","first-page":"1","article-title":"In-band network telemetry via programmable dataplanes","volume":"15","author":"Kim Changhoon","year":"2015","unstructured":"Changhoon Kim, Anirudh Sivaraman, Naga Katta, Antonin Bas, Advait Dixit, Lawrence J Wobker, et al. 2015. In-band network telemetry via programmable dataplanes. In ACM SIGCOMM, Vol. 15. 1--2.","journal-title":"ACM SIGCOMM"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/CloudNet.2018.8549351"},{"key":"e_1_2_1_30_1","first-page":"299","article-title":"Network Coordinates in the Wild","volume":"7","author":"Ledlie Jonathan","year":"2007","unstructured":"Jonathan Ledlie, Paul Gardner, and Margo I Seltzer. 2007. Network Coordinates in the Wild.. In NSDI, Vol. 7. 299--311.","journal-title":"NSDI"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TWC.2017.2689772"},{"key":"e_1_2_1_32_1","volume-title":"Yan Zhuang, Fei Feng, Lingbo Tang, Zheng Cao, Ming Zhang, Frank Kelly, Mohammad Alizadeh, et al.","author":"Li Yuliang","year":"2019","unstructured":"Yuliang Li, Rui Miao, Hongqiang Harry Liu, Yan Zhuang, Fei Feng, Lingbo Tang, Zheng Cao, Ming Zhang, Frank Kelly, Mohammad Alizadeh, et al. 2019. HPCC: High precision congestion control. In Proceedings of the ACM Special Interest Group on Data Communication. 44--58."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2173713"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2017.2706743"},{"key":"e_1_2_1_35_1","volume-title":"Hostping: Diagnosing Intra-host Network Bottlenecks in RDMA Servers. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23)","author":"Liu Kefei","year":"2023","unstructured":"Kefei Liu, Zhuo Jiang, Jiao Zhang, Haoran Wei, Xiaolong Zhong, Lizhuang Tan, Tian Pan, and Tao Huang. 2023. Hostping: Diagnosing Intra-host Network Bottlenecks in RDMA Servers. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23). USENIX Association, Boston, MA, 15--29. https:\/\/www.usenix.org\/conference\/nsdi23\/presentation\/liu-kefei"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3603269.3604824"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","unstructured":"A. Morton. 2016. RFC 7799: Active and Passive Metrics and Methods. Internet Requests for Comments. https:\/\/doi.org\/10.17487\/RFC7799","DOI":"10.17487\/RFC7799"},{"key":"e_1_2_1_38_1","volume-title":"13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16)","author":"Narayana Srinivas","year":"2016","unstructured":"Srinivas Narayana, Mina Tahmasbi, Jennifer Rexford, and David Walker. 2016. Compiling path queries. In 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16). 207--222."},{"key":"e_1_2_1_39_1","unstructured":"P4 Language Consortium. 2018. Behavioral Model. https:\/\/github.com\/p4lang\/behavioral-model."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737529"},{"key":"e_1_2_1_41_1","volume-title":"NP-completeness of some problems of partitioning and covering in graphs. Discrete applied mathematics","author":"P\u00e9roche Bernard","year":"1984","unstructured":"Bernard P\u00e9roche. 1984. NP-completeness of some problems of partitioning and covering in graphs. Discrete applied mathematics, Vol. 8, 2 (1984), 195--208."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2169424"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2785956.2787472"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3050220.3063772"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00577-7"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024853.1024855"},{"key":"e_1_2_1_47_1","unstructured":"S. Bhandari B. Gafni M. Spiegel T. Mizrahi F. Brockners. 2022. In-situ OAM Loopback and Active Flags. Internet-Draft. https:\/\/datatracker.ietf.org\/doc\/html\/draft-ietf-ippm-ioam-flags-08"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2022.3194086"},{"key":"e_1_2_1_49_1","unstructured":"The Abilene Observatory. 2004. The Abilene Observatory Data Collections. Available online. [Online]. Available: http:\/\/www.cs.utexas.edu\/ yzhang\/research\/AbileneTM\/."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111322.1111341"},{"key":"e_1_2_1_51_1","volume-title":"HPETC: History Priority Enhanced Tensor Completion For Network Distance Measurement","author":"Wang Cheng","year":"2023","unstructured":"Cheng Wang and Kun Xie. 2023. HPETC: History Priority Enhanced Tensor Completion For Network Distance Measurement. IEEE Transactions on Parallel and Distributed Systems (2023)."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM53939.2023.10229098"},{"key":"e_1_2_1_53_1","unstructured":"Wikipedia. 2023. Path cover. https:\/\/en.wikipedia.org\/wiki\/Path_cover"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1090191.1080103"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM42981.2021.9488908"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2017.2775230"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2015.7218633"},{"key":"e_1_2_1_58_1","volume-title":"Sketchint: Empowering int with towersketch for per-flow per-switch measurement","author":"Yang Kaicheng","year":"2023","unstructured":"Kaicheng Yang, Sheng Long, Qilong Shi, Yuanpeng Li, Zirui Liu, Yuhan Wu, Tong Yang, and Zhengyi Jia. 2023. Sketchint: Empowering int with towersketch for per-flow per-switch measurement. IEEE Transactions on Parallel and Distributed Systems (2023)."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230543.3230544"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3603269.3604838"},{"key":"e_1_2_1_61_1","volume-title":"INT-Segment: MTU-Adaptive Single-Path In-Band Network-Wide Telemetry. In 2022 IEEE 30th International Conference on Network Protocols (ICNP). IEEE, 1--11","author":"Yuan Qianchen","year":"2022","unstructured":"Qianchen Yuan, Fuliang Li, Tian Pan, Yuhua Lai, Yetao Gu, and Xingwei Wang. 2022. INT-Segment: MTU-Adaptive Single-Path In-Band Network-Wide Telemetry. In 2022 IEEE 30th International Conference on Network Protocols (ICNP). IEEE, 1--11."},{"key":"e_1_2_1_62_1","volume-title":"INT-react: An O (E) Path Planner for Resilient Network-Wide Telemetry Over Megascale Networks. In 2022 IEEE 30th International Conference on Network Protocols (ICNP). IEEE, 1--11","author":"Yuan Qianchen","year":"2022","unstructured":"Qianchen Yuan, Fuliang Li, Tian Pan, Yifan Xu, and Xingwei Wang. 2022. INT-react: An O (E) Path Planner for Resilient Network-Wide Telemetry Over Megascale Networks. In 2022 IEEE 30th International Conference on Network Protocols (ICNP). IEEE, 1--11."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.1996.493353"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592568.1592600"},{"key":"e_1_2_1_65_1","volume-title":"18th USENIX symposium on networked systems design and implementation (NSDI 21)","author":"Zhao Yikai","year":"2021","unstructured":"Yikai Zhao, Kaicheng Yang, Zirui Liu, Tong Yang, Li Chen, Shiyi Liu, Naiqian Zheng, Ruixin Wang, Hanbo Wu, Yi Wang, et al. 2021. $$LightGuardian$$: A $$full-visibility$$, lightweight, in-band telemetry system using sketchlets. In 18th USENIX symposium on networked systems design and implementation (NSDI 21). 991--1010."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2008.4630108"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2016.2612695"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700433","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3700433","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T00:14:35Z","timestamp":1755908075000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700433"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,10]]},"references-count":67,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,12,10]]}},"alternative-id":["10.1145\/3700433"],"URL":"https:\/\/doi.org\/10.1145\/3700433","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,10]]},"assertion":[{"value":"2024-12-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}