Implementation and Comparison of Packet Classification
Modules: Hierarchical Trie, Set-Pruning Trie, Grid of Tries

Abstract

In a network, the Routers provide best possible services by handling or processing each incoming packet independently (i.e. in the same manner). The process of categorizing the packets into ‘flows’ in an internet router is called “packet classification”. All packets which belong to the same flow obey a predefined rule as mentioned in the forwarding table and are processed in the same manner by the router. For ex, all the packets which have same source and destination IP addresses are categorized to form a flow. Packet classification is required for non-best effort services that requires the routers to have the capability to identify and classify traffic in different flows for suitable processing. In general, packet classification on multiple fields is a difficult problem, so we have implemented basic classification algorithms in Python programming language by taking five fields as per which the packets will be classified. The five fields are source IP address, destination IP address, input and output port number and the transmission protocol. Then these algorithm files were executed in NOX (an open source software providing sophisticated network functionality). Then the performance of the three algorithms i.e. the time taken by the algorithms to classify each packet is calculated and compared. This is repeated for different number of packets varying in size and compared and it was found that the grid of tries has the best performance among the three algorithms. But, none of the three trie algorithms simultaneously avoids empty internal nodes and back tracking. This thesis proposes a new efficient packet classification algorithm using the set pruning trie approach. In the proposed algorithm, a hierarchical binary search tree is built for the pruned set of rules, which does not have empty internal nodes. Therefore, backtracking and empty internal nodes both are avoided by implementing the proposed algorithm. Simulation results prove that the proposed algorithm provides an improvement in search performance without increasing the memory requirement when compared with other existing trie based algorithms.