DXR: Towards a Billion Routing Lookups per Second in Software. Zec, M., Rizzo, L., & Mikuc, M. ACM SIGCOMM COMPUTER COMMUNICATION REVIEW, 42(5):29–36, ASSOC COMPUTING MACHINERY, 2 PENN PLAZA, STE 701, NEW YORK, NY 10121-0701 USA, October, 2012. doi abstract bibtex 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.
@article{WOS:000309425900005,
abstract = {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.},
address = {2 PENN PLAZA, STE 701, NEW YORK, NY 10121-0701 USA},
author = {Zec, Marko and Rizzo, Luigi and Mikuc, Miljenko},
doi = {10.1145/2378956.2378961},
issn = {0146-4833},
journal = {ACM SIGCOMM COMPUTER COMMUNICATION REVIEW},
keywords = {Algorithms; Performance; Experimentation},
month = oct,
number = {5},
pages = {29--36},
publisher = {ASSOC COMPUTING MACHINERY},
title = {{DXR: Towards a Billion Routing Lookups per Second in Software}},
type = {Review},
volume = {42},
year = {2012}
}
Downloads: 0
{"_id":"LdxNtd7Tzy27RKgTE","bibbaseid":"zec-rizzo-mikuc-dxrtowardsabillionroutinglookupspersecondinsoftware-2012","author_short":["Zec, M.","Rizzo, L.","Mikuc, M."],"bibdata":{"bibtype":"article","type":"Review","abstract":"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.","address":"2 PENN PLAZA, STE 701, NEW YORK, NY 10121-0701 USA","author":[{"propositions":[],"lastnames":["Zec"],"firstnames":["Marko"],"suffixes":[]},{"propositions":[],"lastnames":["Rizzo"],"firstnames":["Luigi"],"suffixes":[]},{"propositions":[],"lastnames":["Mikuc"],"firstnames":["Miljenko"],"suffixes":[]}],"doi":"10.1145/2378956.2378961","issn":"0146-4833","journal":"ACM SIGCOMM COMPUTER COMMUNICATION REVIEW","keywords":"Algorithms; Performance; Experimentation","month":"October","number":"5","pages":"29–36","publisher":"ASSOC COMPUTING MACHINERY","title":"DXR: Towards a Billion Routing Lookups per Second in Software","volume":"42","year":"2012","bibtex":"@article{WOS:000309425900005,\nabstract = {Can a software routing implementation compete in a field generally\nreserved for specialized lookup hardware? This paper presents DXR, an\nIPv4 lookup scheme based on transforming large routing tables into\ncompact lookup structures which easily fit into cache hierarchies of\nmodern CPUs.\nDXR supports various memory/speed tradeoffs and scales almost linearly\nwith the number of CPU cores. The smallest configuration, D16R, distills\na real-world BGP snapshot with 417,000 IPv4 prefixes and 213 distinct\nnext hops into a structure consuming only 782 Kbytes, less than 2 bytes\nper prefix, and achieves 490 million lookups per second (MLps) in\nsynthetic tests using uniformly random IPv4 keys on a commodity 8-core\nCPU. Some other DXR configurations exceed 700 MLps at the cost of\nincreased memory footprint. DXR significantly outperforms a software\nimplementation of DIR-24-8-BASIC, has better scalability, and requires\nless DRAM bandwidth.\nOur prototype works inside the FreeBSD kernel, which permits DXR to be\nused with standard APIs and routing daemons such as Quagga and XORP, and\nto be validated by comparing lookup results against the BSD radix tree.},\naddress = {2 PENN PLAZA, STE 701, NEW YORK, NY 10121-0701 USA},\nauthor = {Zec, Marko and Rizzo, Luigi and Mikuc, Miljenko},\ndoi = {10.1145/2378956.2378961},\nissn = {0146-4833},\njournal = {ACM SIGCOMM COMPUTER COMMUNICATION REVIEW},\nkeywords = {Algorithms; Performance; Experimentation},\nmonth = oct,\nnumber = {5},\npages = {29--36},\npublisher = {ASSOC COMPUTING MACHINERY},\ntitle = {{DXR: Towards a Billion Routing Lookups per Second in Software}},\ntype = {Review},\nvolume = {42},\nyear = {2012}\n}\n","author_short":["Zec, M.","Rizzo, L.","Mikuc, M."],"key":"WOS:000309425900005","id":"WOS:000309425900005","bibbaseid":"zec-rizzo-mikuc-dxrtowardsabillionroutinglookupspersecondinsoftware-2012","role":"author","urls":{},"keyword":["Algorithms; Performance; Experimentation"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://bibbase.org/f/rTKwnBhyGKSSptYtt/My Collection.bib","dataSources":["DY3AeP9t2QujfB78L","MpTxM7aR49zFotABd"],"keywords":["algorithms; performance; experimentation"],"search_terms":["dxr","towards","billion","routing","lookups","per","second","software","zec","rizzo","mikuc"],"title":"DXR: Towards a Billion Routing Lookups per Second in Software","year":2012}