一种自定义流表中单表多域规则表转换为多表多域规则表的方法

摘要

本发明公开了一种自定义流表中单表多域规则表转换为多表多域规则表的方法，包括以下步骤：（1）构造若干个变异trie树，每一个变异trie树对应目标多表多域规则表的某一个表；（2）将单表多域的规则表规则集按照步骤（1）中的变异trie树结构进行存储；（3）将步骤（2）中存储有单表多域规则表规则集的变异trie树构造成目标多表多域规则表。所述转换方法高效地实现了自定义流表中单表多域规则表到多表多域规则表的转换，有利于减少整个表项的数目，更具灵活性。

说明书

技术领域

本发明涉及一种自定义流表中单表多域规则表转换为多表多域规则表的方 法。

背景技术

目前，随着网络的不断发展，灵活的自定义多级流表已经成为网络设备的发 展趋势。而这种自定义多级流表的表的数目和每个表的匹配域类型都可以灵活设 定。例如，当前非常火热的OpenFlow也是一种自定义的流表技术。Trie树又称为 字典树，其是一种树形结构，并用于保存大量的字符串。Trie树的特点是利用字 符串的公共前缀来节约存储空间，加快检索速度。

发明内容

发明目的：本发明的目的是针对现有技术的不足而提供一种自定义流表中单 表多域规则表转换为多表多域规则表的方法，高效地实现了自定义流表中单表多 域规则表到多表多域规则表的转换。

技术方案：为了实现发明的目的，本发明公开了一种自定义流表中单表多域 规则表转换为多表多域规则表的方法，包括以下步骤：

（1）构造若干个变异trie树，每一个变异trie树对应目标多表多域规则表 的某一个表；

（2）将单表多域的规则表规则集按照步骤（1）中的变异trie树结构进行存 储；

（3）将步骤（2）中存储有单表多域规则表规则集的变异trie树构造成目标 多表多域规则表。

作为优选，为了使得变异trie树形成一个整体从而更高效地完成遍历，步骤 （1）中多表多域规则表的每个表依次各形成一个单独的变异trie树，并且上一 个变异trie树的叶子节点指向下一个变异trie树的根节点。

作为优选，为了完成建立同属于一条规则但由于拆分而分布在不同表的各个 表项之间的联系，并且同时能够避免多匹配错误的问题，步骤（3）存储有单表 多域规则表规则集的变异trie树向目标多表多域规则表的构造从最后一个变异 trie树开始。

作为优选，为了更高效地完成转换工作，并且使得真个转换工作更加灵活， 本发明的步骤（3）包括以下步骤：

（3.1）遍历存储有单表多域规则表规则集的变异trie树得到相应个数的若干 简化规则表；

（3.2）对步骤（3.1）中的各简化规则表中的各流表项逐一添加metadata域；

（3.3）将步骤（3.2）中的添加有metadata域的简化规则表转换为目标多表 多域规则表。

有益效果：本发明与现有技术相比：高效地实现了自定义流表中单表多域规 则表到多表多域规则表的转换，有利于减少整个表项的数目，更具灵活性。

附图说明

图1为传统trie树的结构示意图；

图2为本发明单表多域规则表所转换成的变异trie树结构图；

图3为本发明转换方法的流程示意图；

图4为图4所示单表多域规则表转换成的变异trie树组结构图。

具体实施方式

下面结合附图对本发明作更进一步的说明。

trie树是一种前缀树，用来保存大量的字符串，其结构如图1所示；如图2 所示，本发明的变异trie树是根据目标多表多域规则表各表表结构特点结合传统 trie树结构得到的，多表多域规则表的Table0的各匹配域放在上层，二Table1 的各匹配域放在下层，并继续依次排放；一个表形成一个单独的变异trie树，某 表形成的变异trie树的叶子节点指向下层表所形成变异trie树的根节点。

如图3所示，本发明转换方法的流程为先将整个单表多域规则表按照目标多 表多域规则表的顺序存储到变异trie树中；接着分别遍历各表所对应的变异trie 树得到最简单规则表；然后将最后一个表根据动作的次数复制流表项；最后依次 从最后一个表开始向前进行metadata域的填充。

下面结合实施例对本发明作更进一步的说明。

如表1所示，需要转换的单表多域规则表包括匹配域F1和F2，而Decision 代表匹配成功后需要执行的动作；根据本发明的转换方法将其转换为如图4所示 的变异trie树组，F1放在上层的变异trie树中，而F2和Decision放在下层的变 异trie树中，上层树的叶子节点指向下层树的根节点。

表1

遍历转换后的变异trie树组，得到如表2所示的简化规则表；然后逐条扫描 表1中的单表多域规则表的规则，逐项添加metadata域，即包括给F2匹配域所 在的Tbale2添加metadata field以及给F1匹配域所在的Table2填充相应的write metadata动作，得到如表3所示的填充后的规则表；最终形成如表4所示的目标 多表多域规则表。

表2

表3

表4

本发明的转换方法实现了将一张单表多域的规则表等价拆分成多表多域的 pipeline形式，有利于减少整个表项的数目，更具灵活性。