Network address lookup based on bloom filters

Abstract

In one embodiment, IP lookup into a routing table having prefixes of different prefix lengths is performed using a Bloom filter that was programmed with the prefixes corresponding to all of the different prefix lengths without having to expand any of the prefixes programmed into the Bloom filter. Membership probes are performed into the Bloom filter using candidate prefix values of a given network address. The Bloom filter can be implemented in a distributed manner using Bloom sub-filters, where each Bloom sub-filter is hashed based on a set of hash functions, where each different hash function in the set corresponds to a different prefix length in the routing table. Each Bloom sub-filter can in turn be implemented using a plurality of practically realizable multi-port memory devices controlled by a port scheduler. False-positive matches can be detected and next-hop information for true-positive matches retrieved using an off-chip, hash-based prefix table.