Devices and methods for forwarding information base aggregation
US9491087B1 · kind B1 · utility
Assignees
Inventors
Key dates
| Filing date | Nov 27, 2013 |
| Grant date | Nov 8, 2016 |
| Priority date | — |
| Expiry date | Mar 20, 2034 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/745
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
Networking devices and methods for forwarding information base (FIB) aggregation are provided. A networking device includes a processor operable to access entries in a FIB, and aggregate the FIB entries to produce an aggregated FIB with strong forward correctness. In aggregating the FIB entries, the processor is operable to: (a) associate the FIB entries with nodes (n) in a patricia trie; (b) traverse the patricia trie depth-first in post-order and determine for each node a next-hop set, without expanding the trie, by merging what would be the next-hop sets of its imaginary children nodes if there is a complete binary tree; and (c) traverse the patricia trie depth-first in pre-order, select for the root node a next-hop from its next-hop set and include the FIB entry associated with the root node in the aggregated FIB, for each node having a selected next-hop that appears in its child's next-hop set, select that next-hop for the child as its next-hop and exclude the FIB entry associated with the child node from the aggregated FIB, and for each child node which does not have in its next-hop set the selected next-hop of its parent, select a next-hop from its next-hop set and include t…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.