Patent ID: 6993031

Claim:
A cache table management device used in a router wherein the device comprises: a forwarding table having a plurality of entries, each of said entries having a set of information showing a collection of addresses comprised of prefix bits and prefix lengths, information showing packet output paths for the address collection, the priority level information, and said forwarding table being searched by a longest prefix match search; a cache table for, when entries are substituted, being written the entry group containing the entry to be substituted and the applicable child of the substituted entry from the forwarding table, and for being deleted on moved, when deleting or moving entries, the entry group containing the applicable entry and the applicable parent of the deleted on moved entry; a hit record database containing hit information added to the contents of the applicable entry among all entries of the forwarding table, contents of said hit record database being updated when a hit occurs in the forwarding table or the cache table; a packet processing circuit to extract the destination network address from an input packet, to search the forwarding table or the cache table using the destination network address as a key, and to transmit the packet on the acquired output paths; and an entry selection circuit to select entry groups to be interchanged when needed while taking the information from the bit data base and priority level information into account; wherein the router entry selection device comprises: an entry group typical value circuit to receive entry group information from the hit database, and determining from the entry group information a typical value for evaluating entry usage status, and a typical zone value and/or typical threshold value in the entry priority level; a comparator circuit, having a table linking the entry groups already present in the cache table 102 and the typical values for those entry groups, for comparing the typical values of the entry group and the typical values sent from the entry group typical value circuit, and for sending the priority rankings of the entry groups present in the cache table; an arbitrator circuit to determine the final interchanging ranking of the entry group based on the priority rankings sent from the comparator circuit; and an entry determiner circuit to monitor available space in the cache table and to delete cache table entries from low ranking entries determined by the arbitrator circuit and to send information to the comparator circuit on the deleted entry groups for deletion from the cache table when no empty space is available after checking for available space to add an entry group.