SYSTEM AND METHOD FOR FIB AGGREGATION

摘要

A system and method for FIB aggregation. FIB Aggregation with Quick Selections (FAQS) is a FIB aggregation algorithm that leverages compact data structures and three unique optimization techniques to quickly and incrementally select next hops when handling route updates. As a result, FAQS can run up to 2.53 and 1.75 times faster for IPv4 and IPv6, respectively, than the optimal FIB aggregation algorithm while achieving a near-optimal aggregation ratio. Meanwhile, it consumes much less memory and generates much smaller number of FIB changes when carrying out frequent updates. The performance enhancement of the new algorithm addresses many concerns from ISPs regarding performance issues, and enhances the probability to push FIB aggregation techniques further to the level of production adoption by the industry.