{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T14:13:59Z","timestamp":1761401639842,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2012,9,24]],"date-time":"2012-09-24T00:00:00Z","timestamp":1348444800000},"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":["SIGCOMM Comput. Commun. Rev."],"published-print":{"date-parts":[[2012,9,24]]},"abstract":"<jats:p>Can a software routing implementation compete in a field generally reserved for specialized lookup hardware? This paper presents DXR, an IPv4 lookup scheme based on transforming large routing tables into compact lookup structures which easily fit into cache hierarchies of modern CPUs. DXR supports various memory\/speed tradeoffs and scales almost linearly with the number of CPU cores. The smallest configuration, D16R, distills a real-world BGP snapshot with 417,000 IPv4 prefixes and 213 distinct next hops into a structure consuming only 782 Kbytes, less than 2 bytes per prefix, and achieves 490 million lookups per second (MLps) in synthetic tests using uniformly random IPv4 keys on a commodity 8-core CPU. Some other DXR configurations exceed 700~MLps at the cost of increased memory footprint. DXR significantly outperforms a software implementation of DIR-24-8-BASIC, has better scalability, and requires less DRAM bandwidth. Our prototype works inside the FreeBSD kernel, which permits DXR to be used with standard APIs and routing daemons such as Quagga and XORP, and to be validated by comparing lookup results against the BSD radix tree.<\/jats:p>","DOI":"10.1145\/2378956.2378961","type":"journal-article","created":{"date-parts":[[2012,10,2]],"date-time":"2012-10-02T13:50:00Z","timestamp":1349185800000},"page":"29-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":54,"title":["DXR"],"prefix":"10.1145","volume":"42","author":[{"given":"Marko","family":"Zec","sequence":"first","affiliation":[{"name":"University of Zagreb, Zagreb, Croatia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luigi","family":"Rizzo","sequence":"additional","affiliation":[{"name":"Universita di Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miljenko","family":"Mikuc","sequence":"additional","affiliation":[{"name":"University of Zagreb, Zagreb, Croatia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,9,24]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"IPv6 \/ IPv4 comparative BGP statistics. http:\/\/bgp.potaroo.net\/v6\/v6rpt.html.  IPv6 \/ IPv4 comparative BGP statistics. http:\/\/bgp.potaroo.net\/v6\/v6rpt.html."},{"key":"e_1_2_1_2_1","unstructured":"DXR\n  : Direct\/Range routing lookups home page. http:\/\/www.nxlab.fer.hr\/dxr\/.  DXR: Direct\/Range routing lookups home page. http:\/\/www.nxlab.fer.hr\/dxr\/."},{"key":"e_1_2_1_3_1","volume-title":"QFQ: Efficient packet scheduling with tight guarantees","author":"Checconi F.","year":"2012","unstructured":"F. Checconi , L. Rizzo , and P. Valente . QFQ: Efficient packet scheduling with tight guarantees . IEEE\/ACM Trans. on Networking , 2012 (to appear). F. Checconi, L. Rizzo, and P. Valente. QFQ: Efficient packet scheduling with tight guarantees. IEEE\/ACM Trans. on Networking, 2012 (to appear)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/263109.263133"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629578"},{"key":"e_1_2_1_6_1","volume-title":"IEEE Workshop on High Perf. Switching and Routing","author":"Fu J.","year":"2006","unstructured":"J. Fu , O. Hagsand , and G. Karlsson . Performance evaluation and cache behavior of LC-trie for IP-address lookup . In IEEE Workshop on High Perf. Switching and Routing , Poznan , 2006 . J. Fu, O. Hagsand, and G. Karlsson. Performance evaluation and cache behavior of LC-trie for IP-address lookup. In IEEE Workshop on High Perf. Switching and Routing, Poznan, 2006."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.1998.662938"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851182.1851207"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.779199"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.772439"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.700888"},{"key":"e_1_2_1_12_1","volume-title":"Usenix ATC 2012","author":"Rizzo L.","year":"2012","unstructured":"L. Rizzo . netmap : A novel framework for fast packet I\/O . In Usenix ATC 2012 . Usenix , 2012 . L. Rizzo. netmap: A novel framework for fast packet I\/O. In Usenix ATC 2012. Usenix, 2012."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2093548.2093565"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/65.912716"},{"key":"e_1_2_1_15_1","first-page":"93","volume-title":"USENIX Winter Conference","author":"Sklower K.","year":"1991","unstructured":"K. Sklower . A tree-based packet routing table for Berkeley Unix . In USENIX Winter Conference , pages 93 -- 104 , 1991 . K. Sklower. A tree-based packet routing table for Berkeley Unix. In USENIX Winter Conference, pages 93--104, 1991."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2009.5062180"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/277851.277863"},{"key":"e_1_2_1_18_1","first-page":"1421","volume-title":"INFOCOM","author":"Pradhan P.","year":"1999","unstructured":"Tzi-cker Chiueh and P. Pradhan . High performance IP routing table lookup using CPU caching . In INFOCOM , pages 1421 -- 1428 , 1999 . Tzi-cker Chiueh and P. Pradhan. High performance IP routing table lookup using CPU caching. In INFOCOM, pages 1421--1428, 1999."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2079296.2079325"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/502912.502914"}],"container-title":["ACM SIGCOMM Computer Communication Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2378956.2378961","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2378956.2378961","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:01:06Z","timestamp":1750276866000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2378956.2378961"}},"subtitle":["towards a billion routing lookups per second in software"],"short-title":[],"issued":{"date-parts":[[2012,9,24]]},"references-count":20,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,9,24]]}},"alternative-id":["10.1145\/2378956.2378961"],"URL":"https:\/\/doi.org\/10.1145\/2378956.2378961","relation":{},"ISSN":["0146-4833"],"issn-type":[{"type":"print","value":"0146-4833"}],"subject":[],"published":{"date-parts":[[2012,9,24]]},"assertion":[{"value":"2012-09-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}