Memory-efficient state lookups with fast updates
Open Access
- 28 August 2000
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 30 (4) , 335-347
Abstract
Routers must do a best matching pre x lookup for every packet; solutions for Gigabit speeds are well known. As Internet link speeds higher, we seek a scalable solution whose speed scales with memory speeds while allowing large prex databases. In this paper we s h o w that providing such a solution requires careful attention to memory allocation and pipelining. This is because fast lookups require on-chip or o-chip SRAM which i s l i m i t e d b y either expense or manufacturing process. We s h o w that doing so while providing guarantees on the number of pre xes supported requires new algorithms and the breaking down of traditional abstraction boundaries between hardware and software. We i n troduce new problem-speci c memory allocators that have p r o vable memory utilization guarantees that can reach 100%; this is contrast to all standard allocators that can only guarantee 20% utilization when 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. Our techniques generalize to other IP lookup schemes and to other state lookups besides pre x lookup.Keywords
This publication has 16 references indexed in Scilit:
- IP lookups using multiway and multicolumn search2002
- Fast address lookups using controlled prefix expansionACM Transactions on Computer Systems, 1999
- High-speed policy-based packet forwarding using efficient multi-dimensional range matching1998
- Small forwarding tables for fast routing lookups1997
- Internet routing instability1997
- A real-time garbage collector based on the lifetimes of objectsCommunications of the ACM, 1983
- List processing in real time on a serial computerCommunications of the ACM, 1978
- Worst case fragmentation of first fit and best fit storage allocation strategiesThe Computer Journal, 1977
- Bounds for Some Functions Concerning Dynamic Storage AllocationJournal of the ACM, 1974
- An Estimate of the Store Size Necessary for Dynamic Storage AllocationJournal of the ACM, 1971