Packet classification using a bloom filter in a leaf-pushing area-based quad-trie

Hyesook Lim; Ha Young Byun

doi:10.1109/ANCS.2015.7110131

Packet classification using a bloom filter in a leaf-pushing area-based quad-trie

Hyesook Lim, Ha Young Byun

Electronic and Electrical Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Scopus citations

Abstract

Packet classification is one of the most essential functions that Internet routers should perform at wire-speed for every incoming packet. An area-based quad-trie (AQT) for packet classification has an issue in search performance since many rule nodes can be encountered in a search procedure. A leaf-pushing AQT improves the search performance of the AQT by making a single rule node exist in each search path. This paper proposes a new algorithm to improve the search performance of the leaf-pushing AQT further. The proposed algorithm builds a leaf-pushing AQT using a Bloom filter and a hash table stored in on-chip memories. The level of a rule node and a pointer to a rule database are identified by sequentially querying the Bloom filter and by accessing the hash table, respectively.

Original language	English
Title of host publication	ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	183-184
Number of pages	2
ISBN (Electronic)	9781467366335
DOIs	https://doi.org/10.1109/ANCS.2015.7110131
State	Published - 18 May 2015
Event	11th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2015 - Oakland, United States Duration: 7 May 2015 → 8 May 2015

Publication series

Name	ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems

Conference

Conference	11th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2015
Country/Territory	United States
City	Oakland
Period	7/05/15 → 8/05/15

Bibliographical note

Publisher Copyright:
© 2015 IEEE.

Keywords

area-based quad-trie
Bloom filter
leaf-pushing
packet classification

Access to Document

10.1109/ANCS.2015.7110131

Cite this

Lim, H., & Byun, H. Y. (2015). Packet classification using a bloom filter in a leaf-pushing area-based quad-trie. In ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems (pp. 183-184). Article 7110131 (ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ANCS.2015.7110131

Lim, Hyesook ; Byun, Ha Young. / Packet classification using a bloom filter in a leaf-pushing area-based quad-trie. ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems. Institute of Electrical and Electronics Engineers Inc., 2015. pp. 183-184 (ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems).

@inproceedings{9faa3ab814974c18b7d8d163c5047547,

title = "Packet classification using a bloom filter in a leaf-pushing area-based quad-trie",

abstract = "Packet classification is one of the most essential functions that Internet routers should perform at wire-speed for every incoming packet. An area-based quad-trie (AQT) for packet classification has an issue in search performance since many rule nodes can be encountered in a search procedure. A leaf-pushing AQT improves the search performance of the AQT by making a single rule node exist in each search path. This paper proposes a new algorithm to improve the search performance of the leaf-pushing AQT further. The proposed algorithm builds a leaf-pushing AQT using a Bloom filter and a hash table stored in on-chip memories. The level of a rule node and a pointer to a rule database are identified by sequentially querying the Bloom filter and by accessing the hash table, respectively.",

keywords = "area-based quad-trie, Bloom filter, leaf-pushing, packet classification",

author = "Hyesook Lim and Byun, {Ha Young}",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 11th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2015 ; Conference date: 07-05-2015 Through 08-05-2015",

year = "2015",

month = may,

day = "18",

doi = "10.1109/ANCS.2015.7110131",

language = "English",

series = "ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "183--184",

booktitle = "ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems",

}

Lim, H & Byun, HY 2015, Packet classification using a bloom filter in a leaf-pushing area-based quad-trie. in ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems., 7110131, ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems, Institute of Electrical and Electronics Engineers Inc., pp. 183-184, 11th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2015, Oakland, United States, 7/05/15. https://doi.org/10.1109/ANCS.2015.7110131

Packet classification using a bloom filter in a leaf-pushing area-based quad-trie. / Lim, Hyesook; Byun, Ha Young.
ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems. Institute of Electrical and Electronics Engineers Inc., 2015. p. 183-184 7110131 (ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Packet classification using a bloom filter in a leaf-pushing area-based quad-trie

AU - Lim, Hyesook

AU - Byun, Ha Young

PY - 2015/5/18

Y1 - 2015/5/18

N2 - Packet classification is one of the most essential functions that Internet routers should perform at wire-speed for every incoming packet. An area-based quad-trie (AQT) for packet classification has an issue in search performance since many rule nodes can be encountered in a search procedure. A leaf-pushing AQT improves the search performance of the AQT by making a single rule node exist in each search path. This paper proposes a new algorithm to improve the search performance of the leaf-pushing AQT further. The proposed algorithm builds a leaf-pushing AQT using a Bloom filter and a hash table stored in on-chip memories. The level of a rule node and a pointer to a rule database are identified by sequentially querying the Bloom filter and by accessing the hash table, respectively.

AB - Packet classification is one of the most essential functions that Internet routers should perform at wire-speed for every incoming packet. An area-based quad-trie (AQT) for packet classification has an issue in search performance since many rule nodes can be encountered in a search procedure. A leaf-pushing AQT improves the search performance of the AQT by making a single rule node exist in each search path. This paper proposes a new algorithm to improve the search performance of the leaf-pushing AQT further. The proposed algorithm builds a leaf-pushing AQT using a Bloom filter and a hash table stored in on-chip memories. The level of a rule node and a pointer to a rule database are identified by sequentially querying the Bloom filter and by accessing the hash table, respectively.

KW - area-based quad-trie

KW - Bloom filter

KW - leaf-pushing

KW - packet classification

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

U2 - 10.1109/ANCS.2015.7110131

DO - 10.1109/ANCS.2015.7110131

M3 - Conference contribution

AN - SCOPUS:84936091231

T3 - ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems

SP - 183

EP - 184

BT - ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 11th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2015

Y2 - 7 May 2015 through 8 May 2015

ER -

Lim H, Byun HY. Packet classification using a bloom filter in a leaf-pushing area-based quad-trie. In ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems. Institute of Electrical and Electronics Engineers Inc. 2015. p. 183-184. 7110131. (ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems). doi: 10.1109/ANCS.2015.7110131

Packet classification using a bloom filter in a leaf-pushing area-based quad-trie

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this