线速软多元组报文分类方法

摘要

本发明公开了一种线速软多元组报文分类方法，其步骤为：(1)将规则中的端口字段转换为对应的前缀闭包，得到一个不连续掩码前缀集；首先将端口字段转为对应的前缀闭包，即形成一个覆盖其区间且可以表示为前缀形式的最短的区间；然后将五维前缀集的各个维度连接起来，得到一个不连续掩码的前缀集；(2)通过上述不连续掩码前缀集构造CMT数据结构；(3)使用CMT结构查找算法实现高速报文分类。本发明具有查找速度快、硬件开销小、能耗低等优点。

主权项

一种线速软多元组报文分类方法，其特征在于，步骤为：(1)将规则中的端口字段转换为对应的前缀闭包，得到一个不连续掩码前缀集；首先将端口字段转为对应的前缀闭包，即形成一个覆盖其区间且可以表示为前缀形式的最短的区间；然后将五维前缀集的各个维度连接起来，得到一个不连续掩码的前缀集；(2)通过上述不连续掩码前缀集构造公共掩码树CMT数据结构；(3)使用公共掩码树CMT结构查找算法实现高速报文分类；所述步骤(2)的具体步骤为：(2.a)将整个前缀集作为公共掩码树CMT结构的根节点；(2.b)使用根节点的公共掩码修剪前缀集中的每一项，如果修剪后的前缀集和之前不一致，该前缀将被移入该项的子节点中；(2.c)对节点中的所有项进行排序，使前缀相同的项位于相邻的位置；(2.d)合并前缀相同的项，将这些项的子节点合并成一个大的子节点，并更新该子节点的公共掩码。