Method and apparatus for longest prefix match search
US11178054B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 22, 2019 |
| Grant date | Nov 16, 2021 |
| Priority date | — |
| Expiry date | Nov 26, 2039 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/48
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A network device includes a memory configured to store a plurality of entries in respective locations in the memory, the plurality of entries corresponding to a trie data structure for performing a longest prefix match search. The network device also includes: a memory access engine configured to retrieve from a location in the memory, in a single memory lookup operation, i) longest prefix match information for a node corresponding to a network address in a header of a packet, and ii) pointer information that indicates a child node in the trie data structure. The network device also includes: a child node address calculator configured to use i) the longest prefix match information, and ii) the pointer information, to calculate a memory address of another location in the memory corresponding to the child node.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.