erlman, long nonbranching paths of the trie can be col- lapsed if they do not contain a dictionary entry. This enables the entire substring to be found with only one search in some cases. Another interesting approach, which is based on the idea that the search does not have to be initi- ated by chasing only one bit a time,8 is to trade memory for search time.9 As an example of 2-bit searches, the prefix 10 would have multiple child nodes instead of a 1 and a 0. It would therefore potentially expand to 1000, 1001, 1010, or 1011. Any address that matches the prefix 10 would sim- ply have to match one of the elements of the set {1000, 1001, 1010, 1011}. The search is completed in two steps, as opposed to four. The principle can be expanded to 4, 8, 16, and higher bit-block searches that correspondingly increase the speed but also geometrically multiply the memory needed. Of course, such a trade-off between preprocessing time versus memory is not always feasible. Therefore, a systems designer must always be alert of ramifications of design choices within a cer- tain context. A couple of other clever approaches are to compress the expanded prefixes in the so-called Lulea scheme (from the Swedish city where the research team that invented it is based)10 and to perform a binary search using special hashing functions on prefix lengths. 11 If we imagine prefixes expanded to lengths that are multiples of 16 bits, we will end up having 2 16 child nodes, causing a very serious memory problem. If we suppose that only a small fraction of these 216 possibilities are real prefixes, then most of the nodes will be the result of expanded smaller prefixes and lots of memory 7. Radia Perlman, Interconnections: Bridges, Routers, Switches, and Internetworking Protocols, 2nd ed. (Reading, Massachusetts: Addison-Wesley, 2000). 8. V. Srinivasan and G. Varghese, "Faster IP Lookups using Controlled Prefix Expansion," ACM Sigmetrics 1998, ACM Transactions on Computer Systems, March 1999. 9. Radia Perlman, Interconnections: Bridges, Routers, 