Scale the Internet routing table by generalized next hops of strict partial order

The Internet routing tables have been expanding at a dramatic and increasing rate. Although the latest high-performance routers provide enough capacities, Internet Service Providers (ISPs) cannot afford to upgrade their routers at the pace of routing table growth. Shrinking the routing table, especially the TCAM-based Forwarding Information Base (FIB), is more feasible. In this paper, we propose a scheme to aggregate the FIB based on generalized next hops of strict partial order (SPO). We first use generalized SPO next hops to construct the Nexthop-Selectable FIB (NSFIB), where each prefix has multiple next hops. Our NSFIB aggregation avoids the aggregation performance degrading with the network density increasing, which is one main defect of the traditional single-nexthop FIB aggregation. We then design different levels of aggregation algorithms to aggregate the NSFIB. Besides, we control the path stretch by setting an upper limit to filter bad next hops. We also introduce routing protection by the pre-computed SPO next hops. According to our simulation, our aggregation algorithms shrink the FIB to 5-15%, compared with 20-60% of single-nexthop FIB aggregation algorithms; our method works very well in controlling the path stretch; and SPO next hops protect 50-95% (topology-related) failure-affected packets.