Abstract

Session

Header Processing

Paper

9-3

Full Paper

ps.gz

Title

Memory-Efficient State Lookups with Fast Updates

Author(s)

Sandeep Sikka (Inktomi)
George Varghese (UCSD)

Abstract:

Routers must do a best matching prefix lookup for every packet; solutions for Gigabit speeds are well known. As Internet link speeds move to OC-192 (10 Gbps) and higher, IP lookups must complete in tens of nanoseconds, requiring the use of on-chip or off-chip SRAM, which is limited by either expense or manufacturing process. In this paper, we propose an IP lookup scheme that can scale with memory speeds and yet provide worst-case guarantees. We show that doing so requires new algorithms and the breaking down of traditional abstraction boundaries between hardware and software. A particular focus of this paper is to have a lookup chip provide guarantees on the number of IP prefixes it can support. To do so we introduce new memory allocators that have provable worst-case memory utilization guarantees that can reach 100 \%; this is contrast to all standard allocators that can only guarantee 20 \% utilization when (for example) the requests can come in the range 1..32. An optimal version of our algorithm requires a new (but feasible) SRAM memory design that allows shifted access in addition to normal word access. This small extra feature in the memory design can double the guaranteed number of prefixes the chip can support. Our techniques generalize to other state lookups besdes prefix lookup.