Technical Report Number
The continuous growth in the Internet’s size, the amount of data traﬃc, and the complexity of processing this traﬃc gives rise to new challenges in building high-performance network devices. One of the most fundamental tasks performed by these devices is searching the network data for predeﬁned keys. Address lookup, packet classiﬁcation, 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 eﬃcient algorithms are required. One of the most commonly used techniques for such searching operations is the Ternary Content Addressable Memory (TCAM). While TCAM can oﬀer very fast search speeds, it is costly and consumes a large amount of power. Hence, designing cost-eﬀective, power-eﬃcient, 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 ﬁlters. A Bloom ﬁlter 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 oﬀ-chip memory and their Bloom ﬁlter representations are kept in the on-chip memory. An item needs to be looked up in the oﬀ-chip table only when it is found in the on-chip Bloom ﬁlters. By ﬁltering the oﬀ-chip memory accesses in this fashion, the search operations can be signiﬁcantly accelerated. Our approach involves a unique combination of algorithmic and architectural techniques that outperform some of the current techniques in terms of cost-eﬀectiveness, speed, and power-eﬃciency.
Dharmapurikar, Sarang, "Algorithms and Architectures for Network Search Processors" Report Number: WUCS-2006-43 (2006). All Computer Science and Engineering Research.