{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:53:02Z","timestamp":1760237582522,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2022,8,14]],"date-time":"2022-08-14T00:00:00Z","timestamp":1660435200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Ministry of Science and Technology of Taiwan","award":["104-2221-E-182-005","110-2221-E-182-010","BMRP 942"],"award-info":[{"award-number":["104-2221-E-182-005","110-2221-E-182-010","BMRP 942"]}]},{"DOI":"10.13039\/501100004606","name":"Chang Gung Memorial Hospital","doi-asserted-by":"publisher","award":["104-2221-E-182-005","110-2221-E-182-010","BMRP 942"],"award-info":[{"award-number":["104-2221-E-182-005","110-2221-E-182-010","BMRP 942"]}],"id":[{"id":"10.13039\/501100004606","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>To support advanced network services, Internet routers must perform packet classification based on a set of rules called packet filters. If two or more filters overlap, a filter conflict will occur and lead to ambiguity in packet classification. Further, it may affect network security or even the correctness of packet routing. Hence, it is necessary to detect conflicts to avoid the above problems. In recent years, many conflict detection algorithms have been proposed, but most of them detect conflicts for only prefix fields (i.e., source\/destination IP address fields) of filters. For greater practicality, conflict detection must include non-prefix fields such as source\/destination IP port fields and the protocol field. In this study, we propose an efficient conflict detection algorithm for five-dimensional filters, which include both prefix and non-prefix fields. In the proposed algorithm, a tiny lookup table is created for quickly filtering out a large portion of non-conflicting filter pairs, thereby reducing the overall conflict detection time. Experimental results show that our algorithm reduces the detection time by 10% to 28% compared with other conflict detection algorithms for 20 K filter databases. More importantly, our algorithm can be used to extend any existing conflict detection algorithms for two-dimensional filters to support fast conflict detection for five-dimensional filters.<\/jats:p>","DOI":"10.3390\/a15080285","type":"journal-article","created":{"date-parts":[[2022,8,14]],"date-time":"2022-08-14T21:09:06Z","timestamp":1660511346000},"page":"285","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast Conflict Detection for Multi-Dimensional Packet Filters"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8454-5029","authenticated-orcid":false,"given":"Chun-Liang","family":"Lee","sequence":"first","affiliation":[{"name":"Department of Computer Science and Information Engineering, School of Electrical and Computer Engineering, College of Engineering, Chang Gung University, Taoyuan 33302, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9348-1215","authenticated-orcid":false,"given":"Guan-Yu","family":"Lin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, National Yang Ming Chiao Tung University, Hsinchu 30010, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yaw-Chung","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Computer Science, National Yang Ming Chiao Tung University, Hsinchu 30010, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,8,14]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1145\/1108956.1108958","article-title":"Survey and Taxonomy of Packet Classification Techniques","volume":"37","author":"Taylor","year":"2005","journal-title":"ACM Comput. Surv."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/65.912717","article-title":"Algorithms for Packet Classification","volume":"15","author":"Gupta","year":"2001","journal-title":"IEEE Netw."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"2765","DOI":"10.1109\/TNET.2021.3100114","article-title":"Fast Online Packet Classification with Convolutional Neural Network","volume":"29","author":"Zhang","year":"2021","journal-title":"IEEE ACM Trans. Netw."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"2693","DOI":"10.1109\/TNET.2021.3098320","article-title":"T-Cache: Efficient Policy-Based Forwarding Using Small TCAM","volume":"29","author":"Wan","year":"2021","journal-title":"IEEE ACM Trans. Netw."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J., Lu\u010dansk\u00fd, A., Jane\u010dek, D., Sabo, J., Ko\u0159enek, J., and Antichi, G. (2022). ClassBench-Ng: Benchmarking Packet Classification Algorithms in the OpenFlow Era. IEEE ACM Trans. Netw., 1\u201314.","DOI":"10.1109\/TNET.2022.3155708"},{"key":"ref_6","unstructured":"Hari, A., Suri, S., and Parulkar, G. (2000, January 26\u201330). Detecting and Resolving Packet Filter Conflicts. Proceedings of the IEEE INFOCOM, Tel Aviv, Israel."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1016\/S1389-1286(03)00213-5","article-title":"Fast and Scalable Conflict Detection for Packet Classifier","volume":"42","author":"Baboescu","year":"2003","journal-title":"Comput. Netw."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1109\/TDSC.2012.20","article-title":"Detecting and Resolving Firewall Policy Anomalies","volume":"9","author":"Hongxin","year":"2012","journal-title":"IEEE Trans. Dependable Secur. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Zhang, X., Yin, Y., Liu, W., Peng, Z., Zhang, G., Wang, Y., Tateiwa, Y., and Takahashi, N. (2019, January 16\u201318). A Conflict Detection Method for IPv6 Time-Based Firewall Policy. Proceedings of the 2019 IEEE International Conference on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking, Xiamen, China.","DOI":"10.1109\/ISPA-BDCloud-SustainCom-SocialCom48970.2019.00069"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1137","DOI":"10.1109\/JSYST.2014.2367160","article-title":"Fast and Complete Conflict Detection for Packet Classifiers","volume":"11","author":"Lai","year":"2017","journal-title":"IEEE Syst. J."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1417","DOI":"10.1109\/TNET.2019.2920718","article-title":"TupleMerge: Fast Software Packet Processing for Online Packet Classification","volume":"27","author":"Daly","year":"2019","journal-title":"IEEE ACM Trans. Netw."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1353","DOI":"10.1109\/TNET.2005.860108","article-title":"Conflict Detection and Resolution in Two-Dimensional Prefix Router Tables","volume":"13","author":"Lu","year":"2005","journal-title":"IEEE ACM Trans. Netw."},{"key":"ref_13","unstructured":"(2022, June 01). OpenFlow Specification v1.5.1. Available online: https:\/\/opennetworking.org\/wp-content\/uploads\/2014\/10\/openflow-switch-v1.5.1.pdf."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1049\/ntw2.12038","article-title":"Many-Field Packet Classification with Decomposition and Reinforcement Learning","volume":"11","author":"Jamil","year":"2022","journal-title":"IET Netw."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"3010","DOI":"10.1016\/j.comnet.2012.04.014","article-title":"A New Hierarchical Packet Classification Algorithm","volume":"56","author":"Lim","year":"2012","journal-title":"Comput. Netw."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1907","DOI":"10.1109\/TNET.2018.2852710","article-title":"A Sorted-Partitioning Approach to Fast and Scalable Dynamic Packet Classification","volume":"26","author":"Yingchareonthawornchai","year":"2018","journal-title":"IEEE ACM Trans. Netw."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Wee, J., Choi, J.-G., and Pak, W. (2019). Wildcard Fields-Based Partitioning for Fast and Scalable Packet Classification in Vehicle-to-Everything. Sensors, 19.","DOI":"10.3390\/s19112563"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"107534","DOI":"10.1016\/j.comnet.2020.107534","article-title":"Common Non-Wildcard Portion-Based Partitioning Approach to SDN Many-Field Packet Classification","volume":"181","author":"Alimohammadi","year":"2020","journal-title":"Comput. Netw."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Bremler-Barr, A., and Hendler, D. (2007, January 6\u201312). Space-Efficient TCAM-Based Classification Using Gray Coding. Proceedings of the IEEE INFOCOM, Anchorage, AK, USA.","DOI":"10.1109\/INFCOM.2007.164"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Fong, J., Wang, X., Qi, Y., Li, J., and Jiang, W. (2012, January 22\u201324). ParaSplit: A Scalable Architecture on FPGA for Terabit Packet Classification. Proceedings of the IEEE 20th Annual Symposium on High-Performance Interconnects, Santa Clara, CA, USA.","DOI":"10.1109\/HOTI.2012.17"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Erdem, O., Le, H., and Prasanna, V.K. (2012, January 25\u201330). Hierarchical Hybrid Search Structure for High Performance Packet Classification. Proceedings of the IEEE INFOCOM, Orlando, FL, USA.","DOI":"10.1109\/INFCOM.2012.6195565"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Pnevmatikou, A., Lentaris, G., Soudris, D., and Kokkalis, N. (2020, January 12\u201314). Fast Packet Classification Using RISC-V and HyperSplit Acceleration on FPGA. Proceedings of the IEEE International Symposium on Circuits and Systems, Seville, Spain.","DOI":"10.1109\/ISCAS45731.2020.9180588"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Chen, D., Li, Z., Xiong, T., Liu, Z., Yang, J., Yin, S., Wei, S., and Liu, L. (2020, January 17\u201321). CATCAM: Constant-Time Alteration Ternary CAM with Scalable In-Memory Architecture. Proceedings of the 53rd Annual IEEE\/ACM International Symposium on Microarchitecture, Athens, Greece.","DOI":"10.1109\/MICRO50266.2020.00038"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1145\/285243.285282","article-title":"Fast and Scalable Layer Four Switching","volume":"28","author":"Srinivasan","year":"1998","journal-title":"Comput. Commun. Rev."},{"key":"ref_25","unstructured":"Lakshman, T.V., and Stiliadis, D. (September, January 31). High-Speed Policy-Based Packet Forwarding Using Efficient Multi-Dimensional Range Matching. Proceedings of the ACM SISCOMM, Vancouver, BC, Canada."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/TNET.2004.842232","article-title":"Scalable Packet Classification","volume":"13","author":"Baboescu","year":"2005","journal-title":"IEEE ACM Trans. Netw."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.comcom.2020.12.008","article-title":"A Multilevel Bit Vector Minimization Method for Fast Online Detection of Conflicting Flow Entries in OpenFlow Table","volume":"167","author":"Kuo","year":"2021","journal-title":"Comput. Commun."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/TC.1979.1675432","article-title":"Algorithms for Reporting and Counting Geometric Intersections","volume":"28","author":"Bentley","year":"1979","journal-title":"IEEE Trans. Comput."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1587\/transinf.E95.D.472","article-title":"An Efficient Conflict Detection Algorithm for Packet Filters","volume":"95","author":"Lee","year":"2012","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/s00224-007-9050-5","article-title":"Two-Dimensional Packet Classification and Filter Conflict Resolution in the Internet","volume":"44","author":"Kwok","year":"2009","journal-title":"Theory Comput. Syst."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Maindorfer, C., Mohamed, K.A., Ottmann, T., and Datta, A. (2007, January 6\u201312). A New Output-Sensitive Algorithm to Detect and Resolve Conflicts in Internet Router Tables. Proceedings of the IEEE INFOCOM, Anchorage, AK, USA.","DOI":"10.1109\/INFCOM.2007.295"},{"key":"ref_32","unstructured":"(2022, June 01). Z3 Theorem Prover. Available online: https:\/\/github.com\/Z3Prover\/z3\/wiki."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1109\/TNET.2007.893156","article-title":"Classbench: A Packet Classification Benchmark","volume":"15","author":"Taylor","year":"2007","journal-title":"IEEE ACM Trans. Netw."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/8\/285\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:08:30Z","timestamp":1760141310000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/8\/285"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,14]]},"references-count":33,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2022,8]]}},"alternative-id":["a15080285"],"URL":"https:\/\/doi.org\/10.3390\/a15080285","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,8,14]]}}}