A Cache Architecture for Counting Bloom Filters: Theory and Application
Within packet processing systems, lengthy memory accesses greatly reduce performance. To overcome this limitation, network processors utilize many different techniques, for example, utilizing multilevel memory hierarchies, special hardware architectures, and hardware threading. In this paper, we int...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2011-01-01
|
| Series: | Journal of Electrical and Computer Engineering |
| Online Access: | http://dx.doi.org/10.1155/2011/475865 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832567840011452416 |
|---|---|
| author | Mahmood Ahmadi Stephan Wong |
| author_facet | Mahmood Ahmadi Stephan Wong |
| author_sort | Mahmood Ahmadi |
| collection | DOAJ |
| description | Within packet processing systems, lengthy memory accesses greatly reduce performance. To overcome this limitation, network processors utilize many different techniques, for example, utilizing multilevel memory hierarchies, special hardware architectures, and hardware threading. In this paper, we introduce a multilevel memory architecture for counting Bloom filters. Based on the probabilities of incrementing of the counters in the counting Bloom filter, a multi-level cache architecture called the cached counting Bloom filter (CCBF) is presented, where each cache level stores the items with the same counters. To test the CCBF architecture, we implement a software packet classifier that utilizes basic tuple space search using a 3-level CCBF. The results of mathematical analysis and implementation of the CCBF for packet classification show that the proposed cache architecture decreases the number of memory accesses when compared to a standard Bloom filter. Based on the mathematical analysis of CCBF, the number of accesses is decreased by at least 53%. The implementation results of the software packet classifier are at most 7.8% (3.5% in average) less than corresponding mathematical analysis results. This difference is due to some parameters in the packet classification application such as number of tuples, distribution of rules through the tuples, and utilized hashing functions. |
| format | Article |
| id | doaj-art-fe15ed5b76b44cfdaba4f3311b36f84b |
| institution | Kabale University |
| issn | 2090-0147 2090-0155 |
| language | English |
| publishDate | 2011-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Electrical and Computer Engineering |
| spelling | doaj-art-fe15ed5b76b44cfdaba4f3311b36f84b2025-02-03T01:00:31ZengWileyJournal of Electrical and Computer Engineering2090-01472090-01552011-01-01201110.1155/2011/475865475865A Cache Architecture for Counting Bloom Filters: Theory and ApplicationMahmood Ahmadi0Stephan Wong1Computer Engineering Laboratory, Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, 2600 AA Delft, The NetherlandsComputer Engineering Laboratory, Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, 2600 AA Delft, The NetherlandsWithin packet processing systems, lengthy memory accesses greatly reduce performance. To overcome this limitation, network processors utilize many different techniques, for example, utilizing multilevel memory hierarchies, special hardware architectures, and hardware threading. In this paper, we introduce a multilevel memory architecture for counting Bloom filters. Based on the probabilities of incrementing of the counters in the counting Bloom filter, a multi-level cache architecture called the cached counting Bloom filter (CCBF) is presented, where each cache level stores the items with the same counters. To test the CCBF architecture, we implement a software packet classifier that utilizes basic tuple space search using a 3-level CCBF. The results of mathematical analysis and implementation of the CCBF for packet classification show that the proposed cache architecture decreases the number of memory accesses when compared to a standard Bloom filter. Based on the mathematical analysis of CCBF, the number of accesses is decreased by at least 53%. The implementation results of the software packet classifier are at most 7.8% (3.5% in average) less than corresponding mathematical analysis results. This difference is due to some parameters in the packet classification application such as number of tuples, distribution of rules through the tuples, and utilized hashing functions.http://dx.doi.org/10.1155/2011/475865 |
| spellingShingle | Mahmood Ahmadi Stephan Wong A Cache Architecture for Counting Bloom Filters: Theory and Application Journal of Electrical and Computer Engineering |
| title | A Cache Architecture for Counting Bloom Filters: Theory and Application |
| title_full | A Cache Architecture for Counting Bloom Filters: Theory and Application |
| title_fullStr | A Cache Architecture for Counting Bloom Filters: Theory and Application |
| title_full_unstemmed | A Cache Architecture for Counting Bloom Filters: Theory and Application |
| title_short | A Cache Architecture for Counting Bloom Filters: Theory and Application |
| title_sort | cache architecture for counting bloom filters theory and application |
| url | http://dx.doi.org/10.1155/2011/475865 |
| work_keys_str_mv | AT mahmoodahmadi acachearchitectureforcountingbloomfilterstheoryandapplication AT stephanwong acachearchitectureforcountingbloomfilterstheoryandapplication AT mahmoodahmadi cachearchitectureforcountingbloomfilterstheoryandapplication AT stephanwong cachearchitectureforcountingbloomfilterstheoryandapplication |