Abstract: This paper analyzes the packet filtering technique based on Linux operating system. The packet filtering of Netfilter uses simple linearity graduation algorithm. When the firewall needs to match the number of rules, the performance of firewall falls suddenly, and it becomes the system bottleneck. Therefore, a new packet filtering algorithm based on binary tree and Hash function is proposed, that is B-H. Test proves that the algorithm can achieve the fast match in the massive rules, and enhance the performance of packet filtering greatly.

Key words: Linux operating system, Netfilter firewall, packet filtering, binary tree, Hash function

摘要： 通过对Linux操作系统下Netfilter防火墙中包过滤技术的分析，发现Netfilter包过滤使用简单的线性分级算法，当防火墙需要匹配的规则越来越多时，防火墙的性能会急剧下降，造成系统瓶颈。因此，提出一种基于二叉树和Hash函数的包过滤算法B-H。通过测试证明，该算法在大量规则的情况下能够达到快速匹配，有效地提高了包过滤的性能。

关键词: Linux操作系统, Netfilter防火墙, 包过滤, 二叉树, Hash函数

CLC Number: 

• TP301.6