US Patent No. 9,753,660

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


Patent No. 9,753,660
Issue Date September 05, 2017
Title System And Method For Implementing Hierarchical 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,753,660

1. A memory system for a network device comprising:
a main memory configured to store data elements;
write circuitry configured to:
write a first portion of a first data packet as first data elements to the main memory;
write a first child distributed-linked list to maintain list metadata that includes first data-element pointers to the main
memory to interconnect the first data elements stored in the main memory;

after writing the first portion of the first data packet and before writing a second portion of the first data packet to the
main memory:

write a first portion of a second data packet as second data elements to the main memory;
write a parent distributed linked list that includes a first snapshot that represents (i) a first child pointer to the first
child distributed-linked list and (ii) a first sequence identifier associated with the first snapshot; and

write a second child distributed-linked list that includes second data-element pointers to the main memory to interconnect
the second data elements stored in the main memory;

after writing the first portion of the second data packet to the main memory, write the second portion of the first data packet
as third data elements to the main memory;

update the parent distributed linked list to include a second snapshot that represents (i) a second child pointer to the second
child distributed-linked list and (ii) a second sequence identifier associated with the second snapshot;

write a third child distributed-linked list that includes third data-element pointers to the main memory to interconnect the
third data elements stored in the main memory; and

after writing the second portion of the first data packet to the main memory, update the parent distributed linked list to
include a third snapshot that represents (i) a third child pointer to the third child distributed-linked list and (ii) a third
sequence identifier associated with the third snapshot, wherein a value of the third sequence identifier is between values
of the first sequence identifier and the second sequence identifier; and

read circuitry configured to read the main memory to reconstruct the first data packet and the second data packet in sequence
using (i) snapshots included in the parent distributed linked list and (ii) data-element pointers included in the child distributed-linked
lists, wherein the reconstruction of the first data packet and the second data packet are read in an order according to the
values of the sequence identifiers associated with the snapshots.