Patent ID: 7602785

Claim:
A method of performing a network address lookup, comprising: grouping forwarding prefixes from a routing table by prefix length; associating each of a plurality of Bloom filters with a unique prefix length; programming each of said plurality of Bloom filters with said prefixes corresponding to said associated unique prefix length; performing membership probes to said Bloom filters by using predetermined prefixes of a network address; and utilizing a direct lookup array for initial prefix lengths and asymmetric Bloom filters for the rest of the prefix lengths; wherein said direct lookup array comprises: storing prefixes of not more than a predetermined number for a predetermined length, in a binary trie; performing Controlled Prefix Expansion (CPE) in a CPE trie for a stride length equal to said predetermined number; writing a next hop associated with each leaf at a level of said CPE trie corresponding to said predetermined number to an array slot addressed by bits that label a path from a root of said CPE trie to said leaf; and searching said array using bits of said network address of said predetermined number to index into said array.