FIB Aggregation

This technology is a method of dynamically updating and aggregating changes to forwarding information base (FIB) in real time that is configurable depending on need of end user. By developing a more holistic and configurable approach to FIB aggregation and prioritization, this technology has proven ability to improve efficiency of both newer and older equipment as well as extend its usability.

This technology reduces FIB aggregation’s overhead in the following aspects: (1) reducing the time needed to apply routing changes to the aggregated FIB; (2) speeding up the process to re-aggregate an entire FIB, if a scheme requires such re-aggregations; and (3) reducing the average and maximum number of FIB changes caused by any individual routing table change, so as to reduce the time it takes to push those changes to the line card.
 

Background:

The technique of FIB aggregation reduces FIB size by combining entries whose prefixes are numerically aggregatable and whose next hops are the same. It is a software solution that can be applied to a single router without upgrading the hardware, changing the control plane, or affecting packets’ forwarding paths. Thus it can be deployed incrementally and selectively in a network at operators’ discretion. With the proliferation of internet enabled devices, millions of new addresses are added to internet routing and forwarding tables annually. This causes architectural, efficiency, and topological issues on older routers and switches connecting data networks as they begin approaching their table limits on the number of entities causing service problems for content and access providers alike. Current growth rates are challenging even the most technologically advanced routers as well. While the Internet Engineering Task Force (IETF) is searching for architectural solutions, large customers are reluctant to invest in new equipment that may have to be replaced near-term.
 

Applications:

• Carrier ethernet switches (CES)
• Other routing/switching equipment
• This technology can be deployed at individual routers/switches without impacting on network protocols, operations, or causing any inter-operational problems

Advantages:

• The aggregation reduces the routing table size by 50% for core routers, and up to 90% for edge routers
• Reduces cost associated with replacing the line cards and/or routers
• In the software implementation, it takes 1-2us to process a routing update, compared to 1us without aggregation
• In previous schemes, a RIB update may cause a large number of changes to the aggregated FIB. In present technology, however, most of the time one RIB update causes less than 2 changes to the aggregated FIB

Status: issued U.S. Patent #9,491,087