The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Nov. 08, 2016
Filed:
Nov. 27, 2013
The Arizona Board of Regents on Behalf of the University of Arizona, Tucson, AZ (US);
The University of Memphis Research Foundation, Memphis, TN (US);
Beichuan Zhang, Tucson, AZ (US);
Xin Zhao, Castro Valley, CA (US);
Lan Wang, Germantown, TN (US);
Yaoqing Liu, Potsdam, NY (US);
THE ARIZONA BOARD OF REGENTS ON BEHALF OF THE UNIVERSITY OF ARIZONA, Tucson, AZ (US);
THE UNIVERSITY OF MEMPHIS RESEARCH FOUNDATION, Memphis, TN (US);
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 the FIB entry associated with the child node in the aggregated FIB.