Patent ID: 7990979

Claim:
A non-transitory computer-readable medium having stored thereon a data structure, the data structure comprising: a binary trie T representing a prefix set of all possible destination addresses for routing packets, the binary trie T comprising: a first-level partition, wherein the first-level partition comprises: a subtrie formed by selecting a stride s for the first-level partition, where 0<s ≦T.height+1, where T.height is the maximum level at which there is a descendent of a root R, wherein a node of the subtrie includes: a path Q(N), from the root R of the binary trie T to a root N of the subtrie, a next stride for a next-level partition, a mask that characterizes a next-level perfect hash function, and a pointer to a hash table for the next-level partition; an auxiliary trie representing prefixes having a length less than stride s of the first-level partition, wherein a node of the auxiliary trie includes the root R; wherein the number of first-level partitions is |D s (R)|+1, where D s (R) represents the level l descendents of root R, where l=s, the next-level partition formed by recursively repeating subtrie formation of the first-level partition to each of the |D s (R)|+1 first-level partitions.