Naslov
DXR : towards a billion routing lookups per second in software

Autori
Zec, Marko ; Rizzo, Luigi ; Mikuc, Miljenko

Izvornik
Computer communication review (0146-4833) 42 (2012), 5; 29-36

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Packet Lookup and Classification; Software Routers

Sažetak
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 scalesalmost 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.

Izvorni jezik
Engleski

Znanstvena područja
Elektrotehnika, Računarstvo

POVEZANOST RADA