A Flexible Virtual Network with FIB Aggregation

The technique of Forwarding Information Base (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.

This technology reduces FIB aggregation’s overhead in the following aspects:

• Reduces the time needed to apply routing changes to the aggregated FIB
• Speeds up the process to re-aggregate an entire FIB, if a scheme requires such re-aggregations
• Reduces 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:

Routers exchange information using routing protocols to route packets through the network. The exchanged information is stored in a Routing Information Base (RIB), which stores all IP routing information, and is responsible for next-hop selection. The router processes information in the RIB to determine how to forward packets from the router, with this information stored in a forwarding information base (FIB). The FIB in routers contains a subset of the RIB information, such as the address prefixes and their select next hops, for fast lookup during data forwarding. In the core of the network, it is possible for the FIB to contain hundreds of thousands of entries (e.g. one for each route in the FIB). Once the FIB becomes so large that it can no longer fit in the fast memory of routers’ line cards, ISPs have to upgrade their line cards, eventually making internet services more expensive.
 

Applications:

• This technology can be deployed at individual routers/switches without impacting 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
• Avoids periodic re-aggregation of the entire table required by previous schemes, avoiding significant time delays
• Provides flexibility to optimize for table size, processing time, or a balanced approach between the two