Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

CHAPTER 11 Prefix-Match Lookups > 11.14 EXERCISES - Pg. 266

266 CHAPTER 11 Prefix-Match Lookups number of stages. A careful VLSI scaling analysis of these two approaches would be very useful. Underlying Principles: Although this is a chapter about lookups and thinking about lookups requires paying attention to current market trends, it is important not to forget that this is a book about underlying principles. It is plausible that routers in the misty future may use all-optical switches and all-optical processing, even for lookups. In that case, the specific algorithms described in this chapter may be discarded; but perhaps the underlying design principles will remain. Although the schemes described in this chapter require some algorithmic thinking, they also employ many of the other principles we have stressed. The schemes make heavy use of precomputation, which trades slower insert/delete times for fast search times. The schemes also exploit hardware features such as wide memories, distinguish fast and slow memories, trade memory for time, and optimize the degrees of freedom in a given design. Figure 11.1 summarizes the schemes and the principles used in them. Finally, this chapter cannot hope to do justice to all the interesting IP lookup schemes that have been published in the academic and patent literature. You can look it up. 11.14 EXERCISES 1. Caching Prefixes: Suppose we have the prefixes 10*, 100*, and 1001*. Hugh Hopeful would like to cache prefixes instead of entire 32-bit addresses. Hugh's scheme keeps a set of prefixes in the cache (fast memory), in addition to the complete set of prefixes in slow memory. Hugh's scheme first does a best-matching-prefix search in the cache; if a matching prefix is found, the next hop of the prefix is used. If no matching prefix is found, a best-matching-prefix search is done for the entire database and the resulting prefix cached. Periodically, prefixes that have not been matched for a while are flushed from the cache. Alyssa P. Hacker quickly gives Hugh a counterexample to show him that