Incremental forwarding table aggregation

The global routing table size has been increasing rapidly, outpacing the upgrade cycle of router hardware. Recently aggregating the Forwarding Information Base (FIB) emerges as a promising solution since it reduces FIB size significantly in the short term and it is compatible with any long-term architectural solutions. Because FIB entries change dynamically with routing updates, an important component of any FIB aggregation scheme is to handle routing updates efficiently while shrinking FIB size as much as possible. In this paper, we first propose two incremental FIB aggregation algorithms based on the ORTC scheme. We then quantify the tradeoffs of the proposed algorithms, which will help operators choose the algorithms best suited for their networks.