用于规则的笛卡尔乘积的有效存储器利用的制作方法

1.本发明总体上涉及通信网络，并且具体涉及基于分组报头的通信分组动作的有效确定。


背景技术：

2.在通信网络中，根据分组的一个或更多个报头字段的内容，可以将动作应用于通信分组。
3.在“基于期望最大化聚类的分层特里结构分组分类算法(hierarchical trie packet classification algorithm based on expectation-maximization clustering)”中，布隆迪(bi)和扎霍(zaho)(2017年7月13日；doi.org/10.1371/journal.pone.0181049)作者断言能够处理大规模规则集的分组分类算法是迫切需要的，并解释了基于分层特里结构(trie)的分组分类算法由于它们广泛的实际使用而变得重要，尽管分层特里结构有缺点，诸如回溯和空节点的存在。接下来作者提出一种基于期望最大化聚类(expectation-maximization clustering，htemc)的新的分组分类算法，既采用特里结构路径压缩来消除回溯，又解决了特里结构更新效率低的问题，大大提高了算法的性能。
4.在“可扩展分组分类(scalable packet classification)”，barboscu和varghese(ieee/acm网络汇刊，vol.13，no.1，2005年2月)中，作者断言，随着过滤器数据库在尺寸上增长，以文献报道的分组分类在时间或空间上规模较差，而硬件解决方案(如tcam)不扩展到大分类器。论文试图利用这种观察来产生称为聚合位向量(aggregated bit vector，abv)的可扩展分组分类方案，该方案采用位向量检索算法(bv)(其采用线性时间)并且将两个新想法——位图的递归聚合和过滤器重排——添加到abv，该abv对于许多数据库可能采用对数时间。
5.最后，例如，在“基于态cam的高级分组分类算法(algorithms for advanced packet classification with ternary cams)”马哈德万(lakshminarayanan)等，美国计算机协会数据通信专业组(acm sigcomm)2005中描述了提高分组分类中tcam的效率的技术。


技术实现要素：

6.这里描述的本发明的实施例提供一种网络设备，该网络设备包括一个或更多个端口、动作选择电路和分组处理器。所述一个或更多个端口用于通过网络交换分组，每个分组包括具有至少第一报头字段和第二报头字段的分组报头。所述动作选择电路用于：对于给定分组，基于所述给定分组的所述第一报头字段来确定第一检索关键字，以及基于所述给定分组的所述第二报头字段来确定第二检索关键字，将所述第一检索关键字与第一组比较值进行比较，以响应于所述第一检索关键字与所述第一组中的第一比较值之间的匹配来输出多元素向量，通过级联所述第二检索关键字和所述多元素向量来生成合成检索关键字，
将所述合成检索关键字与第二组比较值进行比较，并且响应于所述合成检索关键字与所述第二组中的第二比较值之间的匹配来输出用于应用于所述给定分组的动作指示符。分组处理器响应于所述分组报头来处理所述分组，包括响应于所述动作指示符将动作应用于所述给定分组，所述动作指示符由比较电路输出。
7.在一些实施例中，所述多元素向量包括独热向量，所述独热向量具有标记元素，所述标记元素在所述独热向量中的位置指示在所述第一组中被发现与所述第一检索关键字匹配的所述第一比较值的索引。在示例性实施例中，所述第二组中的所述第二比较值包括(i)与所述第二报头字段相对应的第二值，以及(ii)比较向量，每个比较向量包括：在(i)对应的第二值和(ii)对应的第一比较值的组合保证输出所述动作指示符的一个或更多个位置中的“不关心(do not care)”值；以及在一个或更多个其他位置中的非设置值。
8.在一些实施例中，所述多元素向量被定义为使得：设置所述多元素向量的具有与所述第二组中的与所述第二检索关键字匹配的第二比较值的索引相对应的索引的一个或更多个元素；以及未设置所述多元素向量的具有与所述第二组中的与所述第二检索关键字不匹配的第二比较值的索引相对应的索引的一个或更多个元素。在示例实施例中，所述第二组中的所述比较值包括：(i)第二检索关键字值，以及(ii)多元素向量比较值，其中在指示第一检索关键字值的索引的位置中的一个或更多个元素被设置，并且在其他位置中的元素被设置为“不关心”值。
9.在公开的实施例中，所述第一比较值和所述第二比较值中的至少一个包括“不关心”值。在一些实施例中，多元素向量包括二进制元素。在一个实施例中，所述动作选择电路包括三态内容寻址存储器(tcam)，用于存储所述第一组比较值和所述第二组比较值中的一个或两个。
10.根据本文描述的实施例，还提供了一种网络设备中的方法。该方法包括通过网络交换分组，每个分组包括具有至少第一报头字段和第二报头字段的分组报头。对于给定分组，基于所述给定分组的第一报头字段来确定第一检索关键字，以及基于所述给定分组的第二报头字段来确定第二检索关键字。将所述第一检索关键字与第一组比较值进行比较，并且响应于所述第一检索关键字与所述第一组中的第一比较值之间的匹配来输出与所述第一比较值相对应的多元素向量。通过级联所述第一检索关键字和所述多元素向量来生成合成检索关键字。将所述合成检索关键字与第二组比较值进行比较，并且响应于所述合成检索关键字与所述第二组中的第二比较值之间的匹配来输出用于应用于所述给定分组的动作指示符。响应于所述分组报头来处理所述分组，包括响应于所述动作指示符将动作应用于所述给定分组，所述动作指示符由比较电路输出。
11.根据本文描述的实施例，还提供了一种用于确定应用于网络设备中的分组的动作的方法。所述方法包括：对于正在所述网络设备中被处理的给定分组，基于所述给定分组的第一报头字段来确定第一检索关键字，以及基于所述给定分组的第二报头字段来确定第二检索关键字。将第一检索关键字与第一组比较值进行比较，并且响应于匹配而输出多元素向量。通过级联第一检索关键字和多元素向量来生成合成检索关键字。将合成检索关键字与第二组比较值进行比较，并且响应于匹配来输出用于应用于给定分组的动作指示符。
附图说明
12.通过以下结合附图对实施例的详细描述，将更充分地理解本发明，在附图中：
13.图1是示意性地示出了根据本发明的实施例的网络设备的框图；
14.图2是根据本发明的实施例的示例双报头字段规则集表；
15.图3是示意性地示出了根据本发明的实施例的具有成员资格向量规则(rule-with-membership-vector)类型的动作选择电路(action select circuit，asc)的框图；
16.图4a是示意性地示出了根据本发明实施例的用于编程具有成员资格向量规则类型的asc的比较电路的方法的流程图；
17.图4b是示意性地示出了根据本发明的实施例的用于确定动作的具有成员资格向量规则的方法的流程图；
18.图5是示意性地示出了根据本发明的实施例的向量成员资格(vector-membership)类型的asc的框图；
19.图6a是示意性地示出了根据本发明的实施例的用于对向量成员资格类型的asc的比较电路进行编程的方法的流程图；
20.图6b是示意性地示出了根据本发明的实施例的用于确定动作的向量成员资格方法(vector-membership method)的流程图；以及
21.图7是示意性地示出了根据本发明的实施例的选择动作所需的比较位的总数的曲线图。
具体实施方式
22.概述
23.诸如网络交换机/路由器及其他的网络设备通过通信网络(例如，以太网或infiniband
tm
)传送分组。根据转发/路由规则，网络设备通常通过入口端口从网络接收分组并且通过出口端口将分组转发至网络。
24.网络设备可包括分组处理器，该分组处理器被配置为根据一组规则处理和路由分组，该组规则通常基于存储在分组报头中的值(在tcp/ip示例中，报头包括五个报头字段，包括源地址字段、入口端口字段、协议字段、目的地址字段和出口端口字段；统称为l4 5元组)。
25.该组规则(有时称为动作表)包括一个或更多个动作，以及对于每个动作，该动作应当被应用到的分组的报头的相应值。有时，为每条规则指定的分组报头字段的值包括“不关心”字段(通常由“x”符号指定)；例如，如果给定动作应当被应用于从给定端口进入的所有分组，而不管其他报头字段的值如何，则相应的规则将包括入口端口报头字段处的给定端口，以及“不关心”所有其他报头字段。
26.通常，一些规则被定义为单字段规则的笛卡尔乘积(cartesian product)，并且虽然在单字段中给定规则的值的数目是可管理的，但是笛卡尔乘积的数目可能极高并且减慢分组处理和/或需要大量电路。当使用三态内容寻址存储器(tcam)完成规则匹配时，tcam大小可能非常大和/或不是所有规则可能都适合tcam。(tcam具有同时搜索所有规则的优点，存在面积大、功耗大的缺点。)
27.本文公开的根据本发明的实施例提供一种基于分组报头的值有效地定位规则并
确定动作的设备和方法。在实施例中，动作选择电路(asc)接收分组报头的两个或更多个字段，并响应于报头字段的内容和预编程的规则集来提取动作。
28.在一个实施例中，asc包括第一比较电路，其将第一分组报头字段与一列比较值相比较，并输出相应的中间结果输出向量。asc组合输出向量和分组报头的第二字段，以生成合成检索关键字，该合成检索关键字被输入到包括第二列比较值的第二比较电路；所述第二比较电路然后输出对应于所述第一分组报头字段和第二分组报头字段的动作。
29.在一些实施例中，所述第一比较电路中的不同比较值被指派成员id，且所述中间结果输出向量是所述成员id的独热(one-hot)表示。第二比较电路将独热表示与其中对应于动作的所有位位置被设置为“不关心”值的字段进行比较，而其他位位置在逻辑-0处。
30.在其他实施例中，第二比较电路包括第一检索列，其包括第二报头字段的检索值。检索值被分配成员id，其以独热格式表示在第二比较电路的第二检索列中。独热表示包括在根据成员id的位置中的单个设置元素，所有其他元素被设置为“不关心”。asc将来自第一比较电路的临时输出向量与第二检索列进行比较，且将第一检索列与第二报头字段进行比较。当在两个检索字段中存在匹配时(在相同行中)，asc指示动作。
31.系统描述
32.诸如网络交换机和路由器之类的网络设备通过入口端口从通信网络(例如，以太网或infiniband
tm
)接收分组，并且通过出口端口将分组转发到网络。(在下文的公开中，我们将主要指交换机和路由器；然而，本发明不限于交换机和路由器，并且可以用于所有合适的网络设备，包括网络接口控制器(nic)、主机信道适配器(hca)、网络使能图形处理器单元(gpu)、数据处理单元(dpu——有时也称为“智能nic”)、以及耦合至通信网络的任何其他计算设备。
33.通常，网络设备包括分组处理电路，该分组处理电路根据网络设备设置的一组规则将处理动作应用于入口分组。一些规则是指分组报头的内容；例如，规则可以表明网络设备将总是丢弃具有等于预设值的源ip端口的入口分组(例如，为了安全)。
34.分组报头可包括多个报头字段(例如，五个报头字段，用于定义源ip地址、源端口、目的地ip地址、目的地端口和协议id)；实际上，虽然一些报头字段可以相对较小，但是其他字段可以包括32位或更多，并且因此，可能的报头组合的数目可以是巨大的。
35.该组规则有时将动作与多个报头字段中的值的组合相关联，例如，丢弃源ip地址＝x和目的地端口＝y的分组，而不考虑其他报头字段的内容。未按规则校验的字段被称为“不关心字段(do not care field)”，并且由x表示。在一些实施例中，对于其中的一些位，还可以在校验后的字段中使用“不关心”值。例如，对于源ip地址报头字段，格式为num1.num2.num3.num4(4个十进制数，由点分隔)，可应用以下规则：“如果字段值为138.100.x.7，则丢弃分组”。该规则将被应用于138.100.2.7、138.100.4.7的字段值，但是不将被应用于138.101.2.7和138.100.2.6的字段值。
36.在实施例中，网络设备包括动作选择电路，以基于分组报头的字段和基于预编程的规则集有效地确定动作。
37.图1是示意性地示出了根据本发明的实施例的网络设备100的框图。网络设备包括：端口102(可以包括入口端口和出口端口)，用于通过诸如以太网、infiniband
tm
或任何其他合适的网络的传送分组；报头提取器104，用于提取入口分组的报头字段；动作选择电路
(asc)106，其被配置成选择要在入口分组上执行的动作(例如，转发或丢弃)；以及分组处理器108，其用于响应于所指示的动作来处理分组(为了概念清晰起见，未示出网络设备100的其他组件)。
38.根据图1所示的示例实施例，asc 106包括第一比较电路110和第二比较电路112。第一比较电路110将分组报头的第一报头字段与第一组检索值进行比较，并且作为响应，输出临时检索结果。第二比较电路将包括第二报头字段和临时检索结果的合成检索值与第二组检索值进行比较，并向分组处理器指示动作。
39.需要说明的是，在实际应用中，报头字段的数目往往大于2，其他规则可以与其他报头字段相关联。在实施例中，这些附加规则可由其他比较电路处理，包括(但不限于)互连的比较电路对。
40.报头字段组合的数量(即使仅针对两个报头字段)可能非常大；因此，对由两个报头字段的组合定义的规则的检索可能消耗相当大量的硅面积(和大量的功率)。在实施例中，如果通过两个单独的比较电路完成检索，则可以显著减小面积和功率，其中，第一比较电路的临时结果用作第二比较电路的输入。在一些实施例中，当字段中的一个字段基本上较小时，较小的字段可由向量表示。
41.在一些实施例中，第一比较电路和/或第二比较电路包括一个或更多个三态内容寻址存储器(tcam)，所述一个或更多个三态内容寻址存储器被配置成用于比较输入数据以比较存储在其中的值；在实施例中，所述第一比较电路和所述第二比较电路都在单个tcam中；首先访问所述tcam以执行所述第一比较电路的比较功能，然后访问所述tcam以执行所述第二比较电路的比较功能；所述tcam可将所述临时结果存储在寄存器中(例如，所述tcam外部)。
42.应当注意，虽然根据图1所示的示例实施例，asc 106基于入口分组报头选择要应用于入口分组的动作，但是在替换实施例中，asc 106可基于出口分组的报头来选择要应用于出口分组的动作。在其他实施例中，asc可以选择要对入口分组和出口分组两者应用的动作。
43.在一些实施例中，网络设备100进一步包括处理器，该处理器监测和配置各个网络设备电路。在其他实施例中，处理器可以是外部的，通过接口(例如，外围组件互连高速或pcie)连接到网络设备。
44.通过示例的方式引用图1所示的以及上面描述的网络设备100和asc106的配置。在替代实施例中可使用其他配置。例如，在实施例中，可以使用多个比较电路对。在一些实施例中，第二比较电路108选择的动作可以被输入到其他电路，其他电路可以例如仅在满足一些其他条件的情况下将动作传送到分组处理器。
45.图2是根据本发明的实施例的示例双报头字段规则集表200。应当注意，典型的规则集表显著大于表200，并且可以达到数千和数万个规则。示例规则集200仅为了实施例的概念清晰而被引用，这将在下文公开。
46.规则集表200包括目的地端口列204、目的地ip地址列206和动作列208。每一列包括与多个规则相对应的多个行。所述目的地端口列的行包括与所述目的地端口报头字段有关的检索值，而所述目的地ip地址列的行包括与所述目的地ip地址报头字段有关的检索值。如果对于任何给定行，目的地ip地址检索值和目的地端口检索值两者都匹配相应报头
字段的值，则网络设备将从动作列208中选择对应于给定行的动作。
47.在一些实施例中，动作可以具有二进制值——例如，转发(逻辑-1)或丢弃(逻辑-0)。在这样的实施例中，可以从规则集表中跳过对应于逻辑值之一的行，并且可以默认选择对应于逻辑电平的动作。例如，在表200中，如果下降是转发的互补值(即，要采取的动作总是转发或丢弃)，则表可以包括将行与仅转发动作进行比较并且将不包括与丢弃有关的行；对于较小的表大小，应在表中存储规则数较少的逻辑值，并默认选择规则数较多的逻辑值。(实际上，可以消除二进制值动作的动作列。)
48.图2中所示的和本文所述的规则集表200是仅为了概念清晰而引用的示例实施例。在替代性实施例中可以使用其他规则集表，例如具有不同的(通常大得多的)规则集大小并且属于不同的报头字段。在实施例中，比较值可包括与对应报头字段位的值无关地匹配的“不关心”值。在又一实施例中，可能的动作的数量可以多于两个。
49.定义
50.在本文的描述中，我们使用了以下定义和解释的若干术语：
51.动作：分组处理器通常响应于分组报头而应用于给定分组的操作。动作包括转发、丢弃和许多其他动作。
52.动作选择电路(例如，asc 106，图1)：响应于分组报头选择动作的电路。在实施例中，asc包括两个或更多个比较电路。
53.报头字段：分组报头的功能部分，例如，目的地ip地址、目的地端口等。典型的报头可包括例如五个报头字段。在下文的描述中，我们有时将提及“第一报头字段”和“第二报头字段”；然而，这些枚举不一定与报头字段在报头内的位置有关，且将用作通用报头字段识别符。
54.检索关键字：与预设的比较数据进行比较的多元素信号。在实施例中，检索关键字可以包括一个或更多个报头字段；在其他实施例中，检索关键字根据报头字段建立(例如，关键字可以是一个或更多个报头字段的签名)；在实施例中，检索关键字可以是合成检索关键字(下文定义)。
55.比较值：与检索关键字比较的一组预设的比较数据。例如，图2的列204中的一组目的地端口号{2，6，3，3，6，31}。
56.比较列：与单个检索关键字比较的一组比较值。可能存在与多于一个比较关键字进行比较的多于一个比较列。例如，列204、206(图2)。
57.数据列：与一个或更多个比较列(例如，图2的数据列208)中的对应的比较值相关联的一组数据元素。
58.比较行：行元素，包含比较列的单个比较值(或者，如果存在多于一个比较列，则来自每个比较列的单个比较值)和对应的数据列元素。
59.输出向量：检索关键字(search key)等于比较值(或者，如果存在多于一个比较列，则所有关键字等于对应的比较值)的比较行的数据元素。在一些实施例中，输出向量可指示动作；在其他实施例中，输出向量为临时比较结果。
60.比较电路：用于将一个或更多个输入检索关键字与一个或更多个相应的比较列进行比较并且用于输出输出向量(output vector)的电路。在一些实施例中，比较电路可以包括tcam。
61.合成检索关键字：包括报头字段(或报头字段的表示)和附加检索数据的检索关键字；在一些实施例中，由第一比较电路生成的输出向量是输入到第二比较电路的合成检索关键字的附加数据。
62.成员组：比较列中的所有唯一关键字值的组。例如，在列204(图2)中，k1成员组是集合{2，3，6，31}，而k2成员组是集合{138.100.17.07，138.100.17.09，138.100.17.43，138.100.17.63}。
63.成员id：分配给成员组的每个元素的id号。在示例实施例中，最小成员id是0，被分配给相关关键字的最小值；下一个成员id是1，被分配给下一个最小关键字值，等等。例如，对于k1成员组{2，3，6，31}，成员id号0，1，2，3分别被分配给2，3，6，31的k1值(其他一对一映射可以在备选实施例中使用)。
64.向量成员资格：当asc响应于给定的第一报头字段值和一组第二报头字段值中的任何一个而选择给定的动作时，该组第二报头字段值的成员id被称为给定的第一报头字段值的向量成员资格。
65.独热向量：多元素向量，具有一个设定元素，所有其他元素不设定。在一些实施例中，未设定元素采用逻辑-0值。
66.示例动作选择电路配置和关联的方法
67.接下来我们将继续描述根据本发明的实施例的两种类型的asc：具有成员资格向量规则类型以及向量成员资格类型。在这两种类型中，asc包括两个互连的比较电路；然而，这两种类型具有不同的比较电路配置和不同的临时检索结果结构。
68.在实施例中，检索列可以包括“不关心”位，其始终匹配相应的输入检索关键字位。在一些实施例中(例如，当检索电路包括tcam或算法tcam时)，多于一行的检索值可以与输入的检索关键字匹配；在实施例中，比较电路被配置为将优先级分配给数据规则(例如，根据行的顺序)，并且如果多于两行匹配，则输出与最高优先级规则相对应的数据。
69.具有成员资格向量规则asc
70.图3是示意性地示出了根据本发明的实施例具有成员资格向量规则类型asc 300的框图。asc 300包括第一比较电路302和第二比较电路304，第一比较电路302接收对应于目的地ip地址报头字段的检索关键字k2并输出临时检索结果独热k2_vector，第二比较电路304接收包括对应于目的地端口报头字段的关键字k1和独热k2_vector的合成检索关键字。
71.第一比较电路302包括检索电路306和二进制到独热解码器308。检索电路将检索关键字k2(例如，连接至分组的目的地ip地址报头字段)与比较列310进行比较，并且响应于匹配，输出包括k2-id列表的对应的数据列312值至二进制到独热解码器308，二进制到独热解码器308然后将k2 id转换为独热k2_vector临时检索结果。
72.第二比较电路304包括存储k1的比较值(例如，分组报头的目的地端口字段)的比较列k1314、存储k2-向量的比较值的比较列316以及存储在k1列314和k2-向量列316的对应行中找到匹配的情况下要(例如，由分组处理器)执行的所需分组动作的数据列318。比较列316存储当需要动作时的“不关心”值(如果比较列314中的对应行指示匹配)以及不需要动作的逻辑-0。k1和k2-向量的级联是第二比较电路的合成检索关键字。
73.(根据示例实施例，asc 300仅指示单个动作；因此，不需要动作列318-如果在任何
比较行中存在匹配，则第二比较电路将指示转发。)
74.如果我们检查例如第二比较电路的第二行，将更全面地理解以上描述。根据第二行，如果k1＝3并且k2向量匹配0xx0的值(即，在位0和3中为0，并且在位1和2中为0或1)，则将指示转发动作。表200(图2)定义，如果k1＝3并且k2为138.100.17.09或138.100.17.43，则第二比较电路应当指示转发动作。
75.我们现在看第一比较电路。如果k2＝138.100.17.09，则k2 id＝1(第二成员，从0开始)，并且k2向量将读取0010(第二位组)；如果k2＝138.100.17.43，则k2 id＝2并且k2向量＝0100。在两种情况下，位0和位3处于0，并且位1或位2处于逻辑1。换言之，如果k1＝3并且k是2138.100.17.09或138.100.17.43，k1的第二行和k2向量的第二行将匹配，并且asc将指示转发动作。
76.在实施例中，具有成员资格向量规则类型的动作选择电路300中的检索单元的总数是：
77.n*nw+m*(mw+n)
78.并且数据位的数量(例如，k2列310)是：
79.n*logn
80.其中n是k2个不同值的数目，nw是k2个条目的宽度(以位为单位)，m是k1个不同值的数目，并且log操作是以2为底，向上取整。
81.图3中示出了并在上文中描述的动作选择电路300的配置是仅为了概念清晰而引用的示例。在替代实施例中可使用其他配置。例如，在一些实施例中，检索两个以上报头字段(例如，k1至kn)；n-1个第一比较电路302输出与报头字段2至n有关的临时独热检索结果向量，这些向量被输入到第二比较电路304；除了k1个比较列314之外，第二比较电路包括n-1个比较列以比较从n-1个第一比较电路输出的向量。
82.在其他实施例中，比较电路302的数据列包括独热k2向量而不是k2id。这将使数据列更宽(在图3所示的示例中——4位而不是2位)，但是将消除对二进制到独热电路308的需要。
83.图4a是示意性地示出了根据本发明的实施例的用于编程具有成员资格向量规则类型的asc的比较电路的方法的流程图400。流程图由处理器110(图1)执行。该方法包括编程第一比较电路和第二比较电路，其具有对应于第一报头字段和第二报头字段(在当前上下文中，第一报头字段是指目的地端口，而第二报头字段是指目的地ip地址(在替代实施例中可以使用其他报头字段))的比较值。
84.该流程图开始于填充第一比较电路检索列(fill first compare circuit search column)操作402，其中处理器用与第二报头字段的报头字段值有关的比较值的列表填充第一比较电路的比较列。接下来，处理器进入填充第一比较电路数据列(fill-first-compare-circuit-data-column)操作404，其中处理器用输出向量填充第一比较电路的数据列，输出向量包括比较列中对应值的id(例如，第一唯一比较值的id可以是0，第二唯一比较值的id可以是1，等等)。如果在比较列中存在n个唯一比较值，则每个输出向量的位数将是log2n，向上取整至下一个整数(注意，独热向量的大小将是2n)。
85.在填充第二比较电路第一比较列(fill second-compare-circuit-first-compare-column)操作406，处理器用第一报头字段的值填充第二比较电路的第一比较列
(在一些实施例中，比较值可以包括“不关心”值)。接下来，在填充第二比较电路第二检索字段(fill second-compare-circuit-second-search-field)操作408，处理器用将包括在与k2成员匹配的位置中的“不关心”元素的行填充第二比较电路的第二比较列，并且用逻辑-0填充其他元素(例如，在图3中，行2，因为k1＝3和k2-id＝1或k2-id＝2的组合导致转发(forward)动作，处理器用0xx0填充第二比较电路的第二检索字段)。
86.最后，在填充数据字段列(fill data field column)操作410中，处理器用对应于匹配的比较行中的k1和k2的组合的动作填充数据列。
87.为了概念清晰，通过示例的方式引用图4a中示出并且在上文中描述的流程图400的配置。在替代实施例中，操作的顺序可以不同和/或操作中的一些可以并发地进行。在一些实施例中，当添加新规则或移除现有规则时，可通过修改不同比较列和数据列中的值来递增地进行asc的设置。
88.图4b是示意性地示出了根据本发明的实施例的用于确定动作的具有成员资格向量规则的方法的流程图450。该流程图由asc 106(图1)执行，并且包括访问被预设(例如，根据图4a的流程图400)的两个比较电路。
89.该流程图开始于访问第一比较电路(access first compare circuit)操作452，其中asc使用k2(第二报头字段的内容)作为检索关键字访问第一比较电路。在一些实施例中，第二报头字段的签名被用作检索关键字。
90.接下来，在获取k2-id(get k2-id)操作454，asc从第一比较电路读取匹配的k2值的id。如上所述(参考图4a)，k2 id的位数目是log2n，其中n是第一比较电路的检索列中的唯一检索值的数目，并且log2n被舍入到下一个更高的整数。
91.asc接下来在转换到独热(convert-to-one-hot)操作456处将k2 id转换为独热向量，其中设置一个位(例如，在逻辑-1处)，且清除所有其他位(例如，逻辑-0)。
92.接下来，在生成合成检索向量(generate composite search vector)操作458，asc将独热k2向量与k1级联——第一报头字段(或者，在实施例中，第一报头字段的签名)的内容，以生成合成检索关键字；然后，在接入第二比较电路操作460，asc使用合成检索向量检索第二比较电路。最后，在获取动作操作462，asc从第二比较电路读取匹配k1和k2的动作。
93.在图4b中示出并且在上文中描述的流程图450的配置是为了概念清晰而引用的示例配置。在替代实施例中可使用其他配置。例如，在一些实施例中，第一比较电路不包括二进制至独热解码器，相反，第一比较电路的数据列包括解码的向量值(并且在这种情况下，检索电路306是第一比较电路304的唯一组件，其可以被丢弃)。
94.在其他实施例中，在第一比较电路和第二比较电路中可以使用其他报头字段；在实施例中，asc在操作462中获得动作的编码(例如，“1”用于传输(transfer)，“0”用于丢弃(drop))。在其他实施例中，第二比较电路的输出可以与其他比较电路的输出耦合，以生成所需动作，并且在其他实施例中，第二比较电路的输出可以用于生成另一合成检索向量，以访问更多比较电路。
95.向量成员资格asc
96.图5是示意性地示出了根据本发明的实施例的向量成员资格类型asc 500的框图。asc 500包括第一比较电路502和第二比较电路504，第一比较电路502接收对应于目的地端
compare-column)602，其中处理器用与第一报头字段的报头字段值有关的比较值的列表填充第一比较电路的比较列。
110.接下来，处理器进入填充第一比较电路数据列(fill-first-compare-circuit-data-column)操作604，其中处理器用成员资格输出向量填充第一比较电路的数据列，其中当第一报头字段匹配k1比较列510中的对应k1成员并且第二报头字段匹配对应于成员资格向量中的元素位置的k2成员时，如果asc应当对分组应用动作，则设置输出向量的每个元素。
111.处理器然后进入填充第二比较电路第一比较列(fill-second-compare-circuit-first-compare-column)操作606，并用与第二报头字段的报头字段值有关的比较值的列表填充第二比较电路的比较列。接下来，在填充第二比较电路第二比较列(fill-second-compare-circuit-second-compare-column)操作608，处理器用k2列的独热成员id表示填充第二比较电路的第二比较列，其中独热向量的未设置元素处于“不关心”值。例如，如果138.110.17.07为第一个k2成员值，则对应的独热向量为xxx1；如果第三成员值为138.110.17.43，则向量为x1xx。
112.最后，在填充第二比较电路数据列(fill-second-compare-circuit-data-column)操作610中，处理器用要应用于分组的数据(对应于k1值和k2值)填充第二比较电路的数据列。在实施例中，该动作可以是仅转发(或者如果未选择转发动作，则为丢弃)，并且操作610可以被跳过。
113.为了概念清晰，通过实例引用图6a中示出并且在上文中描述的流程图600的配置。在替代实施例中，操作的顺序可以不同和/或操作中的一些可以并发地进行。在一些实施例中，当添加新规则或移除现有规则时，可通过修改不同检索和数据列中的值来递增地进行asc的设置。
114.图6b是示意性地示出了根据本发明的实施例的用于确定动作的向量成员资格方法的流程图650。该流程图由asc 106(图1)执行，并且包括在预先设置的两个比较电路中检索(例如，根据图6a的流程图600)。
115.流程图开始于检索第一比较电路(search first compare circuit)操作652，其中asc使用k1(第一报头字段的内容)作为比较关键字来检索第一比较电路。在一些实施例中，第一报头字段的签名用作比较关键字。
116.接下来，在获取输出成员资格向量(get output-membership-vector)操作654，asc读取成员向量，包括针对每个k2成员的设置比特，该设置比特在与对应的k1值一致时将导致动作。
117.asc接下来，在生成合成检索向量(generate composite search vector)操作656处，将k2成员资格向量与k2——第二报头字段的内容(或者，在实施例中，第二报头字段的签名)级联。接下来，在检索第二比较电路(search second compare circuit)操作658，asc使用合成检索向量检索第二比较电路。最后，在获取动作(get action)操作669，asc读取对应于报头字段组合{k1，k2}的动作。
118.在图6b中示出了并且在上文中描述的流程图650的配置是为了概念清晰而引用的示例配置。在替代实施例中可使用其他配置。例如，在一些实施例中，可以在第一和第二比较电路中使用其他报头字段；在实施例中，asc在操作660中获取动作的编码(例如，“1”用于
传输，“0”用于丢弃)。在其他实施例中，第二比较电路的输出可以与其他比较电路的输出耦合，以生成所需动作，并且在其他实施例中，第二比较电路的输出可以用于生成另一合成检索向量，以访问更多比较电路。
119.图7是示意性地示出了根据本发明的实施例的选择动作所需的比较位的总数的曲线图700。该图包括曲线图702和曲线图704，曲线图702显示了具有成员资格规格向量类型的asc中的比较位的数量，曲线图704指示当asc是成员资格向量类型时的比较位的数量。在两个图中，较小报头字段中的成员数量是较大报头字段中的成员数量的0.1％。可以看出，根据实施例，当较大的报头字段(例如，目的地ip地址)包括100000个成员(因此，较小的(例如，目的地端口id)包括100000*0.1％＝100个成员)时，第一和第二比较电路中的比较位的总数对于向量成员资格是10000000，并且对于具有成员规则向量asc是20000000。应当将这些数字与所有组合的完全比较所需的100*100000＝100000000个比较位进行比较。
120.包括规则表200、具有成员资格向量规则类型asc 300、成员资格向量类型asc 106(包括相应的比较电路302、304、502、504、用于比较电路编程的方法400、600、用于根据报头字段确定动作的方法450、650)的网络设备100的配置是纯粹为了概念清晰而示出的示例配置、表和方法。在替代性实施例中可以使用任何其他合适的配置、表和方法。
121.在各种实施例中，上文描述的各个动作选择和/或组id选择任务可以通过硬件、通过软件、或通过硬件和软件的组合来执行。
122.在各种实施例中，网络设备100的不同电路(包括各种asc和各种比较电路)可使用合适的硬件(诸如一个或更多个专用集成电路(asic)或现场可编程门阵列(fpga)或asic和fpga的组合)来实现。
123.处理器110和分组处理器108通常包括一个或更多个通用处理器，其以软件编程以执行分组处理功能。软件可以例如通过网络以电子形式下载到处理器，或者它可以替换地或附加地被提供和/或存储在非暂时性有形介质上，诸如磁性、光学或电子存储器。
124.因此，应当理解，上述实施例是通过举例的方式引用的，并且本发明不限于在上文中具体示出和描述的内容。相反，本发明的范围包括在上文中描述的各种特征的组合和子组合，以及在阅读以上描述时本领域技术人员会想到的并且在现有技术中未公开的其变化和修改。通过引用结合在本专利申请中的文献被认为是本技术的组成部分，除了在这些并入的文献中以与本说明书中明确或隐含的定义相冲突的方式定义任何术语的程度上，仅应当考虑本说明书中的定义。

技术特征：
1.一种网络设备，包括：一个或更多个端口，用于通过网络交换分组，每个分组包括具有至少第一报头字段和第二报头字段的分组报头；动作选择电路，用于：对于给定分组，基于所述给定分组的所述第一报头字段来确定第一检索关键字，以及基于所述给定分组的所述第二报头字段来确定第二检索关键字；将所述第一检索关键字与第一组比较值进行比较，并且响应于所述第一检索关键字与所述第一组中的第一比较值之间的匹配来输出多元素向量；通过级联所述第二检索关键字和所述多元素向量来生成合成检索关键字；以及将所述合成检索关键字与第二组比较值进行比较，并且响应于所述合成检索关键字与所述第二组中的第二比较值之间的匹配来输出用于应用于所述给定分组的动作指示符；以及分组处理器，用于响应于所述分组报头来处理所述分组，包括响应于所述动作指示符将动作应用于所述给定分组，所述动作指示符由比较电路输出。2.根据权利要求1所述的网络设备，其中所述多元素向量包括独热向量，所述独热向量具有标记元素，所述标记元素在所述独热向量中的位置指示在所述第一组中被发现与所述第一检索关键字匹配的所述第一比较值的索引。3.根据权利要求2所述的网络设备，其中所述第二组中的所述第二比较值包括(i)与所述第二报头字段相对应的第二值，以及(ii)比较向量，每个比较向量包括：在(i)对应的第二值和(ii)对应的第一比较值的组合保证输出所述动作指示符的一个或更多个位置中的“不关心”值；以及在一个或更多个其他位置中的非设置值。4.根据权利要求1所述的网络设备，其中所述多元素向量被定义为使得：设置所述多元素向量的具有与所述第二组中的与所述第二检索关键字匹配的第二比较值的索引相对应的索引的一个或更多个元素；以及未设置所述多元素向量的具有与所述第二组中的与所述第二检索关键字不匹配的第二比较值的索引相对应的索引的一个或更多个元素。5.根据权利要求4所述的网络设备，其中：所述第二组中的所述比较值包括：(i)第二检索关键字值，以及(ii)多元素向量比较值，其中在指示第一检索关键字值的索引的位置中的一个或更多个元素被设置，并且在其他位置中的元素被设置为“不关心”值。6.根据权利要求1所述的网络设备，其中所述第一比较值和所述第二比较值中的至少一个包括“不关心”值。7.根据权利要求1所述的网络设备，其中所述多元素向量包括二进制元素。8.根据权利要求1所述的网络设备，其中所述动作选择电路包括三态内容寻址存储器tcam，用于存储所述第一组比较值和所述第二组比较值中的一个或两个。9.一种网络设备中的方法，所述方法包括：通过网络交换分组，每个分组包括具有至少第一报头字段和第二报头字段的分组报头；
对于给定分组，基于所述给定分组的第一报头字段来确定第一检索关键字，以及基于所述给定分组的第二报头字段来确定第二检索关键字；将所述第一检索关键字与第一组比较值进行比较，并且响应于所述第一检索关键字与所述第一组中的第一比较值之间的匹配来输出与所述第一比较值相对应的多元素向量；通过级联所述第一检索关键字和所述多元素向量来生成合成检索关键字；将所述合成检索关键字与第二组比较值进行比较，并且响应于所述合成检索关键字与所述第二组中的第二比较值之间的匹配来输出用于应用于所述给定分组的动作指示符；以及响应于所述分组报头来处理所述分组，包括响应于所述动作指示符将动作应用于所述给定分组，所述动作指示符由比较电路输出。10.根据权利要求9所述的方法，其中所述多元素向量包括独热向量，所述独热向量具有标记元素，所述标记元素在所述独热向量中的位置指示在所述第二组中被发现与所述第二检索关键字匹配的所述第二比较值的索引。11.根据权利要求10所述的方法，其中所述第二组中的所述第二比较值包括(i)与所述第二报头字段相对应的第二值，以及(ii)比较向量，每个比较向量包括：在(i)对应的第二值和(ii)对应的第一比较值的组合保证输出所述动作指示符的一个或更多个位置中的“不关心”值；以及在一个或更多个其他位置中的非设置值。12.根据权利要求9所述的方法，其中所述多元素向量被定义为使得：设置所述多元素向量的具有与所述第二组中的与所述第二检索关键字匹配的第二比较值的索引相对应的索引的一个或更多个元素；以及未设置所述多元素向量的具有与所述第二组中的与所述第二检索关键字不匹配的第二比较值的索引相对应的索引的一个或更多个元素。13.根据权利要求12所述的方法，其中：所述第二组中的所述比较值包括：(i)第二检索关键字值，以及(ii)多元素向量比较值，其中在指示第一检索关键字值的索引的位置中的一个或更多个元素被设置，并且在其他位置中的元素被设置为“不关心”值。14.根据权利要求9所述的方法，其中所述第一比较值和所述第二比较值中的至少一个包括“不关心”值。15.根据权利要求9所述的方法，其中所述多元素向量包括二进制元素。16.根据权利要求9所述的方法，所述方法包括将所述第一组比较值和所述第二组比较值中的一个或两个存储在三态内容寻址存储器tcam中。17.一种用于确定要应用于网络设备中的分组的动作的方法，所述方法包括：对于正在所述网络设备中被处理的给定分组，基于所述给定分组的第一报头字段来确定第一检索关键字，以及基于所述给定分组的第二报头字段来确定第二检索关键字；将所述第一检索关键字与第一组比较值进行比较，并且响应于匹配来输出多元素向量；通过级联所述第一检索关键字和所述多元素向量来生成合成检索关键字；将所述合成检索关键字与第二组比较值进行比较，并且响应于匹配来输出用于应用于
所述给定分组的动作指示符。

技术总结
本公开涉及用于规则的笛卡尔乘积的有效存储器利用。网络设备包括一个或更多个端口以及动作选择电路。端口用于通过网络交换分组。动作选择电路用于：对于给定分组，基于给定分组的第一报头字段来确定第一检索关键字，以及基于给定分组的第二报头字段来确定第二检索关键字，将第一检索关键字与第一组比较值进行比较，响应于第一检索关键字与第一比较值之间的匹配来输出多元素向量，通过级联第二检索关键字和多元素向量来生成合成检索关键字，将合成检索关键字与第二组比较值进行比较，并且响应于合成检索关键字和第二比较值之间的匹配来输出用于应用于给定分组的动作指示符。来输出用于应用于给定分组的动作指示符。来输出用于应用于给定分组的动作指示符。


技术研发人员：G
受保护的技术使用者：迈络思科技有限公司
技术研发日：2023.02.23
技术公布日：2023/8/28