Search Engines Face Software Challenge
An interesting sideshow is brewing in the field of search engines -- not the Googles of this world, but the stuff inside packet processing equipment that performs ultra-fast lookups of huge routing tables.
A lot of recent attention in this field has focused on the arrival of higher-density TCAMs (ternary content addressable memory) chips. But now a bunch of startups are saying they can do much the same thing in software, using algorithms or mathematical and programming tricks.
At least one of these algorithm startups has been acquired already -- five-man outfit Sahasra Networks Inc. (see From Academics to Entrepreneurs) was snatched up in February by Cypress Semiconductor Corp. (NYSE: CY), which hopes to announce a product next year. Meanwhile, others are emerging. Israeli firm HyWire Ltd. announced its architecture at this week's Network Processors Conference, and East-coast startup BestRoute Inc. recently completed a test run of its algorithm on Intel Corp.'s (Nasdaq: INTC) IXP2800 network processor.
Chances are, the competing approaches will settle into separate segments of the overall search-engine market, rather than algorithms completely eliminating TCAMs or vice versa. (Analyst Joe Byrne of Gartner/Dataquest likens the rivalry to an argument between cat owners and dog owners.) For now, though, startups are enjoying the novelty of presenting an algorithmic solution, and everyone else is having fun handicapping the newcomers against the TCAM mainstream.
For the CAM vendors, algorithms haven't been a threat so far. Graham Allan, director of marketing at SiberCore Technologies, says he's seen algorithms targeted mainly at IPv4 routing, a market that comes with its own handicap.
"That's going to be Cisco's ASICs and Juniper's ASICs -- that's what they're competing with," he says. "Algorithmic searches today do have an application, but I don't see how it's not captive."
Solidum Systems Corp. -- now part of Integrated Device Technology Inc. (IDT) (Nasdaq: IDTI) -- had its own search algorithms but always considered them to be a tool for CAMs, rather than a product of their own (see IDT to Acquire Solidum).
"It doesn't matter what algorithm you pick; it's always complex and always slow," says Russ Baker, field application engineer first for Solidum, now for IDT. "We know this is complex, and that's why we started teaming with CAM vendors early on."
The algorithmic upstarts also face the challenge of being startups in a bad market. Being a company of "less than 10" people, BestRoute's best hope is to get the blessing of Intel and other network processor vendors, says Thomas Summit, vice president of business development. He's also trying to get systems vendors interested but is running into the usual "not-invented-here" battle.
"We're talking about a miniscule, unknown little company trying to get attention in this market," Summit says. "I wish we had the visibility into the venture capital community that Pankaj [Gupta, Sahasra's founder] did."
BestRoute's product is BestRouteForwarding, or BRF, a search algorithm that the company has implemented in C code. The company recently completed porting BRF to Intel's IXP2800, which provided some concrete performance data to show the algorithm works. BRF clocked in at 112 million lookups per second, searching tables stored in 200MHz SRAMs and using all four SRAM ports on the network processor.
BestRoute is also in discussions with IBM Corp. (NYSE: IBM) and Agere Systems (NYSE: AGR) to port to their network processors. And the company is talking to "major router vendors" about using the algorithm, says Summit.
BRF won't put any TCAM vendors out of business just yet, however. One of the algorithm's strengths is its ability to work with enormous tables; but with companies such as SiberCore offering 8 million table entries on cascaded chips, customers aren't worried about size restrictions, Summit points out (see SiberCore Intensifies Searches).
So BestRoute will start by aiming for lower-end designs where the removal of a TCAM can make a significant cost or power difference. The system would still require table storage, but the designer could use DRAM, a cheap alternative to a TCAM. DRAM normally updates too slowly to be effective for table searches, but BRF includes patented know-how that speeds the update process, Summit claims.
Unlike BestRoute, HyWire took a hardware approach. This week, the company unveiled its Range Search Engine chip, which combines SRAM table storage with single-instruction, multiple-data (SIMD) microprocessor cores (see HyWire Launches First Product). The chip was engineered specifically to execute HyWire's proprietary search algorithm, and the technology appears to have found at least one friend -- HyWire announced a partnership with Infineon Technologies AG (NYSE/Frankfurt: IFX) last year (see Infineon, HyWire Team Up on Routers).
HyWire's algorithm can use a range of numbers as a search key, and the range can be of arbitrary size. The most similar chip on the market is the Policy Edge from Fast-Chip Inc., according to founder and CEO Moshe Stark. That chip also keys on numerical ranges for searches.
HyWire claims to hit speeds of 250 million lookups per second. The company's chip matches TCAMs' workload of one lookup per clock cycle but simply runs on a faster clock, Stark says.
HyWire's algorithm works like this: Each processor core is assigned a particular segment of memory, and each table result is uniquely represented somewhere in the total available memory. That means that any given search will find exactly one right answer; you'll never see two memory segments returning a match for any given key.
Thus, all the processors check their memory segments in parallel, and the actual search is performed only on the memory segment that contains the match. This cuts down substantially on the search time (multiple-stage searches are never necessary, Stark claims) and also minimizes the amount of data being passed between HyWire's chip and the network processor (every query gets exactly one answer).
Stark wouldn't explain the one trick that makes this method work: the fact that every processor knows immediately whether its memory segment contains the match being sought. He also wouldn't specify how many processor cores are on the chip ("many tens" of cores, was all he would reveal).
However it works, the Range Search Engine's algorithm can be expanded across multiple chips, so that only one memory segment on one of the chips will contain the desired match. Moreover, the processors have the smarts to keep this uniqueness alive as entries are added or deleted. "Our chips manage their own address spaces," Stark says.
For starters, the Range Search Engine can fit 128,000 forwarding entries -- "not the greatest" capacity, Stark admits. A companion chip, still in development, will expand that capacity to "several million entries," he claims.
The Range Search Engine is sampling now, with general availability slated for the third quarter of 2003.
— Craig Matsumoto, Senior Editor, Light Reading