Leveraging locality for FIB aggregation

Snapshots of the Forwarding Information Base (FIB) in Internet routers can be compressed (or aggregated) to at least half of their original size, as shown by previous studies. However, the permanent stream of updates to the FIB due to routing updates complicates FIB aggregation in practice: keeping a (near-)optimally aggregated FIB in face of these routing updates is algorithmically challenging. A sensible trade-off has to be found between the aggregation gain and the complexity of handling routing updates. This paper investigates whether the spatial and temporal locality properties of routing updates conceal opportunities for improving this trade-off in online FIB aggregation. Our contributions include an empirical study of the locality of updates in public Internet routing data. To facilitate this study, we design the Locality-aware FIB Aggregation (LFA) algorithm. We show, that an algorithm as simple as LFA can effectively leverage the locality of FIB churn to keep low the number of updates to the aggregated FIB, as within time periods of a few seconds or minutes, routing updates affect only a limited number of regions in the FIB.