公开(公告)号：US06658002B1

公开(公告)日：2003-12-02

申请号：US09335800

申请日：1999-06-17

申请人： Mark A. Ross ,  Sun-Den Chen ,  Andreas V. Bechtolsheim

发明人： Mark A. Ross ,  Sun-Den Chen ,  Andreas V. Bechtolsheim

IPC分类号： H04L1256

CPC分类号： H04L47/10 ,  H04L45/50 ,  H04L45/7453 ,  H04L47/20 ,  H04L47/2441 ,  H04L47/31 ,  H04L63/101

摘要： An apparatus and method for performing logical operations on information in the communications protocol stack, such as the transport layer (L4) port numbers, characterizing a received packet or frame of data in a data communications device such as a router or switch. The results of the logical operations, along with other packet/frame-identifying data, are used to generate a more efficient lookup key. A content addressable memory (CAM) lookup is used to determine the action indicated by the rules defined by a rule-based routing or switching scheme, such as an access control list (ACL). The results of these logical operations extend the key space and thus provide a finer-grained match between the original, unextended input key and a rule action, thereby pointing to a rule action precisely tailored to packet processing. The rule can thus be applied with fewer CAM entries, providing the versatility improvement and CAM cost reduction necessary to keep up with the ever-increasing rule complexity requirements of advanced data communication and internetworking systems. An embodiment utilizing asymmetrical processing of packets, depending on whether the packet is inbound to the data communications device or outbound from it, is also disclosed. Furthermore, a ternary content-addressable memory (TCAM) implementation is disclosed. Use of a TCAM for ACL or other rule lookups further enhances the efficiency of rule processing by providing a masking capability for each TCAM entry which can be used to provide an additional level of flexibility for rule element checking.

摘要翻译： 对诸如传输层（L4）端口号的通信协议栈中的信息执行逻辑操作的装置和方法，表征诸如路由器或交换机之类的数据通信设备中的接收到的数据包或数据帧。 逻辑操作的结果连同其他分组/帧识别数据一起用于生成更有效的查找键。 内容可寻址存储器（CAM）查找用于确定由基于规则的路由或交换方案（诸如访问控制列表（ACL））定义的规则所指示的动作。 这些逻辑操作的结果扩展了密钥空间，从而在原始的，未扩展的输入密钥和规则动作之间提供了更细粒度的匹配，从而指向了针对数据包处理精确定制的规则操作。 因此，该规则可以应用于较少的CAM条目，提供多功能性改进和CAM成本降低，以适应高级数据通信和互联网络系统日益增长的规则复杂性要求。 还公开了一种利用分组的不对称处理的实施例，这取决于分组是否入站到数据通信设备或者从数据通信设备出站。 此外，公开了三元内容寻址存储器（TCAM）实现。 使用TCAM进行ACL或其他规则查找可以通过为每个TCAM条目提供掩蔽功能来进一步提高规则处理的效率，这可以用于为规则元素检查提供额外的灵活性水平。

公开(公告)号：US5544332A

公开(公告)日：1996-08-06

申请号：US402727

申请日：1995-03-13

申请人： Sun-Den Chen

发明人： Sun-Den Chen

IPC分类号： G06F11/30 ,  G06F9/46 ,  G06F9/52 ,  G06F13/00 ,  G06F13/362 ,  G06F13/36

CPC分类号： G06F9/524 ,  G06F13/362

摘要： Deadlock detection and masking systems are incorporated into a bus coupler intercoupling at least two buses, wherein at least one master is coupled to each bus and at least one slave is coupled to at least one of the buses. The bus coupler also includes an arbiter coupled to the buses to determine which master may control each bus. The deadlock detection system detects a potential arbitration deadlock condition between two master devices seeking control of a bus and access to a slave. Once a potential arbitration deadlock is detected, the masking system is activated to prohibit the second master from gaining control of the second bus for a random period of time. The random time delay acts as a mask to provide the first master device an opportunity to reaccess the slave device and avoid the deadlock situation. By providing a random masking period complementary, synchronized arbitration deadlocks are avoided.

摘要翻译： 死锁检测和屏蔽系统被并入耦合到至少两个总线的总线耦合器中，其中至少一个主站耦合到每个总线，并且至少一个从站耦合到至少一个总线。 总线耦合器还包括耦合到总线的仲裁器，以确定哪个主机可以控制每个总线。 死锁检测系统检测两个主控设备之间潜在的仲裁死锁状态，寻求总线控制和对从站的访问。 一旦检测到潜在的仲裁死锁，则屏蔽系统被激活，以禁止第二主机在随机时间段内获得对第二总线的控制。 随机时间延迟作为掩码，为第一主设备提供重新访问从设备并避免死锁情况的机会。 通过提供互补的随机屏蔽周期，避免了同步的仲裁死锁。

公开(公告)号：US08767540B2

公开(公告)日：2014-07-01

申请号：US13239214

申请日：2011-09-21

申请人： Brian Alleyne ,  Sun Den Chen ,  Ramanathan Lakshmikanthan

发明人： Brian Alleyne ,  Sun Den Chen ,  Ramanathan Lakshmikanthan

IPC分类号： G01R31/08 ,  G06F11/00 ,  G08C15/00 ,  H04J1/16 ,  H04J3/14 ,  H04L1/00 ,  H04L12/26

CPC分类号： H04L47/31 ,  H04L47/20 ,  H04L47/215

摘要： Embodiments of the invention a method for policing a packet at line rate. A hierarchical policer receives a policer request comprising packet characteristics and identifying request configuration information. The hierarchical policer retrieves meter states specified by the request configuration information. The hierarchical policer processes packet characteristics through meters to generate a meter result. The hierarchical policer generates a hierarchical policer table lookup address using a plurality of meter types, a plurality of input color controls, one or more of the packet characteristics, the meter results, and a plurality of coupling algorithm identifiers. The hierarchical policer reads a hierarchical meter result from a hierarchical policer result table, containing at least a final output packet attribute that classifies the packet. The hierarchical policer updates one or more of the meter states based on the plurality of meter state results. The hierarchical policer returns the final packet output to a policing requestor.

摘要翻译： 本发明的实施例提供了一种以线速度对分组进行管理的方法。 分层策略器接收包含分组特性和识别请求配置信息的策略请求。 分层策略器检索由请求配置信息指定的仪表状态。 分层策略器通过米来处理分组特征，以产生测量结果。 分级策略器使用多个仪表类型，多个输入颜色控制，分组特性中的一个或多个，仪表结果和多个耦合算法标识符来生成分层策略表查找地址。 分层策略器从分层策略器结果表中读取分层计量表结果，其中至少包含对数据包进行分类的最终输出数据包属性。 分层监视器基于多个仪表状态结果来更新仪表状态中的一个或多个。 分层策略器将最终的分组输出返回到管理请求者。

公开(公告)号：US20130301641A1

公开(公告)日：2013-11-14

申请号：US13466984

申请日：2012-05-08

申请人： Prashant Anand ,  Ramanathan Lakshmikanthan ,  Sun Den Chen ,  Ning Xu

发明人： Prashant Anand ,  Ramanathan Lakshmikanthan ,  Sun Den Chen ,  Ning Xu

IPC分类号： H04L12/56

CPC分类号： H04L63/0227 ,  H04L45/745 ,  H04L47/2441 ,  H04L47/2483 ,  H04L63/0263 ,  H04L63/101 ,  H04L63/1408

摘要： In one aspect, the present invention reduces the amount of low-latency memory needed for rules-based packet classification by representing a packet classification rules database in compressed form. A packet processing rules database, e.g., an ACL database comprising multiple ACEs, is preprocessed to obtain corresponding rule fingerprints. These rule fingerprints are much smaller than the rules and are easily accommodated in on-chip or other low-latency memory that is generally available to the classification engine in limited amounts. The rules database in turn can be stored in off-chip or other higher-latency memory, as initial matching operations involve only the packet key of the subject packet and the fingerprint database. The rules database is accessed for full packet classification only if a tentative match is found between the packet key and an entry in the fingerprint database. Thus, the present invention also advantageously minimizes accesses to the rules database.

摘要翻译： 一方面，本发明通过以压缩形式表示分组分类规则数据库来减少基于规则的分组分类所需的低延迟存储器的数量。 分组处理规则数据库（例如，包括多个ACE的ACL数据库）被预处理以获得相应的规则指纹。 这些规则指纹比规则小得多，并且容易地被容纳在分类引擎中有限的片上或其他低延迟存储器中。 因为初始匹配操作仅涉及主题分组和指纹数据库的分组密钥，因此规则数据库又可以存储在片外或其他较高延迟的存储器中。 仅当在分组密钥和指纹数据库中的条目之间发现暂时匹配时，才能对完整分组分类进行规则数据库的访问。 因此，本发明还有利地最小化对规则数据库的访问。

公开(公告)号：US20120170472A1

公开(公告)日：2012-07-05

申请号：US12983104

申请日：2010-12-31

申请人： EDMUND CHEN ,  RAMANATHAN LAKSHMIKANTHAN ,  RANJIT ROZARIO ,  BRIAN ALLEYNE ,  STEPHEN CHOW ,  PATRICK WANG ,  EDWARD HO ,  THOMAS YIP ,  SUN DEN CHEN ,  MICHAEL FENG

发明人： EDMUND CHEN ,  RAMANATHAN LAKSHMIKANTHAN ,  RANJIT ROZARIO ,  BRIAN ALLEYNE ,  STEPHEN CHOW ,  PATRICK WANG ,  EDWARD HO ,  THOMAS YIP ,  SUN DEN CHEN ,  MICHAEL FENG

IPC分类号： H04L12/56 ,  H04L12/26

CPC分类号： H04L49/9073 ,  H04L47/12 ,  H04L47/2441 ,  H04L47/32 ,  H04L49/9036 ,  H04L49/9063 ,  H04L49/9078

摘要： Embodiments of the invention include a method for avoiding memory bandwidth utilization during packet processing. The packet processing core receives a plurality of packets. The packet processing core identifies the packet's quality of service (QoS) descriptor. The packet processing core determines that at least one packet should be moved to an off-chip packet stored prior to the packet being transmitted to the egress port. The packet processing core bases that determination, at least in part, on the packet's QoS descriptor. The packet processing core moves the determined packets to the off-chip packet store. The packet processing core determines that at least one packet should not be moved to the off-chip packet store prior to the packet being transmitted to the egress port. This determination is also made, at least in part, based on the packet's QoS descriptor.

摘要翻译： 本发明的实施例包括一种在分组处理期间避免存储器带宽利用的方法。 分组处理核心接收多个分组。 分组处理核心识别分组的服务质量（QoS）描述符。 分组处理核心确定至少一个分组应该被移动到在分组被发送到出口端口之前存储的片外分组。 分组处理核心基于至少部分地确定分组的QoS描述符。 分组处理核心将确定的分组移动到片外分组存储。 分组处理核心在分组被发送到出口端口之前确定至少一个分组不应该被移动到片外分组存储。 该决定至少部分地基于分组的QoS描述符进行。

公开(公告)号：US20100278190A1

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

申请号：US12432373

申请日：2009-04-29

申请人： Thomas C. Yip ,  Michael Feng ,  Sun Den Chen ,  Stephen Chow ,  Edward Ho ,  Patrick Wang ,  Srivi Dhruvanarayan ,  Ranjit Rozario ,  Edmund Chen

发明人： Thomas C. Yip ,  Michael Feng ,  Sun Den Chen ,  Stephen Chow ,  Edward Ho ,  Patrick Wang ,  Srivi Dhruvanarayan ,  Ranjit Rozario ,  Edmund Chen

IPC分类号： H04L12/56

CPC分类号： H04L47/623 ,  H04L47/50 ,  H04L47/60 ,  H04L49/90

摘要： A hierarchical pipelined distributed scheduling traffic manager includes multiple hierarchical levels to perform hierarchical winner selection and propagation in a pipeline including selecting and propagating winner queues of a lower level to subsequent levels to determine one final winning queue. The winner selection and propagation is performed in parallel between the levels to reduce the time required in selecting the final winning queue. In some embodiments, the hierarchical traffic manager is separated into multiple separate sliced hierarchical traffic managers to distributively process the traffic.

摘要翻译： 分级流水线分布式调度业务管理器包括多个层次级别，以在流水线中执行分级获胜者选择和传播，包括选择和传播较低级别的优胜者队列到后续级别，以确定一个最终获胜队列。 获胜者选择和传播在级别之间并行执行，以减少选择最终获胜队列所需的时间。 在一些实施例中，分层业务管理器被分成多个分离的分层分层业务管理器以分布地处理业务。

公开(公告)号：US5892957A

公开(公告)日：1999-04-06

申请号：US868171

申请日：1997-06-03

申请人： Kevin B. Normoyle ,  Zahir Ebrahim ,  Satyanarayana Nishtala ,  William C. Van Loo ,  Sun-Den Chen ,  Charles E. Narad

发明人： Kevin B. Normoyle ,  Zahir Ebrahim ,  Satyanarayana Nishtala ,  William C. Van Loo ,  Sun-Den Chen ,  Charles E. Narad

IPC分类号： G06F15/173 ,  G06F9/46 ,  G06F9/48 ,  G06F13/24 ,  G06F13/14

CPC分类号： G06F9/546 ,  G06F13/24

摘要： An apparatus and method for handling interrupt requests from any of a plurality of interrupters to any of a plurality of interrupt handlers. Each interrupt handler includes an interrupt input request queue for holding a plurality of incoming interrupt requests. A system controller is connected to the interrupters and the interrupt handlers, and includes an input queue coupled to each interrupter for receiving a plurality of interrupt requests. The system controller includes a processor and a memory storing instructions for controlling its operation. The system controller also includes an output queue coupled to each interrupt handler (which in many cases will also be interrupters), and a counter for monitoring the current number, at any given time, of interrupt requests pending in each of the interrupt input queues in the interrupt handlers. When an interrupt request is sent from an interrupter, the system controller determines a target for the request, which may be by a target ID in the request or may be based upon a predetermined method to ensure even distribution of interrupt requests among all or a subset of the interrupt handlers. The system controller determines whether the target interrupt handler's input queue is full, and if not then it passes on the interrupt request and sends a positive acknowledgment to the interrupter. If the queue is full, then a negative acknowledgment is sent, and the interrupter then waits a random period of time and sends the interrupt request again. The target interrupt handler may thus accept multiple interrupt requests and process them in order without negative acknowledgments.

摘要翻译： 一种用于处理从多个中断器中的任一个到多个中断处理程序中的任何一个的中断请求的装置和方法。 每个中断处理程序包括用于保持多个输入中断请求的中断输入请求队列。 系统控制器连接到断续器和中断处理器，并且包括耦合到每个中断器的输入队列，用于接收多个中断请求。 系统控制器包括处理器和存储用于控制其操作的指令的存储器。 系统控制器还包括耦合到每个中断处理器（在许多情况下也将是中断器）的输出队列，以及用于在任何给定时间监视每个中断输入队列中的中断请求的当前号码的计数器 中断处理程序。 当从中断器发送中断请求时，系统控制器确定请求的目标，该请求可以是请求中的目标ID，或者可以基于预定的方法来确保所有或一个子集中的中断请求的均匀分配 的中断处理程序。 系统控制器确定目标中断处理程序的输入队列是否已满，如果不是，则它传递中断请求并向中断器发送肯定确认。 如果队列已满，则发送否定确认，然后中断器等待随机时间段，并再次发送中断请求。 因此，目标中断处理程序可以接受多个中断请求并按顺序进行处理，而不会产生否定的确认。

公开(公告)号：US5727219A

公开(公告)日：1998-03-10

申请号：US854113

申请日：1997-05-09

申请人： Thomas L. Lyon ,  Sun-Den Chen ,  William Joy ,  Leslie D. Kohn ,  Charles E. Narad ,  Robert Yung

发明人： Thomas L. Lyon ,  Sun-Den Chen ,  William Joy ,  Leslie D. Kohn ,  Charles E. Narad ,  Robert Yung

IPC分类号： G06F13/10 ,  G06F13/28 ,  G06F13/38 ,  G06F9/46 ,  G06F13/24

CPC分类号： G06F13/28 ,  G06F13/10 ,  G06F13/385

摘要： A virtual I/O processor (VIOP) is implemented using a programmed I/O (PIO) unit. The PIO unit is complemented by a VIOP interrupt, a VIOP interrupt handler, and a number of VIOP data structures. Preferably, the PIO unit is further complemented with a set of dedicated I/O global registers, a number of VIOP library read/write routines for various I/O device types, and non-blocking read and write operations. During execution, these elements cooperate with each other to perform multiple sequences of programmed I/Os as if they were being performed by a dedicated I/O processor.

摘要翻译： 使用编程的I / O（PIO）单元实现虚拟I / O处理器（VIOP）。 PIO单元由VIOP中断，VIOP中断处理程序和多个VIOP数据结构补充。 优选地，PIO单元进一步补充有一组专用I / O全局寄存器，用于各种I / O设备类型的多个VIOP库读/写例程以及非阻塞读写操作。 在执行期间，这些元件彼此协作以执行多个编程I / O序列，就像它们由专用I / O处理器执行一样。

公开(公告)号：US5689713A

公开(公告)日：1997-11-18

申请号：US425537

申请日：1995-04-20

申请人： Kevin B. Normoyle ,  Zahir Ebrahim ,  Satyanarayana Nishtala ,  William C. Van Loo ,  Sun-Den Chen ,  Charles E. Narad

发明人： Kevin B. Normoyle ,  Zahir Ebrahim ,  Satyanarayana Nishtala ,  William C. Van Loo ,  Sun-Den Chen ,  Charles E. Narad

IPC分类号： G06F15/173 ,  G06F9/46 ,  G06F9/48 ,  G06F13/24 ,  G06F13/14

CPC分类号： G06F9/546 ,  G06F13/24

摘要： An apparatus and method for handling interrupt requests from any of a plurality of interrupters to any of a plurality of interrupt handlers. Each interrupt handler includes an interrupt input request queue for holding a plurality of incoming interrupt requests. A system controller is connected to the interrupters and the interrupt handlers, and includes an input queue coupled to each interrupter for receiving a plurality of interrupt requests. The system controller includes a processor and a memory storing instructions for controlling its operation. The system controller also includes an output queue coupled to each interrupt handler (which in many cases will also be interrupters), and a counter for monitoring the current number, at any given time, of interrupt requests pending in each of the interrupt input queues in the interrupt handlers. When an interrupt request is sent from an interrupter, the system controller determines a target for the request, which may be by a target ID in the request or may be based upon a predetermined method to ensure even distribution of interrupt requests among all or a subset of the interrupt handlers. The system controller determines whether the target interrupt handler's input queue is full, and if not then it passes on the interrupt request and sends a positive acknowledgment to the interrupter. If the queue is full, then a negative acknowledgment is sent, and the interrupter then waits a random period of time and sends the interrupt request again. The target interrupt handler may thus accept multiple interrupt requests and process them in order without negative acknowledgments.

摘要翻译： 一种用于处理从多个中断器中的任一个到多个中断处理程序中的任何一个的中断请求的装置和方法。 每个中断处理程序包括用于保持多个输入中断请求的中断输入请求队列。 系统控制器连接到断续器和中断处理器，并且包括耦合到每个中断器的输入队列，用于接收多个中断请求。 系统控制器包括处理器和存储用于控制其操作的指令的存储器。 系统控制器还包括耦合到每个中断处理器（在许多情况下也将是中断器）的输出队列，以及用于在任何给定时间监视每个中断输入队列中的中断请求的当前号码的计数器 中断处理程序。 当从中断器发送中断请求时，系统控制器确定请求的目标，该请求可以是请求中的目标ID，或者可以基于预定的方法来确保所有或一个子集中的中断请求的均匀分配 的中断处理程序。 系统控制器确定目标中断处理程序的输入队列是否已满，如果不是，则它传递中断请求并向中断器发送肯定确认。 如果队列已满，则发送否定确认，然后中断器等待随机时间段，并再次发送中断请求。 因此，目标中断处理程序可以接受多个中断请求并按顺序进行处理，而不会产生否定的确认。

公开(公告)号：US08879550B2

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

申请号：US13466984

申请日：2012-05-08

申请人： Prashant Anand ,  Ramanathan Lakshmikanthan ,  Sun Den Chen ,  Ning Xu

发明人： Prashant Anand ,  Ramanathan Lakshmikanthan ,  Sun Den Chen ,  Ning Xu

IPC分类号： H04L12/28

CPC分类号： H04L63/0227 ,  H04L45/745 ,  H04L47/2441 ,  H04L47/2483 ,  H04L63/0263 ,  H04L63/101 ,  H04L63/1408

摘要： In one aspect, the present invention reduces the amount of low-latency memory needed for rules-based packet classification by representing a packet classification rules database in compressed form. A packet processing rules database, e.g., an ACL database comprising multiple ACEs, is preprocessed to obtain corresponding rule fingerprints. These rule fingerprints are much smaller than the rules and are easily accommodated in on-chip or other low-latency memory that is generally available to the classification engine in limited amounts. The rules database in turn can be stored in off-chip or other higher-latency memory, as initial matching operations involve only the packet key of the subject packet and the fingerprint database. The rules database is accessed for full packet classification only if a tentative match is found between the packet key and an entry in the fingerprint database. Thus, the present invention also advantageously minimizes accesses to the rules database.

摘要翻译： 一方面，本发明通过以压缩形式表示分组分类规则数据库来减少基于规则的分组分类所需的低延迟存储器的数量。 分组处理规则数据库（例如，包括多个ACE的ACL数据库）被预处理以获得相应的规则指纹。 这些规则指纹比规则小得多，并且容易地被容纳在分类引擎中有限的片上或其他低延迟存储器中。 因为初始匹配操作仅涉及主题分组和指纹数据库的分组密钥，因此规则数据库又可以存储在片外或其他较高延迟的存储器中。 仅当在分组密钥和指纹数据库中的条目之间发现暂时匹配时，才能对完整分组分类进行规则数据库的访问。 因此，本发明还有利地最小化对规则数据库的访问。