Broadly, my research focuses on algorithms and architectures for multi-gigabit networking systems. In particular, I have been working on:
Abstract: The continuous growth in the Internet's size, the amount of data traffic, and the complexity of processing this traffic gives rise to new challenges in building highperformance network devices. One of the most fundamental tasks performed by these devices is searching the network data for predefined keys. Address lookup, packet classification, and deep packet inspection are some of the operations which involve table lookups and searching. These operations are typically part of the packet forwarding mechanism, and can create a performance bottleneck. Therefore, fast and resource efficient algorithms are required. One of the most commonly used techniques for such searching operations is the Ternary Content Addressable Memory (TCAM). While TCAM can offer very fast search speeds, it is costly and consumes a large amount of power. Hence, designing cost-effective, power-efficient, and high-speed search techniques has received a great deal of attention in the research and industrial community.
In this thesis, we propose a generic search technique based on Bloom filters. A Bloom filter is a randomized data structure used to represent a set of bit-strings compactly and support set membership queries. We demonstrate techniques to convert the search process into table lookups. The resulting table data structures are kept in the off-chip memory and their Bloom filter representations are kept in the on-chip memory. An item needs to be looked up in the off-chip table only when it is found in the on-chip Bloom filters. By filtering the off-chip memory accesses in this fashion, the search operations can be significantly accelerated. Our approach involves a unique combination of algorithmic and architectural techniques that outperform some of the current techniques in terms of cost-effectiveness, speed, and power-efficiency.
Longest Prefix Matching Using Bloom Filters, Sarang Dharmapurikar, Praveen Krishnamurthy, David E. Taylor, to appear in IEEE Transactions on Networking.
Fast and Scalable Pattern Matching for Network Intrusion Detection Systems, Sarang Dharmapurikar, John Lockwood, to appear in IEEE JSAC Special Issue on Network Security.
Counter Braids: An Efficient Minimum-Space Statistics Counter Architecture Yi Lu, Sarang Dharmapurikar, Abdul Kader Kabbani, Andrea Montanari, Balaji Prabhakar to appear in the proceedings of ACM SIGMETRICS, June 2008
Fast Packet Classification Using Bloom Filters , Sarang Dharmapurikar, Haoyu Song, Jonathan Turner, John Lockwood ACM Symposim on Architectures for Networking and Communications Systems (ANCS), Dec 2006.
Packet Classification Using Coarse-grained Tuple Spaces , Haoyu Song, Jonathan Turner, Sarang Dharmapurikar ACM Symposim on Architectures for Networking and Communications Systems (ANCS), Dec 2006.
Rethinking Hardware Support for Network Analysis and Intrusion Prevention , Vern Paxson, Krste Asanovic, Sarang Dharmapurikar, John Lockwood, Ruoming Pang, Robin Sommer, Nick Weaver USENIX First Workshop on Hot Topics in Security (HotSec), July 31, 2006.
Algorithms to Accelerate Multiple Regular Expression Matching for Deep Packet Inspection , Sailesh Kumar, Sarang Dharmapurikar, Fang Yu, Patrick Crowley and Jonathan S. Turner, ACM SIGCOMM'06, Italy, September 12-15, 2006.
Fast and Scalable Pattern Matching for Content Filtering , Sarang Dharmapurikar, John Lockwood Proceedings of Symposium on Architectures for Networking and Communications Systems (ANCS), Oct 2005.
Optimizing Memory Bandwidth of a Multi-Channel Packet Buffer , Sarang Dharmapurikar, Sailesh Kumar, John Lockwood and Patrick Crowley, Proceedings of IEEE Globecom'05, St. Louis MO, Nov 2005.
Fast Hash Table Lookup Using Extended Bloom Filter: An Aid to Network Processing, Haoyu Song, Sarang Dharmapurikar, Jonathan Turner and John Lockwood, Proceedings of ACM SIGCOMM'05, Philadelphia PA, August 20-26, 2005.
Robust TCP Stream Reassembly in the Presence of Adversaries, Sarang Dharmapurikar, Vern Paxson, 14th USENIX Security Symposium, August 1-5, 2005, Baltimore, MD.
Longest Prefix Matching Using Bloom Filters, Sarang Dharmapurikar, Praveen Krishnamurthy, David E. Taylor, ACM SIGCOMM'03, August 25-29, 2003, Karlsruhe, Germany.
Deep Packet Inspection Using Parallel Bloom Filters, Sarang Dharmapurikar, Praveen Krishnamurthy, Todd Sproull, John W. Lockwood Symposium on High Performance Interconnects (HotI), Stanford, CA, USA, pp. 44-51, Aug. 20-22, 2003. This was also an invited paper in IEEE Micro Magazine. Here is a copy. Unfortunately, the analysis in these two documents was based on some weak and unjustified assumptions. Here is a document that provides more accurate analysis of the algorithm.
An Extensible, System-On-Programmable-Chip, Content-Aware Internet Firewall, John W. Lockwood, Christopher Neely, Christopher Zuver, James Moscola, Sarang Dharmapurikar, and David Lim; Field Programmable Logic and Applications (FPL), Lisbon, Portugal, Paper 14B, Sep 1-3, 2003.
System-on-Chip Packet Processor for an Experimental Network Services Platform , David Taylor, Alex Chandra, Yuhua Chen, Sarang Dharmapurikar, John Lockwood, Wenjing Tang, Jonathan Turner, IEEE Globecom, December 1-5, 2003, San Francisco, CA, USA.
Beyond Performance: Secure and Fair Memory Management for Multiple Systems on a Programmable Chip , Carlos Macián, Sarang Dharmapurikar, John Lockwood IEEE International Conference on Field-Programmable Technology (FPT'03), Tokyo, Japan, December 2003
Fast Packet Classification Using Bloom Filters, Sarang Dharmapurikar, Haoyu Song, Jonathan Turner, John Lockwood, WUCS-2006-27, May 12, 2006.
Design and Implementation of a String Matching System for Network Intrusion Detection using FPGA-based Bloom Filters, by Sarang Dharmapurikar, Michael Attig, John Lockwood, WUCSE-2004-12, March 25, 2004.
System-on-Chip Packet Processor for an Experimental Network Services Platform, by David Taylor, Alex Chandra, Yuhua Chen, Sarang Dharmapurikar, John Lockwood, Wenjing Tang, Jonathan Turner, WUCSE-2003-22, April 22, 2003.
Synthesizable Design of a Multi-Module Memory Controller, by Sarang Dharmapurikar and John Lockwood; Washington University, Department of Computer Science, Technical Report WUCS-01-26, October, 2001.
Generalized RAD Module Interface Specification of the Field Programmable Port Extender (FPX) Version 2.0 , David E. Taylor, John W. Lockwood, Sarang Dharmapurikar, WUCS-TM-01-15, 7/01.
Method and system for performing longest prefix matching for network address lookup using bloom filters (filed February 9, 2005)[United States Patent Application 20050195832]
Method and apparatus for detecting predefined signatures in packet payload using bloom filters (filed August 14, 2003) [United States Patent Application 20050086520]