网络交换机设备中的准确匹配哈希查找数据库

摘要

本发明的各实施例涉及网络交换机设备中的准确匹配哈希查找数据库。在一种用于在网络设备中转发包的方法中，基于查找关键字生成多个哈希值。多个哈希值至少包括使用第一哈希函数生成的第一哈希值、使用第二哈希函数生成的第二哈希值和使用第三哈希函数生成的第三哈希值。第三哈希函数不同于第一哈希函数和第二哈希函数。使用第一哈希值和第二哈希值搜索查找表以确定用于查找关键字的偏移。然后，使用第三哈希值和为查找关键字确定的偏移搜索转发表以选择与查找关键字对应的转发条目。基于选择的转发条目向网络设备的一个或者多个端口转发包。

说明书

相关申请的交叉引用

本申请要求对通过完全引用将其公开内容明确地结合于此、于 2013年4月4日提交、名称为″Exact Match Hash Algorithm For Very  Large Table in Switches″的第61/808，323号美国临时申请的优先权。

技术领域

本公开内容总体上涉及网络设备，并且更具体地涉及网络设备 中的哈希查找表。

背景技术

这里提供的背景描述是出于总体上呈现公开内容的背景的目 的。当前具名的发明人的工作在背景技术这一节中描述的程度上以 及该描述的可能在提交时未以其他方式符合现有技术的方面既未被 明示地也未被暗示地承认为针对本公开内容的现有技术。

网络设备(比如网络交换机、路由器、边缘设备等)经常运用 如下查找表，这些查找表存储与由网络设备处理的包关联的各种信 息，并且网络设备在查找表中执行查找以用于在网络设备处理包期 间做出各种处理判决。例如，可以执行查找操作以用于包分类、转 发判决、服务质量分类、策略控制列表应用和一般由网络设备执行 的其他处理操作。一般而言，根据与包关联的或者为包生成的关键 字执行对于包的查找。关键字例如被用来搜索表，并且从由表中的 由关键字标识的条目取回与包相关的信息(例如，用于包的转发信 息)。

使用内容可寻址存储器(CAM)来实施一些查找表。基于CAM 的表一般允许通常在单个比较循环中比较向表提供的关键字与表的 所有条目，并且返回指示哪些条目与关键字匹配的结果。然而，尤 其在运用大规模查找表时，基于CAM的表一般在面积和功率消耗方 面成本高。

查找表的备选实现方式利用基于哈希的方案，在该方案中，将 哈希函数应用于关键字以确定哈希表中的其中存储关键字和与关键 字关联的信息(例如，转发信息)的位置。尽管哈希表与CAM实现 方式相比一般更小并且更高效，但是哈希表在哈希函数为向哈希函 数提供的两个或者更多不同关键字生成相同哈希值时表现固有冲 突，并且作为结果，无法向哈希表中插入向哈希表提供的一些关键 字。因此，即使关键字可以与条目匹配，对于向哈希表提供的一些 关键字的查找操作仍然不会产生匹配。因此，难以在运用哈希表时 实现准确匹配查找性能。

发明内容

在一个实施例中，一种用于在网络设备中转发包的方法包括在 哈希值生成器并且基于与包对应的查找关键字生成多个哈希值，至 少包括使用第一哈希函数生成第一哈希值、使用第二哈希函数生成 第二哈希值和使用第三哈希函数生成第三哈希值，第三哈希函数不 同于第一哈希函数和第二哈希函数。该方法也包括使用第一哈希值 和第二哈希值搜索查找表以确定用于查找关键字的偏移，以及使用 第三哈希值和为查找关键字确定的偏移搜索转发表以选择与查找关 键字对应的转发条目。该方法还包括基于选择的转发条目向网络设 备的一个或者多个端口转发包。

在另一实施例中，一种用于在网络中转发包的网络设备包括多 个端口和耦合到多个端口的包处理器，包处理器被配置用于向多个 端口中的一个或者多个适当端口传送经由多个端口中的至少一些端 口接收的包。包处理器包括：哈希值生成器，被配置用于基于与包 对应的查找关键字生成多个哈希值，多个哈希值至少包括使用第一 哈希函数生成的第一哈希值、使用第二哈希函数生成的第二哈希值 和使用第三哈希函数生成的第三哈希值，第三哈希函数不同于第一 哈希函数和第二哈希函数。包处理器也包括耦合到查找表和转发表 的查找单元。查找单元被配置用于使用第一哈希值和第二哈希值搜 索查找表以确定用于查找关键字的偏移，以及使用第三哈希值和为 查找关键字确定的偏移搜索转发表以选择与查找关键字对应的转发 条目。包处理器还包括被配置用于基于选择的转发条目向多个端口 中的一个或者多个端口转发包的转发引擎。

在又另一实施例中，一种用于在网络设备中填充转发数据库的 方法包括在哈希值生成器并且基于查找关键字生成与包对应的多个 哈希值，至少包括使用第一哈希函数生成第一哈希值、使用第二哈 希函数生成第二哈希值和使用第三哈希函数生成第三哈希值，第三 哈希函数不同于第一哈希函数和第二哈希函数。该方法也包括用网 络设备并且至少基于第一哈希值和第二哈希值为查找关键字确定进 入转发表的偏移。该方法还包括用网络设备并且基于第三哈希值和 偏移确定转发表中的用于插入查找关键字的位置。该方法还包括用 网络设备确定是否可以在确定的位置向转发表中插入查找关键字而 未与在确定的位置先前存储的关键字冲突。该方法还包括在确定可 以向转发表中插入查找关键字时，在确定的位置向转发表中插入查 找关键字和与查找关键字关联的转发信息。

在再一实施例中，一种用于在网络设备中填充转发数据库的装 置包括：哈希值生成器，被配置用于基于查找关键字生成多个哈希 值，至少包括使用第一哈希函数生成的第一哈希值、使用第二哈希 函数生成的第二哈希值和使用第三哈希函数生成的第三哈希值，第 三哈希函数不同于第一哈希函数和第二哈希函数。该装置也包括： 更新单元，被配置用于：至少基于第一哈希值和第二哈希值为查找 关键字确定进入转发表的偏移，以及基于第三哈希值和为查找关键 字确定的偏移确定转发表中的用于插入查找关键字的位置。更新单 元也被配置用于确定是否可以在确定的位置向转发表中插入查找关 键字而未与在确定的位置先前存储的关键字冲突、并且在确定可以 向转发表中插入查找关键字时，在确定的位置向转发表中插入查找 关键字和与查找关键字关联的转发信息。

附图说明

图1是根据本公开内容的一个实施例的能够使用多哈希函数 方案高效解决基于哈希的查找数据库中的冲突的示例切换设备的简 化框图；

图2图示根据一个实施例的查找表的示例条目；

图3A-图3B是图示根据一个实施例的用于在数据库中对查找 关键字定位并且从数据库取回与查找关键字关联的信息的示例查找 方案的流程图；

图4A-图4B是图示根据一个实施例的用于向数据库中插入查 找关键字和与查找关键字关联的信息的示例更新方案400的流程图；

图4C是图示根据一个实施例的与图4A-图4B的更新技术结合 实施的冲突解决方案的流程图；

图5A-图5B是图示根据一个示例实施例的应用于数据库表的 条目重排技术的示图；

图6是根据一个实施例的用于在网络设备中转发包的示例方 法的流程图；

图7是根据一个实施例的用于在网络设备中填充转发数据库 的示例方法的流程图。

具体实施方式

图1是根据本公开内容的一个实施例的能够使用多哈希函数 方案高效解决基于哈希的查找数据库中的冲突的示例切换设备100 的简化框图。切换设备100一般是连接两个或者更多计算机系统、 网络段、子网等的计算机联网设备。例如，在一个实施例中，切换 设备100是路由器。然而，注意，切换设备100未必限于特定协议 层或者特定联网技术(例如，以太网)。例如，切换设备100也可 以是桥接器、VPN集中器等。

切换设备100包括耦合到多个端口112的包处理器102，并且 端口112中的每个端口耦合到通信网络(例如，通信网络内的网络 设备)。一般而言，包处理器102被配置用于处理经由入站端口112 接收的包、确定应当经由其传输包的相应出战端口112并且经由确 定的出站端口112传输包。在一些实施例中，包处理器102被配置 用于在入站端口112接收包、在存储器中存储包、在包存储于存储 器中之时执行包的处理、确定应当经由其传输包的一个或者多个出 站端口112并且在做出转发判决之后从存储器取回包并且经由该一 个或者多个出站端口112传输包。在一些实施例中，包处理器102 为包生成包描述符，并且包描述符而不是包本身随后由包处理器102 处理。在一个实施例中，包描述符包括来自包的一些信息，比如包 的头部信息中的一些或者所有头部信息。在一些实施例中，包描述 符附加地包括其他信息，比如包在存储器中存储于何处的指示符。 为了易于说明，下文使用术语“包”以指代包本身或者与包关联的包 描述符。

包处理器102包括耦合到转发数据库105的转发引擎104。在 一个实施例中，转发数据库105存储在与连接到端口112的网络设 备对应的目的地地址(例如，介质访问控制(MAC)地址、网际协 议(IP)地址、VLAN、多播地址等)与网络设备连接到的特定端口 112之间的关联。根据一个实施例，转发数据库105包括转发表106、 查找表107和内容可寻址存储器(CAM)108(例如，二进制CAM (BCAM)或者三进制CAM(TCAM))。在一个实施例中，转发 表106被实施为基于查找关键字生成的由哈希值编索引的哈希表(如 这里使用的术语“关键字”和“查找关键字”可互换)。由于哈希值一般 比查找关键字更短，所以在两个或者更多查找关键字之间的冲突可 能在哈希函数为该两个或者更多查找关键字生成相同哈希值时产 生。在这样的系统中，由于在哈希成相同哈希值的不同关键字之间 的冲突而无法向哈希表中插入一些查找关键字，因此，未充分利用 一些哈希表。在各种实施例中，转发引擎104被配置用于利用为每 个查找关键字生成的多个哈希值以解决转发表106中的冲突，由此 提高转发表106的存储器利用率。

根据一个实施例，转发引擎104被配置用于使用三个不同哈希 函数为每个查找关键字生成三个哈希值，并且有选择地利用该三个 哈希值以确定在转发表106中存储查找关键字的存储器位置。在这 一实施例中，第一哈希值H1用来访问查找表107以标识查找表107 中的与第一哈希值对应的条目。第二哈希值H2用来从查找表107的 标识的条目中的与第一哈希值关联的一个或者多个偏移选择偏移。 选择的偏移然后被应用于第三哈希值H3以确定用于访问转发表106 的索引，并且取回在确定的索引存储的转发条目。由于为查找关键 字生成的第三哈希值用来对转发表106编索引，其中根据与用来为 查找关键字生成第一哈希值和第二哈希值的哈希函数不同的哈希函 数生成第三哈希值，所以在查找关键字未共享相同第三哈希值时的 至少一些情形中避免了在哈希成相同第一哈希值和相同第二哈希值 的不同查找关键字之间的冲突。另外，由于操作表107在至少一些 情形中关联多个偏移与第一哈希值，所以在至少一些情形中，即使 在哈希成相同第一哈希值的不同关键字哈希成第三相同关键字时， 仍然在该不同关键字之间避免了冲突。附加地，在一些实施例中， 在其中查找表107无法解决在哈希成相同第一哈希值的不同关键字 之间的冲突的情形中，例如，在存储于转发表106中的这样的关键 字的数目超过由查找表107的条目支持的最大偏移数目时，如以下 将更具体说明的那样，仍然使用默认偏移来向转发表106中插入这 样的关键字。

由于这里描述的这些和其他冲突解决技术，在至少一些实施例 中，与不能解决这样的冲突的已知系统相比，一般提高了数据库利 用率。例如，在一些实施例中，本公开内容的查找关键字插入技术 促成提高的如通过“第一未命中”标准测量的存储器利用率。第一未 命中标准一般被定义为基于哈希的数据库在数据库中遇到关键字的 第一未命中插入时的利用率(即存储于数据库中的条目相对于由数 据库支持的最大条目数目的百分比)。因而，等于或者接近100％的 根据第一未命中标准的存储器利用率产生高度地利用并且高效的基 于哈希的数据库。在至少一些实施例中，这里描述的多哈希值数据 库结构极大地提高如通过第一未命中标准测量的存储器利用率。附 加地，在一些实施例中，也提高了如通过其他适当标准(比如存储 器容量标准(或者与由数据库支持的最大条目数目对应的、由多个 尝试的插入产生的成功插入的百分比))测量的存储器利用率。应 当注意，根据一个实施例，转发条目的取回仅需用于从查找表107 取回偏移的第一存储器访问和用于从转发表106取回转发条目的第 二存储器访问这两个存储器访问。作为结果，通过使对存储器的访 问数目限于相对小的访问数目(例如，2个)，与需要更大数目的存 储器访问以取回关键字的已知多哈希数据库相比，这里描述的技术 允许从数据库更高效地取回信息(例如，在从存储器取回关键字时 的存储器带宽方面)。作为示例，常规多哈希系统可以通过使用对 应数目的相应哈希函数为关键字生成多个哈希值(例如，4个哈希值) 并且用多个哈希值中的每个哈希值访问存储器以在哈希表中对将允 许插入关键字的条目定位来增加存储器利用率。在这一情况下，关 键字的插入并且相应地关键字的后续取回需要对应数目(例如，4 个)的查找操作。另一方面，本公开内容的技术保证需要有限数目 (例如，仅2个)的查找操作以插入和/或取回关键字。作为结果， 本公开内容的技术通过限制为了取回信息而需要的对存储器的访问 数目来提供高效插入和例如从相对大的基于哈希的数据库和/或在切 换设备外部的存储器中存储的数据库取回关键字而又维持数据库的 高存储器利用率。

在一些实施例中，转发引擎104包括处理器120和存储在处理 器120上可执行的指令的存储器122。在一些这样的实施例中，处理 器120执行转发表106的优化以进一步增加转发表106的利用率。 备选地或者附加地，在一些实施例中，处理器102用来在其中查找 表107不能解决在具有相同第一哈希值的不同关键字之间的冲突的 至少一些情形中辅助解决这样的冲突。例如，如以下将更具体说明 的那样，在一些实施例中，处理器120在这样的冲突的数目超过由 查找表107支持的这样的冲突的最大数目时辅助解决这样的冲突。 另外，在一个实施例中，转发引擎104被配置用于利用附加存储器 (比如CAM108)以用于存储不能解决其冲突的关键字。

尽管数据库105在这里一般被描述为如下转发数据库，该转发 数据库存储在网络设备100的端口112与连接到端口112的网络设 备的地址(例如，MAC地址)之间的关联，但是数据库105一般可 以是存储在查找关键字和与查找关键字关联的属性之间的关联的任 何查找数据库。例如，在一些实施例中，数据库105是存储在关键 字与将对与关键字对应的包执行的一个或者多个策略控制动作(例 如，关于访问控制、服务质量、流量测量、VLAN指派等)之间的 关联的策略控制数据库。在其他实施例中，数据库105存储如下其 他信息，该其他信息一般由网络设备100用来处理由网络设备100 接收的包。另外，尽管数据库105被图示为在转发引擎104外部， 但是在一些实施例中，在转发引擎104中包括数据库105。备选地， 在一些实施例中，数据库105在包处理器102外部和/或在切换设备 100外部。另外，在一些实施例中，数据库105的表106是具有一百 万或者数百万条目的相对大的表。在一个实施例中，在经由适当接 口(例如，双数据速率(DDR)接口、单数据速率(SDR)接口或 者其他适当接口)耦合到转发引擎104的外部(例如，设置于在切 换设备100外部的集成设备上)动态随机存取存储器中实施表106。 然而，一般而言，在各种实施例中，数据库105是任何适当大小的 数据库并且被使用任何适当类型的存储器(例如，静态随机存取存 储器(SRAM)或者另一适当类型的存储器)来实施。也注意，这里 描述的数据库和数据库查找操作并不限于网络设备并且在其他实施 例中在其他适当计算设备中被利用。

继续参照图1，转发引擎104包括耦合到哈希值生成器110的 关键字生成器109。在一个实施例中，关键字生成器109接收包或者 包描述符并且基于在包的头部中或者在包描述符中包括的信息生成 查找关键字。例如，关键字生成器单元109基于在包中包括的或者 与包关联的目的地地址(单播、多播或者广播)、虚拟局域网(VLAN) 标签等中的一项或者多项为包生成查找关键字。在其他实施例中， 关键字生成器109基于在包中包括的或者与包关联的其他信息为包 生成查找关键字。

关键字生成器109向哈希值生成器110提供查找关键字。哈希 值生成器110接收查找关键字，并且为查找关键字生成多个哈希值。 在一个实施例中，哈希值生成器使用三个相异哈希函数(例如，使 用不同生成器多项式(比如32位CRC哈希多项式)或者其他适当 哈希多项式)为查找关键字生成三个哈希值。哈希值生成器110向 数据库控制器单元114提供生成的哈希值(例如，H1、H2和H3)。 在一个实施例中，数据库控制器单元114包括查找单元114a和更新 单元114b。例如，在需要转发信息以做出转发判决时，查找单元114a 在数据库105中执行查找操作以从数据库105取回这一信息。在一 个实施例中，在学习新转发信息时，更新单元114b例如通过向数据 库105中插入查找关键字和与查找关键字关联的信息更新数据库 105。附加地，在一些实施例中，例如在尚未访问条目持续某一时间 段时，更新单元114b从数据库105删除条目。

仍然参照图1，在一个实施例中，查找表107包括根据第一哈 希值H1编索引的多个条目，并且每个条目包括与每个第一哈希值 H1关联的多个偏移。附加地，在一个实施例中，在查找表107的条 目中的偏移中的每个偏移还与偏移对应于的特定查找关键字的第二 哈希值H2关联。在操作中，查找单元114a基于为查找关键字生成 的第一哈希值H1标识查找表107中的与查找关键字对应的条目。查 找单元114a然后基于为查找关键字生成的第二哈希值H2从在查找 表107的标识的条目中包括的多个偏移选择与查找关键字对应的偏 移。查找单元114a然后将选择的偏移应用于第三哈希值H3以确定 转发表106中的与查找关键字对应的位置，并且从转发表106中的 确定的位置取回转发条目。在一个实施例中，在从转发表106取回 转发条目时，查找单元114a比较从转发条目取回的查找关键字与用 来确定条目的位置的查找关键字(即，为由转发引擎104处理的包 生成的查找关键字)。如果取回的关键字与查找关键字匹配，则已 经执行了成功的查找，并且取回的转发信息用来向由转发信息指示 的一个或者多个端口112转发被转发引擎104处理的包。另一方面， 在一个实施例中，如果取回的关键字未与查找关键字匹配，则在转 发表106中的查找失败。在这一情况下，在一个实施例中，查找单 元114a利用查找关键字以搜索CAM108，并且如果在CAM108中 发现用于查找关键字的匹配，则基于CAM108的对应条目获得转发 信息。在一个实施例中，如果在CAM108中未发现用于查找关键字 的匹配，则转发引擎114向(例如，在第2层桥接设备中的)端口 112中的所有端口或者子集“传涌(flood)”包，或者执行另一默认 或者预定操作。

以下与图3A-图3B结合描述根据一个实施例的由查找单元 114a实施的示例查找方案。以下与图4A-图4B结合描述根据一个实 施例的由更新单元114b实施的示例更新方案。在描述示例查找方案 和示例更新方案之前，首先与图2结合描述根据一个实施例的查找 表17的示例条目。

图2图示根据一个实施例的图1的查找表107的示例条目200。 在其他实施例中，图1的查找表107包括具有除了条目200之外的 适当结构的条目。条目200包括多个子条目或者冲突桶(collision  bucket)(“桶”)201。冲突桶201一般通过允许不同偏移用于多个 查找关键字来为哈希成相同第一哈希值H1的多个查找关键字提供 冲突解决。在图2的实施例中，每个桶201包括相应签名字段202、 相应冲突计数器字段204和相应偏移字段206。偏移字段206用来为 哈希成相同第一哈希值H1的不同查找关键字存储相应偏移，并且签 名字段202用来关联偏移与偏移对应于的特定查找关键字。在一个 实施例中，签名字段202将与关键字对应的第二哈希值H2存储为用 于为关键字选择适当偏移的签名。在这一实施例中，在基于为关键 字生成的第一哈希值H1从查找表107取回条目200时，查找单元 114a比较从条目200的签名字段202取回的签名与为关键字生成的 第二哈希值H2。在从签名字段202取回的签名与为关键字生成的第 二哈希值H2匹配的情况下，查找单元114a选择从对应偏移字段206 取回的偏移。在图2的实施例中，条目200包括四个冲突桶201并 且能够存储与单个第一哈希值H1关联的四个不同偏移和签名。在其 他实施例中，条目200包括其他适当数目(例如，1个、2个、3个、 5个、6个等)的冲突桶，并且相应地能够存储与单个哈希值H1关 联的其他对应数目的偏移和签名。

附加地，在一些实施例中，条目200被构造用于支持解决在共 享第一哈希值H1和第二哈希值H2二者、但是具有不同第三哈希值 H3的多个关键字之间的冲突。在这样的情形中，从条目200中的多 个偏移为多个关键字选择相同偏移，但是选择的偏移被应用于不同 第三哈希值H3从而产生转发表106中的不同存储器位置。在一个实 施例中，冲突计数器字段203被用来统计(account for)对应偏移字 段206中的偏移被用于的多个关键字。如以下将更具体说明的那样， 在从转发表106删除偏移被用于的多个查找关键字时利用多个关键 字的这样的统计，从而使得冲突桶保持有效，直至去除多个查找关 键字中的最后查找关键字。在一个实施例中，每个冲突计数器字段 204包括两位并且能够统计最多四个查找关键字。在其他实施例中， 利用其他适当长度的冲突计数器字段。例如，每个冲突计数器字段 204包括除了两位之外的适当数目的位(例如，1、3、4、5位等)， 并且相应地能够统计共享对应偏移的不同对应数目的查找关键字。

图3A-图3B是图示根据一个实施例的用于在数据库中对查证 关键字定位并且从数据库取回与查找关键字关联的信息的示例查找 方案300的流程图。在一个实施例中，在图1的网络设备100中实 施查找方案300。例如在一个实施例中，查找方案300由图1的查找 单元114a实施。在其他实施例中，在其他适当网络设备中实施查找 方案300。类似地，在其他实施例中，图1的网络设备100(例如， 网络设备100的查找114a)实施除了技术300之外的适当查找技术。 为了易于说明，以下将查找方案300描述为与图1的查找表107、转 发表106和CAM108结合由查找单元114a实施。

在块302，获得查找关键字X。在一个实施例中，基于在包中 包括的或者与包关联的信息生成查找关键字X。例如，在一个实施 例中，查找关键字由与包关联的目的地MAC地址和VLAN标签组 成。在其他实施例中，关键字X包括与包关联的其他适当信息。

在块304，生成用于关键字X的多个哈希值。在一个实施例中， 在块304生成的哈希值包括第一哈希值H1=h1(X)、第二哈希值 H2=h2(X)和第三哈希值H3=h3(X)，其中h1、h2和h3是相异哈希函 数。例如，在一个实施例中，使用相异生成器多项式(比如32CRC 多项式)实施哈希函数h1、h2、h3。在一个示例实施例中，第三哈 希值H3=HI+H2+h3(X)。在其他实施例中，以其他适当方式生成第三 哈希值H3。在一些实施例中，与第一哈希值H1和/或第二哈希值 H2独立地生成第三哈希值H3。一般而言，任何适当哈希值生成方 案可以用来在块304为关键字X生成多个哈希值。

在块306，查找单元114a使用在块304生成的第一哈希值H1 执行第一存储器访问。具体而言，在块306的第一存储器访问中， 查找单元114a使用值H1作为进入查找表107的索引访问查找表 107，并且从查找表107取回对应条目。在一个实施例中，取回的查 找条目被构造为图2的条目200。在这一实施例中，取回的查找表包 括四个冲突桶，并且每个冲突桶包括相应签名字段、相应冲突计数 器字段和相应偏移字段。在另一实施例中，以另一适当方式构造取 回的查找表条目。

在块308，查找单元114a分析取回的条目以确定取回的条目 的冲突桶是否包括与在块304为关键字生成的第二哈希值匹配的签 名。另外，在标识具有与H2匹配的签名的冲突桶时，查找单元114a 确定标识的冲突桶是否在冲突桶的偏移字段中包括有效偏移。例如， 在一个实施例中，在冲突桶的偏移字段中的全一(即，偏移字段的 每个位被设置成逻辑一(1))指示偏移无效，并且在冲突桶的偏移 字段中的任何其他值(即，偏移字段的位中的一位或者多位被设置 成逻辑零(0))是有效偏移。在其他实施例中，偏移字段的其他适 当值指示在标识的冲突桶中的偏移不是有效偏移。

如果在块308标识具有与H2匹配的签名并且具有有效偏移的 冲突桶，则查找方案在块310继续，查找单元114a在该块执行第二 存储器访问，从而访问转发数据库106。在第二存储器访问中，查找 单元114a使用H3和从在块308标识的冲突桶的偏移字段取回的偏 移访问转发表106。另一方面，如果在块308未标识具有与H2匹配 的签名的有效冲突桶，则方案300在块312继续，查找单元114a在 该块使用H3和默认偏移执行第二存储器访问。在一些实施例中，默 认偏移可配置。在其他实施例中，默认偏移被预设或者预定并且不 可配置。

在任何情况下，在第二存储器访问(在块310或者在块312) 中，查找单元114a从转发表106取回转发条目。在一个实施例中， 从转发表106取回的转发条目包括关键字和与关键字关联的信息。 现在参照图3B，方案300在块314继续。在块314，查找单元114a 比较在块310或者在块312从转发表106取回的转发条目中的关键 字与在块302获得的查找关键字X。在一个实施例中，在块314的 在取回的条目中的关键字与关键字X匹配这样的确定表明成功查找 已经出现。在这一情况下，根据一个实施例，与关键字关联的取回 的信息(例如，标识应当经由其传输包的一个端口(或者多个端口) 112的转发信息)用来例如对包执行一个或者多个动作，比如向标识 的一个端口(或者多个端口)112转发包。然而，在一些情况下，在 决314确定在决310或者在块312从转发表106取回的转发条目中 的关键字未与在块302获得的关键字X匹配。在这一情况下，方案 300在块316继续，查找单元114a在该块使用关键字X搜索CAM108 以尝试在CAM108中发现用于关键字X的匹配。备选地，在另一实 施例中，查找单元114a在至少一些情形中与访问转发表106和/或访 问查找表107并行地搜索CAM108，这造成在其中关键字位于CAM 108中的情况下的更低延时。在通过完全引用而结合于此、Levi等人、 于2012年8月31日提交、名称为“Efficient TCAM Architecture” 的第61/695，520号美国临时专利申请中更具体描述在一些实施例中 利用的用于与基于CAM的数据库中的搜索并行执行基于哈希的数 据库中的搜索的示例技术。

在任何情况下，当在CAM108中发现用于关键字X的匹配(在 块318为“是”)时，则在CAM108中的成功查找已经出现。在这一 情况下，在一个实施例中，查找单元114a例如从由与关键字X匹配 的条目指示的存储器位置取回与关键字关联的信息，比如转发条目。 在一个实施例中，由与关键字X匹配的条目指示的存储器位置是在 转发表106中的存储器位置。例如，在一个实施例中，在CAM108 中的每个条目指示进入转发表106的索引。在另一实施例中，由与 关键字X匹配的CAM条目指示的存储器位置是在除了转发表106 之外的存储器中的存储器位置。

另一方面，如果在CAM108中未发现匹配(在块318为“否”)， 则查找已经失败，即，在数据库中未发现查找关键字X。在这一情 况下，采取用于失败查找的适当动作。将在失败查找情形中采取的 特定动作依赖于具体实施例和/或场景。例如，在一个实施例和/或场 景中，转发引擎104向(例如，在第2层桥接设备中的)端口112 中的所有的端口传涌包。作为另一示例，在另一实施例和/或场景中， 发起用于向数据库中插入关键字X和与关键字X关联的信息的过 程。附加地或者备选地，在其他实施例中，在失败查找的情况下执 行其他适当默认或者预定操作。

图4A-图4B是图示根据一个实施例的用于向数据库中插入查 找关键字和与关键字关联的信息的示例更新方案400的流程图。在 一个实施例中，在图1的网络设备100中实施更新方案400。例如， 在一个实施例中，图1的更新单元114b完全或者部分实施更新方案 400。在其他实施例中，在其他适当网络设备中实施更新方案400。 类似地，在一些实施例中，图1的网络设备100(例如，网络设备 100的更新单元114b)实施除了更新方案400之外的适当更新方案。 为了易于说明，以下将更新方案400描述为与图1的转发表106、查 找表107和CAM108结合由更新单元114b执行。

在块402，获得将向数据库中插入的查找关键字X。在一个实 施例中，基于在如下包中包括的或者与该包关联的信息生成查找关 键字X，已经为该包将目的地地址链接到特定的一个端口或者(多 个端口)112。在一个实施例中，查找关键字X例如由已经被链接到 特定的一个端口或者(多个端口)112的目的地MAC地址和VLAN 标签中的一项或者多项组成。在其他实施例中，关键字X包括在包 中包括的或者与包关联的其他适当信息。

在块404，生成用于关键字X的多个哈希值。在一个实施例中， 在块304生成的哈希值包括第一哈希值H1=h1(X)、第二哈希值 H2=h2(X)和第三哈希值H3=h3(X)，其中h1、h2和h3是相异哈希函 数。在一些实施例中，使用相异或者有关生成器多项式(比如32CRC 多项式)实施哈希函数h1、h2和h3。在一个示例实施例中，第三哈 希值H3=HI+H2+h3(X)。在其他实施例中，以其他适当方式生成第三 哈希值H3。在一些实施例中，与第一哈希值H1和/或第二哈希值 H2独立地生成第三哈希值H3。一般而言，任何适当哈希值生成方 案可以用来在块404为关键字X生成多个哈希值。

在块406，更新单元使用第一哈希值H1作为进入查找表107 的索引访问查找表107。在块408，更新单元114b确定具有与关键 字X对应的签名的有效冲突桶是否已经在查找表107中存在于在块 406访问的条目中。在一个实施例中，为了确定具有与关键字X对 应的签名的有效冲突桶是否存在于在块406访问的条目中，更新单 元114b比较查找表条目中的冲突桶的签名字段与第二哈希值H2。 在标识具有与第二哈希值H2匹配的签名的冲突桶时，更新单元114b 确定标识的冲突桶是否在冲突桶的偏移字段中包括有效偏移。例如， 在一个实施例中，在冲突桶的偏移字段中的全一(即，偏移字段的 每个位被设置成逻辑一(1))指示偏移无效，并且在冲突桶的偏移 字段中的任何其他值(即，偏移字段的位中的一位或者多位被设置 成逻辑零(0))对应于有效偏移。在其他实施例中，偏移字段的其 他适当值指示在标识的冲突桶中的偏移不是有效偏移。

当在块408标识具有与第二哈希值H2匹配的签名的冲突桶 时，方案400在块410继续，更新单元114b在该块确定对应偏移是 否可以用于向转发表106中插入附加关键字。在一个实施例中，更 新单元114b检查在块408标识的冲突桶的冲突计数器字段，并且如 果冲突计数器未超过某个最大值则确定对应偏移可以用于向转发表 106中插入附加关键字。例如，在一个实施例中，每个冲突计数器字 段包括两位并且能够支持最多四个关键字。在这一实施例中，更新 单元114b在冲突计数器指示三个或者更少关键字当前利用偏移时确 定附加关键字可以利用偏移。另一方面，在冲突计数器字段指示已 经向转发表106中插入冲突桶可以容纳的关键字的最大数目(例如， 在冲突计数器字段中为四的值)时，更新单元114b确定无法向转发 表106中插入附加关键字。

在块412，在确定可以插入附加关键字时，更新单元114b将 对应偏移应用于在块404生成的第三哈希值，并且利用具有偏移的 第三哈希值作为进入转发表106的索引。在块414，更新单元114b 确定在转发表106中的编索引的条目是否为空(即，可用)。参照 图4B，在确定编索引的条目可用时，方案400在块424继续，更新 单元114b在该块向转发表106中的条目中插入关键字X(和与关键 字X关联的信息)。在这一情况下，由于具有大于零(0)的冲突计 数器值的、已经与有效冲突桶关联的偏移用来插入关键字，所以无 需更新查找表以指示新偏移。因而，在这一情况下，方案400跳过 块426并且在块428继续，更新单元114b在该块递增在块408标识 的冲突桶的冲突计数器字段(例如，在关键字X是将与冲突桶关联 的第一关键字的情况下，更新单元114b将计数器字段的值从-1改变 成0)以统计在块424中向转发表106中插入的关键字X。

现在返回到图4A的块408，当在块408未标识具有与第二哈 希值H2匹配的签名的冲突桶时，方案400然后在块418继续，更新 单元114b在该块确定未占用的冲突桶是否存在于在块406访问的查 找表条目中。如果在块418确定未占用的冲突桶存在，则更新单元 114b使用第三哈希值H3访问转发表106，并且搜索转发表106以从 由第三哈希值H3编索引的条目发现可用偏移。换言之，在一个实施 例中，更新单元114b搜索转发表106以寻找未占用的条目，其中该 搜索开始于由H3编索引的条目并且结束于与由查找表107支持的最 大偏移对应的条目。如果标识了这样的条目，则更新单元114b在块 424向标识的条目中插入关键字X(和与关键字X关联的信息)。 然后，在块426，更新单元114b用与在块422标识的条目对应的偏 移更新在块418(图4A)标识的冲突桶。此外，更新单元114b递增 在块418标识的冲突桶的冲突计数器以统计在块424向转发106中 插入的关键字X。

再次参照图4A，块410、414和418中的每个块的“否”分支通 向块416，更新单元114b在该块访问CAM108以尝试向CAM108 中插入关键字X。在块430(图4B)确定是否可以向CAM108中插 入关键字X。在确定可以向CAM108中插入关键字时，更新单元114b 向CAM108中插入关键字(图4B的块432)。另一方面，在确定 无法向CAM108中插入关键字时(例如，当在CAM中无空的空间 时)，关键字X的插入已经失败。

图4C是图示在一些实施例中与图4A-图4B的更新技术400 结合实施的冲突解决方案450的流程图。方案450包括如下一些块， 这些块是技术400的公共块，并且这些块相对于图4A-图4B的对应 块由相似编号的块引用(例如，块432)。在方案450中，在一个实 施例中，支持使用默认偏移向转发表107中的插入。在一个实施例 中，默认偏移可配置。在其他实施例中，默认偏移被预设或者预定 并且不可配置。

冲突解决方案450开始于与图4A的块418对应的块418。当 在块418确定无可用(未使用)冲突桶存在于在块408标识的查找 表条目中时，取代如根据方案400完成的那样前进到块432，方案 450前进到块434，在该块确定是否启用默认偏移。如果在块434确 定未启用默认偏移，则方案450前进到块432，在该块根据方案400 尝试向CAM108中插入关键字。另一方面，当在块434确定启用默 认偏移时，则方案450在块436继续，在该块将默认偏移应用于第 三哈希值H3以确定用于转发表106的索引，并且使用确定的索引访 问转发表106。

在块438确定是否占用了在块436访问的条目。当在块438确 定条目被占用时，则方案350在块432继续，在该块尝试向CAM108 中插入。然而，当在块438确定未占用在块436访问的条目时，在 块436访问的条目向转发表106中插入关键字X。在这一情况下， 根据方案450，在至少一些情形中，即使具有未与关键字X匹配的 签名的关键字已经占用了与用于关键字X的第一哈希值关联的所有 冲突桶，仍然向转发表106中插入关键字X。在一个实施例中，在 效果上，在查找表106“以外”学习这样的关键字。

在一个实施例中，由图1的处理器120和存储器122辅助方案 450的实现方式。具体而言，为了防止对于在查找表106以外学习的 关键字的后续查找错误，在这一实施例中，处理器120在存储器中 (例如，在存储器122中或者在耦合到处理器120的另一存储器中) 存储这样的关键字的签名。后续查找错误可以例如出现于查找表107 中的与关键字X的第一哈希值H1对应的冲突桶随后变成可用(例 如，由于删除与这一冲突桶先前关联的关键字)，并且然后用于具 有与关键字X的第二哈希值H2匹配的第二哈希值H2的其他关键字 时。这将造成为关键字X后续执行的未成功查找，因为将在查找期 间不再访问其中存储X的转发表条目。为了防止这一场景，在一个 实施例中，处理器120检查在查找表106以外学习的关键字的存储 的签名并且防止随后向查找表106中写入与存储的签名匹配的签名。 例如，在一个实施例中，取而代之，在这样的情形中，处理器120 使更新单元114b使用与关键字对应的第三哈希值H3访问转发表 106。

再次参照图1，在一些实施例中，为了进一步提高转发表107 的存储器利用率，处理器120执行存储器122中存储的指令以在一 些情形中实施如下技术，比如基于跳房子哈希化(hopscotch hasing) 的技术，该技术重排转发表106中的条目以由此允许插入原本不能 向转发表106中插入的至少一些查找关键字。图5A-图5B是图示根 据一个示例实施例的用于重排数据库表510中的条目的方案500的 示图。在一个实施例中，(例如，由处理器120)在转发引擎104 中实施方案500以重排转发表106中的条目。在这一实施例中，与 图1的查找表107结合实施方案500。在一个实施例中，与图4A- 图4B的更新方案400结合利用方案500以重排转发表106中的条目 以在更新方案400由于转发表106中的冲突而不能向转发表106中 插入查找关键字时允许向转发表106中插入查找关键字。

在图5A-图5B中所示的实施例中，将表510示出为具有五个 条目512-1至512-5。虽然将表510图示为具有五个条目，但是表510 一般包括任何适当数目的条目，并且在一些实施例中，在表510中 的条目数目多于五个条目或者少于五个条目。根据所示实施例，在 图5A-图5B中在条目512的右侧指示条目索引。一般而言，使用为 查找关键字生成的第三哈希值H3和为查找关键字选择或者确定的 偏移向表500中插入查找关键字。在一个实施例中，偏移的值受最 大偏移限制。在图5A-图5B的示例实施例中，最大偏移等于三。因 而，在这一实施例中，可以在具有在x与x+3之间的索引的可用(未 占用)表条目向表510中插入具有等于x的第三哈希值H3的查找关 键字。在其他实施例中，利用最大偏移的其他适当值。

首先参照图5A，表510的所有条目512初始地为空。将向表 510中插入的第一查找关键字514-1对应于第三哈希值H3=x，并且 用偏移0(即，在由值x编索引的表条目)向表510中插入。将向表 510中插入的第二查找关键字514-2对应于第三哈希值H3=x，并且 用偏移1(即，在由值x+1编索引的表条目)向表510中插入。将向 表510中插入的第三查找关键字514-3对应于第三哈希值H3=x+1， 并且由于第二查找关键字514-2已经占用了由值x+1编索引的条目， 因此用偏移1(即，在由值x+2编索引的表条目)向表510中插入。 将向表510中插入的第四查找关键字514-4对应于第三哈希值H3=x， 并且用偏移3(即，在由值x+2编索引的条目)向表510中插入。

将向表510中插入的第五查找关键字514-5对应于第三哈希值 H3=x。无法向表510中插入查找关键字514-5，因为其他关键字当前 占用在可以向其中插入具有H3=x的关键字的条目范围内的所有条 目(即，在x与x+3之间的条目)。如图5B中所示，在一个实施例 中，第三查找关键字514-3然后移向由x+4编索引的空条目，并且 与第三查找关键字514-3关联的偏移被改变成值3，由此允许在由 x+2编索引的位置向表510中插入第五查找关键字514-5。因而，然 后在由x+2编索引的位置用偏移向3向表510中插入第五查找关键 字514-5。另外，在一个实施例中，更新与查找关键字514-3关联的 查找表条目(例如，在图1的查找表107中的冲突桶中)以反映用 于查找关键字514-3的新偏移。

在一个实施例中，为了避免更新其他查找关键字也与之关联的 偏移，在移动查找关键字514-3之前，检查与查找关键字514-3关联 的冲突桶以保证无其他查找关键字与对应偏移关联。例如，在与查 找关键字514-3关联的冲突计数器的值指示查找关键字514-3是与对 应偏移关联的仅有关键字(例如，冲突计数器的值等于0)时，查找 关键字514-3被移向由x+4编索引的位置，并且相应地更新偏移字 段以对应于由x+4编索引的新位置。然而，在一个实施例中，在冲 突计数器的值指示一个或者多个其他关键字与对应偏移关联(例如， 冲突计数器的值大于0)时，则查找关键字514-3未被移向新位置。 在一些实施例和/或场景中，在这一情况下，不同查找关键字(与指 示查找关键字是与对应偏移关联的仅有关键字的冲突计数器关联的 查找关键字)被移向新位置以允许插入查找关键字515-5。也就是说， 在这一实施例中，查找关键字的重定位仅限于如果查找关键字例如 如由与特定冲突桶关联的对应冲突计数器的值0指示的那样是与冲 突桶关联的仅有查找关键字，则对查找关键字重定位。

备选地，在其中查找关键字514-3与之关联的冲突计数器的值 指示一个或者多个其他关键字与对应偏移关联(例如，冲突计数器 的值大于0)的另一实施例中，包括查找关键字514-3的与冲突桶关 联的所有查找关键字被移向新位置，并且在查找关键字514-3的先前 位置向表510中插入查找关键字514-5。另外，在这一实施例中，例 如在图1的查找表107中更新与重定位的查找关键字关联的相应偏 移以恰当反映重定位的查找关键字的新位置。

图6是根据一个实施例的用于在网络设备中对包执行动作或 者动作集(比如转发包)的示例方法600的流程图。在一个实施例 中，方法600由图1的切换设备100实施。例如，在一个实施例中， 方法600至少部分由图1的转发引擎104实施。在其他实施例中， 方法600由切换设备100的其他适当部件或者由另一适当网络设备 实施。

在块602，基于与包对应的查找关键字生成多个哈希值。在一 个实施例中，哈希值由图1的哈希值生成器110生成。在其他实施 例中，哈希值由切换设备100的其他适当部件或者由另一适当切换 设备生成。在一个实施例中，与包对应的查找关键字包括在包中包 括的或者与包关联的各种信息。例如，查找关键字包括目的地MAC 地址和VLAN标签等中的一项或者多项。在其他实施例中，查找关 键字包括在包中包括的或者与包关联的其他适当信息。

在块604，使用在块602生成的第一哈希值和第二哈希值搜索 查找表。在一个实施例中，搜索图1的查找表107。在另一实施例中， 搜索另一适当查找表。在一个实施例中，查找表包括构造为图2的 条目200的条目。在其他实施例中，查找表包括以其他适当方式构 造的条目。在一个实施例中，基于第一哈希值标识查找表中的条目， 并且使用第二哈希值搜索标识的条目以选择标识的条目的与第二哈 希值对应的子条目。

在块606，使用第三哈希值和在块604确定的偏移搜索适当网 络设备数据库，比如转发表。在一个实施例中，搜索转发表106。在 另一实施例中，搜索另一转发表或者除了转发表之外的适当数据库。 在一个实施例中，搜索数据库包括将偏移应用于第三哈希值以确定 进入数据库的索引，从而访问数据库以取回与确定的索引对应的条 目。在一个实施例中，取回的条目包括用于对包执行一个或者多个 动作的信息。例如，在一个实施例中，取回的条目是指示应当如何 (例如，向哪个端口)转发包的转发条目。在其他实施例中，取回 的条目指示关于除了转发包之外的一个或者多个动作的信息，比如 关于将向包应用的过滤的信息、关于与包的服务质量(QoS)处理关 联的动作或者动作集的信息、与在网络设备中收集统计量有关的信 息等。在块608，将由在块606取回的条目指示的一个或者多个动作 应用于包。例如，在一个实施例中，在转发数据库应用中，基于在 块606选择的转发条目向网络设备的端口转发包。在其他实施例中， 在块608将基于在块606取回的条目的其他适当的一个或者多个动 作应用于包。

图7是根据一个实施例的用于在网络设备中填充转发数据库 的示例方法700的流程图。在一个实施例中，方法700由图1的切 换设备100实施。例如，在一个实施例中，方法700至少部分由图1 的转发引擎104实施。在其他实施例中，方法700由切换设备100 的其他适当部件或者由另一适当网络设备实施。

在块702，基于与包对应的查找关键字生成多个哈希值。在一 个实施例中，哈希值由图1的哈希值生成器110生成。在其他实施 例中，哈希值由切换设备100的其他适当部件或者由另一适当切换 设备生成。在一个实施例中，与包对应的查找关键字包括在包中包 括的或者与包关联的各种信息。例如，查找关键字包括目的地MAC 地址和VLAN标签等中的一项或者多项。在其他实施例中，查找关 键字包括在包中包括的或者与包关联的其他适当信息。

在块704，至少基于第一哈希值和第二哈希值确定进入转发表 的偏移。在一个实施例中，确定偏移包括访问查找表以确定与第一 哈希值和第二哈希值关联的偏移是否已经存在于查找表中。在一个 实施例中，确定偏移包括访问图1的查找表107，该查找表107具有 被构造为图2的条目200的条目。在另一实施例中，确定偏移包括 访问另一适当查找表。在一个实施例中，在与第一哈希值和第二哈 希值关联的偏移已经存在于查找表中时，将偏移设置成从查找表取 回的偏移。然后将偏移应用于第三哈希值以确定进入转发表(例如， 图1的转发表106或者另一适当转发表)的索引。如果与第一哈希 值和第二哈希值关联的偏移尚未存在于查找表中，则使用第三哈希 值访问转发表，并且在可用偏移存在于转发表中时确定转发表中的 这样的可用偏移。在一个实施例中，如果可用偏移未存在于(例如， 受最大偏移值限制的)转发表中，则根据适当重排技术(比如图5A- 图5B的技术500)重排转发表中的条目。在一个实施例中，在这一 情况下，确定偏移为作为重排的结果而变成可用的偏移。在一个实 施例中，在查找表无法支持插入具有第一哈希值的附加关键字时， 将偏移设置成默认偏移。在至少一些实施例中，这些数据库填充技 术高效地解决可能在向转发表中插入关键字期间产生的各种冲突， 由此增加查找表的存储器利用率。

在块706，基于第三哈希和在块706确定的偏移确定转发表中 的位置。在块708，确定是否可以向确定的位置上插入查找关键字而 未与先前存储于转发表中的另一查找关键字冲突。在确定可以在转 发表中的确定的位置插入查找关键字时，在块710在确定的位置插 入查找关键字和与查找关键字关联的信息。

在一个实施例中，当在块708确定无法向确定的位置上插入查 找关键字而未与先前存储于转发表中的另一查找关键字冲突时，访 问附加存储器(比如CAM(例如，图1的CAM108))以确定附加 存储器是否可以容纳查找关键字。在确定附加存储器可以容纳查找 关键字时，查找关键字(并且在一些实施例中与查找关键字关联的 转发信息)被存储于附加存储器中。在一些实施例中，在附加存储 器无法容纳查找关键字时，查找关键字的插入失败。在一个实施例 中，根据方法700的插入技术在至少一些情形中增加转发表的利用 率并且减少失败插入的概率。

可以在硬件中(比如在一个或者定制集成电路、专用集成电路 (ASIC)、现场可编程门阵列(FPGA)等中)实施以上关于图2- 图4描述的各种块、操作等。可以全部或者部分使用执行机器可读 软件和/或固件指令的处理器实施以上关于图5描述的各种块、操作 等。

尽管已经参照如下具体示例描述了本发明(这些具体示例旨在 于仅为举例说明而不是限制本发明)，但是本领域普通技术人员将 清楚，还可以对公开的实施例进行除了以上明确描述的改变、添加 或者修改之外的改变、添加或者修改而不脱离本发明的精神实质和 范围。