Cache table management device for router and program recording medium thereof

• US 6,993,031 B2
• Filed: 04/09/2001
• Issued: 01/31/2006
• Est. Priority Date: 04/07/2000
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Murase, Tutomu
• Primary Examiner(s): Yao, Kwang Bin
• Application Number:
  US09/828,160
• Publication Number:
  US 20010028651A1
• Time in Patent Office: 1,758 Days
• Field of Search: 370/389, 370/392, 370/395.2, 370/395.31, 370/395.32, 370/395.42, 370/428, 370/429
• US Class Current: 370/395.32
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

Abstract

A cache table management device for raising the cache hit probability for entries inserted in groups between a forwarding table 103 and cache 102. A forwarding table 103 stores the priority level of entries inserted and extracted in a cache 102. A packet processing circuit 101 extracts the destination address from the received packet, searches the packet using the destination address, and searches the forwarding table if no hits occur. The hit database 104 stores the contents of the forwarding table for all forwarding table entries, as well as rating values for the cache usage status. An entry selection device 105 refers to the hit database when an entry must be added or deleted between the forwarding table and the cache, and selects the corresponding entry group. That determination is made utilizing typical values for attributes of the priority level such as the average bit rate of each entry group.

Claims

1. 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.

2. A cache table management device used in a router according to claim 1, wherein the cache table is divided into a plurality of zones, and the interchanging, deletion or movement of entry groups is performed in the respective zones.

3. A cache table management device used in a router according to claim 1, wherein the values for evaluating the entry usage status are the hit count and the hit time.

4. A cache table management device used in a router according to claim 1, wherein the typical values are the maximum value among the threshold value and zone, the average value among the hit counts, and the most recent value among the hit times.

5. A cache table management device used in a router according to claim 4, wherein the priority level within entries of the forwarding table is rewritten according to the policy server.

6. A cache table management device used in a router according to claim 1, wherein said attributor circuit generates a random number from 0 to 1, divides the random number into two parts, and allots each part of a hit count and hit time, and has the ranking of the allotted attribute the final ranking.

7. A cache table management device used in a router according to claim 1, wherein the cache table management device is further comprising a means for setting the entry priority level according to information acquired from the received packet.

8. A medium for recording programs implemented in a router, wherein the program comprising:

(a) implementing on a recording device, a forwarding table containing a plurality of entries each of which includes information showing the collection of addresses comprised of prefix bits and prefix lengths, information showing the output paths of packets for the collection of addresses and priority level information, said entries being searched by longest prefix method;

(b) implementing the cache table on a recording device, when an entry of said cache table is interchanged, the entry group comprised of the entry to be added and the child entry of the applicable entry is written from the forwarding table, or when an entry is to be deleted or moved, the entry group comprised of the entry for interchanging and the parent entry of the applicable entry is deleted or moved;

(c) implementing the hit database of all entries of said forwarding table on a recording device wherein said hit database or said hit information of said all entries and are update when a hit occurred in the forwarding table or cache table;

(d) implementing the packet processing circuit in said router extracting the destination network address from the applicable packet header of the input packet, searching the cache table or forwarding table using the destination network address as a key, and for sending the packet on the acquired output path;

(e) implementing entry selection circuit on the router for selecting the entry group to be interchanged by taking into account the priority level information and the information from the hit database when interchanging an entry group;

wherein the entry selection circuit is implemented on the router in an operation comprising;

(a) implementing a function of an entry group typical value circuit which receives entry group information from the hit record database, and determines typical values of entry usage ratings, and typical and/or threshold values for zones constituting entry priority levels;

(b) implementing a function of a comparator circuit having a table which has entry groups linked with entry group typical values for entry groups present in the cache table, comparing the typical values of each entry group on the table with typical values sent from the entry group typical value circuit, and sending the priority rankings of the entry groups present in the cache table;

(c) implementing a function of an arbitration circuit to determine the final interchange ranking of the entry groups based on the priority rankings sent from the comparator circuits; and

(d) implementing a function of an entry determiner circuit for monitoring the available space in the cache table and for deleting, in case of no available space, the cache table entries of low ranking entry groups determined by the arbitrator circuit and sending information to the comparator circuit on the deleted entry groups for deletion from the cache table.