Weighted NSFIB Aggregation With Generalized Next Hop of Strict Partial Order

The size of the global routing table has been growing at an alarming rate. With the exhaustion of IPv4 addresses and the gradual deployment of IPv6 networks, the growth rate will continue to accelerate in the future. Although modern high performance routers provide enough line-card memory, Internet Service Providers (ISPs) cannot afford to upgrade their routers as fast as the growth of global routing tables. In this paper, we propose an algorithm to calculate the generalized next hops with strict partial order (GSPO next hops) of a network prefix and use them for the aggregation of the Nexthop-Selectable Forwarding Information Base (NSFIB). Since the existing NSFIB aggregation algorithm may introduce path stretch, we also propose a weighted NSFIB aggregation algorithm to effectively control path stretch under a given upper limit of the FIB size. Experiment results show that our algorithm can shrink the FIB size by at most 97% under IPv4 networks, and at most 95% under IPv6 networks. Under a given upper limit of the FIB size, our algorithm can reduce the path stretch by at least 22%.