Apparatus and method for maintaining forwarding information in a bridge or router using multiple free queues having associated free space sizes
July 15, 2014. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.Patent ReferencesXY Addressable and updateable compressed video refresh buffer for digital TV display Address translation systems for high speed computer memories Interconnection of communications networks Method of compacting and searching a data index Virtual memory address translation mechanism with combined hash address table and inverted page table Method for efficient support for reference counting Local area network bridge Local area network bridge Key-to-address transformations Method and apparatus for data hashing using selection from a table of random numbers in combination with folding and bit manipulation of the selected random numbers InventorsAssigneeApplicationNo. 965121 filed on 10/22/1992US Classes:709/242, Routing data updating370/241, DIAGNOSTIC TESTING (OTHER THAN SYNCHRONIZATION)370/401Bridge or gateway between networksExaminersPrimary: Lall, Parshotam S.Assistant: Maung, Zarni Attorney, Agent or FirmInternational ClassG06F 015/16AbstractA 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.Other References
| |
