Method and system for using range bitmaps in TCAM access
View Patent ↗Various exemplary embodiments relate to a method and related network node including one or more of the following: determining that a first search value is associated with a first range field; determining a first bitmap associated with the first search value, wherein the first bitmap indicates at least one range encompassing the first search value; generating a search key based on the first bitmap; and accessing the ternary content addressable memory based on the search key.
1. A method for accessing a ternary content addressable memory, the method comprising:
determining that a first search value is associated with a first range field;
determining a first bitmap associated with the first search value, wherein the first bitmap includes a first bit that indicates a first range encompassing the first search value;
generating a search key based on the first bitmap; and
accessing the ternary content addressable memory based on the search key.
2. The method of claim 1 , wherein determining the first bitmap associated with the first search value comprises accessing a record of a lookup table, wherein the record includes the first search value and a pre-computed bitmap for the first search value, wherein the pre-computed bitmap is used as the first bitmap.
3. The method of claim 1 , wherein determining the first bitmap associated with the first search value comprises computing the first bitmap by comparing the first search value to a plurality of ranges.
4. The method of claim 1 , further comprising:
receiving a message, wherein the message includes the first search value; and
forwarding the message to another device based on the accessing the ternary content addressable memory resulting in a match.
5. The method of claim 4 , wherein the search key additionally includes a value copied from the message.
6. The method of claim 1 , wherein:
the first bitmap includes a plurality of bits,
a first bit of the plurality of bits indicates whether the first search value is encompassed by the first range; and
a second bit of the plurality of bits indicates whether the first search value is encompassed by a second range.
7. The method of claim 6 , wherein:
the ternary content addressable memory includes a plurality of records; and
a first record of the plurality of records associated with the first range, wherein the first record includes:
a first bit position associated with the first bit of the plurality of bits, a bit at the first bit position being set equal to the first bit of the plurality of bits, and
a second bit position associated with the second bit of the plurality of bits, a bit at the second bit position being set to a wildcard value.
8. The method of claim 1 , further comprising:
determining that a second search value is associated with a second range field; and
determining a second bitmap associated with the second search value,
wherein generating the search key based on the first bitmap comprises generating a search key based on the first bitmap and the second bitmap.
9. The method of claim 8 , wherein generating the search key based on the first bitmap and the second bitmap comprises:
combining the first bitmap with at least the second bitmap to produce a final range check bitmap; and
including the final range check bitmap in the search key.
10. The method of claim 1 wherein generating the search key based on the first bitmap comprises including the first bitmap in the search key.
11. An access control device comprising:
a network interface configured to receive a message;
a ternary content addressable memory; and
a network processor configured to:
identify a field of the message as a first search value associated with a first range field, determine a first bitmap associated with the first search value, wherein the first bitmap at least one includes a first bit that indicates a first range encompassing the first search value,
generate a search key based on the first bitmap,
access the ternary content addressable memory based on the search key, and
based on the access of the ternary content addressable memory producing a match, performing at least one match action with respect to the message.
12. The access control device of claim 11 , further comprising:
a storage configured to store a lookup table, wherein a record of the lookup table includes the first search value and a pre-computed bitmap for the first search value,
wherein, in determining the first bitmap associated with the first search value, the network processor is configured to use the pre-computed bitmap as the first bitmap.
13. The access control device of claim 11 , further comprising:
a storage configured to store a plurality of ranges associated with the first search value,
wherein, in determining the first bitmap associated with the first search value, the network processor is configured to compute the first bitmap by comparing the first search value to the plurality of ranges.
14. The access control device of claim 13 , wherein the search key additionally includes a value copied from the message.
15. The access control device of claim 11 , wherein:
the first bitmap includes a plurality of bits,
a first bit of the plurality of bits indicates whether the first search value is encompassed by the first range; and
a second bit of the plurality of bits indicates whether the first search value is encompassed by a second range.
16. The access control device of claim 15 , wherein:
the ternary content addressable memory includes a plurality of records; and
a first record of the plurality of records associated with the first range, wherein the first record includes:
a first bit position associated with the first bit of the plurality of bits, a bit at the first bit position being set equal to the first bit of the plurality of bits, and
a second bit position associated with the second bit of the plurality of bits, a bit at the second bit position being set to a wildcard value.
17. The access control device of claim 11 , wherein the network processor is further configured to:
determine that a second search value is associated with a second range field; and
determine a second bitmap associated with the second search value,
wherein, in generating the search key based on the first bitmap, the network processor is configured to generate a search key based on the first bitmap and the second bitmap.
18. The access control device of claim 17 , wherein, in generating the search key based on the first bitmap and the second bitmap, the network processor is configured to:
combine the first bitmap with at least the second bitmap to produce a final range check bitmap; and
include the final range check bitmap in the search key.
19. The access control device of claim 11 , wherein, in generating the search key based on the first bitmap, the network processor is configured to include the first bitmap in the search key.
20. A non-transitory machine-readable storage medium encoded with instructions for accessing a ternary content addressable memory, the medium comprising:
instructions for determining that a first search value is associated with a first range field;
instructions for determining a first bitmap associated with the first search value, wherein the first bitmap includes a first bit that indicates a first range encompassing the first search value;
instructions for generating a search key based on the first bitmap; and
instructions for accessing the ternary content addressable memory based on the search key.