Integrated search engine devices that support LPM search operations using span prefix masks that encode key prefix length

摘要

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.