Exploiting Locality of Churn 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. In practice however, the permanent stream of updates to the FIB due to routing updates complicates FIB aggregation: keeping an 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 number of changes to the aggregated FIB. This paper is the first to investigate whether the spatial and temporal locality properties of updates to the tree-like FIB data structure can be leveraged by online FIB aggregation. Our contributions include (a) an empirical study of the locality of updates in public Internet routing data, (b) the specification and simulations of our Locality-aware FIB Aggregation algorithm (LFA), and (c) a competitive analysis that sheds light on the performance of online algorithms under worst-case update streams. Our results show that even a simple algorithm like LFA can effectively exploit the locality of FIB churn to keep low the number of updates to the aggregated FIB, as most FIB updates affect only a small number of regions in the FIB