A Hybrid Approach to Packet Classification

概要

論文の詳細を見る
Packet classification is one of the key technologies to support differentiated services to classified flows. Combining the top-down lookup tree structure and intelligent constructing strategy of present algorithms, this paper proposes a hybrid approach to packet classification. The filter set, which is used to classify packets, are stored in the leaf chains of a special data structure, in which an index table acts as index to locate several lookup trees. Also, an evaluation formula shows the major criteria on how to build lookup trees and distribute filters to obtain satisfactory efficiency. The performance of the proposed algorithm is discussed by analytical computation and simulation. Theoretically, it has a logarithmic execution time cost with a polynomial space (storage) cost. Further, a simulation of packet classifier built on IBM Power Network Processor is performed to test its performance and do a comparison between multi-tree applied cases and the unapplied. The results show its superiority in complex filter handling and matching modes.
国立情報学研究所の論文
2004-02-27