Patent ID: 9491087
Filing Date: 2016-11-08
CPC Classification: H04L

Claim Text:
1. A networking device comprising a processor and a routing protocol, said processor operable to: access entries in a forwarding information base (FIB), each of said FIB entries comprising an address prefix and an associated selected next-hop; and aggregate the FIB entries to produce an aggregated FIB with strong forward correctness, wherein, in aggregating the FIB entries, the processor is further 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, 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 the FIB entry associated with the child node in the aggregated FIB; and forward a data packet according to the aggregated FIB.