Back to results
US 6,295,576 B1Granted
Associative memory having a mask function for use in a network router
AssigneeNEC Corporation
InventorsNaoyuki Ogura, Tutomu Murase
Life of this patent
Estimating the term…
Loading patent…
Loading patent…
AssigneeNEC Corporation
InventorsNaoyuki Ogura, Tutomu Murase
Estimating the term…
When one or more storage data are coincident with single search data (105), an associative memory with a shortest mask producing function carries out logical multiplication for all of mask information corresponding to the coincident storage data with a mask valid state as true. The result of logical multiplication is used as shortest mask information. In a primary searching operation, the associative memory with a shortest mask producing function is supplied with the search data (105) to provide the shortest mask information on shortest mask lines. Then, as a secondary searching operation, the shortest mask information thus extracted is used as the search data and supplied to the associative memory with a shortest mask producing function. Among the coincident storage data, only a mask match line connected to a particular word having mask information coincident with the shortest mask information is selected as the secondary search result. The associative memory is used in a network router, to calculate an optimum memory address signal (303) by encoding the selected mask match line. In response to the memory address signal (303), a memory data signal (305) enabling shortest network connection is produced as a transfer network address (313). The transfer network address (313) is combined with a data area (312) and a destination network address (311) contained in input transfer data (308) to produce output transfer data (309).
An associative memory including first means for storing a plurality of associative memory words, each of which is a pair of a storage datum and a mask datum, said associative memory comprising second means for carrying out, when at least two of said associative memory words are selected as selected words in a primary searching operation with respect to an external search datum, a logical operation of the mask data of said selected words that determines a shortest mask by which a least number of bits of a respective datum are excluded from a search object in said primary searching operation.
A continuation of first and second associative memories, said first associative memory storing a plurality of first words, each of which is a pair of a storage datum and a mask datum, said first associative memory comprising means for carrying out, when at least two of said first words are selected as selected words as a result of a searching operation for an external search datum, a logical operation of the mask data of said selected words that determines a shortest mask by which a least number of bits of a respective datum are excluded from a search object in said searching operation, said second associative memory storing a plurality of second words, each of said second words comprising a plurality of bits twice in number than each first word, each of said second words comprising a first bit group storing said storage datum and said mask datum stored in each of said first words of said first associative memory at corresponding addresses, and a second bit group storing the mask datum stored in said first bit group of the same second word, the result of said logical operation being supplied in the searching operation to said second bit group of said second associative memory while said search datum is supplied to said first bit group of said second associative memory, selection being made, among said storage data in said second words of said second associative memory, of a particular one of said second words storing said storage datum and said mask datum coincident in bit information with said search datum and the result of said logical operation, respectively.
An associative memory which stores mask information for every single word of storage information to indicate a valid state or an invalid state representative of whether or not every single bit or every plural bits of said storage information should be excluded from a search object, said associative memory comprising first searching means for selecting, among all of those mask information corresponding to one or more storage information coincident with said search data, a particular mask information as a shortest mask information by which a least number of bits of said storage information are excluded from said search object and for delivering said shortest mask information to a shortest mask signal line, and second searching means for producing an identification signal for identifying, among said one or more storage information coincident with said search data, a particular storage information corresponding to said particular mask information coincident with said shortest mask signal line.
A router having an associative memory which stores storage information and mask information combined with every single word of said storage information to indicate by a valid state and an invalid state whether or not a single bit or plural bits of said storage information are to be excluded from a search object and which stores routing information, said router comprising:
A router having a routing information table which stores a plurality of routing information and mask information combined with every single word of said routing information to indicate by a valid state and an invalid state whether or not a single bit or plural bits are to be excluded from a search object, said router comprising:
Dependencies are inferred from the claim text.