Network device storage of incremental prefix trees
US11888743B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 3, 2019 |
| Grant date | Jan 30, 2024 |
| Priority date | — |
| Expiry date | Nov 29, 2042 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L61/5007
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
Prefix entries are efficiently stored at a networking device for performance of a longest prefix match against the stored entries. A prefix entry generally refers to a data entry which maps a particular prefix to one or more actions to be performed by a networking device with respect to network packets or other data structures associated with a network packet that matches the particular prefix. In the context of a router networking device handling a data packet, the one or more actions may include, for example, forwarding a received network packet to a particular “next hop” networking device in order to progress the network packet towards its final destination, applying firewall rule(s), manipulating the packet, and so forth. To reduce a total amount of space occupied by a prefix tree in storage, each of the nodes of a prefix tree may be configured to store only an incremental portion of a prefix relative to its parent node.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.