Associative memory apparatus and routing apparatus
AssigneeFujitsu Limited
InventorsYuichi Uzawa, Yasuhiro Ooba
Life of this patent
Estimating the term…
Abstract
An associative memory apparatus has such a structure as to reduce a load of an updating work and readily cope with an increase of the capacity. The associative memory apparatus outputs longest prefix match in only one searching operation, thereby shortening a processing time for the searching process. The apparatus comprises entry units, each of which includes a logical operating means outputting information about a bit length not masked in entry data when the entry data stored in its own entry unit coincides with bit data that is a key, and a search result outputting means outputting a search match information with respect to the search key only when the entry data stored in its own entry unit is entry data having the longest bit length not masked.
Claims20
An associative memory apparatus comprising:
- a plurality of entry units respectively storing entry data different from one another having bit data to be searched and mask identifying data for masking a necessary bit length in said bit data, and matching each of said entry data with said bit data that is a search key;
- a matching-masking state outputting means inputted information reflecting a result of said matching in units of the same bit digit in each of said entry unit and a mask identifying bit at said bit digit to output reflected result information mutually reflected among said entry units at each bit digit;
- each of said entry units comprising:
- a logical operating means for outputting information about a bit length not masked of said entry data by a logical operation using said reflected result information from said matching-masking state outputting means when said entry data stored in its own entry unit matches with said bit data that is said key as a result of said matching;
- and
- a search result outputting means for outputting search match information about said search key on the basis of an output signal from said logical operating means only when said entry data stored in its own entry unit is entry data having the longest bit length not masked among all entry data coinciding with said bit data that is said key in said matching.
A routing apparatus comprising an associative memory storing a destination address correspondingly to an output destination route, and an output route determining unit analyzing a destination address attached to an inputted packet, and performing a routing process such that said packet is transferred to an output destination route obtained by referring to said associative memory, said routing apparatus comprising:
- said associative memory cell comprising:
- a plurality of entry units for respectively storing entry data different from one another having bit data configuring a destination address to be searched and mask identifying data for masking a necessary bit length in said bit data, and matching said entry data with said bit data configuring the destination address that is a search key;
- a matching-masking state outputting means inputted information reflecting a result of said matching in units of the same bit digit in each of said entry units and a mask identifying bit at said bit digit to output reflected result information mutually reflected among said entry units at each bit digit;
- each of said entry units comprising:
- a logical operating means for outputting information about a bit length not masked of said entry data by a logical operation using said reflected result information from said matching-masking state outputting means when said entry data stored in its own entry unit matches with said bit data that is a key as a result of said matching;
- and
- a search result outputting means for outputting search match information about said search key on the basis of an output signal from said logical operating means only when the entry data stored in its own entry unit is entry data having the longest bit length not masked among all entry data coincides with said bit data that is a key in said matching.
Dependencies are inferred from the claim text.