Techniques for efficient memory management for longest prefix match problems
US6725326B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 15, 2000 |
| Grant date | Apr 20, 2004 |
| Priority date | — |
| Expiry date | Jul 10, 2022 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F12/023
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
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 prefi…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.