For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Scalable Packet Classification with Hash Tables
IEICE TRANSACTIONS on Communications
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)
packet classification, packet forwarding, firewalls, network intrusion detection systems,
Full Text: PDF(123.1KB)>>
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.