{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:52:46Z","timestamp":1760237566284,"version":"build-2065373602"},"reference-count":42,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T00:00:00Z","timestamp":1657152000000},"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":["MOST 104-2221-E-182-005","110-2221-E-182-010","BMRP 942"],"award-info":[{"award-number":["MOST 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":["MOST 104-2221-E-182-005","110-2221-E-182-010","BMRP 942"],"award-info":[{"award-number":["MOST 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>Advanced network services, such as firewalls, policy-based routing, and virtual private networks, must rely on routers to classify packets into different flows based on packet headers and predefined filter tables. When multiple filters are overlapped, conflicts may occur, leading to ambiguity in the packet classification. Conflict detection ensures the correctness of packet classification and has received considerable attention in recent years. However, most conflict-detection algorithms are implemented on a conventional central processing unit (CPU). Compared with a CPU, a graphics processing unit (GPU) exhibits higher computing power with parallel computing, hence accelerates the execution speed of conflict detection. In this study, we employed a GPU to develop two efficient algorithms for parallel conflict detection: the general parallel conflict-detection algorithm (the GPCDA) and the enhanced parallel conflict-detection algorithm (the EPCDA). In the GPCDA, we demonstrate how to perform conflict detection through parallel execution on GPU cores. While in the EPCDA, we analyze the critical procedure in conflict detection as to reduce the number of matches required for each filter. In addition, the EPCDA adopts a workload balance method to enable load balancing of GPU execution threads, thereby significantly improving performance. The simulation results show that with the 100 K filter database, the GPCDA and the EPCDA execute conflict detection 2.8 to 13.9 and 9.4 to 33.7 times faster, respectively, than the CPU-based algorithm.<\/jats:p>","DOI":"10.3390\/a15070237","type":"journal-article","created":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T07:51:56Z","timestamp":1657180316000},"page":"237","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Efficient Parallel Algorithm for Detecting Packet Filter Conflicts"],"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, Tao-Yuan 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,7,7]]},"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":"David","year":"2005","journal-title":"ACM Comput. Surv."},{"key":"ref_2","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_3","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_4","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_5","doi-asserted-by":"crossref","unstructured":"Vamanan, B., and Vijaykumar, T.N. (2011, January 6\u20139). TreeCAM: Decoupling Updates and Lookups in Packet Classification. Proceedings of the Seventh Conference on Emerging Networking EXperiments and Technologies, Tokyo, Japan.","DOI":"10.1145\/2079296.2079323"},{"key":"ref_6","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_7","unstructured":"(2022, May 01). OpenFlow Specification v1.5.1. Available online: https:\/\/opennetworking.org\/wp-content\/uploads\/2014\/10\/openflow-switch-v1.5.1.pdf."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Qu, Y.R., Zhou, S., and Prasanna, V.K. (2014, January 1\u20134). Performance Modeling and Optimizations for Decomposition-Based Large-Scale Packet Classification on Multi-Core Processors. Proceedings of the 2014 IEEE 15th International Conference on High Performance Switching and Routing, Vancouver, BC, Canada.","DOI":"10.1109\/HPSR.2014.6900896"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Qu, Y.R., and Prasanna, V.K. (2014, January 22\u201324). Compact Hash Tables for High-Performance Traffic Classification on Multi-Core Processors. Proceedings of the IEEE 26th International Symposium on Computer Architecture and High Performance Computing, Paris, France.","DOI":"10.1109\/SBAC-PAD.2014.32"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Qu, Y.R., Zhou, S., and Prasanna, V.K. (2013, January 23\u201326). Scalable Many-Field Packet Classification on Multi-Core Processors. Proceedings of the 25th International Symposium on Computer Architecture and High Performance Computing, Porto de Galinhas, Brazil.","DOI":"10.1109\/SBAC-PAD.2013.29"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"3203","DOI":"10.1007\/s10586-020-03081-7","article-title":"Enhancing the Performance of Decision Tree-Based Packet Classification Algorithms Using CPU Cluster","volume":"23","author":"Abbasi","year":"2020","journal-title":"Clust. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1056","DOI":"10.1007\/s11390-018-1873-9","article-title":"Optimizing Multi-Dimensional Packet Classification for Multi-Core Systems","volume":"33","author":"Shen","year":"2018","journal-title":"J. Comput. Sci. Technol."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1145\/1851275.1851207","article-title":"PacketShader: A GPU-Accelerated Software Router","volume":"40","author":"Han","year":"2010","journal-title":"Comput. Commun. Rev."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Hung, C.L., Wang, H.H., Guo, S.W., Lin, Y.L., and Li, K.C. (2011, January 16\u201318). Efficient GPGPU-Based Parallel Packet Classification. Proceedings of the IEEE 10th International Conference on Trust, Security and Privacy in Computing and Communications, Changsha, China.","DOI":"10.1109\/TrustCom.2011.186"},{"key":"ref_15","unstructured":"Kang, K., and Deng, Y. (2011, January 14\u201318). Scalable Packet Classification via GPU Metaprograming. Proceedings of the 2011 Design, Automation & Test in Europe, Grenoble, France."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Hsieh, C.L., and Weng, N. (2014, January 20\u201321). High Performance Multi-Field Packet Classification Using Bucket Filtering and GPU Processing. Proceedings of the 2014 ACM\/IEEE Symposium on Architectures for Networking and Communications Systems, Los Angeles, CA, USA.","DOI":"10.1145\/2658260.2661768"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Qu, Y.R., Zhang, H.H., Zhou, S., and Prasanna, V.K. (2015, January 7\u20138). Optimizing Many-Field Packet Classification on FPGA, Multi-Core General Purpose Processor, and GPU. Proceedings of the 2015 ACM\/IEEE Symposium on Architectures for Networking and Communications Systems, Oakland, CA, USA.","DOI":"10.1109\/ANCS.2015.7110123"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Lee, C.L., Lin, Y.S., and Chen, Y.C. (2015). A Hybrid CPU\/GPU Pattern-Matching Algorithm for Deep Packet Inspection. PLoS ONE, 10.","DOI":"10.1371\/journal.pone.0139301"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1109\/TETC.2015.2460453","article-title":"IP Address Lookup by Using GPU","volume":"4","author":"Chu","year":"2015","journal-title":"IEEE Trans. Emerg. Top. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"80610","DOI":"10.1109\/ACCESS.2020.2990331","article-title":"Packet Classification Using GPU and One-Level Entropy-Based Hashing","volume":"8","author":"Greenberg","year":"2020","journal-title":"IEEE Access"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"2728","DOI":"10.1109\/TNET.2015.2491265","article-title":"Multi-Layer Packet Classification with Graphics Processing Units","volume":"24","author":"Varvello","year":"2016","journal-title":"IEEE ACM Trans. Netw."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Bal\u00e1\u017e, M., and Helebrandt, P. (2019, January 21\u201322). Accelerating SDN Control Plane with GPGPU-Based Packet Classification. Proceedings of the 17th International Conference on Emerging eLearning Technologies and Applications, Star\u00fd Smokovec, Slovakia.","DOI":"10.1109\/ICETA48886.2019.9040001"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"6574","DOI":"10.1007\/s11227-019-02861-2","article-title":"A Calibrated Asymptotic Framework for Analyzing Packet Classification Algorithms on GPUs","volume":"75","author":"Mahdi","year":"2019","journal-title":"J. Supercomput."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"e185","DOI":"10.7717\/peerj-cs.185","article-title":"Enhancing the Performance of the Aggregated Bit Vector Algorithm in Network Packet Classification Using GPU","volume":"5","author":"Abbasi","year":"2019","journal-title":"PeerJ Comput. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/j.jpdc.2022.04.018","article-title":"Efficient Hierarchical Hash Tree for OpenFlow Packet Classification with Fast Updates on GPUs","volume":"167","author":"Lin","year":"2022","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_26","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_27","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 SIGCOMM, Vancouver, BC, Canada."},{"key":"ref_28","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_29","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_30","doi-asserted-by":"crossref","unstructured":"Lee, C.-L., Hsu, Y.-C., Chen, Y.-C., and Hsieh, H.-C. (2020, January 26\u201330). A Fast Bit-Vector-Based Conflict Detection Algorithm for Packet Classifiers. Proceedings of the 8th IIAE International Conference on Industrial Application Engineering, Matsue, Japan.","DOI":"10.12792\/iciae2020.005"},{"key":"ref_31","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_32","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_33","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_34","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1145\/316194.316216","article-title":"Packet Classification Using Tuple Space Search","volume":"29","author":"Srinivasan","year":"1999","journal-title":"Comput. Commun. Rev."},{"key":"ref_35","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 Intl Conf 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_36","unstructured":"(2022, May 01). CUDA C++ Programming Guide 2022. Available online: http:\/\/docs.nvidia.com\/CUDA\/CUDA-c-programming-guide\/."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1145\/361011.361064","article-title":"Scheduling Independent Tasks to Reduce Mean Finishing-Time","volume":"17","author":"Bruno","year":"1974","journal-title":"Commun. ACM"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1145\/321941.321951","article-title":"Exact and Approximate Algorithms for Scheduling Non-Identical Processors","volume":"23","author":"Horowitz","year":"1976","journal-title":"J. ACM"},{"key":"ref_39","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_40","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."},{"key":"ref_41","unstructured":"(2022, May 01). NVIDIA GeForce GTX 970. Available online: https:\/\/www.nvidia.com\/en-us\/geforce\/900-series\/."},{"key":"ref_42","unstructured":"(2022, May 01). NVIDIA Visual Profiler 2022. Available online: https:\/\/developer.nvidia.com\/nvidia-visual-profiler."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/7\/237\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:43:54Z","timestamp":1760139834000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/7\/237"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,7]]},"references-count":42,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2022,7]]}},"alternative-id":["a15070237"],"URL":"https:\/\/doi.org\/10.3390\/a15070237","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,7,7]]}}}