Patent ID: 6570866
Filing Date: 2003-05-27
Classification: H04L

Abstract:
A device for retrieving a longest routing match to a given address from a plurality of entries containing routing information in a router, the device comprising:a plurality of primary retrieving circuits each of which comprises a memory storing at least one first entry and a mask associated therewith, wherein each of the primary retrieving circuits retrieves a primary match entry which is a longest match to the given address and outputs a primary match mask associated with the primary match entry; a selector performing a logical OR operation for selecting a longest match mask from the primary match masks output by the primary retrieving circuits, the longest match mask having a longest non-masking bit length among the primary match masks; and at least one associative memory storing a plurality of second entries, each of which is formed by coupling a first entry with a corresponding mask together, wherein the associative memory compares a combination of the given address and the longest match mask to the plurality of second entries and outputs corresponding to a first entry included in a second entry accessed as the longest routing match.