快速过滤算法在手机上网加速网络中的研究

申江云

【摘要】 传统的包过滤技术一般是由多个过滤规则组成，这些规则在网络设备内被有序地组织起来形成一个链表。当使用访问控制列表来处理数据包时，网络设备顺序地查找该链表以发现匹配地条目。被匹配的条目用来决定对数据包的处理，在线性的查找过程中，平均查找时间与规则的大小成正比。传统的算法在处理手机上网加速网络海量数据小包时，存在处理时间长，不适应现有大数据分析的发展方向。

【关键词】 快速过滤算法 GPRS 缓存加速 UNIX

一、背景介绍

虽然近年来中国移动在快速发展4G用户，但是由于4G覆盖不足和投资成本的制约，中国移动通过2G/3G上网用户仍高达3亿用户，如何提升这部分用户的感知？是摆在每个移动员工的迫切问题。通过分析低速网络上网行为的特征，为提升用户感知，河北移动搭建了手机上网缓存加速系统。随着时间的推移，缓存的海量小包处理时间越来越长，迫切需要一种基于UNIX操作平台的快速过滤算法提升整个缓存系统处理能力和效率。

二、算法分析及介绍

本文提出的快速过滤算法是一个高性能的报文分类算法， 本算法是其衍生出来的一个支持Unix内核框架包过滤模块，由用户态应用程序和内核态模块组成，用于代替一般包过滤算法。本算法和一般包过滤算法对比起来，其优点主要在于分类规模很大时依然能够保持较好的性能。

本算法基本上是将报文分类抽象为多维的范围匹配问题，算法分为四个步骤如图1所示。

具体说明如下：

步骤1：根据数据通信中的TCP/IP模型，按照数据中包含的网络层、应用层的相关数据，初始化形成成有粗到细的多维匹配规则树；

步骤2：算法逐包分析串行数据数据包相应的信息并开始进行规则树匹配；

步骤3：数据包按照有粗到细的匹配树逐层匹配相关的信息，直到最后一层；

步骤4：从最后的匹配域中查找匹配规则，数据包有规则存储到相应的位置，方便下一步查询和使用。

三、算法的价值及优点

本算法没有使用位图，因为Unix不允许以空间换时间。没有使用位图，这是因为该算法不需要位图 。Cisco包过滤算法则是并行的同时得到了所有匹配域值表的位图，因此只要将它们AND，就能得到最终结果，原因在于UNIX并不是并行操作的，而是串行的，本算法对于每一个匹配域也有一个值表，由于一系列的匹配域按照一定的顺序排列好，比如：源地址-目的地址-协议-源端口-目的端口，因此其值表也有这样的串接关系，如下：

在找到目的地址的匹配之前，是不会匹配协议以及后面的匹配域的。具体的规则挂接在最后的匹配域值表中。本算法没有保留原始的配置规则，然后通过位图找到它们，而是直接将规则挂在了它“应该在”的位置。

参 考 文 献

[1]刘胤，杨世平，二种基于RFC算法的快速多维数据包分类算法，计算机工程，2008年第6期。

[2]王嫣然，陈梅，王翰虎，张鑫，一种基于内容过滤的科技文献推荐算法，计算机技术与发展， 2011， 21（2）：66-69

[3]白丽君，基于内容和协作的科技文献过滤方法研究，山西大学学，2013

[4]范立新，用位并行法进行过滤的中文近似串匹配算法，浙江大学，2006