Multiplex communications – Wide area network – Packet switching
Patent
1992-10-22
1997-07-15
Lall, Parshotam S.
Multiplex communications
Wide area network
Packet switching
39520001, 370241, G06F 1516
Patent
active
056491093
ABSTRACT:
A forwarding information management system for a bridge or router is disclosed, including a method and apparatus for maintaining forwarding entries within a forwarding table. The forwarding table is allocated into forwarding entries, and the forwarding entries organized into forwarding entry sets. 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. A forwarding entry adding process creates a new forwarding entry set including a new forwarding entry, selects a non-empty free queue for free space segments large enough to hold the new forwarding entry set, and writes the new forwarding entry set one of the free space segments. Also included in the system are a forwarding entry deleting process, a learning process providing input for the forwarding entry adding process, and an aging process providing input for the forwarding entry deleting process. In an example embodiment, a hash table is used to locate the forwarding entry sets in the forwarding table. In a preferred embodiment, forwarding entries within the forwarding entry sets are organized into balanced binary trees.
REFERENCES:
patent: 4074254 (1978-02-01), Belser et al.
patent: 4587610 (1986-05-01), Rodman
patent: 4627052 (1986-12-01), Hoare et al.
patent: 4677550 (1987-06-01), Ferguson
patent: 4680700 (1987-07-01), Hester
patent: 4695949 (1987-09-01), Thatte et al.
patent: 4715030 (1987-12-01), Koch et al.
patent: 4737953 (1988-04-01), Koch et al.
patent: 4780816 (1988-10-01), Connell
patent: 4922417 (1990-05-01), Churm et al.
patent: 4933937 (1990-06-01), Konishi
patent: 5027350 (1991-06-01), Marshall
patent: 5032987 (1991-07-01), Broder et al.
patent: 5095480 (1992-03-01), Fenner
patent: 5109336 (1992-04-01), Geunther et al.
patent: 5121495 (1992-06-01), Nemes
patent: 5136580 (1992-08-01), Videlock et al.
patent: 5197002 (1993-03-01), Spencer
patent: 5301273 (1994-04-01), Konishi
patent: 5303302 (1994-04-01), Burrows
patent: 5432907 (1995-07-01), Picazo, Jr. et al.
Concepts in data structures and software development by Schneider et al., West publishing company, pp. 134-135, 141-144.
The C programming language by Kernishan et al., Prentice Hall publication, pp. 185-189.
System Software by Beck, Addison-Wesley publishing company, pp. 339-340.
1983, Reingold, E.M. & Hansen, W.J., Data Structures, pp. 123-155 and pp. 246-270, Little, Brown Computer Systems Series.
Benson David
Griesmer Martin Edward
Krishnakumar Parayath Gopal
Dagg David A.
Digital Equipment Corporation
Fisher Arthur W.
Lall Parshotam S.
Maung Zarni
LandOfFree
Apparatus and method for maintaining forwarding information in a does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for maintaining forwarding information in a, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for maintaining forwarding information in a will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1498939