Robust and Efficient TCAM-Based Packet Classification

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. TCAM enables parallel matching of a key against all TCAM entries, which consist of ``0'',``1'' and ``*'' (don't care) bits, in O(1) time. 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 how one can use TCAM to boost memory-efficiency of Aho-Corasick-like Deep Packet Inspection (DPI) algorithms; this is done by efficiently encoding transitions into prefixes and applying Longest Prefix Matching rule.

These works appear in INFOCOM 2010 and INFOCOM 2009 (runner-up to best paper) and in ACM/IEEE Transactions on Networking. Joint work with Anat Bremler-Barr (IDC), Yaron Koral (IDC), Danny Hendler (BGU) and Ron M. Roth (Technion).

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 research scientist at the department of electrical engineering, Columbia University, NY, USA. His main research interests are algorithmic aspects of high-performance switches and routers; in particular: Packet classification, QoS provisioning and competitive analysis. 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. He was also a post-doc fellow at the department of computer science, Ben Gurion University of the Negev, Israel (2007-2008), and at the departmenty of electrical engineering, Politecnico di Torino, Italy (2008-2009). In October 2009, he is expected to join the school of Computer Science of the Hebrew University of Jerusalem, Israel.