Patent ID: 7376657

Claim:
A method for inserting a first prefix into a router database, comprising: segmenting the first prefix into a first plurality of segments; indexing into a first trie node block using a first segment of the first plurality of segments to obtain a first trie node; obtaining a second segment of the first plurality of segments, wherein the second segment of the first plurality of segments includes contiguous zeros; determining a number of contiguous zeros; determining a first skip level using the number of contiguous zeros; inserting the first skip level into the first trie node; obtaining a third segment of the first plurality of segments, wherein the third segment does not contain contiguous zeros; setting a next pointer in the first trie node to point to a second trie node block, wherein the second trie node block corresponds to the third segment; and indexing into the second trie node block using the third segment to obtain a second trie node storing the first prefix in the second trie node, wherein the first prefix is used to route a packet to a destination host.