{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:22:38Z","timestamp":1760232158739,"version":"build-2065373602"},"reference-count":31,"publisher":"MDPI AG","issue":"20","license":[{"start":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T00:00:00Z","timestamp":1666051200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Key R&amp;D Program of China","award":["2021YFB3101302","2021YFB3101303","62020106013","61872061","62272223","2018CC0094","ZYGX2019J075"],"award-info":[{"award-number":["2021YFB3101302","2021YFB3101303","62020106013","61872061","62272223","2018CC0094","ZYGX2019J075"]}]},{"name":"National Natural Science Foundation of China","award":["2021YFB3101302","2021YFB3101303","62020106013","61872061","62272223","2018CC0094","ZYGX2019J075"],"award-info":[{"award-number":["2021YFB3101302","2021YFB3101303","62020106013","61872061","62272223","2018CC0094","ZYGX2019J075"]}]},{"name":"Science and Technology Achievements Transformation Demonstration Project of Sichuan Province of China","award":["2021YFB3101302","2021YFB3101303","62020106013","61872061","62272223","2018CC0094","ZYGX2019J075"],"award-info":[{"award-number":["2021YFB3101302","2021YFB3101303","62020106013","61872061","62272223","2018CC0094","ZYGX2019J075"]}]},{"name":"Fundamental Research Funds for Central Universities","award":["2021YFB3101302","2021YFB3101303","62020106013","61872061","62272223","2018CC0094","ZYGX2019J075"],"award-info":[{"award-number":["2021YFB3101302","2021YFB3101303","62020106013","61872061","62272223","2018CC0094","ZYGX2019J075"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Software-defined measurement (SDM) is a simple and efficient way to deploy measurement tasks and collect measurement data. With SDM, it is convenient for operators to implement fine-grained network-wide measurements at the flow level, from which many important functions can benefit. The prior work provides mechanisms to distribute flows to monitors, such that each monitor can identify its non-overlapped subset of flows to measure, and a certain global performance criterion is optimized, such as load balance or flow coverage. Many applications of network management can benefit from a function that can find large flows efficiently, such as congestion control by dynamically scheduling large flows, caching of forwarding table entries, and network capacity planning. However, the current network-wide measurements neglect the diversity of different flows as they treat large flows and small flows equally. In this paper, we present a mechanism of accuracy-aware collaborative monitoring (ACM) to improve the measurement accuracies of large flows in network-wide measurements at the flow level. The structure of the sketch is an approximate counting algorithm, and a high-measurement accuracy can be achieved by merging the results from multiple monitors with sketches, which is termed as collaborative monitoring. The core idea of our method is to allocate more monitors to large flows and achieve the load balance to provide accuracy-aware monitoring. We modeled our problem as an integer\u2013linear programming problem, which is NP-hard. Thus, we propose an approximation algorithm, named the improved longest processing time algorithm (iLPTA); we proved that its approximation ratio is (12+nl). We propose a two-stage online distribution algorithm (TODA). Moreover, we proved that its approximation ratio is (1+nl\u22121). The iLPTA is an offline approximation algorithm used to assign monitors for each flow, which prove the validity and feasibility of the core idea. The TODA is an online algorithm that attempts to achieve the load balance by selecting the monitor with the smallest load to a large flow. Our extensional experiment results verify the effectiveness of our proposed algorithms.<\/jats:p>","DOI":"10.3390\/s22207932","type":"journal-article","created":{"date-parts":[[2022,10,19]],"date-time":"2022-10-19T00:58:51Z","timestamp":1666141131000},"page":"7932","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["ACM: Accuracy-Aware Collaborative Monitoring for Software-Defined Network-Wide Measurement"],"prefix":"10.3390","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8602-3996","authenticated-orcid":false,"given":"Jiqing","family":"Gu","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, University of Electronic Science and Technology of China, Qingshuihe Campus, Chengdu 611731, China"}]},{"given":"Chao","family":"Song","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, University of Electronic Science and Technology of China, Qingshuihe Campus, Chengdu 611731, China"}]},{"given":"Haipeng","family":"Dai","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Technology, Nanjing University, Nanjing 210023, China"}]},{"given":"Lei","family":"Shi","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, University of Electronic Science and Technology of China, Qingshuihe Campus, Chengdu 611731, China"}]},{"given":"Jinqiu","family":"Wu","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, University of Electronic Science and Technology of China, Qingshuihe Campus, Chengdu 611731, China"}]},{"given":"Li","family":"Lu","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, University of Electronic Science and Technology of China, Qingshuihe Campus, Chengdu 611731, China"}]}],"member":"1968","published-online":{"date-parts":[[2022,10,18]]},"reference":[{"key":"ref_1","unstructured":"Yu, M., Jose, L., and Miao, R. (2013, January 2\u20135). Software defined traffic measurement with OpenSketch. Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201913), Lombard, IL, USA."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Moshref, M., Yu, M., Govindan, R., and Vahdat, A. (2014, January 17\u201322). DREAM: Dynamic resource allocation for software-defined measurement. Proceedings of the ACM SIGCOMM Computer Communication Review, Berkeley, CA, USA.","DOI":"10.1145\/2619239.2626291"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Moshref, M., Yu, M., Govindan, R., and Vahdat, A. (2015, January 1\u20134). SCREAM: Sketch resource allocation for software-defined measurement. Proceedings of the Conference on emerging Networking Experiments and Technologies (ACM CoNEXT), Heidelberg, Germany.","DOI":"10.1145\/2716281.2836099"},{"key":"ref_4","unstructured":"Sekar, V., Reiter, M.K., Willinger, W., Zhang, H., Kompella, R.R., and Andersen, D.G. (2008, January 16\u201318). CSAMP: A system for network-wide flow monitoring. Proceedings of the 5th USENIX Symposium on Networked Systems Design & Implementation, NSDI 2008, San Francisco, CA, USA."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1109\/90.929850","article-title":"Deriving traffic demands for operational IP networks: Methodology and experience","volume":"9","author":"Feldmann","year":"2001","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Yang, K., Li, Y., Liu, Z., Yang, T., Zhou, Y., He, J., Xue, J., Zhao, T., Jia, Z., and Yang, Y. (2021, January 1\u20135). SketchINT: Empowering INT with TowerSketch for Per-flow Per-switch Measurement. Proceedings of the IEEE 29th International Conference on Network Protocols (ICNP), Dallas, TX, USA.","DOI":"10.1109\/ICNP52444.2021.9651940"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Xu, H., Chen, S., Ma, Q., and Huang, L. (May, January 29). Lightweight flow distribution for collaborative traffic measurement in software defined networks. Proceedings of the IEEE INFOCOM 2019\u2014IEEE Conference on Computer Communications, Paris, France.","DOI":"10.1109\/INFOCOM.2019.8737516"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Zhou, Y., Yang, T., Jiang, J., Cui, B., Yu, M., Li, X., and Uhlig, S. (2018, January 10\u201315). Cold filter: A meta-framework for faster and more accurate stream processing. Proceedings of the 2018 International Conference on Management of Data (SIGMOD), Houston, TX, USA.","DOI":"10.1145\/3183713.3183726"},{"key":"ref_9","unstructured":"Roy, P., Khan, A., and Alonso, G. (July, January 26). Augmented Sketch: Faster and more accurate stream processing. Proceedings of the ACM SIGMOD International Conference on Management of Data, San Francisco, CA, USA."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1845","DOI":"10.1109\/TNET.2019.2933868","article-title":"HeavyKeeper: An accurate algorithm for finding top-k elephant flows","volume":"27","author":"Yang","year":"2019","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Yang, T., Jiang, J., Liu, P., Huang, Q., Gong, J., Zhou, Y., Miao, R., Li, X., and Uhlig, S. (2018, January 20\u201325). Elastic sketch: Adaptive and fast network-wide measurements. Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, Budapest, Hungary.","DOI":"10.1145\/3230543.3230544"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Huang, Q., Xin, J., Lee, P.P.C., Li, R., and Gong, Z. (2017, January 21\u201325). SketchVisor: Robust network measurement for software packet processing. Proceedings of the Conference of the ACM Special Interest Group on Data Communication, Los Angeles, CA, USA.","DOI":"10.1145\/3098822.3098831"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Yu, Y., Qian, C., and Li, X. (2014, January 22). Distributed and collaborative traffic monitoring in software defined networks. Proceedings of the Third Workshop on Hot Topics in Software Defined Networking (ACM HotSDN), Chicago, IL, USA.","DOI":"10.1145\/2620728.2620739"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1109\/TPDS.2013.188","article-title":"LEISURE: Load-balanced network-wide traffic measurement and monitor placement","volume":"26","author":"Chang","year":"2013","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Sivaraman, A., Subramanian, S., Alizadeh, M., Chole, S., Chuang, S.T., Agrawal, A., Balakrishnan, H., Edsall, T., Katti, S., and McKeown, N. (2016, January 22\u201326). Programmable packet scheduling at line rate. Proceedings of the ACM SIGCOMM Conference, Florianopolis, Brazil.","DOI":"10.1145\/2934872.2934899"},{"key":"ref_16","unstructured":"Lakhina, A., Crovella, M., and Diot, C. (September, January 30). Characterization of network-wide anomalies in traffic flows. Proceedings of the 2004 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (ACM SIGCOMM), Portland, OR, USA."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1109\/TNET.2016.2611482","article-title":"Optimal rule caching and lossy compression for longest prefix matching","volume":"25","author":"Rottenstreich","year":"2016","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Zhao, B., Li, X., Tian, B., Mei, Z., and Wu, W. (2021, January 14\u201318). DHS: Adaptive Memory Layout Organization of Sketch Slots for Fast and Accurate Data Stream Processing. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, Singapore.","DOI":"10.1145\/3447548.3467353"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","article-title":"An improved data stream summary: The count-min sketch and its applications","volume":"55","author":"Cormode","year":"2005","journal-title":"J. Algorithms"},{"key":"ref_20","unstructured":"Li, Y., Miao, R., Kim, C., and Yu, M. (2016, January 16\u201318). FlowRadar: A better NetFlow for data centers. Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI \u201916), Santa Clara, CA, USA."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Liu, Z., Manousis, A., Vorsanger, G., Sekar, V., and Braverman, V. (2016, January 22\u201326). One sketch to rule them all: Rethinking network flow monitoring with univmon. Proceedings of the ACM SIGCOMM Conference, Florianopolis, Brazil.","DOI":"10.1145\/2934872.2934906"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1109\/TNET.2007.896150","article-title":"Reversible sketches: Enabling monitoring and analysis over high-speed data streams","volume":"15","author":"Schweller","year":"2007","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Liu, X., Shirazipour, M., Yu, M., and Zhang, Y. (2016, January 14\u201315). MOZART: Temporal Coordination of Measurement. Proceedings of the Symposium on SDN Research, Santa Clara, CA, USA.","DOI":"10.1145\/2890955.2890964"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Qian, Y., Liu, Y., Kong, L., Wu, M., and Mumtaz, S. (2018, January 9\u201313). ReFeR: Resource Critical Flow Monitoring in Software-Defined Networks. Proceedings of the 2018 IEEE Global Communications Conference (GLOBECOM), Abu Dhabi, United Arab Emirates.","DOI":"10.1109\/GLOCOM.2018.8647445"},{"key":"ref_25","unstructured":"Yang, G., Yoo, Y., Kang, M., Jin, H., and Yoo, C. (2021). Accurate and Efficient Monitoring for Virtualized SDN in Clouds. IEEE Trans. Cloud Comput."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1057\/jors.1979.78","article-title":"A branch and bound method for the multiconstraint zero-one knapsack problem","volume":"30","author":"Shih","year":"1979","journal-title":"J. Oper. Res. Soc."},{"key":"ref_27","unstructured":"(2021, January 01). CPLEX. Available online: https:\/\/www.ibm.com\/analytics\/cplex-optimizer."},{"key":"ref_28","unstructured":"(2021, January 01). Gurobi. Available online: https:\/\/www.gurobi.com\/."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","article-title":"Optimization and approximation in deterministic sequencing and scheduling: A survey","volume":"Volume 5","author":"Graham","year":"1979","journal-title":"Annals of Discrete Mathematics"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0117039","article-title":"Bounds on multiprocessing timing anomalies","volume":"17","author":"Graham","year":"1969","journal-title":"Siam J. Appl. Math."},{"key":"ref_31","unstructured":"(2021, March 02). CAIDA Trace. Available online: http:\/\/www.caida.org\/data\/monitors\/passive-equinix-chicago.xml."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/22\/20\/7932\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:56:36Z","timestamp":1760144196000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/22\/20\/7932"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,18]]},"references-count":31,"journal-issue":{"issue":"20","published-online":{"date-parts":[[2022,10]]}},"alternative-id":["s22207932"],"URL":"https:\/\/doi.org\/10.3390\/s22207932","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2022,10,18]]}}}