Address lookup in packet data communication networks

An apparatus for performing a longest matching prefix search of a network address for an N-bit input address in a packet data communication system, comprising:

• a memory for storing a table containing an N/x-bit portion of an N-bit address with an associated prefix search list containing prefix values that are candidates for the longest matching prefix, wherein each of said prefix values represent at least one possible network address match to the N-bit input address;
• a binary search algorithm for selecting a specific prefix value in the prefix search list to mask the N-bit input address to form a search value;
• and
• a search algorithm for performing an associative comparison of the search value to address entries in a table having the specific prefix value, where 0<x<N.

A method of performing an address lookup to find a longest matching prefix for an N-bit input address in a packet data communication system, comprising:

• (a) storing a table containing a predefined portion of an N-bit address with an associated prefix search list containing prefix values that are candidates for the longest matching prefix;
• (b) selecting a target prefix value in the prefix search list to structure the N-bit input address to form a search value;
• and
• (c) performing an associative comparison of the search value to address entries in a table having the target prefix value.