用于生成查找和进行判定的引擎、方法和软件定义网络

摘要

本发明的实施例涉及用于生成查找和进行判定的引擎(LED)、方法和软件定义网络。特别地，所述LDE用于针对输入令牌生成查找关键字并基于查找结果的内容来修改所述输入令牌。所述输入令牌由解析器从网络分组报头中解析，并且然后该令牌由LDE进行修改。经过修改的令牌指导对应的网络分组将如何由软件定义联网(SDN)系统中的其他部件进行修改或转发。所述LDE的设计是高度灵活且协议独立的。用于生成查找关键字且用于修改令牌的条件和规则是完全可编程的，以使得所述LDE可以执行SDN系统中的多种可重配置网络特征和协议。

说明书

技术领域

本发明涉及用于生成查找关键字并修改网络分组的引擎架构。更特别地，本发明涉及生成查找并进行判定以便在软件定义网络引擎中进行分组修改和转发的设备和方法。

背景技术

传统上，网络设备中的联网特征和协议是由硬件专用ASIC设计实现的。这些固定ASIC设计限制新协议的部署速率。用以支持新协议的硬件改变在成本和时间两方面都是昂贵的。因此，允许用户借助于软件来部署新特征和协议的可编程联网设备正在变得更有吸引力。

用于实现新网络协议的现有技术的方法是使用在现有技术通用CPU上运行的软件。然而，这些通用CPU的处理容量(当前最大值64位)对于支持达到100Gbps的网络分组流量的当前联网系统而言并不能保证实时性能。

用于实现新网络协议的现有技术的另一方法是使用可重配置FPGA芯片。然而，FPGA芯片的逻辑单元容量方面的限制不允许以其全吞吐量来处理具有大尺寸(诸如几百字节)的网络分组。另外，内部互连布线的高度复杂性使得FPGA芯片以高等待时间在低频率运行。FPGA芯片的这些不良特性不适合于执行现有技术企业和数据中心网络中所需的复杂网络特征。

发明内容

在软件定义联网(SDN)系统中，提出的查找及判定引擎(LDE)能够生成针对输入令牌(token)的查找关键字并基于查找结果来修改输入令牌，使得可以由系统中的其他部件正确地处理和转发对应网络分组。用于生成关键字和修改令牌的条件和规则完全可由软件进行编程且基于针对LDE配置的网络特征和协议。LDE通常包括两个主区块：关键字生成器和输出生成器。根据命名，关键字生成器针对每个输入令牌生成查找关键字，并且输出生成器生成输出令牌，该输出令牌为基于查找结果的输入令牌的经过修改的版本。关键字生成器和输出生成器具有类似的设计架构，该设计架构包括控制路径和数据路径。控制路径检查其输入中的特定字段和位是否满足已配置协议的条件。基于检查结果，其相应地生成指令。数据路径执行由控制路径生成的所有指令，以便在关键字生成器中生成查找关键字，或在输出生成器中生成输出令牌。用于关键字和输出生成的条件和规则完全可在关键字生成器和输出生成器的控制路径中进行编程。

在一方面中，提供了一种用于生成查找并进行判定以便在软件定义网络(SDN)系统中进行分组修改和进行转送的引擎。所提供的引擎为了简化起见而称为查找及判定引擎(LDE)。LDE通常包括关键字生成器和输出生成器，所述关键字生成器被配置成针对每个输入令牌生成查找关键字，所述输出生成器被配置成通过基于与查找关键字相关联的查找结果的内容来修改输入令牌，而生成输出令牌。

在一些实施例中，所述LDE还包括：输入缓冲器，其可以是FIFO缓冲器，用于在由所述LDE来处理输入令牌之前临时地存储输入令牌；模板表，用于识别所述输入令牌中的字段的位置；查找结果收集器，用于将输入令牌与查找结果结合，以及用于将与查找结果结合的输入令牌发送到所述输出生成器；回送检查器，用于确定是应将所述输出令牌发送回到所述LDE还是SDN系统中的另一引擎；以及回送缓冲器，其可以是FIFO缓冲器，用于存储所述回送令牌。

在一些实施例中，至模板表的模板查找指针是所述输入令牌内部的“TemplateID”字段的值。在一些实施例中，模板表的模板查找结果包含许多令牌层的信息、输入令牌中的令牌层的偏移以及元数据位，其为在输入令牌内部不可用的附加控制位。

在一些实施例中，查找结果收集器包括令牌缓冲器和查找结果缓冲器。令牌缓冲器和查找结果缓冲器中的每个的深度至少等于远程搜索引擎(其负责返回针对由LDE生成的每个查找关键字的查找结果)的等待时间，以保证LDE以全吞吐量操作。

在一些实施例中，由回送检查器进行的确定是基于输出令牌中的“DstEngineAddress”字段和LDE地址的比较。

在一些实施例中，回送缓冲器内部的令牌具有比输入缓冲器中的优先级更高的优先级，以避免死锁。

在一些实施例中，关键字生成器包括用于生成指令的控制路径和用于执行由控制路径产生的指令的数据路径。

控制路径包括：控制位提取器，用于从输入令牌提取控制位并从对应模板信息提取元数据位；MUX/CMP锥(cone)，用于比较所述输入令牌中的多位字和对应模板元数据；MUX/LUT逻辑锥(cone)，用于检查所述控制位和所述MUX/CMP锥的输出是否满足针对所述LDE配置的特定网络特征和协议的条件和规则；以及多个指令表，用于基于MUX/LUT逻辑锥的输出而生成所述指令。

在一些实施例中，所述控制位提取器可被软件重配置，以允许用户选择要提取控制位和元数据位之中的哪些位。

在一些实施例中，所述MUX/CMP锥并行地包括多个MUX/CMP单元，其中，所述MUX/CMP单元其中每个包括：两个可重配置复用器，用于从输入令牌和对应模板元数据中选择两个字，以及可重配置比较器，被配置成支持至少三个操作，所述至少三个操作包括匹配/等于(＝＝)、大于(＞)以及小于(＜)。可以将所述MUX/CMP单元其中每个配置成将来自输入令牌和对应模板元数据的字与恒定值相比较。

在一些实施例中，MUX/LUT逻辑锥包括多个级，其中，所述级其中每个并行地包括多个MUX/LUT单元。所述MUX/LUT单元其中每个包括：六个可重配置复用器，用于从该MUX/LUT单元的输入位中选择六位，以及可重配置查找表(LUT)，包含；利用所述六个可重配置复用器的六个输出位而编索引的64位。

由控制路径返回的许多指令能够生成查找关键字。在一些实施例中，由控制路径产生两种指令：拷贝指令和ALU指令。可以将拷贝指令配置成从源拷贝数据或将恒定值拷贝到输出关键字中的位置，其中，所述源是输入令牌和对应模板元数据中的一个。可以将ALU指令配置成将两个操作数的ALU结果拷贝到输出关键字中的位置，其中，两个操作数是从输入源获取的，并且其中，输入源是所述输入令牌和对应模板元数据中的一个。还可以将ALU指令配置成将恒定值和操作数的ALU结果拷贝到输出关键字中的位置，其中，所述操作数被从输入源取到输出关键字中的位置，并且其中，所述源是输入令牌和对应模板元数据中的一个。用于ALU指令的ALU操作是加法(+)、减法(-)、按位与(&)、按位或(|)、按位异或(^)、按位左移(<<)以及按位右移(>>)中的一个。

数据路径包括延迟匹配队列，用于在等待控制路径的同时缓冲输入令牌，以生成指令；以及指令执行块，用以并行地执行由控制路径产生的所有指令，以便生成查找关键字。

在一些实施例中，延迟匹配队列是FIFO缓冲器或输入寄存器，所述FIFO缓冲器或输入寄存器具有等于控制路径的等待时间的深度，以使得所述关键字生成器可以以全吞吐量操作。

在一些实施例中，在执行所有指令之前用全零对查找关键字进行初始化。

在一些实施例中，输出生成器具有与关键字生成器类似的设计，但是具有与关键字生成器的输入数据和输出数据不同的输入数据和输出数据。输出生成器的输入数据包括输入令牌、来自对应模板信息的元数据位和查找结果。输出生成器的输出数据是所述输入令牌的经过修改的版本。

在一些实施例中，所述输出生成器包括MUX/CMP锥，其具有比关键字生成器中的MUX/CMP锥更多的MUX/CMP单元，并且所述输出生成器包括MUX/LUT逻辑锥，其具有比关键字生成器中的MUX/LUT逻辑锥更多的级。

在一些实施例中，在执行所有指令之前将输出令牌初始化成具有与输入令牌相同的内容。

在一些实施例中，关键字生成器和输出生成器两者的控制路径是可编程的，以使得用户能够将LDE配置成支持不同的网络特征和协议。输出令牌的内容由SDN系统中的其他部件使用，以适当地修改和转发其对应网络分组。

在另一方面，提供了一种针对软件定义网络(SDN)引擎中的分组修改和转发生成查找并进行判定的方法。该方法包括在输入缓冲器处缓存输入令牌，检索用于输入令牌中的每个的元数据位，其中，所述元数据位在输入令牌内部不可用，基于输入令牌和元数据位中的每个的至少特定位而针对每个输入令牌生成查找关键字，基于该查找关键字而接收查找结果，基于查找结果和输入令牌的内容而修改输入令牌中的一个或多个字段，确定是将经过修改的令牌送回到当前引擎还是SDN系统中的另一引擎，并且基于该确定，将经过修改的令牌缓存在回送缓冲器中，其中，所述回送缓冲器中的令牌具有所述比输入缓冲器中的令牌更高的优先级。

在一些实施例中，所述输入缓冲器和所述回送缓冲器是FIFO缓冲器。

在一些实施例中，令牌的数据格式包括公共部分和层部分。公共部分包括对应网络分组的通用控制位和到模板表的查找指针的值。查找指针的值由令牌中的“TemplateID”字段给定。在一些实施例中，该方法还包括从模板表检索所述令牌在层部分中的令牌层的数目和偏移。

所述层部分包括对应网络分组的所有已解析分组报头的信息。所述已解析分组报头其中每个均与层部分中的“控制”字段和“数据”字段相关联。

在另一方面中，提供了一种软件定义网络(SDN)系统。该系统包括解析器、至少一个查找及判定引擎、搜索引擎、更新读写块及分组存储器和传输队列块。所述解析器被配置成接收传入网络分组，以解析这些传入网络分组的报头并输出令牌。所述至少一个查找及判定引擎被配置成针对这些令牌生成查找关键字，并且然后基于接收到的查找结果而修改这些令牌。所述搜索引擎被配置成返回用于由每个LDE发送的每个查找关键字的查找结果。更新读写(URW)块被配置成基于经过修改的令牌来修改每个网络分组的分组报头。所述分组存储器和所述传输队列块被配置成将经过修改的分组报头与对应分组的原始有效载荷组合，以便输出。

在一些实施例中，所述至少一个查找及判定引擎包括多个查找及判定引擎，所述多个查找及判定引擎被串行地耦合以便连续地执行多个查找表，或者被并行地耦合以便同时地执行多个查找表的多个查找及判定引擎。在一些实施例中，所述至少一个查找及判定引擎其中每个均包括关键字生成器和输出生成器。所述关键字生成器被配置成生成用于每个输入令牌的查找关键字。所述输出生成器被配置成基于与查找关键字相关联的查找结果的内容而修改输入令牌。

附图说明

图1图示出根据本发明的实施例的用于生成查找关键字并修改令牌的软件定义网络(SDN)引擎的框图。

图2A图示出根据本发明的实施例的令牌的格式。

图2B图示出根据本发明的实施例的模板表的框图。

图3图示出根据本发明的实施例的关键字生成器的框图。

图4A图示出根据本发明的实施例的用于关键字生成的拷贝指令的格式。

图4B图示出根据本发明的实施例的用于关键字生成的ALU指令的格式。

图4C图示出根据本发明的实施例的列出关键字生成指令的源的表格。

图5图示出根据本发明的实施例的查找结果收集器的框图。

图6图示出根据本发明的实施例的输出生成器的框图。

图7A图示出根据本发明的实施例的用于输出生成的拷贝指令的格式。

图7B图示出根据本发明的实施例的用于输出生成的ALU指令的格式。

图7C图示出根据本发明的实施例的列出输出生成指令的源的表格。

图7D图示出根据本发明的实施例的列出输出生成指令的目的地的表格。

图8图示出根据本发明的实施例的软件定义网络(SDN)系统的框图。

根据对如附图中所示的本发明的示例性实施例的以下更加特定的描述，前述内容将是显而易见的，在附图中相同的附图标记贯穿不同视图指示相同部分。附图并非必然按比例绘制，而是替代地着重于举例说明本发明的实施例而布置的。

具体实施方式

在以下描述中，出于说明的目的而阐述许多细节。然而，本领域的技术人员将认识到的是，可以并不使用这些特定细节的情况下实施本发明。因此，本发明并非意图局限于所示的实施例，而是符合与本文所述原理和特征相一致的最宽泛范围。

在软件定义联网(SDN)系统中，提议的查找及判定引擎(LDE)能够针对输入令牌生成查找关键字并且基于查找结果来修改输入令牌，以使得可以由系统中的其他部件正确地处理和转发对应网络分组。用于生成关键字和修改令牌的条件和规则完全可以由软件进行编程，且基于针对LDE配置的网络特征和协议。LDE通常包括两个主块：关键字生成器和输出生成器。正如所命名的那样，关键字生成器针对每个输入令牌生成查找关键字，并且输出生成器生成输出令牌，该输出令牌为基于查找结果的输入令牌的经过修改的版本。关键字生成器和输出生成器具有类似的设计架构，其包括控制路径和数据路径。控制路径检查其输入中的特定字段和位是否满足已配置协议的条件。基于检查结果，其相应地生成指令。数据路径执行由控制路径生成的所有指令，以便在关键字生成器中生成查找关键字，或在输出生成器中生成输出令牌。用于关键字和输出生成的条件和规则在关键字生成器和输出生成器的控制路径中是完全可编程的。所述LDE还包括：输入FIFO，用于临时地存储输入令牌；查找结果收集器，用于收集用于查找关键字的查找结果；回送检查器，用于当在同一LDE处针对该令牌需要多个串行查找表的情况下，将输出令牌送回到LDE；以及回送FIFO，用于存储回送令牌。所述回送路径典型地具有比输入路径更高的优先级，以保证摆脱了死锁。

关键字生成器和输出生成器被同样地配置为在题为“Method andApparatus for Parallel and Conditional Data Manipulation in aSoftware-Defined Network Processing Engine”且于(提交日)提交的美国专利申请号(代理人档案号：XPL-00400)中所讨论的SDN处理引擎，该专利申请被通过引用结合到本文中。

图1图示出根据本发明的实施例的用于生成查找关键字并修改令牌的软件定义网络(SDN)引擎100的框图。本发明的SDN引擎100称为查找及判定引擎(LDE)。LDE 100基于查找结果和输入令牌的内容，而生成查找关键字和经过修改的输入令牌。用于生成查找关键字并修改输入令牌的条件和规则典型地可由用户编程。

LDE 100可以从解析器接收输入令牌。解析器通常解析每个网络分组的报头并输出用于每个网络分组的输入令牌。输入令牌通常具有预定义格式，使得LDE 100将能够处理输入令牌。下面在图2A中详细地讨论输入令牌的格式。如果将多个LDE耦合在链中以便串行地执行多个查找和令牌修改步骤，则LDE 100还可以从先前的LDE接收输入令牌。

在LDE 100处从上游解析器或上游LDE接收到的输入令牌首先被缓存在输入FIFO 105内。输入令牌在输入FIFO 105内部等待直至LDE准备好对其进行处理。如果输入FIFO 105是满的，则LDE 100通知输入令牌的源(即，上游解析器或上游LDE)停止发送新的令牌。

通过从表格、即模板查找块110中进行查找，来识别每个输入令牌中的字段的位置。输入令牌接下来被发送到关键字生成器115。关键字生成器115被配置成拾取输入令牌中的特定数据以用于构建查找关键字。关键字生成器115的配置通常是用户定义的，并且取决于用户想要LDE 100执行的网络特征和协议。

每个输入令牌的查找秘钥被从关键字生成器115输出并发送到远程搜索引擎(未示出)。远程搜索引擎可以执行多个可配置查找操作，诸如TCAM、直接访问、基于哈希和最长前缀匹配查找。针对被发送到远程搜索引擎的每个查找关键字，在查找结果收集器120处向LDE 100返回查找结果。

在生成用于每个输入令牌的查找关键字的同时，关键字生成器115还将输入令牌传递至查找结果收集器120。输入令牌被缓存在查找结果收集器120内部。输入令牌在查找结果收集器120内部等待直至查找结果由远程搜索引擎返回。一旦查找结果可用，则输入令牌连同查找结果一起被发送到输出生成器125。

基于查找结果和输入令牌的内容，输出生成器125修改输入令牌的一个或多个字段，之后将经过修改的令牌发送到输出端。类似于关键字生成器1125，输出生成器125的关于例如用于令牌修改的条件和规则的配置通常也是用户定义的，并且取决于用户想要LDE100执行的网络特征和协议。

在修改令牌之后，将经过修改的令牌发送到回送检查器130。回送检查器130确定是应将经过修改的令牌送回到当前LDE以便执行另一查找，还是将其发送到关联SDN系统中的另一引擎。该回送检查是有利地允许单个LDE对同一令牌串行地执行多次查找而不是使用多个引擎来执行该操作的设计选项。此设计选项在由于诸如芯片面积预算之类的限制而具有有限数目的LED的系统中是有用的。被送回当前LDE的令牌经由回送路径140而被缓存在回送FIFO 135内部。回送路径140始终具有比输入路径(例如，来自输入FIFO 105)更高的优先级，以避免死锁。虽然已将图1描述为使用FIFO缓冲器，但其他缓冲器类型也是可能的。

为了使LDE 100理解每个令牌的内容，令牌具有被SDN系统中的所有引擎理解的公共格式。图2A图示出根据本发明的实施例的令牌200的格式。令牌200包括两个主要部分：公共部分205和层部分210。

公共部分205包含对应网络分组的通用控制位220，他们被解析器放入到令牌中。该控制位包括用于但不限于时间戳、序号、优先级、芯片上SDN系统中的下一引擎地址、源端口、网络分组字节计数等的位。这些通用控制字段220由用户、诸如SDN系统设计师选择，并且通常对SDN系统中的引擎适当地操纵网络分组而言是特别有用的。

令牌的层部分120包含对应网络分组的所有已解析报头。在网络中，每个网络分组常常封装了许多报头，诸如以太网、MPLS、IP、TCP、HTTP、VLAN等。对于网络分组而言，在网络分组在网络上行进的时间期间具有八个或更多不同的报头是常见的。为了使SDN系统中的引擎正确地处理网络分组，由SDN系统中的解析器来解析所有网络分组报头。特别地，解析器解析这些网络分组报头并将分组报头的已解析信息放置在令牌的层部分210中。每个已解析网络分组报头具有在令牌的层部分210内部的对应层205。

令牌中的每个层225包括两个字段：“控制”字段225a和“数据”字段225b。“控制”字段225a包含对应已解析分组报头的主控制位，诸如优先级和协议类型，所述位被解析器嵌入至层205中，以使得SDN系统能够适当地操纵层部分210中的网络分组报头。

“数据”字段225b包含对应已解析网络分组报头的信息的其余部分。

由于此类网络分组可以具有不同尺寸的多个报头，所以每个令牌内部的层部分210还包含具有不同尺寸的多个层。为了识别层225的数目及其尺寸以及其在令牌内部的位置，令牌的公共部分205内部的“TemplateID”字段215被引擎、诸如图1的LDE 100使用。“TemplateID”字段215先前被解析器在解析对应网络分组的同时嵌入公共部分205中。LDE 100使用“TemplateID”字段215的值作为到图2B的模板表250的查找指针，所述模板表250为图1的模板查找表110。

模板表250接收“TemplateID”字段215的值，并返回被放置到层部分210中的层的数目和这些层在令牌中的偏移，如图2B中所示。由于偏移提供了层225在令牌内部的位置，所以应认识到的是层225的顺序不一定需要与相应网络分组的报头的顺序相对应。

另外，模板表250还针对每个输入令牌返回元数据位，所述元数据位为用于该输入令牌的附加控制位。使用模板表250有利地减小每个令牌的尺寸，并因此降低了硬件成本，因为诸如可以将诸如元数据位和层偏移之类的信息放入模板表250中而不是由令牌本身承载。模板表250的配置通常是用户定义的，并且取决于解析器和SDN系统中的引擎所支持的网络特征和网络分组报头。每个输入令牌及其对应模板信息(其由模板表250返回)被结合并从图1的模板查找表110发送到关键字生成器115，以用于生成查找关键字。图3图示出根据本发明的实施例的关键字生成器300的框图。在一些实施例中，图1的关键字生成器115与关键字生成器300类似地配置。在顶层视图处，将关键字生成器300被划分成两个逻辑路径：控制路径305和数据路径310。输入令牌和模板信息被结合，并通过控制路径305和数据路径310流过关键字生成器115。控制路径305负责生成指令，所述指令然后被数据路径310执行以用于生成查找关键字。

关键字生成器控制路径(KGCP)305包括四个块：控制位提取器(CBE)315、MUX/CMP锥(MCC)320、MUX/LUT逻辑锥(MLLC)325和关键字生成指令表(KGIT)330。

KGCP 305中的CBE 315从输入令牌提取重要位，其通常包含被封装在输入令牌中的主要网络特征，包括图2A的公共部分205中的特定位和图2A的层部分210中的层225中的每个的所有控制位225a。从令牌的公共部分205提取的位的位置通常可由软件重配置。另外，CBE 215还提取由模板表250返回的模板查找结果的所有元数据位。

KGCP 305中的MCC 320并行地包括多个可配置MUX/CMP单元。每个MUX/CMP单元比较令牌中的两个任意字。这两个字的位置通常可由软件配置。每个MUX/CMP单元还可以将一个字与恒定值相比较。在一些实施例中，支持三个比较操作：等于(＝＝)、大于(＞)和小于(＜)。每个所选字的位宽通常是16或32位，但可以有不同的尺寸。KGCP 305的MCC 320中的MUX/CMP单元的数目通常从8个至16个，但MCC 320中的MUX/CMP单元的数目也可以不同，只要该数目不小于打包在所述输入令牌的层部分中的令牌层的最大数目即可。

CBE 315和MCC 320的所有输出位均被结合并输出到MLCC325。KGCP 305中的MLLC 325通常具有多个级。每个级并行地包括多个MUX/LUT单元。第一级的输入位是CBE 315和MCC 320的结合输出位。级i的输入位是级i-1的所有输出位。最后一级的输出位形成用于读取KGIT 330的索引。

在一些实施例中，MUX/LUT单元包含六个复用器，其从其输入位中选择六个任意位。这六个所选位的位置通常可由软件配置。这六个所选位中的每个返回一位输出，以形成到64位查找表的指针。每个MUX/LUT单元的设计有利地允许用户对来自其输入位的六个任意位执行逻辑表达式。

由于MLLC 325具有多个级且每个级并行地具有多个MUX/LUT单元，用户可以对MLLC 325编程以执行用于检查令牌以生成适当的查找关键字的若干复杂的表达式和规则，其取决于用户想要图1的LDE 100支持的网络特征和协议。MLLC 325通常具有三个或四个级，但也可以有更多或更少的级。除MLLC 325中的最后一级之外，每个级通常具有32至64个MUX/LUT单元。最后一级中的MUX/LUT单元的数目等于进入KGIT 330的所有索引的位的数目。

MLLC 325的输出位创建用于读取KGIT 330的索引指针。根据关键字尺寸，KGCP 305可以并行地具有一个或多个表。每个表条目包含多个指令。针对每个输入令牌，由KGIT 330返回的指令的数目等于表格的数目乘以每个表格条目的指令的数目。假设关键字尺寸是L字节，并且每个指令允许操纵最多C个字节。由指令表返回的指令的数目应至少等于L/C。

虽然输入令牌和模板信息的结合数据流过控制路径305，但该结合数据还流过数据路径310。关键字生成器数据路径(KGDP)310包括两个块：延迟匹配队列335和关键字生成指令执行块340。

结合数据被缓存在延迟匹配队列335内部。延迟匹配队列335可以是FIFO或移位寄存器。延迟匹配队列335具有等于KGCP 305的等待时间的缓冲器深度，以使得LDE(诸如图1的LDE100)能够以全吞吐量进行操作。一旦由KGCP 305产生用于每个令牌的指令，则从延迟匹配队列335移除对应令牌，并将其发送到关键字生成指令执行块340。关键字生成指令执行块340执行指令并使用输入令牌作为用于构建查找关键字的元数据。在一些实施例中，支持用于构建此输出查找关键字的两种指令：拷贝指令和ALU指令。

图4图示出根据本发明的实施例的用于关键字生成的拷贝指令400的格式。拷贝指令400允许将数据从源拷贝到输出关键字中的特定位置。“Src_ID”字段405指向从其拷贝最多C个字节的源数据。用于每个拷贝指令的C个字节的最大数目是基于设计选项而选择的，包括LDE(诸如图1的LDE 100)的硅面积预算。用于KGDP 310的所有源数据都在图4C中所示的表格中列出。用于构建查找关键字的源数据是所有令牌层、输入令牌的公共部分以及与输入令牌相关联的模板信息中的元数据字段。

“Src_ByteOffset”字段410指示所选源数据中的起始字节位置。C个字节是从该起始字节位置开始被拷贝的。在一些情况下，用户想要拷贝位而不是字节或想要拷贝少于C个字节。在这些情况下，使用“BitMask”字段415来掩蔽被拷贝字节。并且，在一些情况下，用户想要向查找关键字拷贝恒定值，而不是从元数据拷贝恒定值。在这些情况下，设定“IsConst”字段420并使用“BitMask”字段415来包含该恒定值。最后，“Dst_ByteOffset”字段425指向输出关键字终端位置，已拷贝掩蔽字节或恒定值被粘贴到那里。

图4B图示出根据本发明的实施例的用于关键字生成的ALU指令430的格式。ALU指令430中的字段440-475的含义与拷贝指令400中的那些字段相同，不同的是每个ALU指令400允许从元数据进行拷贝或拷贝用于算术逻辑单元(ALU)块的两个操作数的恒定值。ALU操作由“OpCode”字段435选择，其支持至少以下操作：加法(+)、减法(-)、按位与(&)、按位或(|)、按位异或(^)、按位左移(<<)和按位右移(>>)。所述ALU操作在由“Dst_ByteOffset”字段480识别的位置处被粘贴到输出关键字。

基于设计选项来选择每个ALU指令的已拷贝字节的最大数目和ALU操作的位宽。已拷贝字节的数目通常为4字节至8字节，并且ALU操作的尺寸通常为16位或32位。然而，已拷贝字节的数目和ALU操作的尺寸可以不同。

针对每个输入令牌，由KGDP 310并行地执行由KGCP 305产生的所有指令，以用于构建查找关键字。在执行所有指令之前，用全零对查找关键字进行初始化。然后由所有指令来修改查找关键字且然后将查找关键字发送到远程搜索引擎。远程搜索引擎被配置成在某个稍后的时间返回用于每个查找关键字的查找结果。

在KGDP 310执行指令的同时，KGDP 310还将原始输入令牌和对应模板信息传递至图1的查找结果收集器120。图5图示出根据本发明的实施例的查找结果收集器500的框图。在一些实施例中，图1的查找结果收集器120被与查找结果收集器500类似地配置。在等待将由远程搜索引擎返回查找结果的同时，包括输入令牌和对应模板信息的所有输入数据被缓存在令牌缓冲器515内部。令牌缓冲器515的深度至少等于远程搜索引擎的等待时间，以使得LDE(诸如图1的LDE 100)能够以全吞吐量进行操作。

由远程搜索引擎针对对应查找关键字返回的查找结果被缓存在查找结果缓冲器520内部。查找结果收集器500检查查找结果缓冲器520以确定对于令牌缓冲器515内部的输入令牌，查找结果是否是可用的。查找结果收集器500将输入令牌连同其模板信息和对应的查找结果一起从缓冲器515-520取出，将数据结合且将结合的数据发送到图1的输出生成器125。

图6图示出根据本发明的实施例的输出生成器600的框图。在一些实施例中，图1的输出生成器125被与输出生成器600类似地配置。输出生成器600和关键字生成器300的设计是类似的。关键字生成器和输出生成器设计两者的相似性有利地允许大量设计的重用，同时有效地降低用于LDE的开发和验证成本。

在顶层视图处，也将输出生成器600划分成两个逻辑路径：控制路径605数据路径610。输出生成器600和关键字生成器300之间的一些差别包括输入数据和输出数据。输出生成器600的输入数据是原始输入令牌、其对应模板信息和对应查找结果。输出数据是基于查找结果的内容和原始输入令牌本身而修改的令牌。

输出生成器控制路径(OGCP)605包括四个块：控制位提取器(CBE)615、MUX/CMP锥(MCC)620、MUX/LUT逻辑锥(MLLC)625和输出生成指令表(OGIT)630。

由于输出生成器600的输入具有比图3的关键字生成器300的输入数据更多的输入数据，所以输出生成器600中的块大于关键字生成器300中的对应块。特别地，除了输入令牌控制位和模板元数据位的提取之外，OGCP 605中的CBE 615还提取查找结果内部的控制位。因而，查找结果优选地具有被远程搜索引擎和LDE(诸如图1的LDE 100)两者均理解的格式。

OGCP 605中的MCC 620通常具有比图3的KGCP 305中的MCC320更多的MUX/CMP单元。OGCP 605的MCC 620中的MUX/CMP单元的数目通常为从6个至32个，但MCC 620中的MUX/CMP单元的数目可以不同，只要该数目不小于令牌层的数目加1即可(以用于支持对来自查找结果的数据字的附加比较)。

OGCP 605中的MLLC 625通常具有比图3的KGCP 305中的MLLC 325更多的级，以便支持因来自查找结果的附加控制位而更加复杂的检查条件和规则。OGCP 605中的MLLC 625中的级数通常是五级或六级，但可以有更多或更少的级。

OGCP 605通常具有比图3的KGCP 305更多的指令表。由OGCP605返回的指令的数目必须足以操纵输出令牌中的所有字段。假设令牌尺寸是M字节，并且每个指令允许操纵最多C个字节。由指定表返回的指令的数目应至少等于M/C。

在一些实施例中，支持用于生成输出令牌的两种指令：拷贝指令和ALU指令。图7A和图7B图示出根据本发明的实施例的分别用于输出生成的拷贝指令700和ALU指令740的格式。用于输出生成的拷贝指令700和ALU指令740的格式类似于用于关键字生成的拷贝指令400(图4A)和ALU指令430(图4B)的格式，不同之处在于拷贝指令700和ALU指令740具有更多的源数据和目的地。

拷贝指令700的“Src_ID”字段705、“Src_ByteOffsef”字段710、“BitMask”字段715、“Isconst”字段720、和“Dst_ByteOffset”字段730被分别地与拷贝指令400的“Src_ID”字段405、“Src_ByteOffset”字段410、“BitMask”字段415、“IsConst”字段420和“Dst_pyceQffset”字段425类似地配置。

ALU指令740的“OpCode”字段745、“srcA_ID”字段750、“srcA_ByteOffet”字段755、“SrcA_BitMask”字段760、“SrcA_IsConst”字段765、“SrcB_ID”字段770、“SrcB_Byteoffset”字段775、“SrcB_BitMask”字段780、“SrcB_IsConst”字段785和“Dst_ByteOffset”字段795分别地与ALU指令430的“OpCode”字段435、“SrcA_ID”字段、“SrcA_ByteOffset”字段445、“SrcA_BitMask”字段450、“SrcA_IsConst”字段455、“SrcB_ID”字段460、“SrcB_ByteOffset”字段465、“SrcB_BitMask”字段470、“SrcB_IsConst”字段475和“Dst_ByteOffeet”字段480类似地配置。

在图7C中所示的列表中列出了用于输出生成器数据路径(OGDP)610的指令的所有源数据。用于生成输出令牌的元数据是输入令牌的所有层、输入令牌的公共部分、与输入令牌相关联的模板信息的元数据字段以及输入令牌的查找结果。

在图7D中所示的表中列出了用于OGDP 610的指令的所有目的地标识。指令中的“Dst_ID”字段725、790指示选择来自源的已拷贝数据将被粘贴到输出令牌的公共部分或各层之中的哪个目的地。用于粘贴数据的所选目的地中的位置由与关键字生成指令中的那些类似的“Dst_ByteOffset”字段730、795给出。

由OGCP 605产生的所有指令由OGDP 610并行地执行，以用于生成新的输出令牌。在执行所有指令之前将输出令牌初始化成具有与输入令牌相同的内容。在执行所有指令之后，输出令牌是输入令牌的经过修改的版本。

图1的LDE 100是高度灵活、完全可编程且协议独立的，其有利地允许用户通过适当地配置关键字生成器115和输出生成器125的控制路径而执行多种网络特征和协议。例如，可以将LDE 100配置成生成查找关键字，以便作为路由器执行IP查找，或者作为交换机执行以太网L2查找或VLAN查找，或者作为防火墙执行网络攻击检测查找，或作为网络地址转换器执行地址至名称查找。基于查找结果，适当地修改令牌。

然后，由回送检查器130来检查经过修改的令牌，以查看是将经过修改的令牌是送回当前LDD以便完成另一查找还是发送到SDN系统中的其他引擎。支持回送路径140有利地允许在同一引擎处执行多次查找。回送检查器130将经过修改的令牌的公共部分内部的“Dst_EngineAddress”字段与当前引擎的地址相比较。如果他们是相同的，则经由如图1中所示的回送路径140将经过修改的令牌送回到当前引擎。在图1中，回送路径140具有比输入路径(例如，来自输入FIFO 105)更高的优先级，以避免死锁。

如果需要的话，最终输出令牌被发送到另一引擎，以用于执行更多查找，或者发送到更新读写(URW)块。基于令牌中的经过修改的内容，URW块将对应地修改对应网络分组报头(原始令牌被从该对应网络分组报头中解析)。这些经过修改的网络分组报头冉江将被传输队列块与其对应有效载荷组合，以形成最终经过修改的输出网络分组，其反映了针对该LDE配置的网络特征和协议。然后，将经过修改的网络分组发送到SDN系统中的其他部件，以用于进一步处理，或者转发到网络中的另一设备。

图8图示出根据本发明的实施例的软件定义网络(SDN)系统800的框图。系统800包括解析器805、至少一个LDE 810、搜索引擎815、更新读写(URW)块820、分组存储器和传输队列(TxQ)块825。在解析器805处接收网络分组。解析器805解析网络的报头并将控制位和已解析报头放在令牌中。解析器805将令牌发送到一个或多个LED 810并将网络分组的原始分组报头发送到URW 820以及将原始分组有效载荷发送到分组存储器和TxQ 825。

该令牌通常采取被LDE 810所理解的格式。LDE 810中的一个从解析器805接收令牌。如上文所讨论的，每个LDE 810生成查找关键字，并将此查找关键字发送到远程搜索引擎815，其在某个稍后的时间返回查找结果。在从搜索引擎815接收到查找结果之后，LDE810基于查找结果和令牌的内容来修改令牌。基于经过修改的令牌的“Dst_EngineAddress”，可以将经过修改的令牌发送到所述多个LDE810中的另一LDE或同一LDE以用于在需要时执行更多查找。在完成由LDE 810进行的所有需要的查找和令牌修改之后，将最终输出令牌发送到URW块820。URW块820基于经过修改的令牌的内容来修改对应分组报头；因此，经过修改的分组报头适当地反映针对LDE 810配置的网络特征。经过修改的分组报头然后被发送到分组存储器和TxQ块825。分组存储器和TxQ块825将初始分组有效载荷和经过修改的分组报头组合，以形成最终输出网络分组。最终输出网络分组然后被发送到SDN系统中的其他部件，以用于进一步处理，或者被转发到网络中的另一设备，或者可以在期望时送回(回送)到解析器以便能够执行更多查找。

本发明的实施例涉及用于生成用于输入令牌的查找关键字并基于查找结果的内容来修改输入令牌的查找及判定引擎(LDE)。输入令牌由解析器从网络分组报头中解析，并且然后该令牌由LDE修改。被LDE修改的令牌指导对应网络分组将如何由软件定义网络(SDN)系统中的其他部件进行修改或转发；LDE的设计是高度灵活且协议独立的。用于生成查找关键字且用于修改令牌的条件和规则是完全可编程的，以使得LDE可以执行SDN系统中的多种可重配置网络特征和协议。

本领域的技术人员将认识到还存在其他用途和优点。虽然已参考许多特定细节描述了本发明，但本领域的技术人员将认识到在不脱离本发明的精神的情况下，可以以其他特定形式来体现本发明。因此，本领域的技术人员将理解的是，本发明将不受前述说明性细节的限制，而是由所附权利要求书来限定。