Patent ID: 7797348

Claim:
An article of manufacture, comprising: a tangible computer-readable data storage medium; and instructions stored in the computer-readable data storage medium, wherein when the instructions are executed by a computing device, the instructions cause the computing device to search a data structure as part of routing IP packets; wherein the data structure comprises a linearized representation of a tree of two or more searchable strings of IP address prefix data, wherein each string is divided into a plurality of substrings, and wherein the tree comprises a plurality of nodes including first-type nodes configured to store corresponding associated searchable substrings and second-type nodes not configured to store corresponding associated searchable substrings; and wherein the data structure comprises match-failed transition information configured to link to a second-type node from a first-type node and prefix bit transition information configured to link to a first-type node from a second-type node based on a next bit from an IP address for which the data structure is being searched.