Maskable content addressable memory

• US 20060149853A1
• Filed: 12/07/2004
• Published: 07/06/2006
• Est. Priority Date: 12/07/2004
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Shankara, Udayu
• Granted Patent: US 7,746,865 B2
• Time in Patent Office: Days
• US Class Current: 709/238
• 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 comprising

masking a destination address of a packet and a set of address prefixes with a first mask of a plurality of masks to obtain a first masked destination address and a set of first masked address prefixes, and

identifying a port for the packet based upon whether the first masked destination address matches one or more first masked address prefixes.

2. The method of claim 1 further comprising:

receiving a first address prefix associated with a first destination port identifier,

discarding the first address prefix if the first address prefix is absorbable by at least one address prefix of the set of address prefixes, and

associating the first destination port identifier with a corresponding absorbing address prefix of the set of address prefixes.

3. The method of claim 1, further comprising

receiving a first address prefix associated with a first destination port identifier,

discarding the first address prefix if the first address prefix is absorbable by at least one address prefix of the set of address prefixes, and

associating the first destination port identifier with a longest absorbing address prefix of the set of address prefixes.

4. The method of claim 3 wherein associating results in the longest absorbing address prefix having more than one associated port identifier.

5. The method of claim 1 further comprising storing the set of address prefixes in a sorted order from longest address prefix to shortest address prefix.

6. The method of claim 1, further comprising

determining that an expanded address prefix is absorbable by the set of address prefixes,

associating a destination port identifier corresponding to the expanded address prefix with absorbing address prefixes of the address prefixes, and

discarding the expanded address prefix.

7. The method of claim 1, further comprising

expanding an address prefix into a plurality of expanded address prefixes by replacing one or more don'"'"'t care bits with zeros and ones,

absorbing the plurality of expanded address prefixes into the set of address prefixes.

8. The method of claim 1, further comprising

masking the destination address and the set of address prefixes with a second mask of the plurality of masks to obtain a second masked destination address and a set of second masked address prefixes, and

identifying the port for the packet based upon whether the second masked destination address matches one or more second masked address prefixes.

9. An apparatus comprising

a plurality of ports,

a maskable content addressable memory to store a set of address prefixes and to identify a port of the plurality of ports on which a packet is to be sent by masking the set of address prefixes and a destination address of the packet, and

a controller to provide the maskable content addressable memory with the destination address of the packet and to send the packet on the port identified by the maskable content addressable memory.

10. The apparatus of claim 9, wherein the maskable content addressable memory determines a longest matching masked address prefix of the set of address prefixes for the destination address.

11. The apparatus of claim 9, wherein the maskable content addressable memory determines that a first address prefix is absorbable by at least one address prefix of the set of address prefixes, associates a first destination port corresponding to the first address prefix with an absorbing address prefix of the set of address prefixes, and discards the first address prefix.

12. The apparatus of claim 9, wherein the maskable content addressable memory determines that a first address prefix is absorbable by at least one address prefix of the set of address prefixes, associates a first destination port corresponding to the first address prefix with a longest absorbing address prefix of the set of address prefixes, and discards the first address prefix.

13. The apparatus of claim 9, wherein the maskable content addressable memory associates more than one destination port with an address prefix of the set of address prefixes.

14. The apparatus of claim 9, wherein the maskable content addressable memory stores the set of address prefixes in a sorted order from longest address prefix to shortest address prefix.

15. The apparatus of claim 9, wherein the maskable content addressable memory expands an address prefix into a plurality of expanded address prefixes by replacing one or more don'"'"'t care bits with ones and zeros.

16. The apparatus of claim 15, wherein the maskable content addressable memory absorbs one or more of the expanded address prefixes into the set of address prefixes.

17. The apparatus of claim 9, wherein the maskable content addressable memory iteratively masks the set of address prefixes with each mask of a plurality of masks from decreasing order of mask length until a longest masked address prefix is identified.

18. An apparatus comprising

a memory to store a set of address prefixes and a plurality of port identifiers for each address prefix of the plurality of address prefixes, and

logic to identify a port on which a packet is to be sent based upon a applying a plurality of masks to the set of address prefixes and a destination address of the packet.

19. The method of claim 18, wherein the memory comprises ternary storage elements, each ternary element capable of storing a zero, a one, and a don'"'"'t care.

20. The apparatus of claim 18, wherein the logic determines a longest matching masked address prefix of the set of address prefixes for the destination address.

21. The apparatus of claim 18, wherein the logic determines that a first address prefix is absorbable by at least one address prefix of the set of address prefixes, and associates a first destination port corresponding to the first address prefix with an absorbing address prefix of the set of address prefixes.

22. The apparatus of claim 18, wherein the logic stores the set of address prefixes in the memory in a sorted order from longest address prefix to shortest address prefix and selects a matching masked address prefix that is closest to the longest address prefix.

23. The apparatus of claim 18, wherein the logic expands an address prefix into a plurality of expanded address prefixes by replacing one or more don'"'"'t care bits with ones and zeros, and absorbs one or more of the expanded address prefixes into the set of address prefixes.

24. The apparatus of claim 18, wherein the logic iteratively masks the set of address prefixes with each mask of the plurality of masks from decreasing order of mask length until a longest masked address prefix is identified.