Longest prefix match searches with variable numbers of prefixes

摘要

An example network device includes a control plane and a filter lookup module that includes a Bloom filter that supports parallel lookup of a maximum number of different prefix lengths. The filter lookup module accesses the Bloom filter to determine a longest length prefix that matches an entry in a set of prefixes. The control plane receives prefix lengths that include more than the maximum number of different prefix lengths supported by the Bloom filter, wherein the set of prefix lengths is associated with one application, generates, 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 programs the filter lookup module with the two or more groups of different prefix lengths associated with the one application.

主权项

1. A method comprising:
receiving, with a network device, 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; generating, 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; programming, with a control plane of the network device, a filter lookup 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 processing, with the filter lookup module, 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.