Method and apparatus for free space management in a forwarding database having forwarding entry sets and multiple free space segment queues
US5555405A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jul 6, 1993 |
| Grant date | Sep 10, 1996 |
| Priority date | — |
| Expiry date | Jul 6, 2013 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F12/023
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A forwarding information management system for a bridge or router is disclosed, including a method and apparatus for merging free space segments in a forwarding table. The forwarding table is allocated into forwarding entry sets and free space queues. Each forwarding entry set must be within a single contiguous block of the forwarding table memory. A set of free queues is used to manage the free space segments in the forwarding table that are not allocated into forwarding entries. Each free queue maintains pointers to free space segments of a particular size. The forwarding table becomes fragmented as forwarding entries are added. A table packing process is triggered by a predetermined trigger to merge small areas of free space into large areas of free space, making consecutive forwarding entry sets contiguous in order to combine small areas of free space into larger ones. The table packing process moves the forwarding entry sets in atomic operations to ensure that forwarding entry sets remain valid during the moves, thus allowing forwarding decisions to be made based on forwarding information within the forwarding entry set being moved while the forwarding entry set is being moved…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.