论文投稿_医学论文投稿_核心期刊,职称论文投稿发表_论文部落

规则一规则二合并之后
图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.