1、一种IP包分类方法,包括: 步骤10)、网络设备提取接收到的IP包的五元组,对所述五元组执行基于 Counting Bloom Filter预测,获取预测结果; 步骤20)、根据所述预测结果,与组织成Hash表的规则表进行匹配,根据 匹配后的规则,确定IP包分类结果。 2、权利要求1方法,其中,步骤10)进一步包括: 步骤110)、根据具体应用规则,确定所述五元组所需的掩码,决定所述 Counting Bloom Filter预测的轮数; 步骤120)、对所述五元组进行Hash运算,得到中间结果; 步骤130)、将所述中间结果作为k个Hash函数的输入,产生k个地址, 以所述k个地址访问位组,得到k个位; 步骤140)、当所述k个位都为1,将所述k个地址作为预测结果。 3、权利要求2的方法,其中,步骤110)还包括通过掩码屏蔽不关心的五 元组的域。 4、权利要求2的方法,其中,步骤120)可以进一步包括:将源IP、目的 IP、源端口、目的端口进行按位异或,得到一个32位的值tmp1,将tmp1右移 n位后与tmp1按位异或得到tmp2,将tmp2左移m位后与tmp2按位异或得到中 间结果,其中,所述n与m小于32。 5、权利要求2的方法,其中,步骤130)中,所述位组可以是多端口存储 器,所述访问位组可以为读取多端口存储器。 6、权利要求2的方法,其中,步骤20)进一步包括: 步骤210)、根据所述k个Hash函数产生的地址中的第一个地址访问片外 SRAM,获取规则,如果规则无效,执行下一轮匹配; 步骤220)、如果规则有效且被命中并具有最高优先级,那么匹配成功; 步骤230)、如果规则不被命中,那么继续以k个地址中其它地址执行同样 匹配过程;如果k个地址用尽,那么将第k个地址加1,继续尝试,最后将命中 最高优先级规则的匹配结果确定为匹配结果。 7、权利要求6的方法,其中,步骤210)中,所述SRAM中存储规则,并组 织成Hash表。 8、权利要求6的方法,其中,步骤210)还可以包括向所述SRAM中添加规 则的过程:利用第一个ha sh函数计算出一个地址,如果该地址处已经有规则但 不是待加入的规则,则以同样的方式尝试下一个Hash函数,直到使用过所有的 Hash函数;如果还有冲突,那么将地址加1,继续尝试,直到目的地址处空闲 或者找到相同的规则。 9、权利要求6的方法,其中,Counting Bloom Filter预测和规则匹配时 所使用的Hash函数可以部分或者全部共享。 10、一种IP包分类设备,包括: Counting Bloom Filter预测模块,用于对网络设备提取接收到的IP包的 五元组执行基于Counting Bloom Filter预测,获取预测结果; 规则匹配模块,用于根据所述预测结果,与组织成Hash表的规则表进行匹 配,根据匹配后的规则,确定IP包分类结果。 11、权利要求10的设备,还可以包括: SRAM,用于存储分类规则,所述规则在SRAM中的地址根据Counting Bloom Filter所用Hash函数产生。 12、权利要求10的设备,其中,所述Counting Bloom Filter预测模块可 以根据具体应用规则,确定所述五元组所需的掩码,决定所述Counting Bloom Filter预测的轮数;所述Counting Bloom Filter预测模块对所述五元组进行 Hash运算,得到中间结果,将所述中间结果作为k个Hash函数的输入,产生k 个地址,以所述k个地址访问位组,得到k个位;当所述k个位都为1,所述 Counting Bloom Filter预测模块将所述k个地址作为预测结果,并进入下一轮 预测;当所述k个位包括至少一个0时,直接进入下一轮预测。 13、权利要求12的设备,其中,所述位组可以是多端口存储器,所述访问 位组可以为读取多端口存储器,其中,当Counting Bloom Filter计数器值为0, 位组对应位为0,当Counting Bloom Filter计数器值为1,位组对应位为1; 所述Counting Bloom Filter预测模块的计数器由1变为0或由0变为1时, 通过系统总线更新所述位组。 14、权利要求10的设备,其中,所述规则匹配模块还用于根据所述k个Hash 函数产生的地址中的第一个地址访问SRAM,获取规则,如果规则无效,执行下 一轮匹配;如果规则有效且被命中并具有最高优先级,那么匹配成功;如果规 则不被命中,那么继续以k个地址中其它地址执行同样匹配过程,如果k个地 址用尽,那么将第k个地址加1,继续尝试,最后将所述规则匹配模块将命中最 高优先级规则的匹配结果确定为匹配结果。 15、权利要求14的设备,其中,所述规则匹配模块还可以向所述SRAM中 添加规则:所述规则匹配模块利用第一个hash函数计算出一个地址,如果该地 址处已经有数据但不是待加入的规则,则以同样的方式尝试下一个Hash函数, 直到使用所有的Hash函数;如果还有冲突,那么将第k个地址加1,继续尝试, 直到目的地址处空闲或者找到相同的规则。 16、权利要求14的设备,其中,所述Counting Bloom Filter预测模块和 所述规则匹配模块所使用的Hash函数可以部分或全部共享。 17、权利要求10的设备,所述设备可以为由多个所述Counting Bloom Filter 预测模块和多个所述规则匹配模块组成的多路设备,其中,每一路中包括一个 所述Counting Bloom Filter预测模块和一个所述规则匹配模块,各路中的所 述Counting Bloom Filter预测模块和所述规则匹配模块相互独立。
展开