I will describe some research issues in building fast Internet (IP) routers, and concentrate on one aspect of this problem--fast IP lookups. Briefly, the problem is as follows. Every Internet message carries a 32 bit destination Internet (IP) address. Backbone routers must find the longest matching prefix of the address in a database of around 50,000 prefixes in 320 nsec (at gigabit rates) or 32 nsec (at terabit rates).

I will describe several of our approaches to the problem. The first approach, threaded indices, attempts to eliminate the problem entirely by pushing the problem to other parts of the system; it is identical in concept to (but predates) Cisco's tag switching. Problems with threaded indices led us to invent approaches based on binary search on prefix lengths and controlled prefix expansion. These inventions have been licensed to several companies.

While our earlier approaches work well at gigabit rates even in software, scaling to terabit rates requires dedicated hardware and requires placing the entire lookup database in on-chip memory. Limited on-chip memory requires the use of compressed data structures that support incremental updates. I will describe why these problems have recently forced us to reconsider forty years of research on storage allocation and memory compaction, and to invent simple new memory allocators that give much better worst-case bounds than say the buddy system.

I will end by briefly describing some other aspects of building fast routers. One sample problem we are working on is the problem of fast lookup algorithms for firewall filters, a major bottleneck for screening routers today.