US5649109A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for maintaining forwarding information in a bridge or router using multiple free queues having associated free space sizes
Assignee: Enterasys Networks Inc
•
Filing: 1992-10-22
•
Granted: 1997-07-15
•
Expires: 2012-10-22
Abstract
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.
Inventors
- 👤 Martin Edward Griesmer
- 👤 Parayath Gopal Krishnakumar
- 👤 David Benson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 09:12
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/28; H04L12/46; H04L12/4604; H04L12/462; H04L12/4625; H04L45/00; H04L45/54; H04L45/74; H04L45/745
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
294 words
In apparatus for maintaining frame forwarding information in a bridge or a router, comprising: a forwarding table having zero or more forwarding entry sets of different sizes, and zero or more free space segments, each said free space segment having a size; a hash table having a plurality of hash table entries, each one of said plurality of hash table entries pointing to one of said one or more forwarding entry sets of different sizes, each one of said plurality of hash table entries containing the size of said one of said one or more forwarding entry sets; a plurality of free queues, each one of said plurality of free queues having an associated free space segment size, and zero or more queue elements indicating those of said free space segments having said size equal to said associated free space segment size; and a forwarding entry adding process, responsive to an input, said input containing an address and forwarding information, for determining a new forwarding entry set size, said new forwarding entry set size equal to a size of a forwarding entry plus a size contained in one of said plurality of hash table entries, said one of said plurality of hash table entries indexed by a value of a hash index field of an output of a hash function applied to said address contained in said input, and for selecting a non-empty free queue having associated free space segment size greater than or equal to said new forwarding entry get size, and for writing a new forwarding entry set to one of said free space segments indicated by a queue element from said non-empty free queue, said new forwarding entry set having a forwarding entry containing said forwarding information contained in said input.
Claim 2
Dependent Claim
294 words
In apparatus for maintaining frame forwarding information in a bridge or a router, comprising: a forwarding table having zero or more forwarding entry sets of different sizes, and zero or more free space segments, each said free space segment having a size; a hash table having a plurality of hash table entries, each one of said plurality of hash table entries pointing to one of said one or more forwarding entry sets of different sizes, each one of said plurality of hash table entries containing the size of said one of said one or more forwarding entry sets; a plurality of free queues, each one of said plurality of free queues having an associated free space segment size, and zero or more queue elements indicating those of said free space segments having said size equal to said associated free space segment size; and a forwarding entry adding process, responsive to an input, said input containing an address and forwarding information, for determining a new forwarding entry set size, said new forwarding entry set size equal to a size of a forwarding entry plus a size contained in one of said plurality of hash table entries, said one of said plurality of hash table entries indexed by a value of a hash index field of an output of a hash function applied to said address contained in said input, and for selecting a non-empty free queue having associated free space segment size greater than or equal to said new forwarding entry get size, and for writing a new forwarding entry set to one of said free space segments indicated by a queue element from said non-empty free queue, said new forwarding entry set having a forwarding entry containing said forwarding information contained in said input.
Claim 3
Dependent Claim
62 words
The apparatus of claim 1 wherein an index into said hash table for a given hash table entry is equal to a hash index field of the output of a hash function applied to a given address, said given hash table entry pointing to a forwarding entry set having a forwarding entry containing forwarding information for received frames containing said given address.
Claim 4
Dependent Claim
49 words
The apparatus of claim 2 one of said forwarding entries in said forwarding entry set having a field equal to a remainder field of the hash output of said hash function applied to said given address, and a second field containing forwarding information for received frames containing said address.
Claim 5
Dependent Claim
66 words
The apparatus of claim 3, further comprising: a plurality of communications segments; frame receiving means, responsive to said communications segments, for receiving a frame from one of said plurality of communications segments; frame forwarding means, responsive to said frame receiving means, said hash table and said forwarding table, for forwarding said frame based on the contents of said frame and forwarding information in said forwarding table.
Claim 6
Dependent Claim
43 words
The apparatus of claim 4 further comprising a mutual exclusion circuit, coupled with said frame forwarding means, said microprocessor, and said memory, for preventing said frame forwarding means from reading said hash table during a write operation by said forwarding entry adding process.
Claim 7
Dependent Claim
50 words
The apparatus of claim 5 further comprising a learning means, responsive to said frame receiving means receiving a frame, for generating said input when no forwarding entry exists in said forwarding entry table having forwarding information for a station address contained in a source address field of said received frame.
Claim 8
Dependent Claim
59 words
The apparatus of claim 6 wherein said address contained in said input generated by said learning means is equal to a station address contained in a source address field of said received frame, and the forwarding information indicates to forward frames with a destination address equal to said station address to the LAN segment said frame is received from.
Claim 9
Dependent Claim
124 words
The apparatus of claim 5 further comprising a forwarding entry deleting means, responsive to a second input, said second input containing a station address, for determining a new forwarding entry set size equal to the size of the existing forwarding entry set for station addresses related to said station address contained in said second input minus the size of one forwarding entry, selecting a non-empty free queue having associated free space segment size greater than or equal to said new forwarding entry set size, and copying said existing forwarding entry set, without the forwarding entry having forwarding information for said station address contained in said second input, to one of said free space segments indicated by a queue element from said non-empty free queue.
Claim 10
Dependent Claim
61 words
The apparatus as in claim 8, further comprising: a timer; an aging process, responsive to said frame receiving means, said timer and said forwarding table for generating said second input when no frame is received containing destination or source address field contents equal to a given station address, said address contained in said second input equal to said given station address.
Claim 11
Independent Claim
246 words
A method for adding forwarding information to a forwarding table, comprising the steps of: receiving an input, said input containing a station address and forwarding information; determining a size of an existing forwarding entry set having forwarding entries for station addresses related to said station address contained in said input, said size of said existing forwarding entry set contained in a hash table entry within a hash table, said hash table entry within said hash table indexed by a value of a hash index field of an output of a hash function applied to said station address contained in said input; determining a new forwarding entry set size equal to said size of said existing forwarding entry set having forwarding entries for station addresses related to said station address contained in said input plus the size of one forwarding entry; selecting a non-empty free queue from a plurality of free queues, said non-empty free queue having one or more elements pointing to free space segments in said forwarding table, said free space segments being of size equal to or greater than said new forwarding entry set size; and writing a new forwarding entry set to one of said free space segments pointed to by one of said one or more queue elements in said non-empty free queue, said new forwarding entry set containing the forwarding entries from said existing forwarding entry set, as well as a forwarding entry containing said forwarding information contained in said input.
Claim 12
Independent Claim
246 words
A method for adding forwarding information to a forwarding table, comprising the steps of: receiving an input, said input containing a station address and forwarding information; determining a size of an existing forwarding entry set having forwarding entries for station addresses related to said station address contained in said input, said size of said existing forwarding entry set contained in a hash table entry within a hash table, said hash table entry within said hash table indexed by a value of a hash index field of an output of a hash function applied to said station address contained in said input; determining a new forwarding entry set size equal to said size of said existing forwarding entry set having forwarding entries for station addresses related to said station address contained in said input plus the size of one forwarding entry; selecting a non-empty free queue from a plurality of free queues, said non-empty free queue having one or more elements pointing to free space segments in said forwarding table, said free space segments being of size equal to or greater than said new forwarding entry set size; and writing a new forwarding entry set to one of said free space segments pointed to by one of said one or more queue elements in said non-empty free queue, said new forwarding entry set containing the forwarding entries from said existing forwarding entry set, as well as a forwarding entry containing said forwarding information contained in said input.
Claim 13
Independent Claim
200 words
A method for deleting forwarding information from a forwarding table, comprising the steps of: receiving an input, said input containing a station address; determining a size of an existing forwarding entry set having forwarding entries for station addresses related to said station address contained in said input, said size of said existing forwarding entry set contained in a hash table entry within a hash table, said hash table entry within said hash table having indexed by a value of a hash index field of an output of a hash function applied to said station address contained in said input; determining a new forwarding entry set size equal to said size of said existing forwarding entry set having forwarding entries for station addresses related to said station address contained in said input minus the size of one forwarding entry; selecting a non-empty free queue having associated free space segment size greater than or equal to said new forwarding entry set size; and copying said existing forwarding entry set, without the forwarding entry having forwarding information for said station address contained in said second input, to one of said free space segments indicated by a queue element from said non-empty free queue.
Claim 14
Independent Claim
200 words
A method for deleting forwarding information from a forwarding table, comprising the steps of: receiving an input, said input containing a station address; determining a size of an existing forwarding entry set having forwarding entries for station addresses related to said station address contained in said input, said size of said existing forwarding entry set contained in a hash table entry within a hash table, said hash table entry within said hash table having indexed by a value of a hash index field of an output of a hash function applied to said station address contained in said input; determining a new forwarding entry set size equal to said size of said existing forwarding entry set having forwarding entries for station addresses related to said station address contained in said input minus the size of one forwarding entry; selecting a non-empty free queue having associated free space segment size greater than or equal to said new forwarding entry set size; and copying said existing forwarding entry set, without the forwarding entry having forwarding information for said station address contained in said second input, to one of said free space segments indicated by a queue element from said non-empty free queue.
References Cited (Backward Citations)
US4074254A
Cited
US4677550A
Cited
US4680700A
Cited
US4587610A
Cited
US4627052A
Cited
US4695949A
Cited
US4780816A
Cited
US4715030A
Cited
US4737953A
Cited
US4922417A
Cited
US4933937A
Cited
US5121495A
Cited
US5032987A
Cited
US5027350A
Cited
US5109336A
Cited
US5095480A
Cited
US5197002A
Cited
US5136580A
Cited
US5301273A
Cited
US5432907A
Cited
US5303302A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-07-14 | 2001-01-13 | 2001-07-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-07-14 | 2005-01-13 | 2005-07-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-07-14 | 2009-01-13 | 2009-07-15 | $7700.00 | Window Closed / Lapsed |