对Linux系统中的iptables过滤模块的改进  

The Improvement of Iptables Filter Module in Linux Operating System

作　　者：陈鑫[1] 方宁[2] 沈金龙[2] 

机构地区：[1]南京邮电学院电子工程系,江苏南京210003 [2]南京邮电学院计算机科学与技术系,江苏南京210003

出　　处：《南京邮电学院学报（自然科学版）》2005年第2期91-94,共4页Journal of Nanjing University of Posts and Telecommunications

摘　　要：为了改善现有linux系统内核iptables模块在数据包过滤中线性匹配规则的效率。采用了散列表和动态平衡树来组织过滤表,提出了按照三层递进式的搜索规则,减少了原来的线性查找重复匹配的次数,改进了过滤效率,并确保原有功能不变。把A个IP地址、B个网络设备和C个协议规则的过滤表查找时间复杂度从O(A*B*C)降低到m*O(log2A)+n*O(B)+k*O(log2C),(m,n,k为系数因子)。通过适当增加数据结构,安排合理的搜索规则,在有限的系统开销内,可以提高数据包过滤的规则匹配效率。In this paper, the filter efficiency of iptables filter module in Linux kernel is analyzed. In order to improve the filter efficiency, new data structures are proposed including hash tables and height balanced trees.New three-layer incremental filter rules are propssed instead of linear matching rules foreduce the number of iterative matching.It guarantees that the original functions of iptables filter module remainun changed. In a system consisting of A IP addresses, B net devices and C protocols , matching time complexity decreases from O (A*B*C) to m*O(log_2A)+n*O(B)+k*O(log_2C)(m,n and k are coefficients).

关 键 词：LINUX IPTABLES 散列表 平衡树 

分 类 号：TP316.89[自动化与计算机技术—计算机软件与理论]