Integrated search engine devices that utilize SPM-linked bit maps to reduce handle memory duplication and methods of operating same
View Patent ↗An integrated search engine device evaluates span prefix masks for keys residing at leaf parent levels of a search tree to identify a longest prefix match to an applied search key. This longest prefix match resides at a leaf node of the search tree that is outside a search path of the search tree for the applied search key. The search engine device is also configured to read a bitmap associated with the leaf node to identify a pointer to associated data for the longest prefix match. The pointer has a value that is based on a position of a set bit within the bitmap that corresponds to a set bit within the span prefix mask that signifies the longest prefix match.
1. A method of operating a search engine device, comprising:
evaluating a span prefix mask for a key residing at a leaf parent level of a search tree, maintained in a hierarchical memory of the search engine device, to identify a prefix match to an applied search key that resides at a leaf node of the search tree that is outside a search path of the search tree for the applied search key; and
reading a bitmap associated with the leaf node from the memory to identify a pointer to associated data for the prefix match, said pointer having a value that is based on a position of a set bit within the bitmap that corresponds to a set bit within the span prefix mask that signifies the prefix match.
2. The method of claim 1 , wherein said reading a bitmap is followed by reading a handle for the prefix match from a handle memory in the event the prefix match is a longest prefix match that resides outside the search path of the search tree for the applied search key.
3. The method of claim 1 , wherein a width of the bitmap is equivalent to a prefix capacity of the leaf node.
4. The method of claim 1 , wherein the search engine device has a pipelined architecture; and wherein said reading a bitmap is followed by passing the pointer from a leaf parent level of the pipelined architecture to a leaf level of the pipelined architecture.
5. The method of claim 1 , wherein the search engine device has a pipelined architecture, and wherein the memory is linked to a leaf level of the search engine device.
6. The method of claim 1 , wherein the search engine device has a pipelined architecture, and wherein the memory is linked to a leaf parent level of the search engine device.
7. An integrated search engine device, comprising:
a pipelined arrangement of a plurality of search and tree maintenance sub-engines comprising a hierarchical memory configured to store a plurality of databases of keys therein arranged as a corresponding plurality of search trees that span multiple levels of the hierarchical memory, said plurality of search and tree maintenance sub-engines configured to:
evaluate a span prefix mask for a key residing at a leaf parent level of a search tree to identify a prefix match to an applied search key that resides at a leaf node of the search tree yet is outside a search path of the search tree for the applied search key; and
read a bitmap associated with the leaf node to identify a pointer to associated data for the prefix match, said pointer having a value that is based on a position of a set bit within the bitmap that corresponds to a set bit within the span prefix mask that signifies the prefix match.
8. The search engine device of claim 7 , wherein the plurality of search and tree maintenance sub-engines are further configured to:
read a handle for the prefix match from a handle memory in the event the prefix match is a longest prefix match that resides outside the search path of the search tree for the applied search key.
9. The search engine device of claim 7 , wherein a width of the bitmap is equivalent to a prefix capacity of the leaf node.
10. The search engine device of claim 7 , wherein the plurality of search and tree maintenance sub-engines are further configured to:
pass the pointer from a leaf parent level of the pipelined arrangement to a leaf level of the pipelined architecture.
11. The search engine device of claim 7 , wherein the memory is linked to a leaf level of the search engine device.
12. The search engine device of claim 7 , wherein the memory is linked to a leaf parent level of the search engine device.
13. A search engine device, comprising:
means for evaluating a span prefix mask for a key residing at a leaf parent level of a search tree to identify a prefix match to an applied search key that resides at a leaf node of the search tree that is outside a search path of the search tree for the applied search key; and
means for reading a bitmap associated with the leaf node from a memory to identify a pointer to associated data for the prefix match, said pointer having a value that is based on a position of a set bit within the bitmap that corresponds to a set bit within the span prefix mask that signifies the prefix match.
14. The search engine device of claim 13 , wherein the means for reading, following reading the bitmap, reads a handle for the prefix match from a handle memory in the event the prefix match is a longest prefix match that resides outside the search path of the search tree for the applied search key.
15. The search engine device of claim 13 , wherein a width of the bitmap is equivalent to a prefix capacity of the leaf node.
16. The search engine device of claim 13 , wherein the search engine device has a pipelined architecture, and wherein the means for reading the bitmap, following reading the bitmap, passes the pointer from a leaf parent level of the pipelined architecture to a leaf level of the pipelined architecture.
17. The search engine device of claim 13 , wherein the search engine device has a pipelined architecture, and wherein the means for reading comprises means for reading a bitmap from a memory linked to a leaf level of the search engine device.
18. The search engine device of claim 13 , wherein the search engine device has a pipelined architecture, and wherein the means for reading comprises means for reading a bitmap from a memory linked to a leaf parent level of the search engine device.