Longest prefix match searches with variable numbers of prefixes

A network device comprising:

• a hardware control unit comprising:
• a filter lookup module comprising:
• a Bloom filter that supports parallel lookup of a maximum number of different prefix lengths;
• and
• a prefix lookup module that accesses the Bloom filter to determine a longest length prefix that matches an entry in a set of prefixes;
• and
• a control plane configured to receive a set of prefix lengths that include a number of different prefix lengths greater than the maximum number of different prefix lengths supported by the Bloom filter, wherein the set of prefix lengths is associated with one application, generate, based on the received set of prefix lengths, two or more groups of different prefix lengths, wherein each of the two or more groups of different prefix lengths includes no more than the maximum number of different prefix lengths, and program the filter lookup module with the two or more groups of different prefix lengths associated with the one application,
• wherein, after programming the filter lookup module, the filter lookup module sequentially processes respective sets of prefixes each generated using a corresponding one of the two or more groups of different prefix lengths until either 1) a match for a prefix from one of the different groups of prefixes is found in a hash table or 2) the filter lookup modules has processed the respective sets of prefixes generated for each of the two or more groups of different prefix lengths.

A non-transitory computer-readable storage medium encoded with instructions that cause one or more programmable processors of a network device to:

• receive a set of prefix lengths that include a number of different prefix lengths greater than a maximum number of different prefix lengths capable of being looked up in parallel by a Bloom filter of the network device, wherein the set of prefix lengths is associated with one application;
• generate, based on the received set of prefix lengths, two or more groups of different prefix lengths, wherein each of the two or more groups of different prefix lengths includes no more than the maximum number of different prefix lengths;
• program a filter lookup filter module of the network device with the two or more groups of different prefix lengths associated with the one application;
• and
• after programming the filter lookup module, sequentially processes respective sets of prefixes each generated using a corresponding one of the two or more groups of different prefix lengths until either 1) a match for a prefix from one of the different groups of prefixes is found in a hash table or 2) the filter lookup modules has processed the respective sets of prefixes generated for each of the two or more groups of different prefix lengths.