Fast IP routing with LC-tries

Stefan Nilsson and Gunnar Karlsson

One of the bottlenecks of the Internet is the address lookup operations performed by the routers. Expensive tailor-made hardware solutions have typically been used to achieve necessary speed. In this article, we'll show that it is possible to perform the lookups efficiently with a simple data structure -- a level compressed trie or LC-trie. A sortware implementation can sustain several million lookups per second, enough to match a Gbit/sec link. The data structure is simple and it scales well. No modifications are needed when swithching from the 32-bit addressed of IP version 4 (IPv4) to the 128-bit addresses of IP version 6 (IPv6), and we expect the lookup operation to be almost as fast for the longer addresses.
- - -

In Dr. Dobb's Journal, pp. 70-75, Vol. 288, August 1998.
Complete text.