Its complexity and speed has made ternary content-addressable memory (CAM) the foundation for storing networking tables. However, its avaricious consumption of power and board space has compelled many vendors and academics to search for alternatives. They have been trying to create new algorithms for longest-prefix match searches, which are essential in negotiating large routing tables. They hope to utilize standard DRAM or SRAM, which are slower and less complex than CAM, in place of sizeable ternary CAMs and, in so doing, use less power and board space. Some network processor companies have already developed classifiers that utilize commodity memory instead of CAMs.

Cypress Semiconductor Corp. began its foray into CAM alternatives with its recent acquisition of Sahasra, a startup whose two founders have authored most of the research papers on CAM replacement. Cypress, which is based in San Jose, California, has named its new chips after Sahasra. These new Sahasra chips, samples of which will be available in November and released to customers early next year, combine pipelined logic with ordinary SRAM. With Sahasra, Cypress does not aim to replace CAMs in general but ternary CAMs (TCAMs) in particular because they can get too cumbersome when storing routing information. Currently, routers utilize TCAMs in two areas—for policy decisions and routing tables, which help determine where to send packets of information. Routing tables far outnumber policy entries. As networks have increased in size, router tables and CAMs have followed suit, requiring more memory. In fact, California-based NetLogic Microsystems, Inc. shipped devices with an 18-Mbit memory early this year.

Cypress is not the first to attempt CAM replacement. Fast-Chip Inc. has a processor that utilizes proprietary boundary-addressable memory for table storage and uses a DRAM-based chip for voluminous routing tables. EZchip Technologies asserts that its network processor can classify without relying on CAMs. Furthermore, CAM vendors, like Purple Ray, acquired recently by Integrated Silicon Solution, Inc., are testing out new algorithms to enhance CAM speed. Algorithmic modifications can boost the number of searches launched to more than 300 million per second, estimates Christopher Norris, data communications vice president at Cypress. Algorithmic drawbacks, however, include small delays, as the searches are subject to RAM speed, and the limited power of the algorithms themselves. System vendors do not mind the former constraint of latency if in exchange they get line cards that require less power.

Despite the development of algorithmic approaches, CAMs are unlikely to be supplanted. "TCAMs give you the raw bandwidth because you're doing an associated search," says Bhanu Nanduri, head of SiPackets Inc. "There have been no known alternatives that could scale as well as TCAMs." In fact, the focus in networking has shifted to edge switching, which will emphasize policy tables over routing ones, according to Pat Lasserre, strategic marketing director at Integrated Device Technology Inc.

Cypress certainly does not intend to abandon the use of content-addressable memory either. It recently introduced its 18-Mbit NSE10000 product line with samples expected to be available in the fourth quarter. The company is also developing a more advanced group of search engines, which will work with network processors and apply the necessary logic for multi-step searches and if-then cases. These devices, to be named Vishara, are designed to eliminate the lengthy exchange of information between the network processor and ternary CAM when performing a complex search. Samples are expected later this year.

Source: CAM Vendors Consider Algorithmic Alternatives
Craig Matsumoto
EE Times, May 20, 2002
http://www.eet.com/semi/news/OEG20020520S0014