|
规则一规则二合并之后 图5合并算法图解 Algorithm SortAndMergeRules( user_data, RuleList) 1: for each rule e ParseLine( user_data) do 2: if IsValidRule( rule) and not Exsist(rule, RuleList) do 3: ListInsertAfter( rule, RuleList) 4: end if 5 : end for 6: / / sort 7: HeapSort( RuleList, RuleList -> len, RuleCompare, RuleSwap) 8: / / merge 9: len = RuleList - > len 10: for wi o<- 0 , ri o<- 1; ri < ; ri ++ then 11: if RuleList [ri]. start <= RuleList [wi]. end + 1 then 12: if RuleList [ri]. end > RuleList [wi]. end then 13: RuleList [wi]. end = RuleList [ri]. end 14 : end if 15 : else 16: wi + + 17 : if wi < ri then 18: od -> tmp_base[wi] = od -> tmp_base[ri] 19 : end if 20: end if 21 : end for 22: RuleList - > len = wi + 1 23: FreeExtraMem( RuleList) sort算法采用堆排序，其时间复杂度为O(n log n),相对 于基于递归的快速排序其消耗更少的内存，因此更加适合在 内核中使用。 3.1.4Netfilter扩展match模块 模块初始化时同时注册了match模块，核心内容为包匹配函数match()。针对已排序的规则表，采用binarysearch(二分法检索），其时间复杂度为O(logn),可大大提高搜索的效率。 3.2用户态程序设计 在内核中加入match模块后，为了在用户空间使用Iptables对其进行配置，需要编写一个用户态的共享库来提供相关的命令行选项。共享库的」mt()函数在装载时被自动调用，它调用xtables_register_match()函数注册了相关的命令行接口，用户态共享库提供了如下命令行选项： "salist<table>$选择匹配的规则表 #[!]--match-sip$[不]匹配源IP #[!]--match-dip$[不]匹配目的IP iptables-tnat-Atest-msalist--salistchina--match-dip-jRETURN 该规则为，所有目的地址为中国的报文，直接返回，不再经过下面的规则过滤。可用于对国内外流量进行分流。 4性能分析及测试 4.1内存占用分析 从亚太互联网络信息中心（Asia~PacificNetworkInformationCentre,APNIC)的网站上分别获取到的中国大陆以及多家运营商的IP地址列表，经过Salist模块归并处理，结果 见表1。 表1中国及各运营商IP地址段 IP地址段归属 原始IP地址段 归并后IP地址段 条目减少/% 中国 3 808 2 200 42.22 电信 975 738 24.31 联通 849 613 27.80 cmcc 40 36 10. 00 教育网 89 70 21.35 分析以上数据可知，采用Salist之后,IP地址段数量大大减少，假定每条规则所占用的空间相同，Salist中每条规则占用的空间小于普通的Iptables规则），其占用内存数量至少可节约10%以上，条目数量越多，节约空间也越多。4.2匹配速率分析传统的线性匹配算法时间复杂为O(n),匹配n条规则平均所需要的匹配次数为（n+1)/2,Salist中规则表经过排序，采用Bsearch二分查找算法,算法的时间复杂度为O(logn)，匹配n条规则所需的平均次数约为lg(n+1)-1。 对表1数据进行分析，在不考虑归并后条目减少的情况下，匹配次数如表2。 表2匹配次数比较 IP 地址段 归属 顺序查找平均 匹配次数 二分查找 平均查找次数 中国 1904 11 电信 488 8 联通 425 9 cmcc 20 5 教育网 45 6 由以上数据可以看出，规则集条目越多的情况下，采用 Salist匹配所需时间相对大大减少。 5结语 包分类算法已得到了广泛研究和应用，但并没有一个能同时支持大规模规则集、多域、通用、动态更新的高速算法，各种方案都有其优缺点。本方案针对IP地址段进行匹配处理的情况，设计了一个包含规则表管理，Netfilter扩展match模块以及相关的配置库在内的一系列工具，实现了一个高效、灵活的包分类模块。该方案匹配速度快，空间效率高，规则更新复杂度适中，按文件分离的规则表管理机制也降低了对规则集进行维护的难度，通过读写文件更新规则的机制使其便于同其他模块配合使用。 本系统已经成功应用于多种业务场景，比如针对不通网络运营商的负载均衡，国内外IP的快速定位处理，同时因为其方便灵活的规则添加机制，配合域名解析工具，实现了高效的基于域名的包分流模块，而且非常容易同其他系统配合，满足各种复杂的需求。 参考文献： [1]BELLOVINSM，CHESWICKWR.Networkfirewalls[J].IEEECommunicationsMagazine，1994，32(9):50-57. [2]GUPTAP，McKEOWNN.Algorithmsforpacketclassification[J].IEEENetwork:TheMagazineofGlobalInternetworking，2001，15(2):24-32. [3]GUPTAP，McKEOWNN.Dynamicrule-orderingoptimizationfor high-speedfirewallfiltering[C]//ASIACCS106:Proceedingsofthe2006ACMSymposiumonInformation，ComputerandCommunicationsSecu^ty.NewYork:ACM，2006:332-342. [4]周东浩，王勇军.防火墙扩展match模块匹配算法优化[J].计算机工程与设计，2011,32(3):766-769. [5]KATICT，PALEP.Optimizationoffirewallrules[C]//ITI2007:Proceedingsofthe200729thIEEEInternationalConferenceonInformationTechnologyInterfaces.Piscataway:IEEE，2007:685-690. [6]FULPEW.Optimizationofnetworkfirewallpoliciesusingorderedsetsanddirectedacyclicalgraphs[C]//Proceedingsofthe2005IEEEInternetManagementConference.Piscataway:IEEE，2005:1-12. [7]SONUNEG，DANGEA.Optimizationoffirewall[J].JournalofEngineeringComputers&AppliedSciences，2013，2(7):38-42. |
|
核心期刊网（www.hexinqk.com）秉承“诚以为基，信以为本”的宗旨，为广大学者老师提供投稿辅导、写作指导、核心期刊推荐等服务。 核心期刊网专业期刊发表机构，为学术研究工作者解决北大核心、CSSCI核心、统计源核心、EI核心等投稿辅导咨询与写作指导的问题。 投稿辅导咨询电话：18915033935 投稿辅导客服QQ： 投稿辅导投稿邮箱：1003158336@qq.com |
| 你好，欢迎来到！ 设为首页 ｜收藏本站 | ||
|
