Two stage bloom filter for longest prefix match
US9596181B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Oct 20, 2014 |
| Grant date | Mar 14, 2017 |
| Priority date | — |
| Expiry date | May 26, 2035 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/7453
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A device may receive a packet that includes a destination address. The device may analyze a first Bloom filter, based on the destination address, in order to identify a prefix range entry associated with the destination address and included in a set of prefix range entries associated with the first Bloom filter. The device may analyze a second Bloom filter, based on the destination address and the identified prefix range entry, in order to identify a prefix length entry associated with the destination address and included in a set of prefix length entries associated with the second Bloom filter. The device may determine routing information associated with the identified prefix length entry. The routing information may identify a longest prefix match associated with the destination address. The device may provide the packet based on the routing information.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.