一种基于二叉树的流分类查找方法
专利名称：一种基于二叉树的流分类查找方法
技术领域：
本发明涉及数据网络的流分类技术领域，尤其涉及数据网络中基于二叉树的流分类查找方法。
背景技术：
在数据网络中，随着Internet的发展，许多新的服务类型被引入到Internet中，如虚拟专用网络(Virtual Private Network，VPN)、分布式防火墙、基于策略的路由、区分服务、流量计费以及IP安全网关等。这些新的服务类型都是以流分类(Flow Classification)技术为基础的。在数据网络中，流分类实际上是对数据包的分类，即根据数据包头部的一个或多个关键字段，基于一定的策略和规则，识别该数据包所属的流，然后基于所属流的属性，对该数据包进行相应的处理。
流分类的过程如图1所示，系统根据流分类的规则从数据包头部字节中提取关键字段，从流存储表中查找获得数据包所属的流。其中，流分类的算法主要由流分类查找部分来实现，因此流分类查找是流分类过程的关键，决定了流分类速度的快慢和占用存储空间的大小。
出于对数据包吞吐量的考虑，流分类技术中的流分类查找一般采用硬件来实现，主要有三类方法存储器直接查找、基于查找树进行查找和利用Hash算法进行查找。存储器直接查找的流分类方法中最具代表性的是基于TCAM(Ternary Content Addressable Memory)的查找，其特点是查找速度快，支持前缀和范围匹配，但CAM器件价格昂贵，功耗大，且规则的更新较为复杂。利用Hash算法进行流分类查找的特点是实现简单，分类速度快，存储空间小，但是Hash算法固有的冲突和发散问题使得流分类查找的效率较低，直接影响流分类的效果。
相比较之下，基于查找树的流分类查找是一种折中的方案，比较典型的基于查找树的流分类查找是基于二叉树的流分类查找，其空间复杂度较小，可以采用内部RAM实现，成本低。
用于流分类查找的二叉树的结构如图2所示，基于二叉树的流分类查找流程如图3所示。
数据包进行流分类查找时，首先读出二叉树根节点中系统配置的关键字段，与数据包的关键字段进行比较，如果相等，则流分类查找成功；否则，查找二叉树的下一级节点。如果二叉树节点中的关键字段小于数据包的关键字段，则查找下一级节点中居左(或右)的节点，如果二叉树节点中的关键字段大于数据包的关键字段，则查找下一级节点中居右(或左)的节点。然后根据下一级节点中的关键字段数值，确定流分类查找是否成功，或者再下一级节点的位置，依此类推，直到最后一级节点。如果最后一级节点的关键字段依然不相等，则流分类查找失败。
二叉树各级节点的配置内容可以存储在一块(或多块)RAM中，硬件实现简单。其缺点是二叉树查找的步骤较多，流分类的时间比较长，且规则的更新较慢，一次完整的二叉树查找需要多次查找比较操作，次数最大等于二叉树的级数，从而导致流分类的时间比较长，另外，为了保持二叉树查找结果的一致性和正确性，在二叉树查找的过程中不允许改变二叉树的配置内容，因此二叉树一般不支持动态配置。
发明内容
本发明提出一种基于二叉树的流分类查找方法，能够解决流分类查找技术中查找时间长的问题。
为此，本发明采用以下技术方案一种基于二叉树的流分类查找方法，包括以下步骤A、将所述二叉树的L级节点划分成M级流水线；B、M个数据包分时并行地与M级流水线上的二叉树节点进行比较，其中L和M为不小于2的整数，并且L大于M。
步骤A中，所述二叉树节点对应的存储器地址从根节点为1开始，其他子节点的存储器地址依次增加。
所述步骤B中，所述数据包和所述二叉树节点进行比较包括以下步骤B1、根据二叉树节点的存储器地址读所述二叉树节点；B2、获取所述二叉树节点中的关键字段和流ID；B3、比较所述二叉树节点中的关键字段和所述数据包的关键字段；B4、如果所述二叉树节点中的关键字段和所述数据包的关键字段相等，二叉树查找成功，采用所述二叉树节点的流ID，否则产生下一级二叉树节点的地址。
以一级流水线所需要的时间作为固定的周期，不同数据包在同一级流水线中在相同的时间点读取二叉树节点，同一数据包在不同级流水线中在不同的时间点读取二叉树节点。下一级流水线中数据包读取二叉树节点的时间点比上一级流水线中数据包读取二叉树节点晚一个时钟周期。
设置M个寄存器，分别用于存储M个数据包的关键字段。
当所述二叉树需要添加流分类规则，将按照平衡二叉树的编排规则，在相应的节点配置新的规则内容。
将所述二叉树进行备份，形成主二叉树和从二叉树。
当系统发出切换指令，如果主二叉树被使用，将在所述切换指令前最后进入的数据包完成二叉树查找后，主二叉树和从二叉树之间相互切换；如果主二叉树没有被使用，则主二叉树和从二叉树之间相互切换。
采用了本发明的技术方案，将基于二叉树的流分类查找过程划分成若干级流水线，可以同时处理多个数据包的流分类查找，从而降低了数据包流分类查找的平均时间，提高了流分类的吞吐量。另外，本发明采用两块RAM分别作为主从二叉树，流分类查找访问主二叉树，系统流分类规则配置访问从二叉树，从而实现了流分类查找过程中无损伤的动态流分类规则更新。
图1为流分类过程的流程图；图2为用于流分类查找的二叉树结构示意图；图3为基于二叉树的流分类查找流程图；图4为本发明中基于二叉树的流分类查找流程图；图5为主从二叉树切换过程示意图。
具体实施例方式
下面结合附图，通过具体实施方式
对本发明的技术方案作进一步说明。
本具体实施方式
需要两块RAM作为主从二叉树用来存储流分类的规则，RAM的条目数量为2L，L为二叉树节点的级数，取决于流分类规则的数量。条目的内容如表1所示表1
本发明中还需要M个寄存器用来保存M级流水线中数据包的关键字段，格式如表2所示
表2
流分类规则库中的规则数量决定了系统中二叉树的节点数，流分类的数据包吞吐量限制了二叉树查找时每一级流水线内部的时间，从而决定了二叉树查找的流水线级数。假设系统中二叉树存在L级节点，将二叉树查找划分为M级流水线，则一级流水线内部包括N(N＝{L/M}，{}表示向上取整)个二叉树节点的查找，每一个二叉树节点的查找包括读存储器操作、获取节点中存储的数值、关键字段的比较和下一级存储器地址产生等四个步骤时钟周期1二叉树节点读信号和读地址(RAM读)有效；时钟周期2获取二叉树节点中的关键字段和流ID；时钟周期3比较二叉树节点中的关键字段和数据包的关键字段；时钟周期4如果二叉树节点中的关键字段与数据包的关键字段相等，二叉树查找成功，采用该节点的流ID；否则产生下一级二叉树节点的地址。
接收到数据包的关键字段后，则从根节点开始逐级查找平衡二叉树，完成第一级流水线的查找之后，如果查找没有成功，则进入第二级流水线的查找，与此同时，另外一个数据包开始从根节点进行第一级流水线的查找。在第一个数据包完成第二级流水线的查找，同时第二个数据包完成第一级流水线的查找，如果没有查找成功，则第一个数据包进入第三级流水线查找，第二个数据包进入第二级流水线查找，同时第三个数据包开始从根节点进行第一级流水线查找，依此类推，直到所有数据包完成整个二叉树的查找。
最坏情况下(在最后一级节点查找成功)，一次完整的二叉树查找需要在不同的时刻访问二叉树节点存储器L次，采用流水线结构之后，势必会严生M级流水线同时访问存储器的情况，本具体实施方式
中，同一级流水线中不同数据包读取二叉树节点的时间点是相同的，同一数据包在不同级流水线中分别在不同的时间点读取二叉树的节点，从而避免了RAM的访问冲突。
本具体实施方式
提出的采用流水线结构的二叉树流分类查找的流程如图4所示，其主要操作步骤如下(1)第1个数据包进入第1级流水线，将数据包的关键字段保存到关键字段1寄存器中，进行二叉树第1级节点的查找；(2)第1个数据包进行第1级流水线第2级二叉树节点的查找；依次进行；(3)第1个数据包进行第1级流水线中第N级二叉树节点的查找；(4)第1个数据包进入第2级流水线，将关键字段1寄存器中的第1个数据包的关键字段保存到关键字段2寄存器中，进行第2级流水线中二叉树第N+1级节点的查找；同时，第2个数据包进入第1级流水线，将第2个数据包的关键字段保存到关键字段1寄存器中，进行第1级流水线中二叉树第1级节点的查找；依次进行；(5)第1个数据包完成第2级流水线第2*N级节点的查找，将关键字段2寄存器中的第1个数据包的关键字段保存到关键字段3寄存器中，进入第3级流水线查找；同时，第2个数据包完成第1级流水线第N级节点的查找，将关键字段1寄存器中的第2个数据包的关键字段保存到关键字段2寄存器中，进入第2级流水线；第3个数据包进入第1级流水线，将第3个数据包的关键字段保存到关键字段1寄存器中，进行第1级流水线中二叉树第1级节点的查找；依次进行；(6)第1个数据包完成第M-1级流水线的查找，将关键字段M-1寄存器中的第1个数据包的关键字段保存到关键字段M寄存器中，进入第M级流水线的查找；同时，第2个数据包完成第M-2级流水线的查找，将关键字段M-2寄存器中的第2个数据包的关键字段保存到关键字段M-1寄存器中，进入第M-1级流水线；第M-1个数据包进入第1级流水线，将第M-1个数据包的关键字段保存到关键字段1寄存器中，进行第1级流水线第1级节点的查找；依次进行；(7)第1个数据包完成第M级流水线第L级节点(二叉树最后一级节点)的查找，第1个数据包二叉树查找结束；同时，第2个数据包完成第M-1级流水线的查找，进入第M级流水线；第M个数据包进入第1级流水线，进行第1级节点(即根节点)的查找；依次进行；(8)第2个数据包完成第M级流水线第L级节点(二叉树最后一级节点)的查找，第2个数据包二叉树查找结束；同时，第3个数据包完成第M-1级流水线的查找，进入第M级流水线；第M-1个数据包开始第1级流水线第1级节点(即根节点)的查找；依次进行；(9)第M个数据包完成第M级流水线第L级节点(二叉树最后一级节点)的查找，第M个数据包二叉树查找结束。
本具体实施方式
中，为了避免因为流水线结构而导致的RAM访问冲突，第2级流水线的RAM读操作比第1级流水线中的RAM读操作推迟一个时钟周期，第3级流水线的RAM读操作比第2级流水线中的RAM读操作推迟一个时钟周期，第M级流水线的RAM读操作比第M-1级流水线中的RAM读操作推迟一个时钟周期。即同一级流水线中不同数据包读取二叉树节点的时间点是相同的，同一数据包在不同级流水线中分别在不同的时间点读取二叉树的节点。
下面具体说明每一级流水线不同时钟周期所进行的操作。假设二叉树的节点共有12级，分4级流水线，每级流水线完成3级二叉树节点的查找，由于一级二叉树节点的查找需要4个时钟周期，则每级流水线需要12个时钟周期。
第一级流水线的操作包括第1个时钟周期数据包的关键字保存到关键字段1寄存器中；第1级节点RAM读信号有效，地址为1；第2个时钟周期第1级节点RAM读数据有效；第3个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第4个时钟周期如果关键字段相等，则流分类查找成功，否则产生第2级节点的地址2*address或2*address+1，其中address表示上一级节点的地址；第5个时钟周期第2级节点RAM读信号有效；第6个时钟周期第2级节点RAM读数据有效；第7个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第8个时钟周期如果关键字段相等，则流分类查找成功，否则产生第3级节点的地址2*address或2*address+1；第9个时钟周期第3级节点RAM读信号有效；第10个时钟周期第3级节点RAM读数据有效；第11个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第12个时钟周期如果关键字段相等，则流分类查找成功，否则产生第4级节点的地址2*address或2*address+1。
第二级流水线的操作包括第1个时钟周期数据包的关键字保存到关键字段2寄存器中；第2个时钟周期第4级节点RAM读信号有效；第3个时钟周期第4级节点RAM读数据有效；第4个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第5个时钟周期如果关键字段相等，则流分类查找成功，否则产生第5级节点的地址2*address或2*address+1；第6个时钟周期第5级节点RAM读信号有效；第7个时钟周期第5级节点RAM读数据有效；第8个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第9个时钟周期如果关键字段相等，则流分类查找成功，否则产生第6级节点的地址2*address或2*address+1；第10个时钟周期第6级节点RAM读信号有效；第11个时钟周期第6级节点RAM读数据有效；第12个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第12个时钟周期如果关键字段相等，则流分类查找成功，否则产生第7级节点的地址2*address或2*address+1；第二个“第12个时钟周期”表示延迟“第12个时钟周期”1个时钟周期，因为下一级流水线的第1个时钟周期并没有开始读节点，所以可以利用空隙时间进行地址的产生。
第三级流水线的操作包括
第1个时钟周期数据包的关键字保存到关键字段3寄存器中；第2个时钟周期空；第3个时钟周期第7级节点RAM读信号有效；第4个时钟周期第7级节点RAM读数据有效；第5个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第6个时钟周期如果关键字段相等，则流分类查找成功，否则产生第8级节点的地址2*address或2*address+1；第7个时钟周期第8级节点RAM读信号有效；第8个时钟周期第8级节点RAM读数据有效；第9个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第10个时钟周期如果关键字段相等，则流分类查找成功，否则产生第9级节点的地址2*address或2*address+1；第11个时钟周期第9级节点RAM读信号有效；第12个时钟周期第9级节点RAM读数据有效；第12个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第12个时钟周期如果关键字段相等，则流分类查找成功，否则产生第10级节点的地址2*address或2*address+1；第二个“第12个时钟周期”表示延迟“第12个时钟周期”的第1个时钟周期，因为下一级流水线的第1个时钟周期并没有开始读节点，所以可以利用空隙时间进行关键字段的比较；第三个“第12个时钟周期”表示延迟“第12个时钟周期”的第2个时钟周期，因为下一级流水线的第2个时钟周期并没有开始读节点，所以可以利用空隙时间进行地址的产生。
第四级流水线的操作包括第1个时钟周期空；第2个时钟周期数据包的关键字保存到关键字段4寄存器中；第3个时钟周期空；第4个时钟周期第10级节点RAM读信号有效；第5个时钟周期第10级节点RAM读数据有效；第6个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第10个时钟周期如果关键字段相等，则流分类查找成功，否则产生第11级节点的地址2*address或2*address+1；第8个时钟周期第11级节点RAM读信号有效；第9个时钟周期第11级节点RAM读数据有效；第10个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第10个时钟周期如果关键字段相等，则流分类查找成功，否则产生第12级节点的地址2*address或2*address+1；第12个时钟周期第12级节点(最后一级节点)RAM读信号有效；第12个时钟周期第12级节点RAM读数据有效；第12个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第12个时钟周期如果关键字段相等，则流分类查找成功，否则流分类查找失败。
第二、第三和第四个“第12个时钟周期”分别表示延迟“第12个时钟周期”后的第1个、第2个和第3个时钟周期，因为是最后一级流水线，而且没有进行二叉树节点的读操作，所以不影响二叉树流分类查找的流水线操作。
12级节点的二叉树最大可以包含212-1＝4095个节点，即最大可以支持4095条流分类规则。如果硬件装置的工作频率为100MHz，则一级流水线的处理时间为120ns，在系统满速率的情况下，平均处理一个数据包流分类查找的时间为120ns，每秒钟可以完成8百万个数据包的流分类查找。无论是从流分类规则的数量，还是流分类查找的吞吐量，均能满足一般网络中流分类器的要求。
假设流分类查找时的关键字段为32bit宽，则所需RAM的资源为2×4K×(12+32)＝352Kbit。
为了实现流分类过程中分类规则的动态更新，本具体实施方式
中引入了主从两棵平衡二叉树。数据包流分类时硬件所查找的二叉树为主二叉树，系统需要更新流分类规则时，通过软件配置从二叉树，然后向硬件发出二叉树主从切换指令，把原来的主二叉树变为从二叉树，原来的从二叉树变为主二叉树。换句话说，流分类过程中硬件所查找的永远是主二叉树，系统软件所配置的永远是从二叉树，互不影响，从而保证了二叉树查找过程中无损伤地进行流分类规则更新。
在实际应用过程中，流分类规则的更新一般都是小范围的更新，本发明中二叉树的根节点编址为1，其它子节点依次增加，如果需要添加流分类规则，则只需按照平衡二叉树的编排规则，在相应的节点配置新的规则内容，无需改变存储器的编址方式，将二叉树内容的改变减到最少。
图5是本发明中二叉树主从切换状态流程示意图。如图5所示，主从二叉树切换时，如果没有数据包进行二叉树查找，则切换立刻完成。
如果系统发出切换指令时，有数据包正在进行二叉树的查找，则主二叉树不会立刻切换到从状态，已经开始二叉树查找的数据包依然使用原来的主二叉树，直到切换指令前最后进入的数据包完成二叉树查找之后，主二叉树才切换到从状态。
如果系统发出切换指令时，有数据包正在进行二叉树的查找，则从二叉树也不会立刻切换到主状态，直到有新的数据包开始二叉树的查找，或者直到切换指令前最后进入的数据包完成二叉树查找之后，从二叉树才切换到主状态。
以上所述，仅为本发明较佳的具体实施方式
，但本发明的保护范围并不局限于此，任何熟悉该技术的人在本发明所揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求的保护范围为准。
权利要求
1.一种基于二叉树的流分类查找方法，其特征在于，包括以下步骤A、将所述二叉树的L级节点划分成M级流水线；B、M个数据包分时并行地与M级流水线上的二叉树节点进行比较，其中L和M为不小于2的整数，并且L大于M。
2.根据权利要求1所述的一种基于二叉树的流分类查找方法，其特征在于，步骤A中，所述二叉树节点对应的存储器地址从根节点为1开始，其他子节点的存储器地址依次增加。
3.根据权利要求1所述的一种基于二叉树的流分类查找方法，其特征在于，所述步骤B中，所述数据包和所述二叉树节点进行比较包括以下步骤B1、根据二叉树节点的存储器地址读所述二叉树节点；B2、获取所述二叉树节点中的关键字段和流ID；B3、比较所述二叉树节点中的关键字段和所述数据包的关键字段；B4、如果所述二叉树节点中的关键字段和所述数据包的关键字段相等，二叉树查找成功，采用所述二叉树节点的流ID，否则产生下一级二叉树节点的地址。
4.根据权利要求1或3所述的一种基于二叉树的流分类查找方法，其特征在于，不同数据包在同一级流水线中在相同的时间点读取二叉树节点，同一数据包在不同级流水线中在不同的时间点读取二叉树节点。
5.根据权利要求4所述的一种基于二叉树的流分类查找方法，其特征在于，下一级流水线中数据包读取二叉树节点的时间点比上一级流水线中数据包读取二叉树节点晚一个时钟周期。
6.根据权利要求1或3所述的一种基于二叉树的流分类查找方法，其特征在于，设置M个寄存器，分别用于存储M个数据包的关键字段。
7.根据权利要求1所述的一种基于二叉树的流分类查找方法，其特征在于，当所述二叉树需要添加流分类规则，将按照平衡二叉树的编排规则，在相应的节点配置新的规则内容。
8.根据权利要求1或7所述的一种基于二叉树的流分类查找方法，其特征在于，将所述二叉树进行备份，形成主二叉树和从二叉树。
9.根据权利要求8所述的一种基于二叉树的流分类查找方法，其特征在于，当系统发出切换指令，如果主二叉树被使用，将在所述切换指令前最后进入的数据包完成二叉树查找后，主二叉树和从二叉树之间相互切换；如果主二叉树没有被使用，则主二叉树和从二叉树之间相互切换。
全文摘要
本发明公开了一种基于二叉树的流分类查找方法，将所述二叉树的L级节点划分成M级流水线；M个数据包分时并行地与M级流水线上的二叉树节点进行比较，其中L和M为不小于2的整数，并且L大于M。采用了本发明的技术方案，将基于二叉树的流分类查找过程划分成若干级流水线，可以同时处理多个数据包的流分类查找，从而降低了数据包流分类查找的平均时间，提高了流分类的吞吐量。另外，本发明采用两块RAM分别作为主从二叉树，流分类查找访问主二叉树，系统流分类规则配置访问从二叉树，从而实现了流分类查找过程中无损伤的动态流分类规则更新。
文档编号H04L12/46GK101022407SQ20071000567
公开日2007年8月22日 申请日期2007年3月13日 优先权日2007年3月13日
发明者滕焕勇 申请人:中兴通讯股份有限公司
技术领域：
本发明涉及数据网络的流分类技术领域，尤其涉及数据网络中基于二叉树的流分类查找方法。
背景技术：
在数据网络中，随着Internet的发展，许多新的服务类型被引入到Internet中，如虚拟专用网络(Virtual Private Network，VPN)、分布式防火墙、基于策略的路由、区分服务、流量计费以及IP安全网关等。这些新的服务类型都是以流分类(Flow Classification)技术为基础的。在数据网络中，流分类实际上是对数据包的分类，即根据数据包头部的一个或多个关键字段，基于一定的策略和规则，识别该数据包所属的流，然后基于所属流的属性，对该数据包进行相应的处理。
流分类的过程如图1所示，系统根据流分类的规则从数据包头部字节中提取关键字段，从流存储表中查找获得数据包所属的流。其中，流分类的算法主要由流分类查找部分来实现，因此流分类查找是流分类过程的关键，决定了流分类速度的快慢和占用存储空间的大小。
出于对数据包吞吐量的考虑，流分类技术中的流分类查找一般采用硬件来实现，主要有三类方法存储器直接查找、基于查找树进行查找和利用Hash算法进行查找。存储器直接查找的流分类方法中最具代表性的是基于TCAM(Ternary Content Addressable Memory)的查找，其特点是查找速度快，支持前缀和范围匹配，但CAM器件价格昂贵，功耗大，且规则的更新较为复杂。利用Hash算法进行流分类查找的特点是实现简单，分类速度快，存储空间小，但是Hash算法固有的冲突和发散问题使得流分类查找的效率较低，直接影响流分类的效果。
相比较之下，基于查找树的流分类查找是一种折中的方案，比较典型的基于查找树的流分类查找是基于二叉树的流分类查找，其空间复杂度较小，可以采用内部RAM实现，成本低。
用于流分类查找的二叉树的结构如图2所示，基于二叉树的流分类查找流程如图3所示。
数据包进行流分类查找时，首先读出二叉树根节点中系统配置的关键字段，与数据包的关键字段进行比较，如果相等，则流分类查找成功；否则，查找二叉树的下一级节点。如果二叉树节点中的关键字段小于数据包的关键字段，则查找下一级节点中居左(或右)的节点，如果二叉树节点中的关键字段大于数据包的关键字段，则查找下一级节点中居右(或左)的节点。然后根据下一级节点中的关键字段数值，确定流分类查找是否成功，或者再下一级节点的位置，依此类推，直到最后一级节点。如果最后一级节点的关键字段依然不相等，则流分类查找失败。
二叉树各级节点的配置内容可以存储在一块(或多块)RAM中，硬件实现简单。其缺点是二叉树查找的步骤较多，流分类的时间比较长，且规则的更新较慢，一次完整的二叉树查找需要多次查找比较操作，次数最大等于二叉树的级数，从而导致流分类的时间比较长，另外，为了保持二叉树查找结果的一致性和正确性，在二叉树查找的过程中不允许改变二叉树的配置内容，因此二叉树一般不支持动态配置。
发明内容
本发明提出一种基于二叉树的流分类查找方法，能够解决流分类查找技术中查找时间长的问题。
为此，本发明采用以下技术方案一种基于二叉树的流分类查找方法，包括以下步骤A、将所述二叉树的L级节点划分成M级流水线；B、M个数据包分时并行地与M级流水线上的二叉树节点进行比较，其中L和M为不小于2的整数，并且L大于M。
步骤A中，所述二叉树节点对应的存储器地址从根节点为1开始，其他子节点的存储器地址依次增加。
所述步骤B中，所述数据包和所述二叉树节点进行比较包括以下步骤B1、根据二叉树节点的存储器地址读所述二叉树节点；B2、获取所述二叉树节点中的关键字段和流ID；B3、比较所述二叉树节点中的关键字段和所述数据包的关键字段；B4、如果所述二叉树节点中的关键字段和所述数据包的关键字段相等，二叉树查找成功，采用所述二叉树节点的流ID，否则产生下一级二叉树节点的地址。
以一级流水线所需要的时间作为固定的周期，不同数据包在同一级流水线中在相同的时间点读取二叉树节点，同一数据包在不同级流水线中在不同的时间点读取二叉树节点。下一级流水线中数据包读取二叉树节点的时间点比上一级流水线中数据包读取二叉树节点晚一个时钟周期。
设置M个寄存器，分别用于存储M个数据包的关键字段。
当所述二叉树需要添加流分类规则，将按照平衡二叉树的编排规则，在相应的节点配置新的规则内容。
将所述二叉树进行备份，形成主二叉树和从二叉树。
当系统发出切换指令，如果主二叉树被使用，将在所述切换指令前最后进入的数据包完成二叉树查找后，主二叉树和从二叉树之间相互切换；如果主二叉树没有被使用，则主二叉树和从二叉树之间相互切换。
采用了本发明的技术方案，将基于二叉树的流分类查找过程划分成若干级流水线，可以同时处理多个数据包的流分类查找，从而降低了数据包流分类查找的平均时间，提高了流分类的吞吐量。另外，本发明采用两块RAM分别作为主从二叉树，流分类查找访问主二叉树，系统流分类规则配置访问从二叉树，从而实现了流分类查找过程中无损伤的动态流分类规则更新。
图1为流分类过程的流程图；图2为用于流分类查找的二叉树结构示意图；图3为基于二叉树的流分类查找流程图；图4为本发明中基于二叉树的流分类查找流程图；图5为主从二叉树切换过程示意图。
具体实施例方式
下面结合附图，通过具体实施方式
对本发明的技术方案作进一步说明。
本具体实施方式
需要两块RAM作为主从二叉树用来存储流分类的规则，RAM的条目数量为2L，L为二叉树节点的级数，取决于流分类规则的数量。条目的内容如表1所示表1
本发明中还需要M个寄存器用来保存M级流水线中数据包的关键字段，格式如表2所示
表2
流分类规则库中的规则数量决定了系统中二叉树的节点数，流分类的数据包吞吐量限制了二叉树查找时每一级流水线内部的时间，从而决定了二叉树查找的流水线级数。假设系统中二叉树存在L级节点，将二叉树查找划分为M级流水线，则一级流水线内部包括N(N＝{L/M}，{}表示向上取整)个二叉树节点的查找，每一个二叉树节点的查找包括读存储器操作、获取节点中存储的数值、关键字段的比较和下一级存储器地址产生等四个步骤时钟周期1二叉树节点读信号和读地址(RAM读)有效；时钟周期2获取二叉树节点中的关键字段和流ID；时钟周期3比较二叉树节点中的关键字段和数据包的关键字段；时钟周期4如果二叉树节点中的关键字段与数据包的关键字段相等，二叉树查找成功，采用该节点的流ID；否则产生下一级二叉树节点的地址。
接收到数据包的关键字段后，则从根节点开始逐级查找平衡二叉树，完成第一级流水线的查找之后，如果查找没有成功，则进入第二级流水线的查找，与此同时，另外一个数据包开始从根节点进行第一级流水线的查找。在第一个数据包完成第二级流水线的查找，同时第二个数据包完成第一级流水线的查找，如果没有查找成功，则第一个数据包进入第三级流水线查找，第二个数据包进入第二级流水线查找，同时第三个数据包开始从根节点进行第一级流水线查找，依此类推，直到所有数据包完成整个二叉树的查找。
最坏情况下(在最后一级节点查找成功)，一次完整的二叉树查找需要在不同的时刻访问二叉树节点存储器L次，采用流水线结构之后，势必会严生M级流水线同时访问存储器的情况，本具体实施方式
中，同一级流水线中不同数据包读取二叉树节点的时间点是相同的，同一数据包在不同级流水线中分别在不同的时间点读取二叉树的节点，从而避免了RAM的访问冲突。
本具体实施方式
提出的采用流水线结构的二叉树流分类查找的流程如图4所示，其主要操作步骤如下(1)第1个数据包进入第1级流水线，将数据包的关键字段保存到关键字段1寄存器中，进行二叉树第1级节点的查找；(2)第1个数据包进行第1级流水线第2级二叉树节点的查找；依次进行；(3)第1个数据包进行第1级流水线中第N级二叉树节点的查找；(4)第1个数据包进入第2级流水线，将关键字段1寄存器中的第1个数据包的关键字段保存到关键字段2寄存器中，进行第2级流水线中二叉树第N+1级节点的查找；同时，第2个数据包进入第1级流水线，将第2个数据包的关键字段保存到关键字段1寄存器中，进行第1级流水线中二叉树第1级节点的查找；依次进行；(5)第1个数据包完成第2级流水线第2*N级节点的查找，将关键字段2寄存器中的第1个数据包的关键字段保存到关键字段3寄存器中，进入第3级流水线查找；同时，第2个数据包完成第1级流水线第N级节点的查找，将关键字段1寄存器中的第2个数据包的关键字段保存到关键字段2寄存器中，进入第2级流水线；第3个数据包进入第1级流水线，将第3个数据包的关键字段保存到关键字段1寄存器中，进行第1级流水线中二叉树第1级节点的查找；依次进行；(6)第1个数据包完成第M-1级流水线的查找，将关键字段M-1寄存器中的第1个数据包的关键字段保存到关键字段M寄存器中，进入第M级流水线的查找；同时，第2个数据包完成第M-2级流水线的查找，将关键字段M-2寄存器中的第2个数据包的关键字段保存到关键字段M-1寄存器中，进入第M-1级流水线；第M-1个数据包进入第1级流水线，将第M-1个数据包的关键字段保存到关键字段1寄存器中，进行第1级流水线第1级节点的查找；依次进行；(7)第1个数据包完成第M级流水线第L级节点(二叉树最后一级节点)的查找，第1个数据包二叉树查找结束；同时，第2个数据包完成第M-1级流水线的查找，进入第M级流水线；第M个数据包进入第1级流水线，进行第1级节点(即根节点)的查找；依次进行；(8)第2个数据包完成第M级流水线第L级节点(二叉树最后一级节点)的查找，第2个数据包二叉树查找结束；同时，第3个数据包完成第M-1级流水线的查找，进入第M级流水线；第M-1个数据包开始第1级流水线第1级节点(即根节点)的查找；依次进行；(9)第M个数据包完成第M级流水线第L级节点(二叉树最后一级节点)的查找，第M个数据包二叉树查找结束。
本具体实施方式
中，为了避免因为流水线结构而导致的RAM访问冲突，第2级流水线的RAM读操作比第1级流水线中的RAM读操作推迟一个时钟周期，第3级流水线的RAM读操作比第2级流水线中的RAM读操作推迟一个时钟周期，第M级流水线的RAM读操作比第M-1级流水线中的RAM读操作推迟一个时钟周期。即同一级流水线中不同数据包读取二叉树节点的时间点是相同的，同一数据包在不同级流水线中分别在不同的时间点读取二叉树的节点。
下面具体说明每一级流水线不同时钟周期所进行的操作。假设二叉树的节点共有12级，分4级流水线，每级流水线完成3级二叉树节点的查找，由于一级二叉树节点的查找需要4个时钟周期，则每级流水线需要12个时钟周期。
第一级流水线的操作包括第1个时钟周期数据包的关键字保存到关键字段1寄存器中；第1级节点RAM读信号有效，地址为1；第2个时钟周期第1级节点RAM读数据有效；第3个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第4个时钟周期如果关键字段相等，则流分类查找成功，否则产生第2级节点的地址2*address或2*address+1，其中address表示上一级节点的地址；第5个时钟周期第2级节点RAM读信号有效；第6个时钟周期第2级节点RAM读数据有效；第7个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第8个时钟周期如果关键字段相等，则流分类查找成功，否则产生第3级节点的地址2*address或2*address+1；第9个时钟周期第3级节点RAM读信号有效；第10个时钟周期第3级节点RAM读数据有效；第11个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第12个时钟周期如果关键字段相等，则流分类查找成功，否则产生第4级节点的地址2*address或2*address+1。
第二级流水线的操作包括第1个时钟周期数据包的关键字保存到关键字段2寄存器中；第2个时钟周期第4级节点RAM读信号有效；第3个时钟周期第4级节点RAM读数据有效；第4个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第5个时钟周期如果关键字段相等，则流分类查找成功，否则产生第5级节点的地址2*address或2*address+1；第6个时钟周期第5级节点RAM读信号有效；第7个时钟周期第5级节点RAM读数据有效；第8个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第9个时钟周期如果关键字段相等，则流分类查找成功，否则产生第6级节点的地址2*address或2*address+1；第10个时钟周期第6级节点RAM读信号有效；第11个时钟周期第6级节点RAM读数据有效；第12个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第12个时钟周期如果关键字段相等，则流分类查找成功，否则产生第7级节点的地址2*address或2*address+1；第二个“第12个时钟周期”表示延迟“第12个时钟周期”1个时钟周期，因为下一级流水线的第1个时钟周期并没有开始读节点，所以可以利用空隙时间进行地址的产生。
第三级流水线的操作包括
第1个时钟周期数据包的关键字保存到关键字段3寄存器中；第2个时钟周期空；第3个时钟周期第7级节点RAM读信号有效；第4个时钟周期第7级节点RAM读数据有效；第5个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第6个时钟周期如果关键字段相等，则流分类查找成功，否则产生第8级节点的地址2*address或2*address+1；第7个时钟周期第8级节点RAM读信号有效；第8个时钟周期第8级节点RAM读数据有效；第9个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第10个时钟周期如果关键字段相等，则流分类查找成功，否则产生第9级节点的地址2*address或2*address+1；第11个时钟周期第9级节点RAM读信号有效；第12个时钟周期第9级节点RAM读数据有效；第12个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第12个时钟周期如果关键字段相等，则流分类查找成功，否则产生第10级节点的地址2*address或2*address+1；第二个“第12个时钟周期”表示延迟“第12个时钟周期”的第1个时钟周期，因为下一级流水线的第1个时钟周期并没有开始读节点，所以可以利用空隙时间进行关键字段的比较；第三个“第12个时钟周期”表示延迟“第12个时钟周期”的第2个时钟周期，因为下一级流水线的第2个时钟周期并没有开始读节点，所以可以利用空隙时间进行地址的产生。
第四级流水线的操作包括第1个时钟周期空；第2个时钟周期数据包的关键字保存到关键字段4寄存器中；第3个时钟周期空；第4个时钟周期第10级节点RAM读信号有效；第5个时钟周期第10级节点RAM读数据有效；第6个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第10个时钟周期如果关键字段相等，则流分类查找成功，否则产生第11级节点的地址2*address或2*address+1；第8个时钟周期第11级节点RAM读信号有效；第9个时钟周期第11级节点RAM读数据有效；第10个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第10个时钟周期如果关键字段相等，则流分类查找成功，否则产生第12级节点的地址2*address或2*address+1；第12个时钟周期第12级节点(最后一级节点)RAM读信号有效；第12个时钟周期第12级节点RAM读数据有效；第12个时钟周期比较二叉树节点中的关键字段和数据包的关键字段；第12个时钟周期如果关键字段相等，则流分类查找成功，否则流分类查找失败。
第二、第三和第四个“第12个时钟周期”分别表示延迟“第12个时钟周期”后的第1个、第2个和第3个时钟周期，因为是最后一级流水线，而且没有进行二叉树节点的读操作，所以不影响二叉树流分类查找的流水线操作。
12级节点的二叉树最大可以包含212-1＝4095个节点，即最大可以支持4095条流分类规则。如果硬件装置的工作频率为100MHz，则一级流水线的处理时间为120ns，在系统满速率的情况下，平均处理一个数据包流分类查找的时间为120ns，每秒钟可以完成8百万个数据包的流分类查找。无论是从流分类规则的数量，还是流分类查找的吞吐量，均能满足一般网络中流分类器的要求。
假设流分类查找时的关键字段为32bit宽，则所需RAM的资源为2×4K×(12+32)＝352Kbit。
为了实现流分类过程中分类规则的动态更新，本具体实施方式
中引入了主从两棵平衡二叉树。数据包流分类时硬件所查找的二叉树为主二叉树，系统需要更新流分类规则时，通过软件配置从二叉树，然后向硬件发出二叉树主从切换指令，把原来的主二叉树变为从二叉树，原来的从二叉树变为主二叉树。换句话说，流分类过程中硬件所查找的永远是主二叉树，系统软件所配置的永远是从二叉树，互不影响，从而保证了二叉树查找过程中无损伤地进行流分类规则更新。
在实际应用过程中，流分类规则的更新一般都是小范围的更新，本发明中二叉树的根节点编址为1，其它子节点依次增加，如果需要添加流分类规则，则只需按照平衡二叉树的编排规则，在相应的节点配置新的规则内容，无需改变存储器的编址方式，将二叉树内容的改变减到最少。
图5是本发明中二叉树主从切换状态流程示意图。如图5所示，主从二叉树切换时，如果没有数据包进行二叉树查找，则切换立刻完成。
如果系统发出切换指令时，有数据包正在进行二叉树的查找，则主二叉树不会立刻切换到从状态，已经开始二叉树查找的数据包依然使用原来的主二叉树，直到切换指令前最后进入的数据包完成二叉树查找之后，主二叉树才切换到从状态。
如果系统发出切换指令时，有数据包正在进行二叉树的查找，则从二叉树也不会立刻切换到主状态，直到有新的数据包开始二叉树的查找，或者直到切换指令前最后进入的数据包完成二叉树查找之后，从二叉树才切换到主状态。
以上所述，仅为本发明较佳的具体实施方式
，但本发明的保护范围并不局限于此，任何熟悉该技术的人在本发明所揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求的保护范围为准。
权利要求
1.一种基于二叉树的流分类查找方法，其特征在于，包括以下步骤A、将所述二叉树的L级节点划分成M级流水线；B、M个数据包分时并行地与M级流水线上的二叉树节点进行比较，其中L和M为不小于2的整数，并且L大于M。
2.根据权利要求1所述的一种基于二叉树的流分类查找方法，其特征在于，步骤A中，所述二叉树节点对应的存储器地址从根节点为1开始，其他子节点的存储器地址依次增加。
3.根据权利要求1所述的一种基于二叉树的流分类查找方法，其特征在于，所述步骤B中，所述数据包和所述二叉树节点进行比较包括以下步骤B1、根据二叉树节点的存储器地址读所述二叉树节点；B2、获取所述二叉树节点中的关键字段和流ID；B3、比较所述二叉树节点中的关键字段和所述数据包的关键字段；B4、如果所述二叉树节点中的关键字段和所述数据包的关键字段相等，二叉树查找成功，采用所述二叉树节点的流ID，否则产生下一级二叉树节点的地址。
4.根据权利要求1或3所述的一种基于二叉树的流分类查找方法，其特征在于，不同数据包在同一级流水线中在相同的时间点读取二叉树节点，同一数据包在不同级流水线中在不同的时间点读取二叉树节点。
5.根据权利要求4所述的一种基于二叉树的流分类查找方法，其特征在于，下一级流水线中数据包读取二叉树节点的时间点比上一级流水线中数据包读取二叉树节点晚一个时钟周期。
6.根据权利要求1或3所述的一种基于二叉树的流分类查找方法，其特征在于，设置M个寄存器，分别用于存储M个数据包的关键字段。
7.根据权利要求1所述的一种基于二叉树的流分类查找方法，其特征在于，当所述二叉树需要添加流分类规则，将按照平衡二叉树的编排规则，在相应的节点配置新的规则内容。
8.根据权利要求1或7所述的一种基于二叉树的流分类查找方法，其特征在于，将所述二叉树进行备份，形成主二叉树和从二叉树。
9.根据权利要求8所述的一种基于二叉树的流分类查找方法，其特征在于，当系统发出切换指令，如果主二叉树被使用，将在所述切换指令前最后进入的数据包完成二叉树查找后，主二叉树和从二叉树之间相互切换；如果主二叉树没有被使用，则主二叉树和从二叉树之间相互切换。
全文摘要
本发明公开了一种基于二叉树的流分类查找方法，将所述二叉树的L级节点划分成M级流水线；M个数据包分时并行地与M级流水线上的二叉树节点进行比较，其中L和M为不小于2的整数，并且L大于M。采用了本发明的技术方案，将基于二叉树的流分类查找过程划分成若干级流水线，可以同时处理多个数据包的流分类查找，从而降低了数据包流分类查找的平均时间，提高了流分类的吞吐量。另外，本发明采用两块RAM分别作为主从二叉树，流分类查找访问主二叉树，系统流分类规则配置访问从二叉树，从而实现了流分类查找过程中无损伤的动态流分类规则更新。
文档编号H04L12/46GK101022407SQ20071000567
公开日2007年8月22日 申请日期2007年3月13日 优先权日2007年3月13日
发明者滕焕勇 申请人:中兴通讯股份有限公司
最新回复(0)