Integrated search engine devices that support LPM search operations using span prefix masks that encode key prefix length
View Patent ↗A pipelined search engine supports a tree of search keys therein that utilizes span prefix masks to assist in longest prefix match (LPM) detection when the tree is searched. Each of a plurality of the span prefix masks encodes a prefix length of a search key to which the span prefix mask is associated and a value of another search key in the tree that is a prefix match to the search key to which the span prefix mask is associated.
1. An integrated circuit device, comprising:
a pipelined search engine configured to search a tree comprising a plurality of nodes, each of the plurality of nodes comprising a search prefix, and at least one of the search prefixes being associated with a mask configured to assist in longest prefix match (LPM) detection during search of the tree, wherein each bit of the mask is generated by:
performing a Boolean operation on a different vector in a set of vectors and the search prefix associated with the mask; and
determining whether a result of the Boolean operation is equal to or shorter than the search prefix associated with the mask.
2. The integrated circuit device of claim 1 , wherein the search prefixes are multi-segment search prefixes and wherein the tree further utilizes a segment length indicator for each of a plurality of segments of the multi-segment search prefixes that identifies whether a corresponding segment of the plurality of segments of the multi-segment search prefix is a fully specified segment.
3. The integrated circuit device of claim 1 , wherein the tree is configured to support at least a first multi-segment search prefix and a multi-bit length indicator that identifies segments of the first multi-segment search prefix that are fully specified.
4. The integrated circuit device of claim 1 , wherein the mask is a binary number.
5. The integrated circuit device of claim 1 , wherein the Boolean operation is a bitwise AND operation.
6. The integrated circuit device of claim 1 , wherein the bit of the mask is a logic “1” if the result is equal to or shorter than the search prefix, and wherein the bit of the mask is a logic “0” if the result is not equal to or shorter than the search prefix.
7. An integrated circuit device, comprising:
a search engine configured to search a tree of multi-segment search prefixes that are stored with a plurality of multi-bit length indicators that identify segments of the multi-segment search prefixes that are fully specified, wherein the search engine is further configured to search a plurality of masks that are associated with a corresponding plurality of multi-segment search prefixes located at non-leaf levels within the tree and encode prefix lengths of the plurality of multi-segment search prefixes, and wherein each bit of a respective mask is generated by:
performing a Boolean operation on a different vector in a set of vectors and the multi-segment search prefix associated with the respective mask; and
determining whether a result of the Boolean operation is equal to or shorter than the multi-segment search prefix associated with the respective mask.
8. The integrated circuit device of claim 7 , wherein each of the plurality of masks is a binary number.
9. The integrated circuit device of claim 7 , wherein the Boolean operation is a bitwise AND operation.
10. A method of encoding a prefix length of a search prefix to be inserted into a multi-way tree, the method performed by a search engine and comprising:
generating, using an integrated circuit device, a mask for the search prefix, wherein each bit of the mask is generated by:
performing a Boolean operation on a different vector in a set of vectors and the search prefix associated with the mask; and
determining whether a result of the Boolean operation is equal to or shorter than the search prefix associated with the mask.
11. The method of claim 10 , wherein the mask is a binary number.
12. The method of claim 10 , wherein the Boolean operation is a bitwise AND operation.
13. A method of encoding a multi-segment search prefix within a multi-way tree of search prefixes, the method performed by a search engine and comprising:
generating, using an integrated circuit device, a multi-segment mask associated with the multi-segment search prefix, wherein each bit of the multi-segment mask is generated by:
performing a Boolean operation on a different vector in a set of vectors and the multi-segment search prefix associated with the multi-segment mask; and
determining whether a result of the Boolean operation is equal to or shorter than the multi-segment search prefix associated with the multi-segment mask; and
generating a segment length indicator for at least one of the segments of the multi-segment search prefix that identifies whether the corresponding segment of the multi-segment search prefix is a fully specified segment.
14. The method of claim 13 , wherein the multi-segment mask represents an encoded prefix length of the multi-segment search prefix.
15. The method of claim 13 , wherein the multi-way tree is a b-tree.
16. The method of claim 14 , wherein the multi-segment mask is a binary number.
17. The method of claim 13 , wherein the Boolean operation is a bitwise AND operation.
18. A method of encoding a prefix length of a search prefix to be inserted into a b-tree, the method performed by a search engine and comprising:
generating, using an integrated circuit device, a mask for the search prefix, each bit of the mask being generated by:
performing a Boolean operation on a different vector in a set of vectors and the search prefix associated with the mask; and
determining whether a result of the Boolean operation is equal to or shorter than the search prefix associated with the mask.
19. The method of claim 18 , wherein the search prefix is encoded as a multi-segment search prefix that utilizes segment length indicators to identify segments of the multi-segment search prefixes that are fully specified.
20. The integrated circuit device of claim 18 , wherein the mask is a binary number.
21. The method of claim 18 , wherein the Boolean operation is a bitwise AND operation.