Cache table management device for router and program recording medium thereof
First Claim
1. A cache table management device used in a router wherein the device comprising:
- 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.
1 Assignment
0 Petitions
Accused Products
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.
75 Citations
11 Claims
-
1. A cache table management device used in a router wherein the device comprising:
-
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 10)
-
-
9. A medium for recording programs implemented in a router, wherein the program comprising the steps of:
-
(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.
-
-
11. A cache table management device used in a router comprising:
-
a forwarding table for being used to perform longest prefix match searches of all entries, and a cache table for being used to perform longest prefix match searches of a portion of the total entries, wherein when an entry in the forwarding table is input to the cache table, an entry group is selected along with all child entries of the input entry, and when an entry is extracted from the cache table, an entry group is selected along with all parent entries of the extracted entry.
-
Specification