242 CHAPTER 11 Prefix-Match Lookups 11.3 NONALGORITHMIC TECHNIQUES FOR PREFIX MATCHING In this section, we consider two other systems techniques for prefix lookups that do not rely on algorithmic methods: caching and ternary CAMs. Caching relies on locality in address references, while CAMs rely on hardware parallelism. 11.3.1 Caching Lookups can be sped up by using a cache (P11a) that maps 32-bit addresses to next hops. However, cache hit ratios in the backbone are poor [NMH97] because of the lack of locality exhibited by flows in the backbone. The use of a large cache still requires the use of an exact- match algorithm for lookup. Some researchers have advocated a clever modification of a CPU cache lookup algorithm for this purpose [CP99]. In summary, caching can help, but it does not avoid the need for fast prefix lookups. 11.3.2 Ternary Content-Addressable Memories Ternary content-addressable memories (CAMs) that allow "don't care" bits provide parallel search in one memory access. Today's CAMs can search and update in one memory cycle (e.g., 10 nsec) and handle any combination of 100,000 prefixes. They can even be cascaded to form larger databases. CAMs, however, have the following issues. · Density Scaling: One bit in a TCAM requires 10­12 transistors, while an SRAM requires 4­6 transistors. Thus TCAMs will also be less dense than SRAMs or take more area. Board area is a critical issue for many routers. · Power Scaling: TCAMs take more power because of the parallel compare. CAM vendors are, however, chipping away at this issue by finding ways to turn off parts of the CAM to reduce power. Power is a key issue in large core routers.