On the Aggregatability of Router Forwarding Tables

Introduction

Despite growth constraints such as strict address allocation policies (Meyer, Zhang, & Fall, 2007), the routing tables in the default free zone (DFZ) have been growing at an alarming rate in recent years. Currently, a DFZ router stores hundreds of thousands of routes or even a million in tier-1 ISPs. This is in part due to the sheer growth of the Internet, and in part due to the lack of aggregation. When a customer network multi-homes to multiple network providers to ensure resilient Internet connectivity, the customer’s address prefix(es) must be visible in the global routing table in order to be reachable through any of its network providers, thus breaking down provider-based aggregation (Bu, Gao, & Towsley, 2004). Traffic engineering is another contributing factor. For example, a network may try to influence the paths of specific incoming traffic flows by splitting its prefix into several longer ones and injecting them at different network attachment points. Splitting prefixes is also used as a defense mechanism against IP prefix hijacking.

Growing number of globally advertised address prefixes leads to increasing FIB tables, RIB tables, and routing churns. Among these problems, ISPs and vendors are more concerned about the FIB size than RIB size, because it is more difficult to scale up the memory in line cards than in route processors (Fuller, 2006). FIB size can be reduced by FIB aggregation, a purely local solution that can be quickly implemented and deployed in the ISPs. FIB aggregation combines multiple entries in the routing table to one entry in the forwarding table without changing the next hop for data traffic. A simple example of FIB aggregation is the following: if all the longer prefixes, say under 1.0.0.0/8, share the same next hop with the covering prefix 1.0.0.0/8, then only 1.0.0.0/8 needs to be installed in the FIB and all the longer prefixes under 1.0.0.0/8 can be removed from the FIB.

The effectiveness of FIB aggregation depends on how prefixes are distributed over next-hop routers. Generally speaking, the fewer neighbors a router has, the better aggregation it may achieve. In the extreme case that all prefixes share the same single next-hop, aggregation is maximized. According to Li, Alderson, Willinger, and Doyle (2004), although some routers have high degrees up to a couple of hundreds, most connections are with their end-customers, which represent only a small percentage of the address space. The routers still use a small number of transit networks to reach most prefixes.

Besides sharing the same next-hop, prefixes also need to be numerically aggregatable. This is possible due to two factors. First, in IP address allocation, large blocks of Internet addresses are first allocated to Regional Internet Registries (RIRs) and then they further allocate the addresses to networks within the same region. Thus prefixes announced out of the same regions tend to be numerically aggregatable. Second, for prefixes split for traffic engineering or other purposes, a router near the origin network is likely to take different next-hops, but a router further away from the origin network is more likely to have the same next-hop towards these numerically aggregatable prefixes.

Therefore, although FIB aggregation is opportunistic and the aggregation degree varies from router to router, there are inherent properties of the Internet that can make FIB aggregation effective. If FIB aggregation is indeed effective in reducing table size, its most appealing feature is that the impact is limited within a router’s data plane. It does not change any routing protocols, or any router’s routing decisions. Data traffic still flows on the same router paths. Therefore, it can co-exist with almost any new routing protocols, including those architectural solutions to the routing scalability problem in the long run.