US Patent No. 9,767,014

SYSTEM AND METHOD FOR IMPLEMENTING DISTRIBUTED-LINKED LISTS FOR NETWORK DEVICES


Patent No. 9,767,014
Issue Date September 19, 2017
Title System And Method For Implementing Distributed-linked Lists For Network Devices
Inventorship Avinash Gyanendra Mani, San Jose, CA (US)
Mohammad K. Issa, Los Altos, CA (US)
Neil Barrett, Palo Alto, CA (US)
Assignee Innovium, Inc., San Jose, CA (US)

Claim of US Patent No. 9,767,014

1. A memory system for a network device comprising:
a main memory configured to store data elements;
a link memory including a plurality of memory banks, each of the memory banks configured to store a plurality of nodes that
each stores (i) a respective data-element pointer to the main memory for accessing a respective data element referenced by
the respective data-element pointer, and (ii) a respective sequence identifier for determining an order for accessing the
plurality of memory banks, wherein the data-element pointers in the plurality of memory banks point to the data elements stored
in the main memory to form a list of data elements that represent a data packet;

a free-entry manager configured to generate an available bank set including one or more locations in the link memory; and
a context manager configured to maintain the metadata for forming the list of data elements, the context manager including
a plurality of head entries that correspond to the plurality of memory banks,

wherein each head entry of the plurality of head entries is configured to store (i) a respective link-memory pointer pointing
to a respective node in the respective memory bank of the link memory and (ii) the respective sequence identifier for the
respective node,

circuitry configured to use the head entries in the context manager to:
determine, based on the respective sequence identifier stored in each head entry of the plurality of head entries, the order
for accessing the plurality of memory banks; and

access the plurality of memory banks based on the determined order to reconstruct the data packet.