Double density content addressable memory (CAM) lookup scheme
View Patent ↗The number of content addressable memory (CAM) lookups is reduced from two to one. Each side (left and right sides) of a CAM is programmed with network addresses, such as IP addresses, based on certain bits of the network addresses. These bits of the network addresses (which represent packet routes) are examined and used to determine whether the particular network address is to be placed on the left or right sides of the CAM. The grouping of certain network addresses either on the left or right sides of the CAM can be performed by examining an individual bit of each network address, by performing an exclusive OR (XOR) operation on a plurality of bits of each network address, and/or by searching for bit patterns of the network address in a decision table. Network addresses that cannot be readily assigned to a particular side of the CAM using these grouping techniques are programmed into both sides of the CAM. During packet routing, techniques similar to the grouping techniques that populated the CAM are used to determine which of the two sides of the CAM is to be searched.
1. A system comprising:
a memory comprising a first portion and a second portion; and
a lookup handler configured to:
determine a value based upon one or more bits of a packet;
select, based upon the determined value, one of the first portion and the second portion to be used for the packet; and
cause the selected portion of the memory to be accessed for processing the packet.
2. The system of claim 1 wherein the one or more bits are from a network address included in the packet.
3. The system of claim 2 wherein the lookup handler is configured to determine the value based upon 26 th and 27 th bits of the network address.
4. The system of claim 2 wherein the lookup handler is configured to determine the value based upon 28 th , 27 th , and 26 th bits of the network address.
5. The system of claim 2 wherein the lookup handler is configured to determine the value based upon 28 th bit of the network address.
6. The system of claim 2 wherein the network address is a destination address of the packet.
7. The system of claim 1 wherein:
the one or more bits comprise a plurality of bits; and
the lookup handler is configured to determine the value by performing an operation on the plurality of bits.
8. The system of claim 7 wherein the operation is an exclusive OR (XOR) operation.
9. The system of claim 1 wherein the lookup handler is configured to:
use the value to determine data stored in a decision table; and
use the data from the decision table to select one of the first portion and the second portion.
10. The system of claim 1 wherein the memory is an N-bit memory and the first portion corresponds to upper N/2 bits portion of the memory and the second portion corresponds to lower N/2 bits portion of the memory.
11. The system of claim 1 wherein the memory is a content addressable memory (CAM).
12. The system of claim 1 further comprising a forwarding component configured to forward the packet using information obtained from accessing the selected portion of the memory.
13. A method comprising:
determining, by a network device, a value based upon one or more bits of a packet received by the network device;
selecting, based upon the determined value, one of a first portion and a second portion of a memory in the network device to be used for the packet; and
causing the selected portion of the memory determined to be accessed for processing the packet.
14. The method of claim 13 wherein the one or more bits are from a network address included in the packet.
15. The method of claim 14 wherein determining the value comprises determining the value using 26 th and 27 th bits of the network address.
16. The method of claim 14 wherein determining the value comprises determining the value using 28 th , 27 th , and 26 th bits of the network address.
17. The method of claim 14 wherein determining the value comprises determining the value using the 28 th bit of the network address.
18. The method of claim 14 wherein the network address is a destination address of the packet.
19. The method of claim 13 wherein:
the one or more bits comprise a plurality of bits; and
determining the value comprises determining the value by performing an operation on the plurality of bits.
20. The method of claim 19 wherein the operation is an exclusive OR (XOR) operation.
21. The method of claim 13 wherein selecting one of the first portion and the second portion comprises:
using the value to determine data stored in a decision table; and
using the data from the decision table to select one of the first portion and the second portion.
22. The method of claim 13 wherein the memory is an N-bit memory and the first portion corresponds to upper N/2 bits portion of the memory and the second portion corresponds to lower N/2 bits portion of the memory.
23. The method of claim 13 wherein the memory is a content addressable memory (CAM).
24. The method of claim 13 further comprising forwarding the packet using forwarding information obtained from accessing the selected portion of the memory.
25. A network device comprising:
a content-addressable memory (CAM) comprising a first side and a second side; and
one or more components configured to:
determine whether to use the first side or the second side based upon contents of a packet received by the network device;
obtain forwarding information for the packet using the side of the CAM determined to be used; and
forward the packet using the forwarding information.