System And Method For Implementing Hierarchical Distributed-Linked Lists For Network Devices

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 parent distributed-linked list configured to store linked-list metadata. And, the memory system includes a child distributed-linked list configured to maintain list metadata to interconnect the one or more data elements stored in the main memory to generate at least a first snapshot, said linked-list metadata references the snapshot.

What is claimed is: 
     
         1 . A memory system for a network device comprising:
 a main memory configured to store one or more data elements;   a parent distributed-linked list configured to store linked-list metadata; and   a child distributed-linked list configured to maintain list metadata to interconnect said one or more data elements stored in said main memory to generate at least a first snapshot, said linked-list metadata references said snapshot.   
     
     
         2 . The memory system of  claim 1 , wherein said parent distributed-linked list includes a parent snapshot memory, said parent snapshot memory configured to store said linked-list metadata of said first snapshot. 
     
     
         3 . The memory system of  claim 2 , wherein said parent distributed-linked list further includes a parent link memory, said parent link memory configured to store linked-list metadata to interconnect said first snapshot with at least a second snapshot. 
     
     
         4 . The memory system of  claim 3 , wherein said parent distributed-linked list further includes a parent free-entry manager, said parent free-entry manager configured to generate a parent available bank set including one or more locations in said parent link memory. 
     
     
         5 . The memory system of  claim 4 , wherein said parent free-entry manager is configured to generate said parent available bank set including said one or more locations such that a write operation to said link memory does not conflict with a read operation. 
     
     
         6 . The memory system of  claim 4 , wherein said parent free-entry manager is configured to generate said parent available bank set including said one or more locations such that an access conflict will not occur. 
     
     
         7 . The memory system of  claim 3 , wherein said parent link memory is further configured to store linked-list metadata that includes a memory address for said second snapshot stored in said parent snapshot memory. 
     
     
         8 . The memory system of  claim 1 , wherein said child distributed linked list further includes a child link memory, said child link memory configured to store list metadata that includes one or more pointers to interconnect said one or more data elements in said main memory. 
     
     
         9 . The memory system of  claim 8 , wherein said child link memory is further configured to store said list metadata that includes a memory address for at least one of said one or more data elements stored in said main memory. 
     
     
         10 . The memory system of  claim 9 , wherein said child link memory is further configured to store said list metadata that includes a snapshot sequence identifier for at least one of said one or more data elements stored in said main memory. 
     
     
         11 . The memory system of  claim 1 , wherein said data element is a data packet. 
     
     
         12 . The memory system of  claim 1 , wherein said data element is a cell of a data packet. 
     
     
         13 . The memory system of  claim 1 , wherein a set of said one or more data elements form a sequence of data elements. 
     
     
         14 . A method for implementing a memory system in a network device comprising:
 storing one or more data elements;   maintaining list metadata to interconnect the one or more data elements to generate a data-element list; and   generating at least a first snapshot based on said list metadata.   
     
     
         15 . The method of  claim 14 , wherein storing said one or more data elements are in response to receiving said one or more data elements. 
     
     
         16 . The method of  claim 14  further comprising allocating one or more locations in a memory. 
     
     
         17 . The method of  claim 14  further comprising maintaining linked-list metadata to interconnect said first snapshot with at least a second snapshot to generate a snapshot list. 
     
     
         18 . The method of  claim 14 , further comprising determining a next data element of said data-element list based on said list metadata. 
     
     
         19 . The method of  claim 17 , further comprising determining a location in a memory of said second snapshot based on said linked-list metadata. 
     
     
         20 . An apparatus comprising:
 a means for storing one or more data elements;   a means for maintaining list metadata to interconnect the one or more data elements to generate a data-element list; and   a means for generating at least a first snapshot based on said list metadata.   
     
     
         21 . A non-transitory program storage device readable by a machine, embodying a program of instructions executable by the machine to perform data transfer, the method comprising:
 storing one or more data elements;   maintaining list metadata to interconnect the one or more data elements to generate a data-element list; and   generating at least a first snapshot based on said list metadata.