Patent ID: 7313138

Claim:
A router device for routing a packet based on its destination address, comprising: a routing table for storing routing entries including routing information relating the destination address of the packet to a routing path; a cache memory for storing some of the routing entries in the routing table together with mask-length information of the destination address as a cache entry; a first retrieval section for retrieving the cache entry which corresponds to the destination address of the packet by making reference to the cache memory based on the destination address; a second retrieval section for retrieving the routing entry which corresponds to the destination address by making reference to the routing table; a storage section for storing the routing entry retrieved by the second retrieval section together with the mask-length information of the destination address as the cache entry in the cache memory; and an output section for outputting a retrieval result sent from the first or second retrieval section, wherein the first retrieval section comprises, a take-out section for taking out the destination address of the input packet, an extraction section for extracting a mask length of a network address from the routing table, a creation section for creating an address by an AND operation between the destination address and a minimum mask length among the mask lengths, a search section for searching the cache memory for the cache entry by regarding the created address to be a virtual network address, a decision section for deciding whether the cache entry is a link entry comprising an entry group to which the cache entry relates, if the cache entry is searched, and a prompting section for prompting the extraction section to take out the mask length larger than the mask length extracted earlier, until the decision section decides which the cache entry once decided to be the link entry is not the link entry.