基于多核NPU的多线程报文分类算法

摘要

Packet classification in firewalls, routers and other devices has important applications. In this paper, considering the performance problems of the traditional method in packet classification application, a multi-thread algorithm MCN-EGT is proposed based on the EGT （Extended Grid of Trie） algorithm. It distributes rules over multiple classification trees, so that each of them becomes smaller; the classification will be distributed to different trees in parallel. When rules updates, in most cases not all the trees should be renewed, which saves time. Experiments show that the performance of MCN-EGT algorithm is about 2-3 times better than the EGT algorithm based on high-performance CPU.%报文分类技术在防火墙、路由器等设备中有重要的作用。本文针对传统报文分类方法在应用中存在的性能问题，在EGT（Extended Gridof Trie）算法的基础上，提出了一种基于多核NPU的多线程报文分类方法MCN—EGT，它将规则分散建立在多个分类树上，从而使每棵分类树的规模较小；在分类时将不同的报文分散到多棵分类树上并行查找，同时在规则更新时一般不用更新所有的分类树，节约了规则更新的时间。实验表明该方法比现有基于高性能CPU的EGT算法性能提高2—3倍。