Patent ID: 6996559

Claim:
A method of resolving B bit long addresses of packets into prefixes of any length up to B by a use of a data structure, wherein the data structure comprises a length sorted table Q and a plurality of secondary search units, table Q containing data related to prefixes of length not exceeding A, A≦B and each secondary search unit including tables V and T, wherein tables V and T are in one-to-one correspondence to one another and each comprising a 2×M memory, M being a positive integer, the method comprising steps of: (1) indexing table Q by using first A bits of an address to generate a corresponding prefix of length equal to or less than A, or a pointer to a secondary search unit; (2) accessing table V of the secondary search unit indicated by the pointer using each successive remaining bit of the address in order; (3) accessing table T of the secondary search unit at each successive location corresponding to a location of table V accessed in step (2); and (4) reading a valid data contained at a location in table T, the valid data being a prefix of length more than A, wherein steps (2)–(4) are performed for at least two of said addresses in at least two of the secondary search units in parallel, and wherein each secondary unit comprises one or more search branches and a pointer to a secondary search unit indicates an identity of the secondary unit and a branch number h, data relating to two or more search branches are interleaved in tables V and T of a secondary unit, and the method further comprises a step of accessing table V at a location indicated by the branch number h of the secondary unit identified by the pointer.