IEICE TRANSACTIONS on Communications
Scalable Packet Classification with Hash Tables
Summary :
In the last decade, the technique of packet classification has been widely deployed in various network devices, including routers, firewalls and network intrusion detection systems. In this work, we improve the performance of packet classification by using multiple hash tables. The existing hash-based algorithms have superior scalability with respect to the required space; however, their search performance may not be comparable to other algorithms. To improve the search performance, we propose a tuple reordering algorithm to minimize the number of accessed hash tables with the aid of bitmaps. We also use pre-computation to ensure the accuracy of our search procedure. Performance evaluation based on both real and synthetic filter databases shows that our scheme is effective and scalable and the pre-computation cost is moderate.
- Publication
- IEICE TRANSACTIONS on Communications Vol.E93-B No.5 pp.1155-1158
- Publication Date
- 2010/05/01
- Publicized
- Online ISSN
- 1745-1345
- DOI
- 10.1587/transcom.E93.B.1155
- Type of Manuscript
- Special Section LETTER (Special Section on Technology and Architecture for Sustainable Growth of the Internet)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Pi-Chung WANG, "Scalable Packet Classification with Hash Tables" in IEICE TRANSACTIONS on Communications,
vol. E93-B, no. 5, pp. 1155-1158, May 2010, doi: 10.1587/transcom.E93.B.1155.
Abstract: In the last decade, the technique of packet classification has been widely deployed in various network devices, including routers, firewalls and network intrusion detection systems. In this work, we improve the performance of packet classification by using multiple hash tables. The existing hash-based algorithms have superior scalability with respect to the required space; however, their search performance may not be comparable to other algorithms. To improve the search performance, we propose a tuple reordering algorithm to minimize the number of accessed hash tables with the aid of bitmaps. We also use pre-computation to ensure the accuracy of our search procedure. Performance evaluation based on both real and synthetic filter databases shows that our scheme is effective and scalable and the pre-computation cost is moderate.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.E93.B.1155/_p
Copy
@ARTICLE{e93-b_5_1155,
author={Pi-Chung WANG, },
journal={IEICE TRANSACTIONS on Communications},
title={Scalable Packet Classification with Hash Tables},
year={2010},
volume={E93-B},
number={5},
pages={1155-1158},
abstract={In the last decade, the technique of packet classification has been widely deployed in various network devices, including routers, firewalls and network intrusion detection systems. In this work, we improve the performance of packet classification by using multiple hash tables. The existing hash-based algorithms have superior scalability with respect to the required space; however, their search performance may not be comparable to other algorithms. To improve the search performance, we propose a tuple reordering algorithm to minimize the number of accessed hash tables with the aid of bitmaps. We also use pre-computation to ensure the accuracy of our search procedure. Performance evaluation based on both real and synthetic filter databases shows that our scheme is effective and scalable and the pre-computation cost is moderate.},
keywords={},
doi={10.1587/transcom.E93.B.1155},
ISSN={1745-1345},
month={May},}
Copy
TY - JOUR
TI - Scalable Packet Classification with Hash Tables
T2 - IEICE TRANSACTIONS on Communications
SP - 1155
EP - 1158
AU - Pi-Chung WANG
PY - 2010
DO - 10.1587/transcom.E93.B.1155
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E93-B
IS - 5
JA - IEICE TRANSACTIONS on Communications
Y1 - May 2010
AB - In the last decade, the technique of packet classification has been widely deployed in various network devices, including routers, firewalls and network intrusion detection systems. In this work, we improve the performance of packet classification by using multiple hash tables. The existing hash-based algorithms have superior scalability with respect to the required space; however, their search performance may not be comparable to other algorithms. To improve the search performance, we propose a tuple reordering algorithm to minimize the number of accessed hash tables with the aid of bitmaps. We also use pre-computation to ensure the accuracy of our search procedure. Performance evaluation based on both real and synthetic filter databases shows that our scheme is effective and scalable and the pre-computation cost is moderate.
ER -
English
