Robust and efficient TCAM-based classification

David Hay

Politecnico di Torino, Italy


Abstract: Ternary content-addressable memory (TCAM) devices are increasingly used for performing high-speed packet classification, one of the most challenging tasks in router design today. A TCAM consists of an associative memory that compares a search key in parallel against all entries and thus provides high throughput. In this talk we tackle two challenges related to these devices. First, we present PEDS, a novel parallel error detection scheme that locates the erroneous entries in a TCAM device. Time permitting, we will also discuss the representation of rules that contain range fields (e.g. source or destination ports) and present a novel scheme for dealing with them efficiently. These are joint works with Anat Bremler-Bar (IDC, Israel), Danny Hendler (BGU, Israel) and Ronny Roth (Technion, Israel). Based on papers appeared in INFOCOM 2009. Runner-up for the best paper award. Bio: David Hay received his BA (summa cum laude) and PhD degree in computer science from the Technion - Israel Institute of Technology in 2001 and 2007, respectively. He is currently a post-doctoral fellow at the department of electrical engineering, Politecnico di Torino, Italy. His main research interests are algorithmic aspects of high-performance switches and routers; in particular: QoS provisioning, competitive analysis and packet classification. Between 1999-2002, David Hay was with IBM Haifa Research Labs. During summer 2006, he was interning at the Data Center Business Unit of Cisco Systems, San Jose. In 2007-2008, he was a post-doc fellow at the department of computer science, Ben Gurion University of the Negev, Israel.

[David Hay]
[Politecnico di Torino, Italy]