用于从存储器到处理客户端提供复制数据的系统和方法

摘要

提供了用于网络设备的系统和方法。设备包括多个分组处理客户端。设备进一步包括多个存储器，其中存储器的数量大于分组处理客户端的数量，每个存储器存储数据副本，分组处理客户端被配置为选择性地读取来自任何存储器的控制数据。仲裁器被配置为在第一时钟周期中为多个分组处理客户端从读取来自其的控制数据的多个存储器当中选择存储器的第一子集，并且在继第一时钟周期之后的第二时钟周期中为多个分组处理客户端从读取来自其的控制数据的多个存储器当中选择存储器的第二子集。

说明书

相关申请的交叉引用

本申请要求2012年7月2日提交的、名称为“Scalable N to M  Arbiter”的第61/667,180号美国临时专利申请和2012年10月24日 提交的、名称为“Scalable N to M Arbiter”的第61/717,970号美国临 时专利申请的优先权，将它们整体并入于此。

技术领域

本文中描述的技术总体上涉及对共享资源的多设备访问，并且 更具体地涉及网络通信系统中的多设备存储器访问。

背景技术

对共享资源的多设备访问常常导致在某些配置中使整个系统变 慢的访问带宽复杂化。这种情况在诸如网络交换机之类的高速通信 系统中尤为突出，其中多个分组处理客户端寻求访问存储在存储器 中的控制数据。

给出上面描述作为对本领域中相关技术的一般概述，并且不应 被解释为承认其包含的任何信息构成抵触本专利申请的现有技术。

发明内容

提供了用于从网络接收分组数据的网络设备的系统和方法的示 例。设备包括用于处理从网络接收的分组数据的多个分组处理客户 端。设备进一步包括多个存储器，其中存储器的数量大于分组处理 客户端的数量，每个存储器存储将由分组处理客户端使用的控制数 据的副本，并且分组处理客户端被配置为选择性地读取来自任何存 储器的控制数据。仲裁器被耦合到分组处理客户端和存储器，仲裁 器被配置为在第一时钟周期中为多个分组处理客户端从读取来自其 的控制数据的多个存储器当中选择存储器的第一子集，并且在继第 一时钟周期之后的第二时钟周期中为多个分组处理客户端从读取来 自其的控制数据的多个存储器当中选择存储器的第二子集，存储器 的第二子集包括未包括在存储器的第一子集中的至少一些存储器。

作为另一示例，向被配置为处理通过网络接收的分组数据的多 个分组处理客户端提供控制数据的方法包括：用将由多个、N个分 组处理客户端使用的复制控制数据更新多个、M个存储器，其中M 大于N。在第一时钟周期期间从M个存储器当中将一个存储器分配 给每个分组处理客户端以用于访问控制数据，每个分组处理客户端 从M个存储器当中被分配一个不同的存储器，并且其中M个存储器 当中的至少一个存储器是在第一时钟周期期间未分配给分组处理客 户端的第一未分配的存储器。在第二时钟周期期间从M个存储器当 中将不同存储器分配给每个处理客户端以用于访问控制数据，其中 M个存储器当中的至少一个存储器是在第二时钟周期期间未分配给 分组处理客户端的第二未分配的存储器，第二未分配的存储器不同 于第一未分配的存储器。

附图说明

图1是描绘从网络接收分组数据的网络设备的框图。

图2描绘用于访问复制在每个存储器处的数据的存储器向处理 客户端的示例分配。

图3是描绘针对时钟周期0至2以及时钟周期3至5的存储器- 处理客户端分配的图表。

图4描绘用于存储器向处理客户端的分配以访问复制在每个存 储器处的数据的另一示例算法。

图5是描绘针对时钟周期0至2以及时钟周期3至5使用关于 图2和图4所描述算法的存储器-处理客户端分配的图表。

图6是描绘网络设备的框图。

图7是描绘向被配置为处理通过网络接收到的分组数据的多个 分组处理客户端提供控制数据的方法的流程图。

具体实施方式

图1是描绘从网络接收分组数据的网络设备的框图。网络设备 包括多个、N个分组处理客户端102，以用于处理从网络接收到的分 组数据。设备还包括多个、M个存储器104。存储器(M)104的数 量大于分组处理客户端(N)102的数量。例如，在本公开的一个实 施例中，M＝5个存储器向N＝3个处理客户端提供数据。每个存储器 104存储将由分组处理客户端102使用的控制数据的副本。分组处理 客户端102被配置为读取来自任一存储器104的控制数据。设备进 一步包括耦合到分组处理客户端102和存储器104的仲裁器106。在 实施例中，仲裁器106被配置为在第一时钟周期中为多个分组处理 客户端102从读取来自其的控制数据的多个存储器104当中选择存 储器的第一子集(例如，子集A)。仲裁器106进一步被配置为在 第二时钟周期中为多个分组处理客户端102从读取来自其的控制数 据的多个存储器104当中选择存储器的第二子集(例如，子集B)。 存储器的第二子集包括存储器的未包括在存储器的第一子集中的至 少一些存储器。进一步地，仲裁器106被配置为选择存储器的子集 使得存储器的第二子集不包括其在存储器的第一子集中的至少一个 存储器。注意，在实际设备中，可以存在更大或更小数目的处理客 户端102以及更大或更小数目的存储器106。而且，如下面将更详细 描述的，在实际设备中，在所选子集之间、在两个相应周期之间可 以存在与图1所见不同的变化。

在本公开的一个实施例中，例如，仲裁器106被配置为以伪随 机方式作为机制向分组处理客户端102分配存储器104，以用于在访 问存储器104中的负载平衡和确保公平。在一些实施例中，因为分 组处理客户端占用不止一个时钟周期以执行在特定存储器上的读操 作(诸如访问存储在特定存储器上的查找数据表)，或者因为特定 存储器不能够以连续(back-to-pack)方式执行某些类型的访问(例 如，某些DDR3协议不支持在连续周期从同一页中读取数据)，由 于特定存储器忙碌或不能够执行，在下一时钟周期中被分配特定存 储器的分组处理客户端不能够执行其读操作。总是紧接在存储器已 被分配给另一忙碌分组处理客户端之后被分配该存储器的特定分组 处理客户端将会经常被阻塞而无法执行读操作，从而使特定分组处 理客户端的总体处理变慢。相比之下，针对先前时钟周期未分配存 储器之后被分配该存储器的特定分组处理客户端更加可能能够执行 其期望的读操作，因为先前未分配的存储器已经有不止一个时钟周 期以完成在其作业队列中尚未完成的任何先前请求。例如，在其中 网络设备在被超额订购的系统中进行操作的本公开的一个实施例 中，M个存储器的带宽不足以服务所有客户端请求。在这样的实施 例中，诸如通过使用本文中描述的某些算法，网络设备试图向每个 处理客户端提供存储器访问的相同部分。

为了对抗这样的不公平，在一个实施例中，网络设备执行操作 以伪随机方式向分组处理客户端分配存储器，伪随机方式确保：因 为某些存储器未在每个时钟周期期间被分配给分组处理客户端，在 一组处理周期期间，每个分组处理客户端至少一次被分配在先前时 钟周期期间未被分配给另一分组处理客户端的存储器。通过具有比 处理器更多的控制数据拷贝，并且通过循环对含有那些控制数据拷 贝的存储器的访问，在一个实施例中，通过降低由在两个连续周期 在给定存储器处读取数据导致的阻塞，网络设备支持增加的带宽。

图1公开了依照实施例的其在本公开的一个实施例中被用于便 于这种伪随机存储器分配的附加网络设备元件。在图1中，仲裁器 106包括移位逻辑108，移位逻辑108的形式为作为处理客户端移位 寄存器操作的第一移位寄存器110和作为存储器移位寄存器112操 作的第二移位寄存器112中的一个或两者。这些移位寄存器包括每 个时钟周期以环绕方式左或右移X个位置(例如，一个或多个位置) 的条目的阵列。处理客户端移位寄存器110的示例功能关于图2进 一步详细描述，并且存储器移位寄存器112的示例功能关于图4描 述。仲裁器106进一步包括使分组处理客户端与存储器匹配的分配 逻辑114。

图2描绘用于向处理客户端分配存储器以访问复制在每个存储 器处的数据的示例分配机制。图2的示例包括N＝3个处理客户端和 M＝5个存储器。从而，在每个时钟周期中，两个存储器将不会被分 配给处理客户端，同时三个存储器将被分配给处理客户端。在202 处描绘处理客户端移位寄存器。客户端移位寄存器202包括针对每 个处理客户端的条目，它们依次被编号为0、1、2。客户端移位寄存 器202标识针对特定时钟周期分组处理客户端被分配存储器的顺序。 在图2的示例中，针对周期0，处理客户端被分配存储器，使得处理 客户端0被分配第一存储器，处理客户端1被分配第二存储器，以 及处理客户端2被分配第三存储器。针对周期1，如在204处指示的， 客户端移位寄存器左移一个位置，使得处理客户端1被分配第一存 储器，处理客户端2被分配第二存储器，以及处理客户端0被分配 第三存储器。针对周期2，如在206处指示的，客户端移位寄存器左 移另一个位置，使得处理客户端2被分配第一存储器，处理客户端0 被分配第二存储器，以及处理客户端1被分配第三存储器。在实施 例中，这样的存储器向处理客户端的分配被执行得足够快，使得每 个处理客户端均能够在每个周期中执行读操作，从而阻止了分配的 存储器忙碌或因其它原因而不能够执行。

除了变化处理客户端被分配存储器的顺序之外，按数字顺序分 配存储器，其中存储器分配起始点也基于分配逻辑而变化。针对周 期0、1和2中的每个周期的这种分配逻辑分别被指示在图2中的 207、209、211处。在图2的示例中，将分配给处理客户端的第一存 储器根据如下公式确定：

起始存储器＝(cycle*N)％M，   (等式1) 其中cycle是时钟周期数，N是分组处理客户端的数目，％表示模运 算，以及M是存储器的数目。从而，针对时钟周期0，存储器0使 将被分配的第一存储器(即，起始存储器＝(0*3)％5＝0)。 如在208处描绘的，存储器0根据在202处的客户端移位寄存器中 示出的顺序被分配给第一处理客户端(处理客户端0)。存储器1 是将被分配的下一存储器，并且按客户端移位寄存器202顺序被分 配给第二存储器(处理客户端1)。进一步地，存储器2是将被分配 的第三存储器，并且存储器2按客户端移位寄存器202顺序被分配 给第三存储器(处理客户端2)。如在208处指示的，针对时钟周期 0，因为处理客户端0、1、2中的每个处理客户端已经被分配了存储 器，存储器3和存储器4未被分配处理客户端。

针对时钟周期1，如在204处指示的，客户端移位寄存器向左移 位一个位置，并且分配逻辑确定存储器3是将被分配给处理客户端 的第一存储器(即，起始存储器＝(1*3)％5＝3)。从而，针 对时钟周期1，如在210处描绘的，根据在204处的客户端移位寄存 器中示出的顺序，存储器3被分配给第一处理客户端(处理客户端 1)。存储器4是将被分配的下一存储器，并且按客户端移位寄存器 204顺序被分配给第二存储器(处理客户端2)。存储器以环绕方式 被分配。从而，存储器0是将被分配的第三存储器，并且存储器0 按客户端移位寄存器204顺序被分配给第三存储器(处理客户端0)。 如在210处指示的，针对时钟周期1，存储器1和存储器2未被分配 处理客户端。

针对时钟周期2，如在206处指示的，客户端移位寄存器向左移 位一个位置，并且分配逻辑确定存储器1是将被分配给处理客户端 的第一存储器(即，起始存储器＝(2*3)％5＝1)。从而，针 对时钟周期2，如在212处描绘的，根据在206处的客户端移位寄存 器中示出的顺序，存储器1被分配给第一处理客户端(处理客户端 2)。在本公开的一个实施例中，因为存储器按依次顺序被分配，存 储器2是将被分配的下一存储器，并且按客户端移位寄存器206顺 序被分配给第二存储器(处理客户端0)。进一步地，存储器3是将 被分配的第三存储器，并且存储器3按客户端移位寄存器206顺序 被分配给第三存储器(处理客户端1)。如在212处指示的，针对时 钟周期2，存储器0和存储器4未被分配处理客户端。

图3是依照实施例针对时钟周期0至2以及时钟周期3至5的 存储器-处理客户端分配的映射。通过使用图2中描绘的过程确定了 时钟周期0至2分配，同时周期3至5分配经由该同一算法的继续 迭代来确定。如上面描述的，在被分配给该处理单元的存储器在一 个或多个紧接在前的时钟周期中是空闲的时，处理客户端更可能能 够执行期望的读操作。在所描绘的六个周期内，每个处理客户端0、 1、2至少三次被分配在紧接在前的时钟周期中空闲的存储器。从而， 在本公开的一个实施例中，随着时间的推移，网络设备试图跨处理 客户端集均匀地供应高质量存储器分派时隙。

图4描绘依照本公开的备选实施例的用于向处理客户端分配存 储器以访问复制在每个存储器处的数据的另一示例算法。虽然使用 存储器移位寄存器代替客户端移位寄存器以及图2中使用的分配逻 辑的变体，但是图4的算法产生与图2的算法完全相同的分配结果。 图2的算法在每个时钟周期期间标识哪些处理客户端由每个存储器 服务(或者是空闲的)。这样的映射针对在经由仲裁器返回结果时 将存储器连接到正确处理客户端是有用的。图4的算法标识哪个存 储器正服务每个处理客户端。这样的映射针对经由仲裁器将处理客 户端请求发送到适当的存储器是有用的。从而，在本公开的实施例 中，仲裁器执行图2和图4中的算法中的一个或两者，以辅助发送 读请求和返回读请求结果。在其它实施例中，如参照图5进一步详 细描述的，仲裁器执行图2和图4算法之一，并且转译成另一分配 表示。

在图4的实施例中，存储器移位寄存器402包括针对每个存储 器的条目，它们依次被编号为0、1、2、3、4。存储器寄存器402 标识针对特定时钟周期将存储器分配给处理客户端的顺序。在图4 的示例中，如在402处描绘的，在周期0期间，处理客户端被分配 存储器，使得存储器0被分配给第一处理客户端，存储器1被分配 给第二处理客户端，存储器2被分配给第三处理客户端，存储器3 被分配给第四处理客户端，以及存储器4被分配给第五处理客户端。 在404处，针对周期1，存储器移位寄存器左移一个位置，使得存储 器1被分配给第一处理客户端，存储器2被分配给第二处理客户端， 存储器3被分配给第三处理客户端，存储器4被分配给第四处理客 户端，以及存储器0被分配给第五处理客户端。在406处，针对周 期2，存储器移位寄存器左移一个位置，使得存储器2被分配给第一 处理客户端，存储器3被分配给第二处理客户端，存储器4被分配 给第三处理客户端，存储器0被分配给第四处理客户端，以及存储 器1被分配给第五处理客户端。

因为存在比存储器更少的处理客户端，在每个周期中，分配逻 辑确定哪些存储器将不分配给处理客户端。在每个周期中，从被选 择用于分配的存储器子集中削减M-N个存储器，从而在存储器的子 集中留下N个存储器以用于分配给N个处理客户端。在图4的示例 中，因为M＝5并且N＝3，削减两个存储器。分配逻辑在由如下公式 标识的存储器处开始从将被分配的存储器子集中削减存储器：

起始存储器＝(cycle*(N-1))％M–(cycle*(N-1)+N)％ M，  (等式2)

其中cycle是时钟周期数，N是分组处理客户端的数目，％表示模运 算，以及M是存储器的数目。从而针对周期0，如在408处指示的， 在存储器移位寄存器的位置3处开始削减存储器，从而导致存储器3 和存储器4被削减，从而留下存储器0、存储器1和存储器2以用于 分配(即，起始存储器＝(0*(3-1))％5–(0*(3-1)+3)％ 5＝3)。如在410处指示的，针对周期1，在存储器移位寄存器的位 置0处开始削减存储器，从而导致存储器1和存储器2被削减，从 而留下存储器3、存储器4和存储器0以用于分配。如在412处指示 的，针对周期2，在存储器移位寄存器的位置3处开始削减存储器， 从而导致存储器4和存储器0被削减，从而留下存储器1、存储器2 和存储器3以用于分配。

在实施例中，然后在由如下公式标识的处理客户端处开始将余 留存储器(例如，在408处的存储器)分配给处理客户端：

起始客户端＝cycle％N，    (等式3)

其中cycle是时钟周期数，％表示模运算，以及N是分组处理客户端 的数目。从而，针对周期0，如在414处描绘的，处理器客户端0 被分配在408处余留的第一存储器(存储器0)；客户端1被分配在 408处的第二存储器(存储器1)；以及客户端2被分配在408处的 第三存储器(存储器2)。如在416处描绘的，针对周期1，处理器 客户端1被分配在408处余留的第一存储器(存储器3)；客户端2 被分配在408处的第二存储器(存储器4)；以及客户端0被分配在 408处的第三存储器(存储器0)。如在418处描绘的，针对周期2， 处理器客户端2被分配在408处余留的第一存储器(存储器1)；客 户端0被分配在408处的第二存储器(存储器2)；以及客户端1 被分配在408处的第三存储器(存储器3)。

图5是描绘在实施例中针对时钟周期0至2以及时钟周期3至5 使用关于图2和图4所描述算法的存储器-处理客户端分配的图表。 在实施例中，在502处，图5描绘按照存储器的客户端映射，从而 图示根据图2算法的存储器分配，同时在504处，图5描绘按照客 户端的存储器映射，从而图示根据图4算法的存储器分配。这些映 射是类似的。例如，针对周期2，针对图2和图4算法两者所确定的 映射，存储器1被映射到处理客户端2，存储器2被映射到处理客户 端0，以及存储器3被映射到处理客户端1。从而，在本公开的不同 实施例中，利用不同算法，并且算法的变化被用于实现导致存储器 之间公平的负载平衡的存储器向处理客户端的伪随机分配的共同结 果。

另外，使用图2、图4算法之一所产生的结果可以被转译成另一 结果。例如，针对时钟周期1，通过使用图2算法，如在506处指示 的，存储器0被分配该处理单元0，存储器3被分配给处理单元1， 以及存储器4被分配给处理单元2，在这种情况下，按照客户端的存 储器映射的等效物(其可以使用图4算法来确定)还可以通过如下 方式来确定：标识哪个存储器被分配给处理客户端0(存储器0)， 哪个存储器被分配给处理客户端1(存储器3)，以及哪个存储器被 分配给处理客户端2(存储器4)，如在508处指示的。另外，为了 从508处的图4算法的图4存储器映射客户端转译成图4表示，仲 裁器迭代通过存储器0至5的每个存储器，从而标识哪个存储器已 被分配给哪个处理客户端，其中一些存储器未分配，并且从而在506 处的表示中被标记为空闲。

仲裁器分配的伪随机性质使得能够可预测，这在本公开的一些 实施例中是重要的。例如，在其中存储器响应时间跨存储器总体大 幅变化的某些实施例中，重要的是，处理客户端拥有如下数据，该 数据标识针对特定时钟周期预期来自哪个存储器的数据。在存储器 占用不止一个时钟周期以提供控制数据结果以及处理客户端在连续 时钟周期内做出存储器请求时，处理客户端需要拥有如下数据，该 数据标识针对给定时钟周期的请求预期来自哪个存储器的数据，从 而使得处理客户端能够使返回数据与适当的读请求匹配。通过在处 理客户端处单独地或者与仲裁器并行地实现仲裁器算法，即使在存 储器响应时间显著变化的情况下，处理客户端仍然可靠地发挥作用。 例如，在其中处理客户端1在时钟周期1请求来自存储器1中的复 制查找表中的第一位置的数据并且在时钟周期2进一步请求来自存 储器2中的复制查找表中的第二位置的数据的实施例中，在存储器2 在存储器1之前返回其数据时，处理客户端利用其按照时钟周期的 存储器分配数据，以匹配来自存储器1的数据与第一请求并且匹配 来自存储器2的数据与第二请求，尽管顺序颠倒地接收那些响应。

图6是描绘网络设备的框图。网络设备600包括第一电基板602， 以及用于处理从网络接收的分组数据606、设置在第一电基板602 上的多个分组处理客户端604。网络设备600进一步包括在电路基板 602外部的多个存储器608，例如使用双倍数据速率3(DDR3)技术 实现的外部存储器。在本公开的其它实施例中，更大或更小数目的 存储器被实现，并且还在本公开的其它实施例中，存储器被实现在 SRAM中或者在电路基板602本身上。在实施例中，存储器608的 数量大于分组处理客户端604的数量。每个存储器608存储将由分 组处理客户端604使用的控制数据的副本。分组处理客户端604被 配置为读取来自任一存储器608的控制数据。网络设备600进一步 包括设置在第一电基板602上、耦合到分组处理客户端604和存储 器608的仲裁器610。仲裁器610被配置为在第一时钟周期中为多个 分组处理客户端604从读取来自其的控制数据的多个存储器608当 中选择存储器的第一子集(例如，子集A)，并且在第二时钟周期 中为多个分组处理客户端604从读取来自其的控制数据的多个存储 器608当中选择存储器的第二子集(例如，子集B)，其中存储器 的第二子集包括未包括在存储器的第一子集中的至少一些存储器。

在本公开的一个实施例中，每个存储器包括网络设备中用于处 理分组的控制数据的副本。这种复制数据由相应分组处理客户端使 用。例如，在其中分组处理客户端是LAN交换机的部件的一个实施 例中，复制数据包括交换机查找表。当接收到分组时，处理客户端 读取在接收分组的帧头中的MAC地址。处理客户端访问在一个存储 器上的一个复制交换机查找表，以确定针对接收分组的适当输出端 口。当访问针对接收分组的端口数据时，处理客户端将接收分组转 发在适当的输出端口上。

图7是描绘向被配置为处理通过网络接收的分组数据的多个分 组处理客户端提供控制数据的方法的流程图。在702处，多个、M 个存储器更新有将由多个、N个分组处理客户端使用的复制控制数 据，其中M大于N。在704处，在第一时钟周期期间从M个存储器 当中将一个存储器分配给每个分组处理客户端以用于访问控制数 据，每个分组处理客户端从M个存储器当中被分配一个不同的存储 器，其中M个存储器当中的至少一个存储器是在第一时钟周期期间 未分配给分组处理客户端的第一未分配的存储器。在706处，在第 二时钟周期期间从M个存储器当中将不同存储器分配给每个处理客 户端以用于访问控制数据，其中M个存储器当中的至少一个存储器 是在第二时钟周期期间未分配给分组处理客户端的第二未分配的存 储器，第二未分配的存储器不同于第一未分配的存储器。

本申请使用示例说明发明。发明的可取得专利权的范围包括其 它示例。例如，在本公开的实施例中，图1的处理客户端是网络交 换机、路由器或其它网络设备的部件。