Packet Classification Algorithms

This paper deals with packet classification in computernetworks. Classification is the key task in many networkingdevices, most notably packet filters – firewalls. Thispaper therefore concerns the area of computer security.The paper is focused on high-speed networks with thebandwidth of 100Gb/s and beyond. General-purpose processorscannot be used in such cases, because their performanceis not sufficient. Therefore, specialized hardwareis used, mainly ASICs and FPGAs. Many packet classificationalgorithms designed for hardware implementationwere presented, yet these approaches are not ready forvery high-speed networks. This paper addresses the designof new high-speed packet classification algorithms,targeted for the implementation in dedicated hardware.The algorithm that decomposes the problem into severaleasier sub-problems is proposed. The first subproblem isthe longest prefix match (LPM) operation, which is usedalso in IP packet routing. As the LPM algorithms withsufficient speed have already been published, they can beused in out context. The following subproblem is mappingthe prefixes to the rule numbers. This is where the paperbrings innovation by using a specifically constructedhash function. This hash function allows the mapping tobe done in constant time and requires only one memorywith narrow data bus. The algorithm throughput can bedetermined analytically and is independent on the numberof rules or the network traffic characteristics. Withthe use of available parts the throughput of 266 millionpackets per second can be achieved. Additional three algorithms(PFCA, PCCA, MSPCCA) that follow in thispaper are designed to lower the memory requirements ofthe first one without compromising the speed. The secondalgorithm lowers the memory size by 11% to 96 %,depending on the rule set. The disadvantage of low stabilityis removed by the third algorithm, which reduces the memory requirements by 31% to 84 %, compared tothe first one. The fourth algorithm combines the thirdone with the older approach and thanks to the use of severaltechniques lowers the memory requirements by 73%to 99 %.