Scalable Packet Classification with Hash Tables

Pi-Chung WANG  

Publication
IEICE TRANSACTIONS on Communications   Vol.E93-B   No.5   pp.1155-1158
Publication Date: 2010/05/01
Online ISSN: 1745-1345
Print ISSN: 0916-8516
Type of Manuscript: Special Section LETTER (Special Section on Technology and Architecture for Sustainable Growth of the Internet)
Category: 
Keyword: 
packet classification,  packet forwarding,  firewalls,  network intrusion detection systems,  

Full Text: PDF(123.1KB)
>>Buy this Article


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.