一种数据包的高效过滤方法

摘要

本发明公开了一种数据包的高效过滤方法，该方法首先将所有过滤规则进行预处理，得到与CPU内核数量相同份数的各过滤字段类型过滤规则的过滤规则检索表和映射关系表，然后各CPU内核获取待处理数据包的各过滤字段信息，通过右移位操作和二分法查找，从而确定各过滤字段信息对应的过滤规则，然后对数据包中各过滤字段信息按照相应的过滤规则进行处理，从而完成数据包过滤。该方法能够快速准确地匹配过滤规则，大大提高了过滤速度和数据吞吐性能，提高了过滤数据包的效率。

说明书

技术领域

本发明涉及数字信息传输技术领域，具体涉及一种数字信息处理的方法。

背景技术

随着互联网技术的飞速发展，互联网的数据信息量不仅越来越大，而且数据信息也越来越多样。网络用户在要求网络数据流量稳定的同时还希望对一些特定的数据信息采取特定的过滤策略。因此，能够实现这些需求的技术之一就是数据包过滤方法：在庞大的数据信息中，只选择需要的数据包，过滤不需要甚至有威胁的数据包。通常数据包过滤的方法是根据数据包的字段内容，如源/目的IP地址、数据包长度、IP协议、端口号以及应用层信息等制定所需的过滤规则，然后将待处理的数据包匹配相应的过滤规则，从而决定数据包是否被过滤。然而，现有的基于多个域的数据包过滤方法由于匹配过滤规则消耗的资源过高且不能够无锁并行处理，因此现有的数据包过滤方法在性能上已经无法满足在互联网数据信息的多样性和庞大的数据流量下的性能需求，尤其是在骨干网络节点上，这种性能需求表现得更加明显。人们尝试采用各种方法来解决这一问题，其中，效率较高且具有代表性的有HASH表数据包过滤方法、RFC递归流分类数据包过滤方法和简单二叉树查找过滤法，但是这些方法均有不足之处：HASH表数据包过滤方法虽然易于实现、存储需求小、支持范围匹配和动态更新，但其效率受规则的分布情况和规则数量影响极大，当有冲突时，查找时间比较长；RFC递归流分类数据包过滤方法虽然速度较快、扩展性好、易于并行处理，但是由于递归流分类数据包过滤方法的性能与分类器的结构有关，因此该方法缺乏一般性，需要根据不同的分类器做出微调才能发挥最佳性能且该方法消耗内存资源较大；简单二叉树查找过滤法便于硬件实现，规则维数扩展性好，支持范围匹配和动态更新，但查找时间随规则数的增加急速增长，在多维的情况下，不适用于高速网络应用。

发明内容

鉴于现有技术的不足，本发明所要解决的技术问题是提供一种数据包的高效过滤方法，该方法能够快速准确地与过滤规则匹配，以提高过滤数据包的效率。

本发明实现上述目的的技术方案是：

一种数据包的高效过滤方法，该方法由以下步骤组成：

1）按以下步骤建立包含各过滤字段类型过滤规则的过滤规则检索表和映射关系表：

1.1）首先，将所有过滤规则按过滤字段类型进行分类，并将属于同一种过滤字段类型的过滤规则写入一种过滤规则检索表中，然后将所有的过滤规则检索表复制出与处理数据包的CPU内核数量相同份数的拷贝并存储到内存中，并且每份拷贝均设有一与所述的CPU的一个内核对应的编号；

1.2）然后，将每份拷贝中各过滤规则检索表中的过滤规则携带的过滤字段数据范围的端点值投影到数轴上表示，从数轴原点开始，将相邻的两个端点间的区间作为一个有效区间，从而得到各过滤字段类型的有效区间索引表，并按顺序对每个有效区间索引表中的各区间进行编号；

1.3）将所述数轴上各过滤规则检索表中字段范围的最大值与数轴原点之间的长度用二进制表示，得到有效区间索引表的二进制长度值，然后将各有效区间索引表的长度值做右移位操作至结果为小于或等于256的十进制数，并以该十进制数作为元区间的个数将有效区间索引表的长度值等分为大小为2^Y的元区间，再按每个元区间在所述数轴上的顺序把每个元区间用十进制数进行编号，得到各过滤字段类型的元区间索引表和各过滤字段类型对应的右移位操次数表；其中，所述的元区间大小2^Y中的Y为所述右移位操次数；

1.4）然后，以元区间索引表和有效区间索引表中元区间和有效区间在数轴上的对应关系，建立所述元区间索引表、有效区间索引表以及过滤规则之间的映射关系表；

2）按以下步骤完成数据包的过滤操作：

2.1）从待过滤的数据包中获取各过滤规则检索表所需的过滤字段数据；

2.2）获取当前处理该数据包的CPU内核的编号，并根据该编号定位内存中处理该数据包所对应的过滤规则检索表的拷贝；

2.3）将步骤2.1）中获取的过滤字段数据用二进制表示，并将所得到的二进制数值做右移位操作，再将移位操作的结果转换为十进制数，然后以该十进制数作为元区间编号，由所述的映射关系表中依次查找到对应的有效区间的范围、有效区间的编号和过滤规则进行过滤规则匹配；在上述查找过程中，如查找到对应的有效区间编号仅为一个，该有效区间编号对应的过滤规则即与该过滤字段匹配；若查找到对应的有效区间编号为多个，则先对查找到对应的有效区间的范围做二分法查找，直至有效区间的范围缩小到仅对应于一个有效区间编号时，该有效区间编号对应的过滤规则即与该过滤字段匹配；当一个过滤字段对应多条匹配的过滤规则时，则选择过滤规则检索表中过滤规则优先级高的规则作为与该过滤字段匹配的过滤规则；该步骤中所述的右移位操作次数与该过滤字段的类型在所述各过滤字段类型对应的右移位操次数表中的右移位操次数相等；

2.4）按各过滤字段类型的匹配优先级重复步骤2.3）完成待处理数据包中的所有过滤字段类型的过滤规则匹配后，CPU的各内核则对相应数据包拷贝进行过滤处理。

与现有技术相比，本发明提供的一种高效数据包过滤方法具有以下优点和效果：

A）本发明在过滤数据包之前根据过滤规则建立了各个过滤字段类型的元区间索引表、有效区间索引表、过滤规则之间的映射关系表，由于有效区间与过滤规则之间存在相对确定的对应关系，而通过右移位操作即可快速定位待处理的过滤字段信息所对应的有效区间编号的范围，极大地缩小了待匹配过滤规则的范围，显著地提高了数据包匹配过滤规则的速度，进而大大提高了数据包过滤效率；

B）在现有的数据包并行处理技术中，由于内存地址中只有一份过滤规则检索表，因此一个CPU内核在访问内存时，必须对内存地址加锁，在当前CPU内核访问该内存地址结束后，才允许其他CPU内核访问该地址，因此在数据包并行处理时存在互相等待的过程。而本发明在建立过滤规则检索表时在内存中复制了与CPU内核数量相同份数的拷贝，且每份拷贝都设有一与处理当前数据包的CPU内核对应的编号，因此每个CPU内核在进行数据包过滤处理时独享一份过滤规则检索表，无需竞争访问内存地址资源，使得在处理大量数据包过滤时，可根据CPU内核数量实现真正意义上的无锁并行处理数据包过滤，大大提高了数据吞吐性能。

附图说明

图1为本发明所述的一种数据包的高效过滤方法的一个具体实施例的过滤过程示意图；

图2为本发明所述的一种数据包的高效过滤方法的一个具体实施例的元区间索引表、有效区间索引表、过滤规则之间的映射关系表示意图。

具体实施方式

下面结合附图和实施例对本发明做进一步的详细描述。

如图1所示，本例为一个内部网络骨干节点上采用双核CPU处理数据包过滤的过程，每个CPU上获得的的数据包所包含的字段信息如表1所示，本例过滤数据包的过程如下：

表1待处理数据包过滤字段类型数据表

CPU内核数据包长度源IP地址目的IP地址源端口目的端口1128010.0.0.5561.191.206.1723000222900192.168.1.9961.191.206.172500080

1）对节点所有过滤规则按以下步骤进行预处理，得到一包含各过滤字段信息的过滤规则检索表和映射表，该节点的数据包过滤规则按优先由高到低排列后如表2所示（过滤规则序号值较小的优先级较高）：

表2数据包过滤规则表

规则序号数据包长度源IP地址目的IP地址源端口目的端口处理动作10-500172.16.12.1-172.16.12.255Nlll0-100080放行264192.168.1.1-192.168.1.255NullNullNull禁止31000-148010.0.0.1-10.0.0.25561.191.206.172-61.191.206.1722000-6553522放行4600-800NullNull0-655350-65535禁止5600-1480192.168.1.99-192.168.1.99NullNullNull禁止

1.1）首先将表2中所有过滤规则按过滤字段类型进行分类，并将属于同一种过滤字段类型的过滤规则写入一种过滤规则检索表中，表2中含有5种过滤字段类型：数据包长度、源IP地址、目的IP地址、源端口和目的端口，因此分为5种过滤规则检索表，然后将各过滤规则检索表复制2份拷贝并存储到内存，且每份拷贝均设有一与CPU的一个内核对应的编号；

1.2）根据过滤规则携带的过滤字段数据范围的端点值投影到数轴上表示，得到以5种过滤字段的不重叠的有效区间索引表，步骤1.1）中所述的5种过滤字段的有效区间索引表分别如表3～表8所示，并按顺序对有效区间索引表中的各有效区间进行编号；

表3数据包长度的有效区间索引表

有效区间编号过滤字段数据对应规则00-63规则1164规则1、2265-500规则13600-800规则4、54801-999规则551000-1480规则3、5

表4源IP地址的有效区间索引表

有效区间编号过滤字段数据对应规则010.0.0.1-10.0.0.255规则31172.16.12.1-172.16.12.255规则12192.168.1.1-192.168.1.98规则23192.168.1.99-192.168.1.99规则54192.168.1.100-192.168.1.255规则2

表5目的IP地址的有效区间索引表

有效区间编号过滤字段数据对应规则060.191.206.172-60.191.206.172规则3

表6源端口有效区间索引表

有效区间编号过滤字段数据对应规则00-1000规则1、411001-1999规则422000-65535规则3、4

表7目的端口有效区间索引表

有效区间编号过滤字段数据对应规则00-21规则4122-22规则3、4223-79规则4380-80规则1、4481-65535规则4

1.3）将表3～表7所示的有效区间索引表的长度转为二进制表示，即将表3～表7中各过滤字段的最大端点到原点的距离转为二进制表示，由于IP地址在作为数据处理时，通常表示为32位二进制数据处理，因此在划分IP地址的元区间索引表时，IP地址将会由32位二进制数据转换为十进制数处理，5种过滤字段类型的有效区间索引表的长度用二进制表示依次为10111001000、11000000101010000000000111111111、111100101111111100111010101100、1111111111111111、1111111111111111，由此，将5种过滤字段类型的有效区间索引表划分为小于或等于256个元区间的右移位操作的次数如表8所示，从而5种过滤字段类型的有效区间索引表可依次划分为186个、193个、243个、256个、256个等大小的元区间，各过滤字段的元区间大小依次为8、16777216、4194304、256、256，并按顺序对各元区间进行编号，其中，数据包长度的元区间索引表、源IP地址的元区间索引表及源端口的元区间索引表的划分依次如表9～表11，目的IP地址的元区间索引表、目的端口的元区间索引表的划分和表10、表11类似，不再赘述；

表8各字段类型右移位操次数表

过滤字段类型数据包长度源IP地址目的IP地址源端口目的端口右位移操作次数3242288

表9数据包长度的元区间索引表

元区间编号元区间数值范围00-718-15216-23……1841472-14791851480

表10源IP地址的元区间索引表

元区间编号元区间数值范围00-16777215116777216-33554431……10167772160-184549375……28469762048-486539263……1923221225472-3238002687

表11源端口的元区间索引表

元区间编号元区间数值范围00-2551256-5112512-767……

25465024-6527925565280-65535

1.4）然后，以5种过滤字段类型的元区间索引表和有效区间索引表中元区间和有效区间在数轴上的对应关系，建立5种过滤字段类型的元区间索引表、有效区间索引表、过滤规则之间的映射关系表，映射关系表的示意图如图2所示；

2）根据各过滤字段类型的匹配优先级将表1中待处理的数据包按匹配优先级顺序进行匹配处理，从而确定数据包中各字段对应的过滤规则，完成数据包的过滤操作，本例中过滤字段匹配优先顺序为：数据包长度——源IP地址——目的IP地址——源端口号——目的端口号，因此，过滤规则匹配过程为：

2.1）从待过滤的数据包中获取各过滤规则检索表所需的字段信息，待过滤的数据包所包含的字段信息如表1所示；

2.2）由于数据包从接收到数据包过滤处理完成均由相应的软件分配给指定的CPU内核完成，因此我们可以轻易获取当前处理该数据包的CPU内核的编号，并根据该编号定位内存中处理该数据包对应的拷贝，本例中CPU内核1对应处理表1中的数据包1，CPU内核2对应处理表1中数据包2；

2.3）将表1中各数据包的过滤字段数据转换为二进制表示：数据包1的数据包长度、源IP地址、目的IP地址、源端口、目的端口分别用二进制表示为：10100000000、00001010000000000000000000110111、00111101101111111100111010101100、101110111000、00010110；数据包2的数据包长度、源IP地址、端口号分别为：1110000100、11000000101010000000000101100011、00111101101111111100111010101100、00001001110001000、01010000，分别对数据包1和数据包2的各过滤字段的二进制数值按照步骤1.3）中所述的右移位操作次数进行移位操作，分别得到数据包1中数据包长度、源IP地址、目的IP地址、源端口、目的端口对应的十进制元区间编号为：160、10、246、11、0；数据包2中数据包长度、源IP地址、目的IP地址、源端口、目的端口对应的十进制元区间编号为：112、192、246、19、0，再根据步骤1.4）所得到的5种过滤字段类型映射关系表即可得到数据包1各过滤字段的元区间编号对应的有效区间编号依次为：5、0、0、2、1；数据包1各过滤字段的元区间编号对应的有效区间编号分别为：5、2或3或4、0、2、3；

2.4）由于数据包1的各过滤字段的元区间编号仅对应一个有效区间编号，因此数据包1的过滤规则匹配过程结束，各过滤字段按照对应的规则进行过滤处理，由于数据包1中存在过滤字段数据匹配多条规则，按照优先级较高的过滤规则对数据包1进行处理，处理数据包1的优先级最高的过滤规则为过滤规则3，因此CPU内核1对其予以放行；在数据包2中，源IP地址字段的元区间编号对应多个有效区间编号，因此需要对该过滤字段数据对应的有效区间范围做二分法查找，从而进一步缩小范围，当缩小的有效区间范围仅对应一个区间编号时，即当数据包2中的过滤字段的元区间编号对应区间编号为5、3、0、2、3时，过滤规则匹配过程结束，然后根据匹配的过滤规则对该数据包进行过滤处理，由此得到处理数据包2的优先级最高的过滤规则为过滤规则5，因此CPU内核2禁止其通过。