Efficient construction of multibit tries for IP lookup
Authors:
- 26 August 2003
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 11 (4) , 650-662
Abstract
Srinivasan and Varghese (see ACM Trans. Comput. Syst., p.1-40, 1999) have proposed the use of multibit tries to represent routing tables used for Internet (IP) address lookups. They propose dynamic programming algorithms to determine the strides of optimal multibit fixed-stride and variable-stride tries. We improve on these algorithms by providing alternative dynamic programming formulations for both fixed- and variable-stride tries. While the asymptotic complexities of our algorithms are the same as those for the corresponding algorithms of Srinivasan and Varghese, experiments using real IPv4 routing table data indicate that our algorithms run considerably faster. Our fixed-stride trie algorithm is two to four times faster on a SUN workstation and 1.5 to three times faster on a Pentium IV PC. On a SUN workstation, our variable-stride trie algorithm is between two and 17 times faster than the corresponding algorithm of Srinivasan and Varghese; on a Pentium IV PC, our algorithm is between three and 47 times faster. An added feature of our variable-stride trie algorithm is the ability to insert and delete prefixes taking a fraction of the time needed to construct an optimal variable-stride trie "from scratch".Keywords
This publication has 12 references indexed in Scilit:
- Fast routing table lookup using CAMs2002
- IP lookups using multiway and multicolumn search2002
- Fast address lookups using controlled prefix expansionACM Transactions on Computer Systems, 1999
- Optimal routing table design for IP address lookups under memory constraints1999
- Fast address lookup for Internet routers1998
- 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
- Routing on longest-matching prefixesIEEE/ACM Transactions on Networking, 1996