Patent ID: 8089961

Claim:
A method for routing a packet, the method comprising: storing, using a suffix node format, a subtree of an ordered tree data structure into a given word size of random-access memory (RAM), wherein the suffix node format comprises one or more data structures that at least represents a set of internet protocol prefixes with common leading bits, wherein the RAM is logically partitioned into a first portion with suffix nodes associated with groupings of subtree splits in at least one ternary content-addressable memory (TCAM), and a second portion for storing suffix nodes to determine the next action to perform on a packet; storing indices to the subtree in RAM into the TCAM; receiving a packet with at least one destination address; using a portion of the destination address to perform a lookup in the TCAM to retrieve an index value; indexing the RAM to retrieve the subtree corresponding to the index value; and using the subtree which has been retrieved to determine a next action to perform on the packet.