用于在分组转发装置中针对每个模块在因特网协议切换模式之间进行自动选择的方法、系统以及计算机可读介质

摘要

本申请描述的主题包括用于在分组转发装置中针对每个模块在因特网协议切换模式之间进行自动选择的方法、系统以及计算机可读介质。根据一个方案，本申请描述的主题包括分组转发装置，其包括至少一个输入/输出（I/O）模块。至少一个I/O模块包括最长前缀匹配（LPM）表和因特网协议转发数据库（IPFDB），并且分组转发装置包括IP路由表和IPFDB。当I/O模块以LPM模式操作时，I/O模块上的IPFDB填充有与活动主机相对应的条目填充，I/O模块上的LPM表填充有具有从IP路由协议知悉的路由的IP路由表，并且由I/O模块接收的层3分组是使用I/O模块的IPFDB和LPM表进行路由的。自动模式选择模块确定I/O模块上的LPM表的容量。自动模式选择模块还确定存储在IP路由表中的IP路由的总数量，并确定IP路由的总数量与LPM表的容量之间的关系。响应于确定IP路由的总数量与LPM表的容量具有预定关系，自动模式选择模块还自动地将I/O模块从LPM模式切换到IPFDB模式，其中IPFDB和LPM表填充有与活动主机相对应的条目，并且由I/O模块接收到的层3分组是使用I/O模块的IPFDB和LPM表进行路由的。

说明书

优先权要求

本申请要求享有于2010年3月15日递交的、美国临时专利申请序列 No.61/340,279以及于2010年6月21日递交的、美国专利申请序列No. 12/820,111的优先权，这两个专利申请的每一个的公开内容以引用方式全部 内容并入本文。

技术领域

本申请描述的主题涉及对因特网协议（IP）分组进行路由。更具体地， 本申请描述的主题涉及用于在分组转发装置中针对每个模块在IP切换模式 之间进行自动选择的方法、系统以及计算机可读介质。

背景技术

传统IP网络设施硬件利用用于对IP分组进行路由的两种通用方式之 一。在第一种方式（在下文中，称为“LPM模式”或“LPM方式”）中， 每个分组的IP目的地地址被用作用于搜索包括可变长度地址前缀的基于硬 件的最长前缀匹配（LPM）表的关键词。硬件LPM表中的匹配产生了进入 IP邻接表的索引，在该IP邻接表中，获得对分组进行成功路由所需要的下 一跳转发信息。在第一种方式中，可使用与相邻IP分组转发装置交换信息 的一个或多个路由协议来填充硬件LPM表，或可经由配置来填充硬件LPM 表。

在第二种方式（在下文中，称为“IPFDB模式”或“IPFDB方式”）中， 每个分组的IP目的地地址被用作用于搜索以活动主机的IP地址填充的、基 于硬件的IP主机转发数据库（IPFDB）的关键词。应理解当以IPFDB模式 操作时，活动主机可包括直接连接的主机和远程位于网络另一侧的主机。 硬件IPFDB中的匹配产生了对分组进行成功路由所需要的下一跳转发信 息。在第二种方式中，活动主机的IP地址基于“要求”被填充到IPFDB中。 即，当给定主机的流起动时，其IP地址初始没有被存储在IPFDB中并且必 须被慢路处理（slowpath process），其中慢路处理包括使用中央处理器（CPU） 处理分组。分组的成功的慢路处理导致活动主机的IP地址被编入后续分组 的硬件IPFDB中。

例如，参见图1，I/O模块102A和106A可以以LPM模式或IPFDB模 式操作。在LPM模式中，LPM表200和204可由与可变长度地址前缀和用 于达到目的地的下一跳相应的条目进行填充，并且IPFDB 202和206可由 全长32-或128-比特的主机条目进行填充。在IPFDB模式中，LPM表200 和204以及IPFDB 202和206可由全长32-或128-比特主机条目进行填充。 此外，I/O模块102A-102C和106A-106B可以以“混合模式”操作，在该 混合模式中，对于每个I/O模块，IPFDB可由直接连接的主机的全址条目 进行填充，并且LPM表可由可变长度前缀和全主机地址的混合进行填充。 在于2005年12月23日递交的、美国专利申请序列No.11/317,665以及于 2006年12月22日递交的、美国专利申请序列No.11/644,701中描述了关 于此方面的额外细节，这两个美国申请的公开内容以引用方式全部内容并 入本文。

LPM方式的一个优点是当整个路由表可被包括在可用硬件LPM表中 时，几乎数量不限的主机终端站可通过交换机通信，而没有慢路干扰。相 反，IPFDB方式的一个优点是当路由表与硬件LPM表不适应（例如对于少 量的主机）时，路由可以更快。例如，通过基于在位于每个I/O模块上的基 于硬件的IPFDB中的精确匹配查找对分组进行路由，可使用较少的存储器 和CPU资源来对分组进行慢路处理。换言之，当整个路由表可被包括在可 用硬件LPM表中时，LPM方式更具有优势；而当整个路由表不能被包括在 可用硬件LPM表中时，IPFDB方式更具有优势。

当生产费用敏感的网络设备时，硬件LPM表的大小对于某些应用会受 限。在一个示例场景中，边缘模块可支持512个LPM IPv4路由和2K个IPv4 主机，并且聚合模块可支持512,000个LPM IPv4路由和16,000个IPv4主 机。接着，考虑控制面路由表的大小为250,000个IPv4路由和1,000个直接 连接的IPv4主机的网络。可理解，这整个路由表不能被包括在边缘模块 102A-102C的可用硬件LPM表中，然而可被整体包括在聚合模块 106A-106B的LPM表中。这样，对于边缘模块102A-102C而言IPFDB-模 式路由可能是适当的，以避免不必要的慢路处理。由于边缘模块不能在大 小为512的LPM表中存储250,000个路由，所以只将250,000个路由中的 512个（即0.2%）填充到此HW表中不会有太大的用处。因而，在分组转 发设备中，通过仅保持活动主机的高速缓冲存储器而不是整个路由表， IPFDB方式需要较少的存储器和较少CPU功率。

相反，LPM-模式路由对于聚合模块106A-106B可能是适当的，这是由 于路由表在硬件范围内，这是因为可以使用硬件IPFDB路由到所有直接连 接的主机，并且可以使用硬件LPM表路由到所有经由网关连接的主机，而 不需要对分组进行慢路处理。

与传统分组转发装置相关联的一个问题是它们可能在特定条件下对某 些I/O模块使用低效方式。例如，在分组转发装置100中，如果I/O模块 102A和106A以LPM模式操作（默认），则低容量I/O模块102A可能存储 数个路由的实质上无意义的片段，对分组转发装置100没有增加任何性能 优点。

另一个问题是某些分组转发设备可能不具有足够的存储器来以软件保 存全部路由表，也不具有足够的CPU功率来处理所有的路由增加和删除操 作。例如，传统LPM模式操作需要更多的存储器和CPU功率来处理路由 增加和删除操作，而IPFDB模式并不需要，这是由于替代地，IPFDB模式 仅保持了活动主机的高速缓冲存储器，而不是整个路由表。如上文所示， 在IPFDB模式适当而并未使用的场景下，传统分组转发装置可次优地操作。

因此，存在对更有效地利用IP分组转发装置中的基于硬件的LPM表 和IPFDB的改进的方法、系统以及计算机可读介质的需求。

发明内容

本申请描述的主题包括用于在分组转发装置中针对每个模块在因特网 协议切换模式之间进行自动选择的方法、系统以及计算机可读介质。根据 一个方案，本申请描述的主题包括一种分组转发装置，其包括至少一个输 入/输出（I/O）模块。至少一个I/O模块包括最长前缀匹配（LPM）表和因 特网协议转发数据库（IPFDB），并且分组转发装置包括IP路由表和IPFDB。 当I/O模块以LPM模式操作时，I/O模块上的IPFDB填充有与活动主机相 对应的条目，I/O模块上的LPM表被填充具有从IP路由协议知悉的路由的 IP路由表，并且使用I/O模块的IPFDB和LPM表来路由I/O模块所接收到 的层3分组。自动模式选择模块确定I/O模块上的LPM表的容量。自动模 式选择模块还确定被存储在IP路由表中的IP路由的总数量，并确定IP路 由的总数量与LPM表的容量之间的关系。响应于确定IP路由的总数量与 LPM表的容量具有预定关系，自动模式选择模块还将I/O模块从LPM模式 自动切换到IPFDB模式，其中IPFDB和LPM表填充有与活动主机相对应 的条目，并且使用I/O模块的IPFDB和LPM表路由I/O模块所接收到的层 3分组。

根据另一个方案，公开了一种用于针对每个模块自动地选择转发方式 的方法。该方法包括：以LPM模式操作多输入/输出（I/O）模块分组转发 装置中的I/O模块。I/O模块包括最长前缀匹配（LPM）表和因特网协议转 发数据库（IPFDB），并且分组转发装置包括IP路由表。以LPM模式操作 I/O模块包括用与活动主机相对应的条目填充IPFDB，用来自具有从IP路 由协议知悉的路由的IP路由表的条目填充LPM表，以及使用I/O模块的 IPFDB和LPM表对I/O模块所接收到的层3分组进行路由。确定LPM表 的容量。确定存储在IP路由表中的IP路由的总数量以及IP路由表中的IP 路由的总数量与LPM表的容量之间的关系。响应于确定IP路由表中的IP 路由的总数量与LPM表的容量具有预定关系，将I/O模块从LPM模式自 动切换到IPFDB模式，其中以IPFDB模式操作I/O模块包括用与活动主机 相对应的条目填充IPFDB和LPM表，并且使用I/O模块的IPFDB和LPM 表对I/O模块接收到的层3分组进行路由。

可以用硬件、软件、固件或其任意组合来实施本申请描述的用于在分 组转发装置中针对每个模块在因特网协议切换模式之间进行自动选择的主 题。可使用以有形的、非暂时性的计算机可读介质体现的计算机可执行指 令来实施本申请描述的主题。适于实施本申请描述的主题的示例非暂时性 的计算机可读介质包括盘存储装置、芯片存储装置、可编程逻辑装置以及 专用集成电路。此外，实施本申请描述的主题的计算机程序产品可在单个 装置或计算平台上实施，或可分布在多个装置或计算平台上。

附图说明

现在将参考附图解释本申请描述的主题，其中：

图1为示出了根据本申请描述的主题的实施例的多模式层3分组转发 装置的网络图，该分组转发装置包括连接到多个终端装置的边缘模块和连 接到一个或多个核心网络装置的聚合模块；

图2为示出了根据本申请描述的主题的实施例的在IP路由的总数量与 I/O模块的基于硬件的LPM表的容量之间的示例关系的图表，该关系用于 在LPM转发模式与IPFDB转发模式之间进行选择；

图3为根据本申请描述的主题的实施例的示例多模式层3分组转发装 置的方框图，该分组转发装置包括可以以LPM转发模式和IPFDB转发模式 之一进行操作的I/O模块；

图4为示出了根据本申请描述的主题的实施例的用于在多模式层3分 组转发装置处路由分组的示例步骤的流程图；以及

图5为示出了根据本申请描述的主题的实施例的用于在多模式层3分 组转发装置处路由分组的示例步骤的更详细流程图。

具体实施方式

如上文所述，由于传统网络装置可能包括具有不同的基于硬件的LPM 表大小的I/O模块的混合，从而可能希望以LPM模式操作某些I/O模块而 以IPFDB模式操作其他模块。根据本申请描述的主题，公开了用于针对每 个模块在IP切换模式之间进行自动选择的方法。该方法可包括：确定位于 多模块IP分组转发装置（例如路由器）中的每个I/O模块上的硬件LPM表 的容量。接着，确定当前存储在软件LPM表中（被所有I/O模块共享）的 路由的数量。如果软件LPM表可被整体地存储在I/O模块的硬件LPM表 内，则可为该I/O模块自动选择LPM模式。反之，如果软件LPM表的内 容不能存储在特定I/O模块的硬件LPM表内，则可以将该I/O模块自动转 换为以IPFDB模式操作，这可更有效的使用硬件资源。因而，可基于网络 条件最佳地自动地操作包括具有不同硬件LPM表大小的I/O模块的多模块 分组转发装置。在下文中，现将关于图1描述包括多模块IP分组转发装置 的示例系统。

图1为示出了根据本申请描述的主题的实施例用于针对每个模块在IP 切换模式之间进行自动选择的多模块IP分组转发装置的网络图。参见图1， 分组转发装置100可包括一个或多个I/O模块102A-102C和106A-106B。 例如，分组转发装置100可包括边缘模块102A-102C，其连接到表示直接 通信主机的终端104。例如，I/O模块102B可连接到标注了主机1_A-主机n_A的任意数量的主机104。类似地，I/O模块102B可连接到标注了主机1_B-主 机n_B的主机104，I/O模块102C可连接到标注了主机1_C-主机n_C的主机 104。

聚合模块106A和106B可连接到核心网络装置108（即标注了核心1 到核心n的任意数量的核心），核心网络装置108用于处理大量的网络业务。 由于核心网络装置108典型地与大量路由和较少直接连接的主机相关联， 所以考虑到路由表大小和IP主机（直接和远程）的可能数量，可以对聚合 模块106A和106B进行优化，用于执行最长前缀匹配搜索。

由于此原因，可以理解的是，边缘模块102A-102C也可被称为低容量 I/O模块，这是由于它们可能具有较小的IPFDB和LPM表大小，因此与大 容量聚合模块106A-106B相比，它们支持较少的主机和路由。此外，在低 容量I/O模块（边缘模块102A-102C）的种类内，硬件IPFDB和LPM表的 相对大小可以改变。为了对其进行说明，I/O模块102A在下文中可被称为 “低容量”I/O模块（例如支持512个路由和2,000个主机），I/O模块102B 可被称为“较低容量”I/O模块（例如支持256个路由和1,500个主机），并 且I/O模块102C可被称为“最低容量”I/O模块（例如支持128个路由和 1,000个主机）。

与低容量边缘模块102A-102C相反，聚合模块106A-106B可具有明显 较大的硬件IPFDB和LPM表大小，因此可支持明显较大量的主机和路由。 聚合模块106A和106B可连接到标注了核心1到核心n的一个或多个核心 网络装置108，因此可处理比边缘模块102A-102C大得多的业务量。聚合 模块106A和106B的每一个还可包括基于硬件的IPFDB和LPM表。聚合 模块106A-106B还可被称为高容量模块，这是由于聚合模块106A-106B的 每一个例如支持约16,000个主机和250,000个路由。

如上文所述，当路由数量较少时，所有的I/O模块102A-102C和 106A-106B都可从LPM转发方式中受益。然而，随着路由数量增加并越过 预定阈值，仅高容量I/O模块可从LPM转发方式中受益。因此，本申请描 述的主题提供了一旦路由数量超过阈值，就将低容量I/O模块自动地转换到 IPFDB转发。结果是，到达给定I/O模块的业务可以自动地利用针对该模 块的最佳转发方式（即LPM或IPFDB）。因此，包括以LPM和IPFDB转 发模式的混合进行操作的多个I/O模块的分组转发装置可被称作混合模式 或多模式分组转发装置。

本申请描述的自动方式的一个优点是其通过将硬件LPM表用作各个活 动主机的高速缓冲存储器，来允许低容量I/O模块中的更多HW转发。并 不是将整个路由表的无意义片段存储在LPM表，相反低容量I/O模块可在 LPM表和IPFDB中都存储活动主机，从而为尽可能多的主机提供更快的 HW转发。

本申请描述的自动方式的另一个优点是其避免了强制用户为每个I/O 模块正确地预配置适当模式。为给定I/O模块准确地预测IP路由的数量可 能是困难的，此外，IP路由的数量可随着时间改变。结果是某些I/O模块 被低效地配置或者正确地配置每个I/O模块所需要的时间对用户是繁重地。 通过允许分组转发装置针对每个模块自动地选择最佳分组转发方式，所有 I/O模块都有效地操作而不会对用户造成负担。

图2A-2D为示出了根据本申请描述的主题的实施例的在IP路由的总数 量与基于硬件的LPM表的容量之间的示例关系的图表，所述关系用于在 LPM转发模式与IPFDB转发模式之间进行选择。具体地，图2A和图2B 示出了低容量I/O模块和高容量I/O模块的相对的表大小。图2C和图2D 分别示出了用于区分LPM模式和IPFDB模式对于在图2A和图2B中所示 的示例低容量I/O和高容量I/O模块而言何时为最优的示例阈值。如同在本 申请所使用的，低容量I/O模块可以指具有相对较小的HW LPM表大小的 I/O模块。相反，高容量I/O模块可以指具有相对较大的HW LPM表大小的 I/O模块。如上文所述，边缘模块典型地为低容量I/O模块，并且聚合模块 典型地为高容量I/O模块。然而，可理解在低容量和高容量I/O模块之间， 可能存在硬件LPM表大小中的进一步变化。例如，在生产费用敏感的网络 设备中，某些低容量I/O模块可包括支持最大为256个路由的基于硬件的 LPM表，而其他低容量I/O模块可包括支持最大为512个路由的基于硬件 的LPM表。

图2A示出了用于低容量I/O模块102A的基于硬件的LPM表和IPFDB 的示例大小。参见图2A，低容量I/O模块102A可包括HW LPM表200和 HW IPFDB 202。LPM表200的容量可以根据能够被存储在该表中的路由的 数量来测量，如图2A的左栏所示。相反，IPFDB 202的容量可以通过能够 存储的最大数量的主机条目来测量，如图右栏所示。例如，LPM表200可 存储多达512个路由并且IPFDB 202可存储多达2,000个主机。可以理解的 是，图2A-图2D的各方面可不按照比例进行显示。

类似地，图2B示出了用于高容量I/O模块106A的基于硬件的LPM表 和IPFDB的示例大小。高容量I/O模块106A可以比低容量I/O模块102A 支持相对较大数量的路由和/或主机。例如，HW LPM表204可支持最大 250,000个路由并且HW IPFDB 206可支持最大16,000个主机。

接着，考虑分组转发装置100的软件路由表当前存储25,000个路由的 场景。由于25,000个路由可被整体存储在高容量I/O模块106A上的HW LPM表204内（即25,000<250,000），所以可能希望以LPM模式操作（或 继续操作）高容量I/O模块106A。相反，由于25,000个路由不能被存储在 低容量I/O模块102A上的HW LPM表200内（即25,000>512），所以可 能希望以IPFDB模式操作低容量I/O模块102A。在下文中，将关于图2C 和图2D更详细的描述这些场景中的每个场景。

图2C和图2D分别示出了HW LPM表200和204的容量与存储在软件 中的路由数量之间的示例关系。具体地，图2C中示出的图表与图2A中示 出的低容量I/O模块102A相对应，而图2D中示出的图表与图2B中示出 的高容量I/O模块106A相对应。参见图2C，可以理解的是，随着存储在 软件中的路由数量增加，存储路由所需要的HW LPM表200的百分比也增 加。对于HW LPM表200，达到在512个路由时达到表容量的100%，如点 208所示。在一个实施例中，对于少于512个的路由数量和/或小于100%的 容量利用比而言，以LPM模式操作低容量I/O模块102A可能是最佳的。 在其他实施例中，用于操作低容量I/O模块102A的最佳值可以小于或大于 512个路由/100%容量利用率。一个示例阈值点（在该点下LPM模式对于 低容量I/O模块102A可为最佳）可由阴影区域210表示。相反地，对于大 于512个路由/100%容量利用率的值（或无论选择哪个阈值），IPFDB模式 可为最佳，如无阴影区域212所示。

继续上面描述的软件路由表当前存储25,000个路由的示例场景，可以 理解的是，25,000个路由远在表示LPM模式何时最佳的阴影区域210之外。 如数据点214所示，25,000个路由与HW LPM表200的容量的约4,882%相 对应。或者，以其他方式表达，HW LPM表200仅能够存储软件表中所存 储的路由的总数量的2%（未示出）。

参见图2D，可以理解的是，类似图2C，随着存储在软件中的路由数 量增加，存储路由所需要的HW LPM表204的百分比也增加。对于HW LPM 表204，在250,000个路由处达到表容量的100%，如点216所示。因此， 与低容量I/O模块102A相反，可以在大得多的路由数量处实现相同的利用 百分比阈值。例如，如果软件表（未示出）中的路由数量小于与小于100% 的容量利用百分比相对应的250,000个路由，则以LPM模式操作高容量I/O 模块106A可能是最佳的。类似图2C，LPM模式对于高容量I/O模块106A 可为最佳的值可由阴影区域218表示，而IPFDB模式可为最佳的值可以由 无阴影区域220表示。

返回到上面描述的软件表存储25,000个路由的示例场景，与图2C相 反，可以理解的是，25,000个路由很好地在表示何时LPM模式最佳的阴影 区域218内。如数据点222所示，25,000个路由与HW LPM表106A的容 量的约10%相对应。因此，可为高容量I/O模块106A自动选择LPM模式， 而可为低容量I/O模块102A自动选择IPFDB。

图3为示出了根据本申请描述的主题的实施例的多模式层3分组转发 装置的示例组件的方框图。参见图3，分组转发装置100可包括经由交换机 结构连接在一起的一个或多个I/O模块和管理模块。例如，分组转发装置 100可包括低容量I/O模块102A和高容量I/O模块106A。模块102A可包 括用于处理由I/O模块102A接收的分组的分组转发硬件300。分组转发硬 件300可包括：转发引擎302；硬件LPM表200，用于存储来自从IP路由 协议（即可变长度前缀和下一跳地址）知悉的IP路由表（即软件LPM表 312）的条目；以及硬件IPFDB 202，用于存储与本地和/或远程主机相对应 的条目。可以理解的是，可从位于管理模块304上的IP路由表接收在每个 I/O模块的LPM表中包含的路由。类似地，I/O模块106A可包括分组转发 硬件300，其包括转发引擎302、硬件实现的LPM表204以及硬件实现的 IPFDB 206。可理解，为了简化在图3中没有示出额外I/O模块（例如I/O 模块102B、102C以及106B），但是在分组转发装置100中可以包括额外 I/O模块，而不会偏离在本申请描述的主题的范围。还可以理解，硬件LPM 表和硬件IPFDB可以是或者可以不是相同的硬件结构。例如，某些转发硬 件结构可以将单个表用于LPM和主机条目。单个表可以容纳路由和/32个 直接主机，或者如果存在太多主机的话，则该表可自动切换到容纳/32个本 地和远程主机。

在一个实现中，转发引擎302可首先在IPFDB 202/206中执行查找，以 确定将所接收到的分组转发到何处。如果IPFDB 202/206中的查找失败，则 在LPM表200/204中执行查找。如果LPM表200/204中的查找失败，则可 以将分组转发到管理模块304，管理模块304在软件表312和/或314中执 行查找以转发分组。

除了I/O模块102A和106A之外，分组转发装置100可包括管理模块 304和交换机结构306。交换机结构306在I/O模块102A、106A和管理模 块304之间切换分组。管理模块304可控制I/O模块102A和106A的全部 操作。此外，管理模块304可包括控制其操作的CPU 308以及存储软件实 现的LPM表312（即IP路由表）和软件实现的IPFDB 314的存储器310。 具体地，软件LPM表312可包括通过参与IP路由协议（例如路由信息协 议（RIP）和开放式最短路优先（OSPF））或经由配置知悉的条目。管理模 块304还可包括自动模式选择模块316，其用于自动选择用以操作I/O模块 102A和106A中的每一个的IP切换模式（即LPM模式或IPFDB模式）。

在一个实施例中，管理模块304可包括控制软件IPFDB 314的更新的 IPFDB更新控制器（未示出）。在一个实施例中，IPFDB更新控制器（未示 出）可以维持分组转发查找未命中的计数，这些分组查找未命中需要由CPU 308在软件LPM表312和软件IPFDB 314中进行查找。如上文所示，软件 LPM表312和软件IPFDB 314可包括被知悉但是还没有被填充到硬件的条 目。当使用模块102A或106A中的一个模块上的分组转发硬件300发生未 命中时，可以将分组转发到管理模块304进行转发。管理模块304可在软 件LPM表312或软件IPFDB 314中执行查找并转发分组。根据再一个可能 的实施例，IPFDB更新控制器（未示出）可与分组未命中计数表（未示出） 通信，以追踪分组转发硬件查找导致未命中的分组的数量。通过对分组进 行采样以及仅当满足特定条件时才向IPFDB 314添加主机，IPFDB更新控 制器（未示出）可避免不必要地用主机条目填充IPFDB 314。在2005年12 月23日递交的、美国专利申请序列No.11/317,665以及名称为“Method and  System for Automatic Expansion and Contraction of IP Host Forwarding  Database”、代理方案号为2717P146的继续美国专利申请中描述了此方面的 额外细节。

除了上述基于“机架”的实施例之外，本申请描述的主题还可应用于 基于“堆栈”的实施例。如在本申请使用的，“堆栈”可包括多个单独的交 换机（每个交换机被完全封入金属片中），这些交换机可经由电缆连接在一 起以形成一个逻辑交换机。堆栈中的每个交换机可被称作“节点”，其中堆 栈中的每个节点可以像图3中示出的机架实施例中的I/O模块102A-106A 一样进行行动。类似地，在交换机之一上运行的软件可执行例如管理模块 304所执行的那些功能之类的功能，并且将交换机互连的电缆可执行与交换 机结构306的功能类似的功能。

图4为示出了根据本申请描述的主题的实施例用于在分组转发装置中 针对每个模块在IP切换模式之间进行自动选择的示例步骤的流程图。参见 图4，在步骤400中，确定基于硬件的LPM表的容量，其中，确定该容量 包括确定可以存储在基于硬件的LPM表中的IP路由的最大数量。例如， 可以确定硬件LPM表200的容量为支持最大为512个路由。类似地，可以 确定硬件LPM表204的容量为支持最大为250,000个路由。

在步骤402中，可以确定存储在基于软件的LPM表中的IP路由的数 量。例如，基于软件的LPM表312可以存储25,000个路由。可以理解，与 在步骤400中进行的确定相反，存储在软件LPM表312中的路由的数量可 能不等于软件表的容量（实际上，对于软件表的容量并不存在限制），而是 等于分组转发装置100所处理的路由的数量。例如，可以通过处理路由协 议更新向软件表312添加路由，或者使用配置指令添加路由。结果是，存 储在软件表312中的路由的数量可以随时间而改变。

在步骤404中，可以确定存储在基于软件的LPM表中的IP路由的总 数量与基于硬件的LPM表的容量之间的关系。该关系可包括特定I/O模块 的硬件LPM表的容量的阈值百分比。例如，512个路由可为LPM表200 的容量的100%，但是仅为LPM表204的容量的0.2%。替代地，该关系可 包括路由的阈值数量，其可以或可以不与容量利用的特定百分比相对应。 该关系可包括将路由数量与硬件LPM表所支持的路由数量相比较。例如， 25,000个路由可大于LPM表200所支持的512个路由，但是可小于LPM 表204所支持的250,000个路由。

在步骤406中，响应于确定IP路由的总数量与基于硬件的LPM表的 容量具有预定关系，可以以IPFDB模式自动操作I/O模块，其中以IPFDB 模式操作I/O模块包括用与主机相对应的条目填充基于硬件的IPFDB和基 于硬件的LPM表，以及使用I/O模块的IPFDB和LPM表对由I/O模块接 收的层3分组进行路由，并且其中，与主机相对应的条目包括主机的全IP 地址。例如，可以确定这些数量的路由是否可以被全部存储在给定I/O模块 的基于硬件的LPM表内。换言之，可以将该关系表示为硬件LPM表的容 量的阈值利用百分比。在其他实施例中，在路由的数量超过与硬件LPM表 的100%相对应的阈值之前，I/O模块可在LPM与IPFDB模式之间进行切 换。例如，随着软件路由表变得填充有额外路由，可能希望在达到512个 路由之前（例如500个路由）将低容量I/O模块102A切换到IPFDB模式。 例如，这可能是由于当LPM表200达到90%容量时性能下降所引起的。可 替代地，可能希望在达到512个路由之后（的某个点例如520个路由）将 低容量I/O模块102A切换到IPFDB模式。例如，如果LPM表200基于网 络条件一直存储大约510到515个路由，那么可能希望避免重复刷新LPM 表200并用主机条目替换它，直到LPM表200被明显淹没为止（例如5,000 个路由）。

此外，应理解，除了上面描述的用于确定可存储在容量为已知或固定 量的硬件表中的路由的最大数量的方法之外，还可以存在容量是依赖于数 据（又名“算法的”）的其他类型的硬件表。本申请描述的主题还可应用于 算法硬件LPM表，而不偏离本申请描述的主题的范围。在一个可能的实施 例中，可以使用通知机制来指示不能添加特定路由，这是由于其不适应硬 件LPM表。可以在LPM与IPFDB模式之间进行转换的决策过程中使用这 种通知。例如，LPM与IPFDB模式之间的转换可在第一通知为“满”时被 执行，或者某些数量的路由超过了它。

如上文所述，本申请描述的自动模式选择方式的一个优点是其通过将 硬件LPM表用作各个活动主机的高速缓冲存储器，来允许低容量I/O模块 中的更多HW转发。并不是将整个路由表的无意义片段存储在LPM表中， 相反低容量I/O模块可以在LPM表和IPFDB两者中存储活动主机，从而为 尽可能多的主机提供更快的HW转发。此外，通过允许分组转发装置针对 每个模块自动地选择最佳分组转发方式，所有的I/O模块都可以有效地操 作，而不会通过为每个I/O模块配置操作模式而增加用户的负担。

图5为示出了根据本申请描述的主题的实施例用于在分组转发装置中 针对每个模块在IP切换模式之间进行自动选择的示例步骤的更详细流程 图。参见图5，在步骤500处，所有I/O模块初始可以以LPM模式操作。 例如，分别位于I/O模块102A和106A上的硬件LPM表200和204可填 充有与可变长度因特网协议（IP）地址和下一跳地址相对应的条目。分别位 于I/O模块102A和106A上的硬件IPFDB 202和206可填充有包括全长IP 地址（例如32-位IPv4或128-位IPv6）的与主机相对应的条目。最后，以 LPM模式操作所有I/O模块可包括使用硬件LPM表200和204以及硬件 IPFDB 202和206对I/O模块102A和106A所接收的层3分组进行路由。

在步骤502中，确定IP路由的数量是否超过预定阈值。例如，对于低 容量模块102A，可确定存储在软件LPM表312中的IP路由的数量是否超 过512个路由。应理解，可以针对每个模块来进行这种确定，以考虑位于 每个I/O模块上的基于硬件的LPM表的容量的潜在差异。因而，对于高容 量模块106A，可确定存储在软件LPM表312中的IP路由的数量是否超过 250,000个路由。

如果在步骤502中确定IP路由数量没有超过预定阈值，则控制可返回 到步骤502，在步骤502中，I/O模块可继续以LPM模式操作并且可再次确 定IP路由的数量是否没有超过预定阈值。

然而，如果在步骤502中确定IP路由数量超过预定阈值，则控制可进 行到步骤504，在步骤504中，可以将低容量I/O模块转换为以IPFDB模 式操作。可以理解的是，使用低容量和高容量模块仅仅旨在进行说明而不 是限制，这是因为虽然低容量模块可首先转换为IPFDB模式，然而如果路 由表充分增加则高容量模块也可转换为IPFDB模式。由于低容量I/O模块 之前是以LPM模式操作的（即步骤500），所以转换为以IPFDB模式操作 的过程初始可包括删除存储在硬件LPM表中的路由，除了本地传递所需要 的直接交互路由之外。在IPFDB模式中，仍然可以在I/O模块的硬件IPFDB 中存储任何本地主机和远程主机。可以理解的是，当从LPM模式转换成 IPFDB模式时，可以不删除子网路由、删除一些子网路由或删除所有子网 路由。删除一些而不是所有的子网路由将给出较大的主机高速缓冲存储器 空间，而在LPM表中留有一些子网路由用以进行LPM转发。例如可通过 硬件“命中位”来确定要保留或删除的精确路由，“命中位”表示当转发分 组时是否使用一个路由进行查找。可以删除在某个时间段上没有被“命中” 的路由，以为LPM表中的主机获得更多空间。

在步骤506中，当以IPFDB模式操作时，I/O模块可根据需要安装额 外主机。例如，可基于采样的慢路转发的分组来添加主机。再次参见图3， 慢路处理可包括在I/O模块102A处接收分组、确定目的地地址并未位于 IPFDB 202或LPM表200中、以及经由交换机结构306将分组转发到管理 模块304。管理模块304可在处理之后将与分组相对应的主机条目添加到软 件IPFDB 314。管理模块304接着可将主机条目信息添加到硬件IPFDB 202 和/或206。

在步骤508中，对于以IPFDB模式操作的I/O模块，确定是否退出 IPFDB模式。例如，可以确定路由数量是否降到了第二阈值以下。可以理 解的是，在一个实施例中，第二阈值可小于第一阈值，以避免颠簸 （thrashing），其可能由在LPM模式与IPFDB模式之间来回重复以及从而 重复删除和再次填充基于硬件的表200-206所导致。例如，继续上面描述的 当路由数量超过512个路由（即第一阈值）时进入IPFDB模式的实例，仅 当路由数量下降到低于400个路由（即第二阈值）时，才可退出IPFDB模 式。然而，可以理解的是，在其他实施例中，第一和第二阈值可以相同， 而不偏离本申请描述的主题的范围。

如果在步骤508中确定路由数量没有下降到低于第二阈值，则控制可 返回到步骤508，在步骤508中，可再次确定路由数量是否下降到低于第二 阈值。可替代地，如果路由数量已经下降到低于第二阈值，则存在退出 IPFDB模式的数个选项之一。

第一选项可包括如果满足步骤508中的条件则迅速退出IPFDB模式。 换言之，路由数量是否已经下降到低于第二阈值可为退出IPFDB模式的唯 一条件。其他选项可包括在退出IPFDB模式之前的额外条件。

如图5所示，第二选项可包括在步骤510中确定除了路由数量低于第 二阈值之外是否已经过去了预定的时段。例如，仅在路由数量低于400个 路由（即第二阈值）持续30秒之后，才可以退出IPFDB模式。可以理解的 是，时段可为预配置的或动态的或者可针对每个模块定制。因而，可为每 个I/O模块设定30秒的时段，低容量模块可具有15秒的时段，并且高容量 I/O模块可具有45秒的时段，或者可基于网络条件或其他因素动态调节时 段。

第三选项可包括在步骤512中确定路由数量是否低于第二阈值（即步 骤508）并且是否移除或禁止了所有的低容量模块。例如，在路由数量下降 到低于400个路由（第二阈值）并且物理地或通过管理员配置移除或禁止 了低容量I/O模块102A-102C之后，可以退出IPFDB模式。如果在步骤512 中使用试探法，并且接着插入或使能低容量I/O模块，则可用所有IP路由 和主机更新低容量I/O模块（即填充的其硬件LPM表和IPFDB），并且初 始可以以LPM模式操作低容量I/O模块。可以理解的是，本申请描述的主 题可以应用在单一的机器范围的操作模式中，或者可以用在以下情况中： 单独地考虑每个I/O模块，并基于该模块的最佳操作将该模块置于其自己的 操作模式中。

退出IPFDB模式514可包括一个或多个步骤。在一个实施例中，如果 使用在步骤508或510中描述的试探法，则退出IPFDB模式514可以包括： 在步骤516中用非直接路由更新所有低容量I/O模块，以及在步骤518中移 除不再需要的远程主机。例如，由于在转换回LPM模式期间硬件LPM表 200中的主机条目被路由取代，所以某些路由可消除在硬件IPFDB 202中存 储某些远程主机条目的需要，从而也可将这些远程主机条目移除。

应理解的是，可改变本发明的各种细节而不偏离本发明的范围。此外， 前述描述仅是为了说明的目的，而不是为了限制的目的。