Scalable Packet Classification For Multi-core Platforms

Nowadays, networks are required to provide more, faster and safer services than ever before. The diversity of services is based on packet classification, by which network packets are classified into different flows in accordance with the relevant fields in their headers (in general source/destination IP address, source/destination port number and protocol). And then corresponding processing is imposed to packets belonging to different flows. Packet classification has become an important and supportive networking technology.As line-rate and network traffic continues to rise, packet classification has become a performance bottleneck to high-speed network processing. At present, whether hardware or software-based schemes could not meet the demand of high-speed packet processing. Hardware-based schemes can provide considerably high classifying rate, but do not have the flexibility of dynamic classification requirements. On the other hand, software-based ones are more flexible but unable to meet the requirements of high line-rate. Multi-core creates a new way to achieve the efficient and flexible packet classification, because with rising computing ability of multi-core, schemes can accomplish classifying rate closed to hardware-based as well as flexibility. However, parallel programming on multi-core remains a tough problem. There are still numbers of issues need to be addressed on how to design scalable parallel algorithms.This thesis mainly includes two parts. In the first part, in the view that existing parallel speedup models fail to explain phenomena of super-linear speedup and system efficiency degradation on shared memory multi-core architectures, a workload-differentiated parallel speedup model is presented. The improved model divides the system workload into computational workload and memory access workload, and explicitly introduces memory access influence into speedup. It theoretically explains both super-linear speedup and degradation of parallel system efficiency. And validity of the speedup model is checked by a set of simulation experiments. Several rules for optimized parallel algorithm design on multi-core are summarized according to the speedup model, and afterward these rules are applied as optimization guidance to design and implementation of scalable parallel packet classification. The second part includes the design and implementation of a high-speed packet classification algorithm, TIC (Two-stage Interpreting based Classification), based on multi-core platforms. Exploiting the characteristics of classifiers and multi-core architectures, TIC divides five-tuple packet classification process into two stages: (1) searching prefixes composed from the source/destination address; (2) a list of range matching made from the source/destination port number and protocol. The second stage adopts interpreting based range matching, which greatly reduces the memory overhead and avail itself of adequate computing ability on multi-core. In essence, TIC achieves the best tradeoff between time and space complexity by balancing workload of computation and memory access, which ensures that the TIC algorithm has good scalability on multi-core architectures. In the platforms of IXP2800 NPU and X86 architecture-based quad-core Xeon5410, TIC algorithm's classifying rate is able to meet OC-192 (10Gbps) line-rate level. Furthermore, TIC has the speed that is close to or higher than current fastest software-based algorithm, and the memory requirement and preprocessing time are greatly reduced.