Loading patent…
AssigneeCisco Technology, Inc.
InventorsAbhijit Patra, Rina Panigrahy, Samar Sharma
Estimating the term…
Techniques for efficient memory management that enable rapid longest prefix match lookups in memory. In general, the present invention is efficacious wherever maintenance of a good distribution of holes in a sorted list is required. This technique relies on a proactive hole management methodology to preserve a good distribution of holes in each memory region in such a way that one does not have to search for holes in order to insert or store a new entry into the list. In particular, all holes in a given region are kept in one or more contiguous sub-region. Keeping the holes contiguous requires a hole move every time there is a delete operation. The amortized cost of these operations is justified by the resulting simplification in later insert (store) and delete operations. For example, during an insert the new entry is placed at the end of the contiguous sub-region of used entries in the region. During a delete, when a hole is created in the middle of a contiguous sub-region of used entries, the last used entry is moved into the hole, thus keeping the holes contiguous. Such an organization of holes and movement of used entries within a region is permissible within the longest prefix match type of lookup table, because all entries within a region, by definition, have an IP prefix of equal length.
A method of memory management comprising the steps of:
A computer system for memory management, comprising computer instructions for:
A computer system comprising a processor, a memory, and a network interface, said processor configured to perform the steps of:
A computer-readable storage medium, comprising computer instructions for:
A computer data signal embodied in a carrier wave, comprising computer instructions for:
Dependencies are inferred from the claim text.