Multiplex communications – Wide area network – Packet switching
Patent
1993-07-06
1996-09-10
Kulik, Paul V.
Multiplex communications
Wide area network
Packet switching
370 8513, 364DIG2, 36494062, 364970, G06F 1202
Patent
active
055554059
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. The table packing process further ensures that the forwarding entry sets are efficiently moved such that they are accessible to the hardware frame forwarding apparatus, which is optimized to only read forwarding entry sets that do not cross memory page boundaries.
REFERENCES:
patent: 4695949 (1987-09-01), Thatte et al.
patent: 4797810 (1989-01-01), McEntee et al.
patent: 4933937 (1990-06-01), Konishi
patent: 5025367 (1991-06-01), Gurd et al.
patent: 5027350 (1991-06-01), Marshall
patent: 5088036 (1992-02-01), Ellis et al.
patent: 5109336 (1992-04-01), Guenther et al.
patent: 5121495 (1992-06-01), Nemes
patent: 5247634 (1993-09-01), Cline et al.
patent: 5339411 (1994-08-01), Heaton, Jr.
Tremblay, Jean-Paul et al., "An Introduction to Data Structures with Applications," 2d Ed, 1984 by McGraw-Hill, Inc., pp. 498-535.
Cohen, Jacques, "Garbage Collection of Linked Data Structures," Computing Surveys, vol. 13, No. 3, 1981, pp. 341-367.
Benson David
Griesmer Martin E.
Dagg David A.
Digital Equipment Corporation
Fisher Arthur
Johnston A. Sidney
Kulik Paul V.
LandOfFree
Method and apparatus for free space management in a forwarding d does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for free space management in a forwarding d, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for free space management in a forwarding d will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1328522