Performance Improvement of Packet Classification for Enabling Differentiated Services

Pi-Chung WANG  

IEICE TRANSACTIONS on Communications   Vol.E93-B   No.6   pp.1403-1410
Publication Date: 2010/06/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E93.B.1403
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Section on Quality of Communication Networks and Services)
packet classification,  packet filtering,  quality of services,  firewalls,  next generation networks,  

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

In differentiated services, packet classification is used to categorize incoming packets into multiple forwarding classes based on pre-defined filters and make information accessible for quality of service. Although numerous algorithms have presented novel data structures to improve the search performance of packet classification, the performance of these algorithms are usually limited by the characteristics of filter databases. In this paper, we use a different approach of filter preprocessing to enhance the search performance of packet classification. Before generating the searchable data structures, we cluster filters in a bottom-up manner. The procedure of the filter clustering merges filters with high degrees of similarity. The experimental results show that the technique of filter clustering could significantly improve the search performance of Pruned Tuple Space Search, a notable hash-based algorithm. As compared to the prominent existing algorithms, our enhanced Pruned Tuple Space Search also has superior performance in terms of speed and space.