面向IP地址集过滤的高效包分类技术

摘要

针对传统防火墙线性匹配算法匹配效率低、维护困难等问题，提出并实现了一种面向IP地址集过滤的高效、灵活的Netfilter扩展框架Salist。 Salist包含一个基于内核虚拟文件的表管理模块，一个可自动对IP地址集进行去重、归并和排序的表内规则管理模块，一个基于Bsearch算法的高效的包匹配模块。通过理论分析和实际测试证明， Salist使包匹配算法时间复杂度由传统线性匹配的O( n)降低为O( log n)，规则合并减少了规则表占用的内核内存空间10%以上，按文件分离的规则管理机制简化了对规则集进行维护的难度。结果表明Salist使用在核心网络设备中可极大提高包转发速率，降低规则的内存占用和管理难度。