skip to main content
Department of Computer Science University of Colorado Boulder
cu: home | engineering | mycuinfo | about | cu a-z | search cu | contact cu cs: about | calendar | directory | catalog | schedules | mobile | contact cs
home · events · colloquia · 1998-1999 · 

Colloquium - Degermark

ECOT 831

Small Forwarding Tables for Fast Address Lookups
Mikael Degermark
Luleå University of Technology, Sweden

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.

Mikael Degermark photo

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.

Hosted by Karl Winklmann.

The Department holds colloquia throughout the Fall and Spring semesters. These colloquia, open to the public, are typically held on Thursday afternoons, but sometimes occur at other times as well. If you would like to receive email notification of upcoming colloquia, subscribe to our Colloquia Mailing List. If you would like to schedule a colloquium, see Colloquium Scheduling.

Sign language interpreters are available upon request. Please contact Stephanie Morris at least five days prior to the colloquium.

See also:
Department of Computer Science
College of Engineering and Applied Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
Send email to

Engineering Center Office Tower
ECOT 717
FAX +1-303-492-2844
XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado
Privacy · Legal · Trademarks
May 5, 2012 (13:29)