US Patent No. 10,740,006

SYSTEM AND METHOD FOR ENABLING HIGH READ RATES TO DATA ELEMENT LISTS


Patent No. 10,740,006
Issue Date August 11, 2020
Title System And Method For Enabling High Read Rates To Data Element Lists
Inventorship William Brad Matthews, San Jose, CA (US)
Bruce H. Kwan, Sunnyvale, CA (US)
Mohammad K. Issa, Los Altos, CA (US)
Neil Barrett, Palo Alto, CA (US)
Avinash Gyanendra Mani, San Jose, CA (US)
Assignee Innovium, Inc., San Jose, CA (US)

Claim of US Patent No. 10,740,006

1. A network device comprising:a main memory storing data elements from groups of data elements, each group of data elements including an ordered sequence of data elements;
a child link memory including a plurality of memory banks, wherein each memory bank stores one or more entries, each entry including: (i) an address of a main memory location that stores a data element identified by the entry, and (ii) an address of a child link memory bank that stores a next data element in a group of data elements that includes the data element identified by the entry;
a child manager including, for each memory bank of the plurality of memory banks in the child link memory, one or more head nodes and one or more tail nodes,
wherein each head node maintains (i) an address of a main memory location that stores a particular head data element that is a first data element in a respective memory bank for a group of data elements that includes the particular head data element, (ii) an address to a child link memory entry in the same memory bank, and (iii) a data element sequence number that represents a position of the particular head data element in an ordered sequence of data elements in the group of data elements that includes the particular head data element, and
wherein each tail node maintains an address to a main memory location that stores a particular tail data element that is a most recent data element in the respective memory bank for a group of data elements that includes the particular tail data element; and
a parent manager that includes one or more head entries for each memory bank in the plurality of memory banks in the child link memory,
wherein each head entry of the one or more head entries stores (i) a snapshot pointer for accessing metadata about a particular group of data elements in a snapshot memory; and (ii) a snapshot sequence number indicating another group of data elements to be accessed next,
wherein the metadata about a group of data elements includes (i) pointers to at least one of the one or more head nodes or the one or more tail nodes corresponding to the group of data elements in the child manager, and (ii) sequence numbers that correspond to data element sequence numbers for at least one of the one or more head nodes or the one or more tail nodes corresponding to the group of data elements, and
wherein the snapshot sequence number corresponds to an arrival order in which groups of data elements arrive at the network device, the particular group of data elements and the another group of data elements being successive groups of data elements to have arrived at the network device.