Faster IP lookups using controlled prefix expansion
Authors:
Open Access
- 1 June 1998
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 26 (1) , 1-10
Abstract
Internet (IP) address lookup is a major bottleneck in high performance routers. IP address lookup is challenging because it requires a longest matching prefix lookup. It is compounded by increasing routing table sizes, increased traffic, higher speed links, and the migration to 128 bit IPv6 addresses. We describe how IP lookups can be made faster using a new technique called controlled prefix expansion . Controlled prefix expansion, together with optimization techniques based on dynamic programming, can be used to improve the speed of the best known IP lookup algorithms by at least a factor of two. When applied to trie search, our techniques provide a range of algorithms whose performance can be tuned. For example, with 1 MB of L2 cache, trie search of the MaeEast database with 38,000 prefixes can be done in a worst case search time of 181 nsec, a worst case insert/delete time of 2.5 msec, and an average insert/delete time of 4 usec. Our actual experiments used 512 KB L2 cache to obtain a worst-case search time of 226 nsec, a worst-case worst case insert/delete time of 2.5 msec and an average insert/delete time of 4 usec. We also describe how our techniques can be used to improve the speed of binary search on prefix lengths to provide a scalable solution for IPv6. Our approach to algorithm design is based on measurements using the VTune tool on a Pentium to obtain dynamic clock cycle counts.Keywords
This publication has 9 references indexed in Scilit:
- Scalable high speed IP routing lookupsACM SIGCOMM Computer Communication Review, 1997
- Small forwarding tables for fast routing lookupsACM SIGCOMM Computer Communication Review, 1997
- IP switching and gigabit routersIEEE Communications Magazine, 1997
- Trading packet headers for packet processingIEEE/ACM Transactions on Networking, 1996
- Internet Protocol, Version 6 (IPv6) Specification1995
- Efficient fair queueing using deficit round robinACM SIGCOMM Computer Communication Review, 1995
- a I t P mACM SIGCOMM Computer Communication Review, 1995
- A Border Gateway Protocol 4 (BGP-4)1995
- Analysis and simulation of a fair queueing algorithm1989