公开(公告)号：US10795873B1

公开(公告)日：2020-10-06

申请号：US15359616

申请日：2016-11-22

Applicant: Innovium, Inc.

Inventor： William Brad Matthews ,  Puneet Agarwal

IPC: G06F16/22 ,  G06F16/23 ,  G06F16/2455

Abstract: Certain hash-based operations in network devices and other devices, such as mapping and/or lookup operations, are improved by manipulating a hash key prior to executing a hash function on the hash key and/or by manipulating outputs of a hash function. A device may be configured to manipulate hash keys and/or outputs using manipulation logic based on one or more predefined manipulation values. A similar hash-based operation may be performed by multiple devices within a network of computing devices. Different devices may utilize different predefined manipulation values for their respective implementations of the manipulation logic. For instance, each device may assign itself a random mask value for key transformation logic as part of an initialization process when the device powers up and/or each time the device reboots. In an embodiment, described techniques may increase the entropy of hashing function outputs in certain contexts, thereby increasing the effectiveness of certain hashing functions.

公开(公告)号：US10742558B1

公开(公告)日：2020-08-11

申请号：US16057354

申请日：2018-08-07

Applicant: Innovium, Inc.

Inventor： William Brad Matthews ,  Puneet Agarwal ,  Bruce Hui Kwan

IPC: H04L12/815 ,  H04L12/861 ,  H04L12/935 ,  H04L12/863 ,  H04L12/933 ,  H04L12/879 ,  H04L12/54 ,  H04L12/813 ,  H04L12/801 ,  H04L12/823

Abstract: A traffic manager is shared amongst two or more egress blocks of a network device, thereby allowing traffic management resources to be shared between the egress blocks. Among other aspects, this may reduce power demands and allow a larger amount of buffer memory to be available to a given egress block that may be experiencing high traffic loads. Optionally, the shared traffic manager may be leveraged to reduce the resources required to handle data units on ingress. Rather than buffer the entire unit in the ingress buffers, an arbiter may be configured to buffer only the control portion of the data unit. The payload of the data unit, by contrast, is forwarded directly to the shared traffic manager, where it is placed in the egress buffers. Because the payload is not being buffered in the ingress buffers, the ingress buffer memory may be greatly reduced.

公开(公告)号：US10735339B1

公开(公告)日：2020-08-04

申请号：US15407159

申请日：2017-01-16

Applicant: Innovium, Inc.

Inventor： William Brad Matthews ,  Puneet Agarwal ,  Ajit Kumar Jain

IPC: H04L12/875

Abstract: A network device organizes packets into various queues, in which the packets await processing. Queue management logic tracks how long certain packet(s), such as a designated marker packet, remain in a queue. Based thereon, the logic produces a measure of delay for the queue, referred to herein as the “queue delay.” Based on a comparison of the current queue delay to one or more thresholds, various associated delay-based actions may be performed, such as tagging and/or dropping packets departing from the queue, or preventing addition enqueues to the queue. In an embodiment, a queue may be expired based on the queue delay, and all packets dropped. In other embodiments, when a packet is dropped prior to enqueue into an assigned queue, copies of some or all of the packets already within the queue at the time the packet was dropped may be forwarded to a visibility component for analysis.

公开(公告)号：US10587536B1

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

申请号：US15996378

申请日：2018-06-01

Applicant: Innovium, Inc.

Inventor： Bruce Hui Kwan ,  Puneet Agarwal

IPC: H04L12/883 ,  H04L12/823 ,  H04L12/879 ,  H04L12/815

Abstract: Techniques for improved handling of queues of data units are described, such as queues of buffered data units of differing types and/or sources within a switch or other network device. When the size of a queue surpasses the state entry threshold for a certain state, the queue is said to be in the certain state. While in the certain state, data units assigned to the queue may be handled differently in some respect, such as being marked or being dropped without further processing. The queue remains in this certain state until its size falls below the state release threshold for the state. The state release threshold is adjusted over time in, for example, a random or pseudo-random manner. Among other aspects, in some embodiments, this adjustment of the state release threshold addresses fairness issues that may arise with respect to the treatment of different types or sources of data units.

公开(公告)号：US10541946B1

公开(公告)日：2020-01-21

申请号：US15410651

申请日：2017-01-19

Applicant: Innovium, Inc.

Inventor： William Brad Matthews ,  Puneet Agarwal

IPC: H04L12/861 ,  H04L12/741

Abstract: Nodes within a network are configured to adapt to changing path states, due to congestion, node failures, and/or other factors. A node may selectively convey path information and/or other state information to another node by annotating the information into packets it receives from the other node. A node may selectively reflect these annotated packets back to the other node, or other nodes that subsequently receive these annotated packets may reflect them. A weighted cost multipathing selection technique is improved by dynamically adjusting weights of paths in response to feedback indicating the current state of the network topology, such as collected through these reflected packets. In an embodiment, certain packets that would have been dropped may instead be transformed into “special visibility” packets that may be stored and/or sent for analysis. In an embodiment, insight into the performance of a network device is enhanced through the use of programmable visibility engines.

公开(公告)号：US10540867B1

公开(公告)日：2020-01-21

申请号：US15729386

申请日：2017-10-10

Applicant: Innovium, Inc.

Inventor： Kapil Vishwas Shrikhande ,  David Alan Jarosh ,  William Brad Matthews

IPC: H04L29/06 ,  G08B5/38 ,  G08B5/36 ,  H04L12/26

Abstract: Approaches, techniques, and mechanisms are disclosed for monitoring and reporting status information in a computing device. According to one embodiment, status messages are generated with respect to a subsystem of a computing system, such as a computer chip configured to perform network switching and routing functions in a network device. The status messages convey status information, such as configuration and/or operational states, metrics, or other statistics. A message decoder within the system may be configured to receive and analyze the status messages. Based thereon, the message decoder generates output data in a specific format that controls an output device, such as an LED array. The message decoder then sends the output data to the output device. Enabling the reporting of status information through LED indicators and other typically custom and proprietary output devices is thus greatly simplified. A status chain for collecting and reporting status information is also described.

公开(公告)号：US10320691B1

公开(公告)日：2019-06-11

申请号：US15410644

申请日：2017-01-19

Applicant: Innovium, Inc.

Inventor： William Brad Matthews ,  Puneet Agarwal

IPC: H04L12/833 ,  H04L12/751 ,  H04L12/727 ,  H04L12/823 ,  H04L12/707

Abstract: Nodes within a network are configured to adapt to changing path states, due to congestion, node failures, and/or other factors. A node may selectively convey path information and/or other state information to another node by annotating the information into packets it receives from the other node. A node may selectively reflect these annotated packets back to the other node, or other nodes that subsequently receive these annotated packets may reflect them. A weighted cost multipathing selection technique is improved by dynamically adjusting weights of paths in response to feedback indicating the current state of the network topology, such as collected through these reflected packets. In an embodiment, certain packets that would have been dropped may instead be transformed into “special visibility” packets that may be stored and/or sent for analysis. In an embodiment, insight into the performance of a network device is enhanced through the use of programmable visibility engines.

公开(公告)号：US09941899B1

公开(公告)日：2018-04-10

申请号：US15681249

申请日：2017-08-18

Applicant: Innovium, Inc.

Inventor： Mani Kumaran ,  Rupa Budhia ,  Meg Lin

IPC: H03M7/30 ,  H04B7/26

CPC classification number: H03M7/3082 ,  H03M7/30 ,  H04B7/2606

Abstract: This disclosure relates to compressing and/or decompressing a group of similar data units, such as a table or queue of data units processed by a networking device or other computing apparatus. Each data unit in the group may only have values for fields in a master set. The described systems are particularly suited for hardware-level processing of groups of sparsely-populated data units, in which a large number of the data units have values for only a small number of the fields. In an embodiment, non-value carrying fields in a data unit are compressed based on a compression profile selected for the data unit. The compression profile indicates, for each master field, whether the compressed data unit includes a value for that field. Non-value carrying fields are omitted from the compressed data unit. The compression profile also permits compression of value-carrying fields using variable-width field lengths specified in the profile.

公开(公告)号：US09929970B1

公开(公告)日：2018-03-27

申请号：US14958830

申请日：2015-12-03

Applicant: Innovium, Inc.

Inventor： William Brad Matthews ,  Puneet Agarwal

IPC: G06F15/173 ,  H04L12/911 ,  H04L12/26

CPC classification number: H04L47/70 ,  H04L43/04 ,  H04L43/0817

Abstract: Described techniques enable resource accounting and tracking in high access rate systems using low cost memories. A first set of counters is maintained in relatively lower cost memory. The first counters generally indicate the amount of resources used for each object in a set of objects, but on a potentially delayed basis. A second set of counters of smaller size is stored in a relatively higher cost memory that supports high arrival and departure rates for accurate accounting. Each second counter indicates the amount of resources assigned (or unassigned) to an object since the object's first counter was last updated, and is incremented or decremented whenever this amount changes. A background process is configured to update individual first counters from the corresponding second counters on a recurring basis. The exact times at which a given first counter is updated may vary in accordance with a variety of approaches.

公开(公告)号：US09690507B2

公开(公告)日：2017-06-27

申请号：US15192882

申请日：2016-06-24

Applicant: Innovium, Inc.

Inventor： William Brad Matthews ,  Bruce H. Kwan ,  Mohammad K. Issa ,  Neil Barrett ,  Avinash Gyanendra Mani

IPC: G06F3/06 ,  G06F12/06

CPC classification number: G06F3/0619 ,  G06F3/0613 ,  G06F3/0629 ,  G06F3/0644 ,  G06F3/065 ,  G06F3/067 ,  G06F3/0673 ,  G06F5/06 ,  G06F7/08 ,  G06F12/0607 ,  G06F2205/064

Abstract: A memory system for a network device is described. The memory system includes a main memory configured to store one or more data elements. Further, the memory system includes a link memory that is configured to maintain one or more pointers to interconnect the one or more data elements stored in the main memory. The memory system also includes a free-entry manager that is configured to generate an available bank set including one or more locations in the link memory. In addition, the memory system includes a context manager that is configured to maintain metadata for a list of the one or more data elements.