Associative memory having a mask function for use in a network router

An associative memory which stores a mask information therein corresponding to each single or each plural words of storage data, the mask information enabling to set in accordance with a valid state or an invalid state whether or not each single bit or each plural bits of the storage data should be excluded from a search object;

• said associative memory comprising a first associative sub-memory and a second associative sub-memory, said first associative sub-memory comprising:
• i) a first circuit means for conducting a primary search operation for each single word of the storage data so as to exclude a single or plural bits of the storage data from the search object with use of an external search data input to the memory when the mask information corresponding to each single word is in a valid state;
• ii) a second circuit means for selecting a single or plural words as a candidate data;
• iii) a third circuit means for conducting a logical AND operation to obtain a matched mask logical AND information between each mask information corresponding to the selected candidate data, with assuming the valid state of the mask information as true;
• and
• iv) a fourth circuit means for conducting a first logical operation between the matched mask logical AND information and the search data;
• said second associative sub-memory storing the same storage data in each word corresponding to addresses of each word of said first associative sub-memory;
• wherein the primary search operation is performed in a manner that the external search data is input to said first associative sub-memory to obtain a result of logical operation and a secondary search operation is performed in a manner that the result of logical operation is input to said second associative sub-memory as a search data to select a word in which a bit information of the storage data matches with the result of logical operation.

An associative memory which stores a mask information therein corresponding to each single or each plural words of storage data, the mask information enabling to set in accordance with a valid state or an invalid state whether or not each single bit or each plural bits of the storage data should be excluded from a search object;

• said associative memory comprising a first searching means and a second searching means, said first searching means comprising:
• i) a first circuit means for conducting a primary search operation for each single word of the storage data so as to exclude a single or plural bits of the storage data from the search object with use of an external search data input to the memory when the mask information corresponding to each single word is in a valid state;
• ii) a second circuit means for generating an intermediate information in a manner to select a mask information having a minimum bit number in a storage information set to be excluded from the search object among all the mask information which corresponds to the storage data matching with the search data when one or more storage data match with the search data;
• and
• iii) a third circuit means for outputting to an arithmetic result output line the result of a first logical operation between the intermediate information and a search information;
• said second searching means outputting to the arithmetic result output line a signal to identify the matched storage data.

A router for storing routing information therein having an associative memory which stores a mask information therein corresponding to each single or each plural words of storage data, the mask information enabling to set in accordance with a valid state or an invalid state whether or not each single bit or each plural bits of the storage data should be excluded from a search object;

• said router comprising:
• i) a first searching means for outputting to an arithmetic result output line the result of a first logical operation between a matched mask logical AND information and a search data in a manner that a primary search operation for excluding a single bit or plural bits for each word of the storage data corresponding to a mask information from the search object when the mask information is valid is performed wherein a destination network address of input transfer data is selected as the search data, and the matched mask logical AND information is generated in such a manner to conduct a logical AND operation between each mask information corresponding to the storage data which matches with the destination network address with assuming the valid state of the mask information as true;
• ii) a second searching means for outputting a match signal to identify the routing information having the storage data matching with information of the arithmetic result output line;
• and
• iii) means for determining a transfer address of the input transfer data in response to the match signal.

A router for storing a plurality of routing information in a routing information table which stores a mask information therein corresponding to each single or each plural words of storage data, the mask information enabling to set in accordance with a valid state or an invalid state whether or not each single bit or each plural bits of the storage data should be excluded from a search object;

• said router comprising:
• i) means for generating an arithmetic result output signal as a result of a first logical operation between a matched mask logical AND information and a search data in a manner that a primary search operation for excluding a single bit or plural bits for each word of the storage data corresponding to a mask information from the search object when the mask information is valid is performed wherein a destination network address of input transfer data is selected as the search data, and the matched mask logical AND information is generated in such a manner to conduct a logical AND operation between each mask information corresponding to the storage data which matches with the destination network address with assuming the valid state of the mask information as true;
• ii) means for outputting a match signal to identify the routing information having the storage data matching with information of the arithmetic result output line;
• and
• iii) means for determining a transfer address of the input transfer data in response to the match signal.