2003 · 40 citations · 11 references
ComputingComputer EngineeringComputer ScienceAlgorithmsComputer NetworksData StructuresAlgorithm AnalysisDynamic ProgrammingInternet RoutingLookup TablesRoutingRouting AlgorithmsOptimal Prefix ComputationRouting PrefixesRouting Table ConstructionRouting Tables
Srinivasan and Varghese (1999) have proposed the use of multibit tries to represent routing tables used for Internet (IP) address lookups. They propose an O(n /sub */W/sup 2//sub */ k) dynamic programming algorithm to determine the strides for an optimal variable-stride trie that has at most k levels. Here, n is the number of prefixes in the routing table and W is the length of the longest prefix. We improve on this algorithm by providing an alternative dynamic programming formulation. The complexity of our algorithm is O(n/sub */W/sub */k), on real router data sets. This is an improvement by a factor of W over the corresponding algorithm of Srinivasan. Experiments conducted by us indicate that our variable-stride algorithm is between 2 and 17 times as fast for IPv4 routing table data.
11
Scalable high speed IP routing lookups
Marcel Waldvogel, George Varghese, Jon Turner et al. · 1997 · 663 citations · Full text
Small forwarding tables for fast routing lookups
Mikael Degermark, Andrej Brodnik, Svante Carlsson et al. · 1997 · 591 citations · Full text
Fast routing table lookup using CAMs
A. McAuley, Paul Francis · 2002 · 310 citations
Faster IP lookups using controlled prefix expansion
V. Srinivasan, George Varghese · 1998 · 280 citations