公开(公告)号：US07237059B2

公开(公告)日：2007-06-26

申请号：US11321918

申请日：2005-12-28

申请人： William N. Eatherton ,  Jaushin Lee ,  Bangalore L. Priyadarshan ,  Priyank Ramesh Warkhede ,  Fusun Ertemalp ,  Hugh Weber Holbrook ,  Dileep Kumar Devireddy ,  Bhushan Mangesh Kanekar ,  Venkateshwar Rao Pullela

发明人： William N. Eatherton ,  Jaushin Lee ,  Bangalore L. Priyadarshan ,  Priyank Ramesh Warkhede ,  Fusun Ertemalp ,  Hugh Weber Holbrook ,  Dileep Kumar Devireddy ,  Bhushan Mangesh Kanekar ,  Venkateshwar Rao Pullela

IPC分类号： G06F12/00

CPC分类号： G06F17/30982

摘要： Methods and apparatus are disclosed for performing lookup operations using associative memories, including, but not limited to modifying search keys within an associative memory based on modification mappings, forcing a no-hit condition in response to a highest-priority matching entry including a force no-hit indication, selecting among various sets or banks of associative memory entries in determining a lookup result, and detecting and propagating error conditions. In one implementation, each block retrieves a modification mapping from a local memory and modifies a received search key based on the mapping and received modification data. In one implementation, each of the associative memory entries includes a field for indicating that a successful match on the entry should or should not force a no-hit result. In one implementation, an indication of which associative memory blocks or sets of entries to use in a particular lookup operation is retrieved from a memory.

摘要翻译： 公开了用于使用关联存储器执行查找操作的方法和装置，包括但不限于基于修改映射修改关联存储器内的搜索关键字，响应于最高优先级的匹配条目来响应不受限制的条件，包括力 - 指示，在确定查找结果中选择各种组或存储器中的关联存储器条目，以及检测和传播错误条件。 在一个实现中，每个块从本地存储器检索修改映射，并且基于映射和接收到的修改数据修改接收到的搜索密钥。 在一个实现中，每个关联存储器条目包括用于指示条目上的成功匹配应该或不应该强制无命中结果的字段。 在一个实现中，从存储器检索在特定查找操作中使用的哪些关联存储器块或条目集合的指示。

公开(公告)号：US07103708B2

公开(公告)日：2006-09-05

申请号：US10215719

申请日：2002-08-10

申请人： William N. Eatherton ,  Jaushin Lee ,  Bangalore L. Priyadarshan ,  Priyank Ramesh Warkhede ,  Fusun Ertemalp ,  Hugh Weber Holbrook ,  Dileep Kumar Devireddy ,  Bhushan Mangesh Kanekar ,  Venkateshwar Rao Pullela

发明人： William N. Eatherton ,  Jaushin Lee ,  Bangalore L. Priyadarshan ,  Priyank Ramesh Warkhede ,  Fusun Ertemalp ,  Hugh Weber Holbrook ,  Dileep Kumar Devireddy ,  Bhushan Mangesh Kanekar ,  Venkateshwar Rao Pullela

IPC分类号： G06F12/00

CPC分类号： G06F17/30982

摘要： Methods and apparatus are disclosed for performing lookup operations using associative memories, including, but not limited to modifying search keys within an associative memory based on modification mappings, forcing a no-hit condition in response to a highest-priority matching entry including a force no-hit indication, selecting among various sets or banks of associative memory entries in determining a lookup result, and detecting and propagating error conditions. In one implementation, each block retrieves a modification mapping from a local memory and modifies a received search key based on the mapping and received modification data. In one implementation, each of the associative memory entries includes a field for indicating that a successful match on the entry should or should not force a no-hit result. In one implementation, an indication of which associative memory blocks or sets of entries to use in a particular lookup operation is retrieved from a memory.

摘要翻译： 公开了用于使用关联存储器执行查找操作的方法和装置，包括但不限于基于修改映射来修改关联存储器内的搜索关键字，以响应于包括力不在的最高优先级匹配条目来强制无命中条件 - 指示，在确定查找结果中选择各种组或存储器中的关联存储器条目，以及检测和传播错误条件。 在一个实现中，每个块从本地存储器检索修改映射，并且基于映射和接收到的修改数据修改接收到的搜索密钥。 在一个实现中，每个关联存储器条目包括用于指示条目上的成功匹配应该或不应该强制无命中结果的字段。 在一个实现中，从存储器检索在特定查找操作中使用的哪些关联存储器块或条目集合的指示。

公开(公告)号：US07065609B2

公开(公告)日：2006-06-20

申请号：US10215700

申请日：2002-08-10

申请人： William N. Eatherton ,  Jaushin Lee ,  Bangalore L. Priyadarshan ,  Priyank Ramesh Warkhede ,  Fusun Ertemalp

发明人： William N. Eatherton ,  Jaushin Lee ,  Bangalore L. Priyadarshan ,  Priyank Ramesh Warkhede ,  Fusun Ertemalp

IPC分类号： G06F12/00

CPC分类号： G06F17/30982

摘要： Methods and apparatus are disclosed for performing lookup operations using associative memories, including, but not limited to modifying search keys within an associative memory based on modification mappings, forcing a no hit condition in response to a highest priority matching entry including a force no hit indication, selecting among various blocks or sets of associative memory entries in determining a lookup result, and detecting and propagating error conditions. In one implementation, indications of which associative memory blocks to use and/or enable in a particular lookup operation are retrieved from one or more memories, such as that based on received a profile ID. In one implementation, which may or may not be in a cascaded configuration, one or more identified or received error conditions are propagated in such a manner as to identify a source of each error condition.

摘要翻译： 公开了用于使用关联存储器执行查找操作的方法和装置，包括但不限于：基于修改映射修改关联存储器内的搜索关键字，以响应于包括不存在命中指示的最大优先级匹配条目来强制无命中条件 在确定查找结果中选择各种块或相关联存储器条目集合，以及检测和传播错误条件。 在一个实现中，在一个或多个存储器（例如基于接收到的简档ID的那些）中检索在特定查找操作中使用和/或启用的联想存储器块的指示。 在一个实现中，其可以是或可以不是级联配置，一个或多个识别或接收的错误条件以识别每个错误状况的源的方式传播。

公开(公告)号：US07028136B1

公开(公告)日：2006-04-11

申请号：US10355694

申请日：2003-01-31

申请人： Bangalore L. Priyadarshan ,  Jaushin Lee ,  William N. Eatherton

发明人： Bangalore L. Priyadarshan ,  Jaushin Lee ,  William N. Eatherton

IPC分类号： G06F12/00

CPC分类号： G06F17/30982

摘要： Methods and apparatus are disclosed for, inter alia, managing idle time and performing lookup operations to adapt to refresh requirements and/or operational rates of the particular associative memory or other devices used to implement the system. A system typically a controller coupled to a circuit including includes multiple associative memories. The controller receives performance information from at least one of the associative memories and generates idle time corresponding to the performance information. This performance information may include an actual refresh requirement for each of the associate memories or the worst-case requirement of one of the associative memories, so that the controller can intermittently provide the actual refresh cycles required, if any, by a particular implementation. This performance information may indicate for some or all instructions the actual time required by a particular instruction, so that the controller can operate based on the actual time required, rather than inefficiently operating on a worst-case time defined in a specification or data sheet.

摘要翻译： 公开了用于特别地管理空闲时间和执行查找操作以适应特定关联存储器或用于实现系统的其他设备的刷新需求和/或操作速率的方法和装置。 通常是耦合到电路的控制器的系统包括多个关联存储器。 控制器从至少一个相关存储器接收演奏信息，并产生与演奏信息相对应的空闲时间。 该性能信息可以包括每个相关存储器的实际刷新需求或关联存储器之一的最坏情况要求，使得控制器可以间歇地提供特定实现所需的实际刷新周期（如果有的话）。 该性能信息可以指示特定指令所需的实际时间的某些或所有指令，使得控制器可以基于实际所需的时间进行操作，而不是在规范或数据表中定义的最坏情况下无效操作。

公开(公告)号：US06775737B1

公开(公告)日：2004-08-10

申请号：US09973508

申请日：2001-10-09

申请人： Priyank Ramesh Warkhede ,  William N. Eatherton ,  Shyamsundar N. Maniyar ,  Peram Marimuthu

发明人： Priyank Ramesh Warkhede ,  William N. Eatherton ,  Shyamsundar N. Maniyar ,  Peram Marimuthu

IPC分类号： G06F1200

CPC分类号： H04L45/00 ,  H04L45/48 ,  H04L69/22

摘要： Methods and apparatus are disclosed for allocating and using range identifiers as input values to associative memories, especially binary content-addressable memories (CAMs) and ternary content-addressable memories (TCAMs). In one implementation, each of multiple non-overlapping intervals are identified with one of multiple unique identifiers. An indication of a mapping between the multiple non-overlapping intervals and the multiple unique identifiers is maintained. A particular unique identifier is determined from said multiple unique identifiers based on a value and said multiple non-overlapping intervals. A lookup operation is performed on an associative memory using the particular unique identifier to generate a result. One implementation uses a trie representation of a range tree of the intervals to derive the unique identifiers. Moreover, one implementation evaluates and selects among various possible trie representations, especially to determine identifiers such that a TCAM prefix may match multiple intervals corresponding to a desired range.

摘要翻译： 公开了分配和使用范围标识符作为关联存储器，特别是二进制可内容寻址存储器（CAM）和三元可内容寻址存储器（TCAM）的输入值的方法和装置。 在一个实现中，多个非重叠间隔中的每一个用多个唯一标识符之一标识。 维持多个非重叠间隔与多个唯一标识符之间的映射的指示。 基于值和所述多个非重叠间隔从所述多个唯一标识符确定特定唯一标识符。 使用特定唯一标识符对关联存储器执行查找操作以生成结果。 一个实现使用间隔的范围树的特里表示来导出唯一标识符。 此外，一个实现在各种可能的特里表示中进行评估和选择，特别是确定标识符，使得TCAM前缀可以匹配对应于期望范围的多个间隔。

公开(公告)号：US06654342B1

公开(公告)日：2003-11-25

申请号：US09521278

申请日：2000-03-07

申请人： Zubin D. Dittia ,  William N. Eatherton ,  John Andrew Fingerhut ,  Michael B. Galles ,  Jonathan S. Turner

发明人： Zubin D. Dittia ,  William N. Eatherton ,  John Andrew Fingerhut ,  Michael B. Galles ,  Jonathan S. Turner

IPC分类号： G01R3108

CPC分类号： H04L12/5602

摘要： Methods and apparatus are disclosed for accumulating and distributing flow control information via update messages and piggybacked flow control information in other messages. One implementation operates using at least two techniques. Using a first technique, for every packet entering the switching system from a line card, the switching system conveys flow control information (typically congestion or both congestion and no-congestion indications) for the packet's destination to the line card. Using a second technique, the switching system will periodically convey congestion and no-congestion indications for all destinations to the line cards. In one implementation, when the first technique is used to provide only congestion indications, the periodic distribution of flow control information using the second technique provides non-congested indications which allows the line cards and their sources to resume or begin sending to the non-congested destinations.

摘要翻译： 公开了用于通过更新消息积累和分发流量控制信息的方法和装置以及其他消息中的捎带流控制信息。 一个实现使用至少两种技术来进行操作。 使用第一种技术，对于从线路卡进入交换系统的每个分组，交换系统将分组目的地的流量控制信息（通常拥塞或两者拥塞和无拥塞指示）传送到线路卡。 使用第二种技术，交换系统将周期性地向线路卡传送所有目的地的拥塞和无拥塞指示。 在一个实现中，当第一技术被用于仅提供拥塞指示时，使用第二技术的流量控制信息的周期性分布提供非拥塞指示，其允许线路卡及其源恢复或开始发送到非拥塞 目的地。

公开(公告)号：US07496035B1

公开(公告)日：2009-02-24

申请号：US10355831

申请日：2003-01-31

申请人： Ganesh Sadasivan ,  Rengabashyam Srinivas ,  William N. Eatherton ,  Xiaoxue Ma ,  Peram Marimuthu

发明人： Ganesh Sadasivan ,  Rengabashyam Srinivas ,  William N. Eatherton ,  Xiaoxue Ma ,  Peram Marimuthu

IPC分类号： G08C15/00

CPC分类号： H04L49/901 ,  H04L47/10 ,  H04L47/2441 ,  H04L49/90 ,  Y10S707/99943

摘要： Methods and apparatus are disclosed for defining flow types and instances thereof such as for identifying packets corresponding to instances of the flow types. A flow type is defined and includes a set of properties including at least one of the possible properties selectable when defining a flow type. An instance of the flow type is defined and a set of corresponding associative memory entries is generated. A lookup word generator of a packet processing engine is typically notified of the use of the flow type, and one or more lookup words are generated typically by extracting fields from a received packet and/or from other sources. Based on a result of lookup operations on the set of associative memories entries using the generated one or more lookup words, the received packet can be identified as whether it matches or does not match the instance of the flow type.

摘要翻译： 公开了用于定义流类型和实例的方法和装置，例如用于识别与流类型的实例对应的分组。 定义流类型并且包括一组属性，其包括在定义流类型时可选择的可能属性中的至少一个。 定义流类型的实例，并生成一组对应的关联内存条目。 典型地通过从所接收的分组和/或来自其它来源提取字段来生成分组处理引擎的查找词生成器，使用流类型，并且生成一个或多个查找词。 基于使用所生成的一个或多个查找词的关联存储器条目集合的查找操作的结果，可以将接收的分组识别为与流类型的实例匹配还是不匹配。

公开(公告)号：US07313093B1

公开(公告)日：2007-12-25

申请号：US10304421

申请日：2002-11-26

申请人： William N. Eatherton ,  John H. W. Bettink

发明人： William N. Eatherton ,  John H. W. Bettink

IPC分类号： H04L12/56

CPC分类号： H04L47/10 ,  H04L47/30 ,  H04L47/32

摘要： Methods and apparatus are disclosed for selectively discarding packets such as in, but not limited to a packet switching system, by reacting to packet traffic conditions to reduce or eliminate the indiscriminate discarding of packets during identified overload conditions. Typically, a first element forwards multiple packets to a second element, each of the multiple packets being associated with a packet overload condition type of possible packet overload condition types, including, but not limited to a discard-on-overload type and a retain-on-overload type. The first element forwards a condition indication to the second element. The second element receives the condition indication and a particular packet. The second element discards the particular packet if the received condition indication is associated with the overload state and the packet overload condition type of the particular received packet is associated with the discard-on-overload type. Otherwise, the second element typically further processes the particular packet.

摘要翻译： 公开了用于选择性地丢弃分组的方法和装置，所述分组例如在但不限于分组交换系统中，通过对分组业务条件做出反应以减少或消除在所识别的过载条件期间不加区分地丢弃分组。 通常，第一元件将多个分组转发到第二元素，多个分组中的每一个与可能的分组过载条件类型的分组过载条件类型相关联，包括但不限于丢弃过载类型和保留 - 过载类型。 第一个元素将条件指示转发给第二个元素。 第二个元件接收条件指示和特定数据包。 如果接收到的条件指示与过载状态相关联并且特定接收到的分组的分组过载状况类型与丢弃过载类型相关联，则第二元素丢弃该特定分组。 否则，第二元素通常进一步处理特定分组。

公开(公告)号：US07249149B1

公开(公告)日：2007-07-24

申请号：US10833532

申请日：2004-04-26

申请人： William N. Eatherton ,  Zubin D. Dittia

发明人： William N. Eatherton ,  Zubin D. Dittia

IPC分类号： G06F7/00

CPC分类号： H04L12/56 ,  H04L45/7457 ,  Y10S707/99943 ,  Y10S707/99945 ,  Y10S707/99948

摘要： Disclosed are, inter alia, methods, apparatus, data structures, computer-readable media, mechanisms, and means for defining, creating and using tree bitmap data structures, such as for, but not limited to their use in performing lookup operations (e.g., longest prefix matching, etc.). The data structure typically includes a tree bitmap for identifying for each node of multiple nodes within a stride of a number of tree levels greater than one whether each node is a prefix or vacant node, the multiple nodes representing multiple tree levels, a lowest level subset of the multiple nodes corresponding to a lowest level of the tree levels in the stride, the lowest level subset of the multiple nodes including two or more nodes. A child bitmap is typically used for identifying which trie paths emanate and which trie paths do not emanate from the lowest level subset of the multiple nodes.

摘要翻译： 公开的方法，装置，数据结构，计算机可读介质，机制和用于定义，创建和使用树位图数据结构的装置，诸如但不限于它们在执行查找操作中的用途（例如， 最长前缀匹配等）。 数据结构通常包括树位图，用于识别大于每个节点是否为前缀或空闲节点的多个树级别的步长内的多个节点的每个节点，多个节点表示多个树级别，最低级别子集 对应于步幅中的树级的最低级的多个节点，包括两个或多个节点的多个节点的最低级子集。 子位图通常用于识别出现哪些特洛伊路径，哪些特里路径不从多个节点的最低级子集发出。

公开(公告)号：US06728211B1

公开(公告)日：2004-04-27

申请号：US09520685

申请日：2000-03-07

申请人： Vinod Gerard John Peris ,  Jonathan S. Turner ,  Zubin D. Dittia ,  William N. Eatherton

发明人： Vinod Gerard John Peris ,  Jonathan S. Turner ,  Zubin D. Dittia ,  William N. Eatherton

IPC分类号： H04L1226

CPC分类号： H04L47/10 ,  H04L47/12 ,  H04L47/26 ,  H04L47/32 ,  H04L49/101 ,  H04L49/20 ,  H04L49/201 ,  H04L49/254 ,  H04L49/3027

摘要： Methods and apparatus are also disclosed for responding to received flow control messages indicating a previously congested port is now in a non-congested state. Many different components that have packets to send to a particular output will receive an indication that they are now allowed to send these packets at roughly the same time as the other components. If all components start sending at the same time, then the packet switch might become congested, possibly very quickly. If the packet switch cannot respond and transmit flow control messages to all of these sources fast enough, certain internal buffers could overflow and thus packets might be lost. On implementation causes components to start sending to the destination at varying times to gradually increase the traffic being sent to the destination. In this manner, the traffic in the packet switch gradually rises which allows buffers within the packet switch to drain while new traffic is arriving, and allows the packet switch time to react and throttle-back the traffic in a reasonable manner should paths leading to the output become congested.

摘要翻译： 还公开了用于响应指示先前拥塞的端口现在处于非拥塞状态的接收的流控制消息的方法和装置。 具有发送到特定输出的数据包的许多不同组件将接收到它们现在允许与其他组件大致相同的时间发送这些数据包的指示。 如果所有组件同时开始发送，则分组交换机可能会变得拥塞，可能非常快。 如果分组交换机不能快速响应并向所有这些源发送流量控制消息，某些内部缓冲区可能会溢出，从而数据包可能丢失。 在实施时，组件可以在不同的时间开始发送到目的地，以逐渐增加发送到目的地的流量。 以这种方式，分组交换机中的业务量逐渐上升，这允许分组交换机内的缓冲区在新的业务到达时消失，并且允许分组交换时间以合理的方式作出反应并节省流量，如果通向 输出变得拥塞。