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

Efficient packet classification technique for IP address set filtering

作　　者：乔龙飞[1] 刘剑英 郑建生[1] 

机构地区：[1]武汉大学卫星导航定位技术研究中心,武汉430079 [2]北京极科极客科技有限公司,北京100000

出　　处：《计算机应用》2015年第A01期22-24,28,共4页journal of Computer Applications

摘　　要：针对传统防火墙线性匹配算法匹配效率低、维护困难等问题,提出并实现了一种面向IP地址集过滤的高效、灵活的Netfilter扩展框架Salist。Salist包含一个基于内核虚拟文件的表管理模块,一个可自动对IP地址集进行去重、归并和排序的表内规则管理模块,一个基于Bsearch算法的高效的包匹配模块。通过理论分析和实际测试证明,Salist使包匹配算法时间复杂度由传统线性匹配的O(n)降低为O(log n),规则合并减少了规则表占用的内核内存空间10%以上,按文件分离的规则管理机制简化了对规则集进行维护的难度。结果表明Salist使用在核心网络设备中可极大提高包转发速率,降低规则的内存占用和管理难度。Traditional network firewall uses a linear package matching algorithm which is very inefficient, and it”s also very difficult to manage complex rules and tables. To improve this, this paper designed and implemented a Netfilter extension framework called Salist （ simple address list） . Salist contains a table management module based on kernel virtual file system, a rule management module that can automatically merge and sort rules in tables and an efficient packet matching module based on Bsearch algorithm. The time complexity of the packet matching algorithm declines to O （ log n ） from O （ n ） . The kernel memory space to store the rules reduces by at lease 10 percent. The management of the rules is much easier because rules are stored in different files in kernel space. The results show that the Salist framework can substantially improve the network packet forwarding speed.

关 键 词：网络防火墙 NETFILTER/IPTABLES 包匹配 Bsearch 

分 类 号：TP393.05[自动化与计算机技术—计算机应用技术] TP316.8[自动化与计算机技术—计算机科学与技术]