Method and system for performing longest prefix matching for network address lookup using bloom filters
US7602785B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Feb 9, 2005 |
| Grant date | Oct 13, 2009 |
| Priority date | — |
| Expiry date | Dec 24, 2027 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/74591
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
The present invention relates to a method and system of performing parallel membership queries to Bloom filters for Longest Prefix Matching, where address prefix memberships are determined in sets of prefixes sorted by prefix length. Hash tables corresponding to each prefix length are probed from the longest to the shortest match in the vector, terminating when a match is found or all of the lengths are searched. The performance, as determined by the number of dependent memory accesses per lookup, is held constant for longer address lengths or additional unique address prefix lengths in the forwarding table given that memory resources scale linearly with the number of prefixes in the forwarding table. For less than 2 Mb of embedded RAM and a commodity SRAM, the present technique achieves average performance of one hash probe per lookup and a worst case of two hash probes and one array access per lookup.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.