Forwarding packets using a probabilistic filter and a grouping technique
US9979650B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 30, 2015 |
| Grant date | May 22, 2018 |
| Priority date | — |
| Expiry date | Mar 29, 2036 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/7453
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A device may receive a packet with a destination address, and may input, to a probabilistic filter, prefixes associated with the destination address. A prefix may include one or more most significant bits of the destination address. The device may identify candidate prefixes associated with a response from the probabilistic filter. The device may identify a longest candidate prefix of the candidate prefixes, and may perform a lookup to determine that a memory component includes a parent prefix that matches the longest candidate prefix. The parent prefix may be associated with a child prefixes that include the parent prefix and one or more additional bits. The device may identify a longest matching prefix, of the parent prefix and the child prefixes, that matches one or more most significant bits of the destination address and that corresponds to an output component. The device may output the packet via the output component.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.