Project Summary

Recent advances in networking, databases, and Internet applications have resulted in several important trends. Advanced network hardware has emerged to ensure the fast and efficient routing of messages. The increasing sizes of data have led to the development of sophisticated one-pass data stream management algorithms by the database community. Network attacks, spam, Distributed Denial of Service attacks, and Internet fraud in general are now recognized as major problems for diverse internet applications. The confluence of these trends motivates the research in this proposal, which intends to solve some of these internet problems using data streams algorithms implemented on advanced network hardware. In particular, we propose to develop data stream algorithms that are specifically designed for network processors units (NPU) that are integrated with content addressable memories. Given the ubiquitous availability of NPUs, the proposed approach will have the potential for use in the on-line analytical processing of message flows as well as in the identification of network attacks and fraud. The proposed research is high risk since it involves the integration of specialized hardware and software components from different vendors, including Intel for the NPU, IDT or NetLogic for the content addressable memories, and Monta Vista and Teja for the operating systems. This integration process is fraught with risks given the need for one-on-one communication with the support personnel of the different vendors to successfully integrate these novel computing platforms. However, the research will have high impact since, if successful, it will lay the foundations for the widespread use of efficient hardware devices throughout the internet for the detection of spam, fraud and DDoS, as well as enable data-centric analysis of network traffic for the networks of the future.

Principal Investigator

• Amr El Abbadi

Collaborator

• Divyakant Agrawal

Graduate Student Researcher

• Sudipto Das
• Shyam Antony

Acknowledgement

This work was supported by NSF award IIS-0744539 SGER: Leveraging Advanced Hardware for Streaming Applications

Publications

• Sudipto Das, Divyakant Agrawal, Amr El Abbadi, CAM Conscious Integrated Answering of Frequent Elements and Top-k Queries over Data Streams, 4th International Workshop on Data Management on New Hardware, DaMoN 2008, in conjunction with SIGMOD/PODS 2008, pages 1 - 10.
  Abstract, Paper
  
  Frequent elements and top-k queries constitute an important class of queries for data stream analysis applications. Certain applications require answers for both frequent elements and top-k queries on the same stream. In addition, the ever increasing data rates call for providing fast answers to the queries, and researchers have been looking towards exploiting specialized hardware for this purpose. Content Addressable Memory(CAM) provides an efficient way of looking up elements and hence are well suited for the class of algorithms that involve lookups. In this paper, we present a fast and efficient CAM conscious integrated solution for answering both frequent elements and top-k queries on the same stream. We call our scheme CAM conscious Space Saving with Stream Summary (CSSwSS), and it can efficiently answer continuous queries. We provide an implementation of the proposed scheme using commodity CAM chips, and the experimental evaluation demonstrates that not only does the proposed scheme outperforms existing CAM conscious techniques by an order of magnitude at query loads of about 10%, but the proposed scheme can also efficiently answer continuous queries.
• Sudipto Das, Shyam Antony, Divyakant Agrawal, Amr El Abbadi, CoTS: A Scalable Framework for Parallelizing Frequency Counting over Data Streams, UCSB CS Tecnical Report 2008-08, June 2008.
  Abstract, Paper
  
  Applications involving analysis of data streams have gained significant popularity and importance. Frequency counting, frequent elements and top-k queries form a class of operators that are used for a wide range of stream analysis applications. In spite of the abundance of these algorithms, all known techniques for answering data stream queries are sequential in nature. The imminent ubiquity of Chip Multi-Processor (CMP) architectures requires algorithms that can exploit the parallelism of such architectures. In this paper, we first explore the challenges in parallelizing frequent elements and top-k queries in the context of the inherent parallelism available in multi-core processors, evaluate different naive techniques for intra-operator parallelism, and summarize the insights obtained from the different parallelization efforts. Our experimental analysis of the naive designs implemented in the paper shows that intra-operator parallelism is not straightforward and requires a complete redesign of the system. Based on the lessons learnt from this analysis, we design an efficient and scalable framework for parallelizing frequency counting, frequent elements and top-k queries over data streams. The proposed CoTS (Co-operative Thread Scheduling) framework is based on the principle of threads co-operating rather than contending. Our experiments on a state-of-the-art quad-core chip multiprocessor architecture and synthetic data sets demonstrate the scalability of the proposed framework, and the efficiency is demonstrated by peak throughput of more that 60 million elements per second. In addition, for skewed data distributions, despite using heavy weight synchronization primitives, the implementation of the proposed framework outperforms the sequential implementation by a factor of 2 - 4X.
• Sudipto Das, Shyam Antony, Divyakant Agrawal, Amr El Abbadi, CoTS: A Scalable Framework for Parallelizing Frequency Counting over Data Streams, 25th International Conference on Data Engineering (ICDE 2009), Shanghai, China.
  Abstract, Paper
  
  Applications involving analysis of data streams have gained significant popularity and importance. Frequency counting, frequent elements and top-k queries form a class of operators that are used for a wide range of stream analysis applications. In spite of the abundance of these algorithms, all known techniques for answering data stream queries are sequential in nature. The imminent ubiquity of Chip Multi-Processor (CMP) architectures requires algorithms that can exploit the parallelism of such architectures. In this paper, we first explore the challenges in parallelizing frequent elements and top-k queries in the context of the inherent parallelism available in multi-core processors, evaluate different naive techniques for intra-operator parallelism, and summarize the insights obtained from the different parallelization efforts. Our experimental analysis of the naive designs implemented in the paper shows that intra-operator parallelism is not straightforward and requires a complete redesign of the system. Based on the lessons learnt from this analysis, we design an efficient and scalable framework for parallelizing frequency counting, frequent elements and top-k queries over data streams. The proposed CoTS (Co-operative Thread Scheduling) framework is based on the principle of threads co-operating rather than contending. Our experiments on a state-of-the-art quad-core chip multiprocessor architecture and synthetic data sets demonstrate the scalability of the proposed framework, and the efficiency is demonstrated by peak throughput of more that 60 million elements per second. In addition, for skewed data distributions, despite using heavy weight synchronization primitives, the implementation of the proposed framework outperforms the sequential implementation by a factor of 2 - 4X.

Related Links

• Euclid - Hardware Acceleration of Database Operations