Maskable content addressable memory

• US 7,746,865 B2
• Filed: 12/07/2004
• Issued: 06/29/2010
• Est. Priority Date: 12/07/2004
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Shankara, Udaya
• Primary Examiner(s): Trost, IV; William
• Assistant Examiner(s): CHRISS, ANDREW W
• Application Number:
  US11/006,845
• Publication Number:
  US 20060149853A1
• Time in Patent Office: 2,030 Days
• Field of Search: 370/392
• US Class Current: 370/393
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

Abstract

A maskable content addressable memory may store one or more address prefixes. A port on which the packet may be sent is determined by comparing the destination address of a received packet by masking the address prefixes and the destination address.

Claims

1. A method in a router comprising:

generating a first address prefix and a second address prefix by masking the first address prefix with a first mask and the second address prefix with a second mask in response to receiving a first new address with a first port identifier and a second new address with a second port identifier,

discarding the first address prefix and the second address prefix if the first address prefix and the second address prefix are absorbable by a third address prefix, wherein the third address prefix is stored in a content addressable memory prior to receiving the first new address and the second new address,

storing the first port identifier and the second port identifier with the third address prefix in addition to a third port identifier stored with the third address prefix prior to receiving the first new address and the second new address,

extracting a destination address from a received data unit,

generating a first masked destination address by masking the destination address using a third mask,

sending the data unit to a third port identified by the third port identifier if the first masked destination address matches with at least a first portion of the third address prefix, wherein the length of the first portion is at least greater than a length of a second mask and less than the length of the third mask.

2. The method of claim 1 comprises,

generating a second masked destination address by masking the destination address using a second mask if the first masked destination address does not match with at least the first portion of the third address prefix, and

sending the data unit to a second port identified by the second port identifier if the second masked destination address matches with at least a second portion the third address prefix, wherein the length of the second portion of the third address prefix is at least greater than a length of a first mask and less than the length of the third and the second mask.

3. The method of claim 1 comprises,

generating a third masked destination address by masking the destination address using a first mask if the second masked destination address does not match with at least the second portion of the third address prefix, and

sending the data unit to a first port identified by the first port identifier if the third masked destination address matches with a third portion of the third address prefix, wherein the length of the third portion is equal to the length of the first mask.

4. The method of claim 1 further comprises,

receiving a fourth new address and a fourth port identifier,

determining if the fourth new address is absorbable by at least one of a plurality of address prefixes stored in the content addressable memory, and

storing a fourth address prefix and a fourth port identifier in the content addressable memory, wherein the fourth address prefix represents the fourth new address.

5. The method of claim 4, wherein the first address prefix is the longest matching address prefix.

6. The method of claim 4, wherein the plurality of address prefixes are stored in a sorted order starting from the longest matching address prefix.

7. The method of claim 6 comprises storing the first address prefix in the first address location within the content addressable memory.

8. The method of claim 1, wherein the third address prefix represents the first address prefix and the second address prefix by storing the first port identifier and the second port identifier along with the third address prefix.

9. The method of claim 1 further comprises

generating a fifth address prefix and a sixth address prefix by padding don'"'"'t care bits to the fourth address prefix until the length of the fifth address prefix and the sixth address prefix equals a mask length that is closest to the length of the fourth address prefix,

comparing the fifth address prefix and the sixth address prefix with the plurality of address prefixes,

discarding the fifth address prefix if the fifth address prefix matches with at least a portion of one of the plurality of address prefixes, and

storing the sixth address prefix if the sixth address prefix does not match with any of the plurality of address prefixes.

10. An apparatus comprising:

a plurality of ports comprising a first, second, and a third port

a controller coupled to the plurality of ports, wherein the controller is to extract a destination address from a data unit received over the first port, and

a maskable content addressable memory coupled to the controller, wherein the maskable content addressable memory further comprises a maskable content addressable memory (MCAM) logic and a memory, wherein the MCAM logic is to,

generate a first address prefix and a second address prefix by masking the first address prefix with a first mask and the second address prefix with a second mask in response to receiving a first new address with a first port identifier and a second new address with a second port identifier,

discard the first address prefix and the second address prefix if the first address prefix and the second address prefix are absorbable by a third address prefix, wherein the third address prefix is stored in a content addressable memory prior to receiving the first new address and the second new address,

store in the memory the first port identifier and the second port identifier with the third address prefix in addition to a third port identifier stored with the third address prefix prior to receiving the first new address and the second new address,

extract a destination address from a received data unit,

generate a first masked destination address by masking the destination address using a third mask, and

send the data unit to a third port identified by the third port identifier if the first masked destination address matches with at least a first portion of the third address prefix, wherein the length of the first portion is at least greater than a length of a second mask and less than the length of the third mask.

11. The apparatus of claim 10, wherein the MCAM logic is to generate a second masked destination address by masking the destination address using a second mask if the first masked destination address does not match with at least the first portion of the third address prefix, and

send the data unit to a second port identified by the second port identifier if the second masked destination address matches with at least a second portion the third address prefix, wherein the length of the second portion of the third address prefix is at least greater than a length of a first mask and less than the length of the third and the second mask.

12. The apparatus of claim 10, wherein the MCAM logic is to,

generate a third masked destination address by masking the destination address using a first mask if the second masked destination address does not match with at least the second portion of the third address prefix, and

send the data unit to a first port identified by the first port identifier if the third masked destination address matches with a third portion of the third address prefix, wherein the length of the third portion is equal to the length of the first mask.

13. The apparatus of claim 10, wherein the MCAM logic is to,

receive a fourth new address and a fourth port identifier,

determine if the fourth new address is absorbable by at least one of a plurality of address prefixes stored in the content addressable memory, and

store a fourth address prefix and a fourth port identifier in the content addressable memory, wherein the fourth address prefix represents the fourth new address.

14. The apparatus of claim 13, wherein the first address prefix is the longest matching address prefix.

15. The apparatus of claim 13, wherein the plurality of address prefixes are stored in a sorted order starting from the longest matching address prefix.

16. The apparatus of claim 10, wherein the MCAM logic is to store the first address prefix in the first address location within the content addressable memory.

17. The apparatus of claim 10, wherein the third address prefix represents the first address prefix and the second address prefix by storing the first port identifier and the second port identifier along with the third address prefix.

18. The apparatus of claim 10, wherein the MCAM logic is to,

generate a fifth address prefix and a sixth address prefix by padding don'"'"'t care bits to the fourth address prefix until the length of the fifth address prefix and the sixth address prefix equals a mask length that is closest to the length of the fourth address prefix,

comparing the fifth address prefix and the sixth address prefix with the plurality of address prefixes,

discard the fifth address prefix if the fifth address prefix matches with at least a portion of one of the plurality of address prefixes, and

storing the sixth address prefix if the sixth address prefix does not match with any of the plurality of address prefixes.