Colloquium Speaker
| Speaker: | Mikael Degermark Lulea University, Sweden | |
|---|---|---|
| Topic: | Small Forwarding Tables for Fast Address Lookups | |
| Date: | Monday, March 29, 1999 | |
| Time: | 4:00 PM | |
| Place: | Gould-Simpson, 701 |
| Speaker: | Mikael Degermark Lulea University, Sweden | |
|---|---|---|
| Topic: | Small Forwarding Tables for Fast Address Lookups | |
| Date: | Monday, March 29, 1999 | |
| Time: | 4:00 PM | |
| Place: | Gould-Simpson, 701 |
As late as 1997 the networking community assumed it was impossible to do IP address lookups in software fast enough to support gigabit speeds. IP address lookups must find the routing entry with the longest matching prefix, a task that was thought to require hardware support at lookup frequencies of millions per second.
The talk will present the IP address lookup problem and a data structure and accompanying algorithm that achieves lookup frequencies suitable for gigabit speeds. The lookup algorithm and data structure was first published in the Sigcomm '97 conference where it received the student paper award.
A forwarding table using this data structure is small enough to fit in the (second-level) cache of conventional general- purpose processors. With the table in cache, 200-300 MHz processors are capable of performing several million lookups per second. This means that it became feasible to do full IP address lookups for each IP packet at gigabit speeds without special hardware.
The forwarding tables are very small, a large routing table with 40,000 routing entries can be compacted to a forwarding table of 150-160 Kbytes. Although other fast address lookup schemes have been published after Sigcomm'97, none of these produce smaller forwarding tables.