Nexthop-Selectable FIB aggregation: An instant approach for internet routing scalability

Abstract Recently, the core net routing table is growing at an alarming speed which has become a major concern to Internet Service Providers. One effective solution is Forwarding Information Base (FIB) aggregation. All the previous studies assume every prefix has only one next hop. In this paper, we argue that a packet can be delivered to its destination by multiple selectable next hops. Based on this observation, we propose Nexthop-Selectable FIB aggregation. Prefixes, including those which originally have different next hops, are aggregated if they share one common next hop. We provide a systematic study on this Nexthop-Selectable FIB aggregation problem. We present several practical choices to build selectable next hops for prefixes. We propose a non-trivial O(N) algorithm to optimally solve the problem. We then study a generalized problem where we assign weights for different next hops to bound path stretch. We further develop an optimal incremental updating algorithm with constant running time. We evaluate our algorithms through a comprehensive set of simulations with BRITE and real world topologies. Our evaluation shows that the aggregated FIB is one order of magnitude smaller than the original one.