Premium
Scalable packet classification using a compound algorithm
Author(s) -
Wang PiChung
Publication year - 2009
Publication title -
international journal of communication systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.344
H-Index - 49
eISSN - 1099-1131
pISSN - 1074-5351
DOI - 10.1002/dac.1085
Subject(s) - computer science , scalability , network packet , algorithm , filter (signal processing) , wire speed , quality of service , data mining , tuple , bloom filter , database , computer network , mathematics , discrete mathematics , computer vision
In next‐generation networks, 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 or security handling in the network. To pursue better search performance, numerous algorithms of packet classification have been proposed and optimized for certain filter databases; however, these algorithms may not scale in either storage or speed performance or both for the filter databases with different characteristics. This paper presents an efficient algorithm by combining two complementary algorithms, Cross‐producting and Pruned Tuple Space Search , to make packet classification both fast and scalable. Unlike the existing algorithms whose performance is contingent on the filter database attributes, our algorithm shows better scalability and feasibility. We evaluate the performance of our scheme with filter databases of varying sizes and characteristics. The experimental results demonstrate that the new algorithm improves the speed and storage performance simultaneously. We also introduce the procedure of incremental updates. Copyright © 2009 John Wiley & Sons, Ltd.