Tuple pruning using bloom filters for packet classification

Hyesook Lim; So Yeon Kim

doi:10.1109/MM.2010.44

Tuple pruning using bloom filters for packet classification

Hyesook Lim, So Yeon Kim

Electronic and Electrical Engineering

Research output: Contribution to journal › Article › peer-review

35 Scopus citations

Abstract

Tuple pruning for packet classification provides fast search and a low implementation complexity. The tuple pruning algorithm reduces the search space to a subset of tuples determined by individual field lookups that cause off-chip memory accesses. The authors propose a tuple-pruning algorithm that reduces the search space through Bloom filter queries, which do not require off-chip memory accesses.

Original language	English
Article number	5467010
Pages (from-to)	48-58
Number of pages	11
Journal	IEEE Micro
Volume	30
Issue number	3
DOIs	https://doi.org/10.1109/MM.2010.44
State	Published - May 2010

Bibliographical note

Funding Information:
This work was supported by the National Research Foundation of Korea (NRF) through a grant funded by the Korean government (2010-0000483) and by the Korean Ministry of Knowledge Economy under the HNRC-ITRC support program supervised by the NIPA (NIPA-2010-C1090-1011-0010).

Keywords

Bloom filter
hardware
packet classification
tuple pruning
tuple space search

Access to Document

10.1109/MM.2010.44

Cite this

@article{4b5c92b4ea4446aa9f45871d49025c3e,

title = "Tuple pruning using bloom filters for packet classification",

abstract = "Tuple pruning for packet classification provides fast search and a low implementation complexity. The tuple pruning algorithm reduces the search space to a subset of tuples determined by individual field lookups that cause off-chip memory accesses. The authors propose a tuple-pruning algorithm that reduces the search space through Bloom filter queries, which do not require off-chip memory accesses.",

keywords = "Bloom filter, hardware, packet classification, tuple pruning, tuple space search",

author = "Hyesook Lim and Kim, {So Yeon}",

note = "Funding Information: This work was supported by the National Research Foundation of Korea (NRF) through a grant funded by the Korean government (2010-0000483) and by the Korean Ministry of Knowledge Economy under the HNRC-ITRC support program supervised by the NIPA (NIPA-2010-C1090-1011-0010).",

year = "2010",

month = may,

doi = "10.1109/MM.2010.44",

language = "English",

volume = "30",

pages = "48--58",

journal = "IEEE Micro",

issn = "0272-1732",

publisher = "IEEE Computer Society",

number = "3",

}

TY - JOUR

T1 - Tuple pruning using bloom filters for packet classification

AU - Lim, Hyesook

AU - Kim, So Yeon

N1 - Funding Information: This work was supported by the National Research Foundation of Korea (NRF) through a grant funded by the Korean government (2010-0000483) and by the Korean Ministry of Knowledge Economy under the HNRC-ITRC support program supervised by the NIPA (NIPA-2010-C1090-1011-0010).

PY - 2010/5

Y1 - 2010/5

N2 - Tuple pruning for packet classification provides fast search and a low implementation complexity. The tuple pruning algorithm reduces the search space to a subset of tuples determined by individual field lookups that cause off-chip memory accesses. The authors propose a tuple-pruning algorithm that reduces the search space through Bloom filter queries, which do not require off-chip memory accesses.

AB - Tuple pruning for packet classification provides fast search and a low implementation complexity. The tuple pruning algorithm reduces the search space to a subset of tuples determined by individual field lookups that cause off-chip memory accesses. The authors propose a tuple-pruning algorithm that reduces the search space through Bloom filter queries, which do not require off-chip memory accesses.

KW - Bloom filter

KW - hardware

KW - packet classification

KW - tuple pruning

KW - tuple space search

UR - http://www.scopus.com/inward/record.url?scp=77954613180&partnerID=8YFLogxK

U2 - 10.1109/MM.2010.44

DO - 10.1109/MM.2010.44

M3 - Article

AN - SCOPUS:77954613180

SN - 0272-1732

VL - 30

SP - 48

EP - 58

JO - IEEE Micro

JF - IEEE Micro

IS - 3

M1 - 5467010

ER -

Tuple pruning using bloom filters for packet classification

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this