{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:32:01Z","timestamp":1750221121352,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,11,16]],"date-time":"2018-11-16T00:00:00Z","timestamp":1542326400000},"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":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>Packet classification methods rely upon packet content\/header matching against rules. Thus, throughput of matching operations is critical in many networking applications. Further, with the advent of Software Defined Networking (SDN), efficient implementation of software approaches to matching are critical for the overall system performance.<\/jats:p>\n          <jats:p>\n            This article presents\n            <jats:sup>1<\/jats:sup>\n            GenMatcher, a generic, software-only, arbitrary matching framework for fast, efficient searches. The key idea of our approach is to represent arbitrary rules with efficient prefix-based tries. To support arbitrary wildcards, we rearrange bits within the rules such that wildcards accumulate to one side of the bitstring. Since many non-contiguous wildcards often remain, we use multiple prefix-based tries. The main challenge in this context is to generate efficient trie groupings and expansions to support all arbitrary rules. Finding an optimal mix of grouping and expansion is an NP-complete problem.\n          <\/jats:p>\n          <jats:p>Our contribution includes a novel, clustering-based grouping algorithm to group rules based upon their bit-level similarities. Our algorithm generates near-optimal trie groupings with low configuration times and provides significantly higher match throughput compared to prior techniques. Experiments with synthetic traffic show that our method can achieve a 58.9X speedup compared to the baseline on a single core processor under a given memory constraint.<\/jats:p>","DOI":"10.1145\/3281663","type":"journal-article","created":{"date-parts":[[2018,11,16]],"date-time":"2018-11-16T13:08:54Z","timestamp":1542373734000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["GenMatcher"],"prefix":"10.1145","volume":"15","author":[{"given":"Ping","family":"Wang","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, Texas A8M University, College Station, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luke","family":"McHale","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, Texas A8M University, College Station, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul V.","family":"Gratz","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, Texas A8M University, College Station, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex","family":"Sprintson","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, Texas A8M University, College Station, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,11,16]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"{n. d.}. The CAIDA Anonymized 2012 Internet Traces\u20142012. Retrieved from http:\/\/www.caida.org\/data\/passive\/passive_2012_dataset.xml.  {n. d.}. The CAIDA Anonymized 2012 Internet Traces\u20142012. Retrieved from http:\/\/www.caida.org\/data\/passive\/passive_2012_dataset.xml."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2576768.2598284"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081932"},{"volume-title":"Proceedings of the 2016 IEEE International Conference on Cluster Computing (CLUSTER). 1--10","author":"Bayatpour M.","key":"e_1_2_1_4_1"},{"volume-title":"Greedy sequential maximal independent set and matching are parallel on average. CoRR abs\/1202.3205","year":"2012","author":"Blelloch Guy E.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2555243.2555269"},{"volume-title":"Proceedings of the 2016 IEEE 21st International Workshop on Computer Aided Modelling and Design of Communication Links and Networks (CAMAD). 24--30","author":"Elmahgiubi M.","key":"e_1_2_1_7_1"},{"volume-title":"MPI: A Message-Passing Interface Standard Version 3.1","year":"2015","author":"Interface Forum Message Passing","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1940092.1940138"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2014.53"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312036"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2881025.2881036"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2014.52"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2619239.2626294"},{"volume-title":"Proceedings of the 2016 IEEE 24th International Conference on Network Protocols (ICNP). 1--10","author":"Kogan K.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2017.2728642"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3001647.3001691"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2017.02.005"},{"volume-title":"Proc. BMVC. 81","author":"Leibe B.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2966884.2966907"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465322"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732951.2732965"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2772722.2772747"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2009.2030188"},{"volume-title":"IEEE INFOCOM 2008\u2014The 27th Conference on Computer Communications.","author":"Liu A. X.","key":"e_1_2_1_25_1"},{"volume-title":"Mahdi Jafari Siavoshani, and Mohammdsadegh Saberian.","year":"2017","author":"Lotfollahi Mohammad","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2007.892845"},{"volume-title":"Semi-supervised Clustering on Heterogeneous Information Networks","author":"Luo Chen","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1811039.1811065"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347123"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2014.95"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2165323"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ANCS.2011.36"},{"volume-title":"Proceedings of the 2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). 521--526","author":"Nikolenko S. I.","key":"e_1_2_1_34_1"},{"volume-title":"Jordan","year":"2015","author":"Pan Xinghao","key":"e_1_2_1_35_1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2007.82"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SBAC-PAD.2013.29"},{"key":"e_1_2_1_38_1","first-page":"6","article-title":"Generalized parallelization of string matching algorithms on SIMD architecture","volume":"11","author":"Rasool Akhtar","year":"2013","journal-title":"International Journal of Computer Science and Infomation Security"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486001.2486009"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/65.912716"},{"volume-title":"Proceedings of the 2015 12th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD). 2190--2195","author":"Sia Y. K.","key":"e_1_2_1_41_1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035954"},{"volume-title":"2010 Proceedings IEEE INFOCOM. 1--9.","author":"Song H.","key":"e_1_2_1_43_1"},{"volume-title":"Proceedings of the 17th International Conference on Machine Learning (ICML\u201900)","year":"2000","author":"Wagstaff Kiri","key":"e_1_2_1_44_1"},{"volume-title":"Proceedings of the 18th International Conference on Machine Learning (ICML\u201901)","year":"2001","author":"Wagstaff Kiri","key":"e_1_2_1_45_1"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2740070.2626297"},{"volume-title":"Proceedings of the 12th IEEE International Conference on Network Protocols (ICNP\u201904)","author":"Yu Fang","key":"e_1_2_1_47_1"},{"volume-title":"The application of deep learning on traffic identification. BlackHat","year":"2015","author":"Wang Z.","key":"e_1_2_1_48_1"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3281663","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3281663","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:10Z","timestamp":1750208530000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3281663"}},"subtitle":["A Generic Clustering-Based Arbitrary Matching Framework"],"short-title":[],"issued":{"date-parts":[[2018,11,16]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3281663"],"URL":"https:\/\/doi.org\/10.1145\/3281663","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2018,11,16]]},"assertion":[{"value":"2018-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}